Betrachte die Menge der Strings S, die die binäre Repräsentation der Zahlen 0 bis 99 enthält. Was ist die kürzeste Kette T, so dass jedes Element von S eine Teilkette von T ist?Die kürzeste binäre Sequenz zur Abdeckung der Dezimalzahlen 0-99
Was Sie fragen, ist sehr ähnlich der binären De Bruijn sequence. Der Algorithmus für dieses Problem, der Eulerian cycles verwendet, kann leicht angepasst werden, um Ihr Problem zu lösen.
+1 Sehr cool :) Ich war eigentlich auf der Suche nach einer mathematischen Reprentation dafür. Wie kannst du es mit Computer bekommen? –
Sie müssen etwas Graphentheorie erlernen :) Die Algorithmen werden in den zwei Seiten erklärt, mit denen ich verknüpfte. – marcog
marcog: Vielen Dank! Ich werde :) –
"Der Maschine ist die Reihenfolge Ihrer Sequenz egal": Was kümmert es, wenn nicht die Bestellung? Auch das Beispiel scheint keinen Sinn zu ergeben. – sth
@sth Ihre Sequenz kann etwas wie 101010101111010110001010000000011 sein. Wenn die richtige Antwort 111 lautet, versucht die Maschine, sie zu erreichen. Es ist wie eine Regex "* 111 *". –
Meinst du "Betrachten Sie die Menge der Strings S, die die binäre Darstellung der Zahlen 0 bis 99 enthält. Was ist die kürzeste Zeichenfolge T, so dass jedes Element von S Teilstring von T ist?" – RossFabricant