Minimum non.des coups de monnaie (commutateur) nécessaires pour que toutes les pièces soient faites face au même côté (têtes ou queues)

Question

Considérez cela, j'ai n monnaies et je les ai placés dans un ordre aléatoire (la 1ère pièce est la tête, la 2e est la queue, etc.). Vous ne connaissez pas la commande. Vous pouvez renvoyer une pièce de monnaie à la fois, puis je vous dis que si toutes les pièces font face au même côté ou non. Vous continuez à rouler jusqu'à ce que toutes les pièces soient au sens du même côté.

J'ai essayé de le casser à des cas de base inférieurs :
(1) Quand il y a 1 pièce de monnaie : pas besoin de retourner
(2) Quand il y a 2 pièces : Les seuls cas impairs que vous pouvez avoir sont {h, t} ou {t, h}, alors à basculer la première pièce fera le tour
(3) Quand il y a 3 pièces : il y a 6 cas impairs que vous pouvez vous retrouver, mais 3 d'entre eux sont similaires les uns aux autres, seulement 3 cas à considérer avec {h, t , T}, {t, h, t} et {t, t, h} (même avec une tête T et 2). La stratégie pour cela pourrait passer la 1ère pièce de monnaie si la commande n'est toujours pas faite, puis retournez la deuxième pièce, si la commande n'est toujours pas faite, puis retournez la 1ère pièce à nouveau.

J'ai du mal à trouver un algorithme général pour N pièces . Des idées?

Answer 1

Voici un algorithme général. Le nombre maximum de retombées nécessaires est 2 ^ {n-1} -1 $ .

Entrée: pièce 0, pièce 1, pièce de monnaie 2, ..., pièce $ N-1 $

Procédure:
$ \ quad $ Si toutes les pièces font face au même côté, retournez.

$ \ quad $ pour $ i $ de 1 à 2 $ ^ {N-1} -1 $ inclus:
$ \ quad \ quad $ si $ i $ est divisible par 2 $ ^ k $ mais pas 2 ^ {k + 1} $ :
$ \ quad \ quad \ quad \ quad $ bascule $ k $
$ \ quad \ quad \ quad \ quad $ Si toutes les pièces font face au même côté, retournez.

---

Par exemple, s'il n'y a pas plus de 8 pièces de monnaie, puis retournez les pièces de monnaie aux endroits suivants successivement tant que toutes les faces ne font pas face au même côté.

0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0

Answer 2

Sans entrer dans les détails, vous recherchez quelque chose qui est connu comme un code gris.Tout code de gris cyclique qui a le tout zéro bitstring à la partie opposée du cycle car le tout un bitstring donne une solution de solution attendue minimale en supposant une entrée aléatoire uniforme.