Минимальный нет.монеты Flips (Switch) необходимо, чтобы все монеты сталкивались на одной и той же стороне (головами или хвостами)

Question

Рассмотрим это, у меня есть n монет, и я поместил их в случайном порядке (1-я монета - это голова, 2-е хвосты и т. Д.). Вы не знаете заказ. Вы можете перевернуть одну монету за раз, а затем я скажу, если все монеты сталкиваются с той же стороной или нет. Вы продолжаете переворачивать до тех пор, пока все монеты не смотрятся в ту же сторону.


Я пытался сломать его на меньший базовые чехлы :
(1) Когда есть 1 монета : Нет необходимости переворачивать
(2) Когда есть 2 монеты : единственные нечетные случаи, которые вы можете иметь, есть {h, t} или {t, h}, поэтому переворачивая первую монету, сделает трюк
(3) Когда есть 3 монеты : есть 6 нечетных случаев, которые вы можете в конечном итоге, но 3 из них похожи друг на друга, поэтому только 3 случая для рассмотрения с {h, t , T}, {t, h, t} и {t, t, h} (то же самое с одним T и 2 головками). Стратегия для этого можно было перевернуть 1-й монету, если порядок все еще не сделан, то переверните вторую монету, если порядок еще не сделан, затем переверните 1-я монету снова.

У меня трудно приступить к общему алгоритму для монет . Любые идеи?

Answer 1

Вот общий алгоритм. Максимальное количество переворотов требуется $ 2 ^ {N - 1} -1 $ .

вход: монета 0, монета 1, монета 2, ..., монета $ n-1 $

Процедура:
$ \ Quad $ Если все монеты сталкиваются с той же стороной, возврат.

$ \ Quad $ для $ i $ от 1 до $ 2 ^ {n - 1} -1 $ включительно:
$ \ Quad \ Quad $ Если $ i $ делится на $ 2 ^ k $ Но не $ 2 ^ {k + 1} $ :
$ \ Quad \ Quad \ Quad $ Flip Coin $ K $ $ \ Quad \ Quad \ Quad $ Если все монеты сталкиваются с той же стороной, вернитесь.

---

Например, если существует не более 8 монет, то просто переверните монеты в следующих местах последовательно, если все лица не сталкиваются с одной и той же стороной.

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

Не входя в детали, вы ищете что-то, что известно как серый код.Любой циклический серый код, который имеет все нулевую битушку в противоположной части цикла, так как вся одна бита, дает минимальное ожидаемое время решения, предполагая равномерное случайный вход.