Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » Superposition de nombres binaires Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=enigmatus]@nodgim #43 : Je ne vais pas m'inscrire mais j'ai regardé ton lien. Si j'ai bien compris, l'énigme que tu poses ici permet de résoudre le problème des 1000 bouteilles dont 2 sont empoisonnées, le nombre de bits du code étant le nombre de testeurs (au testeur n° k est attribué le bit n° k des codes). Chaque testeur n'a besoin de boire qu'une seule fois, en composant son breuvage à partir des bouteilles dont le code contient un bit à 1 en k ème colonne. Toujours avec ta méthode, j'en suis à 27 bits, dont 8 tirés au hasard et mis à 1. Suivant les tirages, j'arrive à 1000 entre 55 et 80 secondes. Une fois le programme s'est arrêté à 996, après avoir épuisé les combinaisons, mais il arrive fréquemment jusqu'à 1015. Voici le script : [code]#!/usr/bin/env python3 # -- encoding: utf-8 -- # # enigmatus mai 2016 (sur une idée de nodgim) # import sys from itertools import combinations as C from random import seed, shuffle from time import time #seed(0) k=0 k+=1;N=int(sys.argv[k]) # Nb de bits k+=1;M=int(sys.argv[k]) # Nb de bits choisis à 1 try: k+=1;B=int(sys.argv[k]) # Nb de nombres voulu except IndexError: B=None try: k+=1;NN=int(sys.argv[k]) # Nb max de tirages except IndexError: NN=None #------------------------------------------------- def bi(n,l): # Représentation binaire de n sur l bits s=bin(n)[2:] ret='0'(l-len(s))+s return ret cods=[]; soms=set() #------------------------------------------------- def gener_bits(): # Génération dans un ordre aléatoire des combinaisons de M bits pris parmi N lst=list(C(range(N),M)) shuffle(lst) for bits in lst: yield bits return #------------------------------------------------- def gener_cod(): # Génération et test des encodages global soms, nn genbits=gener_bits() nn=0 while not NN or nn<NN: try: bits=next(genbits) except StopIteration: print('\nFini : Combinaisons épuisées=%d'%nn); break nn+=1 cod=0 for k in bits: cod+=1<<k deja=False som_new=set() for cod0 in cods: som=cod0\|cod if som in som_new or som in soms: deja=True; break else: som_new.add(som) if not deja: soms\|=som_new cods.append(cod) yield bi(cod,N) return #------------------------------------------------- mat=[]; c=0; nn1=0; T0=T1=time() gencod=gener_cod() while True: try: cod=next(gencod) except StopIteration: print('\nFini : Nb max de tirages=%d'%nn); break c+=1; T2=time(); print("%4d %s %7d %7d %8.3f %10.3f %9.6f %9.6f"%(c,cod,nn-nn1,nn,T2-T1,T2-T0,(T2-T1)/(nn-nn1),(T2-T0)/nn)); sys.stdout.flush() nn1=nn; T1=T2 mat.append(cod) if B and c>=B: print('\nFini : Résultat atteint=%d'%c); break print("%d nombres de %d bits générés, avec tirage aléatoire de %d bits"%(len(mat),N,M))[/code] À lancer ainsi (les 2 derniers paramètres sont facultatifs) : [code]./le_script.py nb_de_bits nb_de_bits_a_1 nb_de_codes_a_generer nb_max_de_tirages[/code][/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez à la devinette suivante : Le père de toto a trois fils : Tim, Tam et ?* Retour Résumé de la discussion nodgim 04-05-2016 08:14:38 Bonjour à tous, Dans le prolongement du sujet "nombres premiers d'addition" voici une autre énigme beaucoup plus complexe: Dans un segment de n bits, combien peut-on compter au maximum de codes différents tels que la superposition de 2 quelconques d'entre eux donne à chaque fois un code différent ? Par superposition, il faut comprendre qu'à un rang donné, il y a 1 si au moins un des deux codes est à 1, et 0 si les 2 codes sont à 0. Vous allez vous rendre compte rapidement qu'il n'est pas efficace de travailler dans l'ordre croissant des codes. Et que donc, l'usage d'un programme doit être précédé d'une réflexion poussée. Le sujet étant très ouvert, je ne donne pas de temps. Chacun peut élaborer sa propre méthode et la présenter ici. Cette question fait l'objet déja d'un sujet sur un site voisin depuis un certain temps. Rien de probant n'en est sorti sur la preuve d'un maximum... Pied de page des forums P2T basé sur PunBB Screenshots par Robothumb © Copyright 2002–2005 Rickard Andersson
Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact