considérer l'ensemble des chaînes S qui contient la représentation binaire des nombres de 0 à 99. Quelle est la plus courte chaîne T de telle sorte que chaque élément de S est une sous-chaîne de T?La plus courte séquence binaire pour couvrir les numéros 0-99 déc
Qu'est-ce que vous demandez est très similaire à la De Bruijn sequence binaire. L'algorithme pour ce problème, qui utilise Eulerian cycles, peut facilement être adapté pour résoudre votre problème.
+1 Très cool :) Je cherchais en fait pour une reprentation mathématique pour elle. Comment pouvez-vous l'obtenir avec un ordinateur? –
Vous devrez apprendre la théorie des graphes :) Les algorithmes sont expliqués dans les deux pages auxquelles je suis lié. – marcog
marcog: Merci beaucoup! Je vais :) –
« La machine ne se soucie pas de l'ordre de votre séquence »: Que faut-il se soucient, sinon l'ordre? De plus, l'exemple ne semble pas avoir de sens. – sth
@sth Votre séquence peut être quelque chose comme 101010101111010110001010000000011. Si la réponse correcte est 111, la machine essaie de la faire correspondre. C'est comme une regex "* 111 *". –
Voulez-vous dire « Considérez l'ensemble des chaînes S qui contient la représentation binaire des nombres de 0 à 99. Quel est le plus court T chaîne telle que chaque élément de S est de T sous-chaîne? » – RossFabricant