Интересная задача на логику?

Question

[KirAmp]

Вчера на работе коллега задал программистическую загадку. До сих пор думаю над ее решением.


Дан некоторый замкнутый массив чисел (для простоты окружность) заполненный нулями и единицами в случайном порядке. Длинны N.

Как только лишь меняя элементы на 0 и 1 и перебирая их по одному можно найти N.

Answer 1

[Дмитрий Гукетлев]

мне кажется можно еще упростить решение:

0. запоминаем текущее значение. допустим ноль.

1. Идем вправо, считая шаги пока не дойдем до нуля, при этом прошли A шагов
2. Ставим вместо нуля единицу
3. Идем на А шагов влево (на исходную)
4. Если там 1 (значение изменилось) то N=A, если там 0 то идем на пункт 1

По идее должно быть вдвое короче, т.к. возвращаться на исходную нужно в среднем вдвое реже.

Comments

[Глеб Старков]

0110 — и вы имеете бесконечный цикл.

1. Берем первый элемент (0) меняем на 1
2. Идем вправо до нуля (1,1,0), три шага, меняем 0 на 1
3. Идем влево три шага. Наша единица не изменилась.
4. Идем вправо до следующего нуля… а нулей больше нет.

[MiXei4]

«1. Берем первый элемент (0) меняем на 1» — такого в исходном алгоритме не было.

[Глеб Старков]

Да, я ошибся. Спасибо.

Answer 2

[BrainHacker]

Задачка аналогична с закольцованным составом из вагонов, нужно посчитать количество вагонов. И можно включать/выключать свет в вагонах (менять на 0 и 1 соответственно). Предположим, что у нас есть вагон (точка массива), в котором мы сейчас находимся. Включаем свет в данном вагоне (1). Идем в соседний левый вагон, выключаем свет (0). Идем в соседний правый вагон от начального, выключаем свет (0). Итак, у нас есть последовательность 010. Опять идем в соседний левый вагон и включаем свет (1). Идем в соседний правый вагон и проверям: если свет выключен (а мы его на предыдущих шагах включили), то количество вагонов равно 2. Если нет, то алгоритм продолжается.
То есть, каждую итерацию можно описать так:

011...110
<-
111...11x
->
if
111...111 мы нашли середину состава, можно посчитать количество вагонов
else (имеем 111...110)
do
111...111
0111...1110.
repeat

Answer 3

[Mrrl]

Вопрос в том, сколько у нас памяти — можем ли мы запомнить число N. А то дадут вам массив длиной в 2^2^64…
Интересно было бы написать программу для машины Тьюринга, которая выключит свет во всем поезде.

Comments

[Mrrl]

[+]+>[+]<[>+>+[+>+]+[+<+]<]
Интересно…

Answer 4

[Mrrl]

Если уж упрощать, то:

1. Ставим на ячейку 1.
2. A:=1
3. A:=A*2
4. Делаем A шагов вправо, после каждого шага записываем в ячейку 0.
5. Делаем A шагов влево.
6. Если в ячейке 1, идем на пункт 3.
7. Ставим в ячейку 1 и идем вправо, считая шаги, пока не найдем 1.

Максимальное число шагов — N*9-12 (при N>1)

Comments

[m_z]

1111
4. 00_11
5. _0011
6. != 1
7. 1011 -> 3
?

[Mrrl]

У Вас _ стоит перед ячейкой, на которой находится каретка? Тогда
4. 10_01
— у меня написано "после каждого шага записываем в ячейку 0."

[m_z]

упс, тогда изменим начальное число, 01111:
4) 00_011
5) _00011
6) != 1

[Mrrl]

Первое действие забыли :)
1) _11111
A=2
4) 10_011
5) _10011
A=4
4) 1000_1
5) _10000
A=8
4) 000_00
5) _00000
7) _10000 N=5

[m_z]

так стоп, начальное число было 01111, а не 11111.

[Mrrl]

Да. А первое действие — «1. Ставим на ячейку 1.». Вот 0 и превратился в 1.

Answer 5

[Zak]

А цель какая, определить N за минимальное число шагов? Уточните, могу я запоминать состояния элементов, которые установил?

Comments

[KirAmp]

да, за минимальное число шагов.
можно запомнить состояние у определенного элемента

Answer 6

[Mrrl]

Кстати, «перебирая их по одному» можно понять, как «двигаясь только вправо». В этом случае, насколько я понимаю, задача неразрешима.

Comments

[KirAmp]

можно перебирать в обе стороны :) Если в одну, то да — неразрешаема

[Mrrl]

А доказать, что неразрешима, можете? ;)