Pull to refresh

Старая задача про роботов

Reading time1 min
Views12K
Наверняка многие знают задачу про 2х роботов.


Напомню условие:

Есть 2 робота.
Их на парашютах сбрасывают на дискретную, бесконечную прямую.
Изначально неясно какое между роботами расстояние и кто слева, а кто справа.

Надо написать программу для роботов, которая будет гарантировать их встречу.
Программа одинаковая для обоих роботов, коммуникации между роботами нет.

Допустимые операторы:
moveLeft // 1 шаг влево
moveRight // 1 шаг вправо
goto //перейти на n-ую строчку программы
if (startPoint) goto //проверить есть ли под ногами парашют. (неважно чей, реакция как на свой, так и на чужой) если true, переходим на n-ую строчку программы.

Я всю жизнь думал что есть только одно решение (пока не буду его говорить, может кто задачу 1й раз видит).
Но недавно мне сказали что моё решение неправильное 0_о, мотивировав это тем, что
каждая операция выполняется мгновенно, поэтому моё решение не канает.

Может тут кто подскажет решение, которое канает при доп ограничении «мгновенное выполнение комманд»?
Просто я как-то видимо слишком для этого тупой…

upd: если роботы оказываются в одной клетке, то всё — победа. Лишний if только загромождает (в данном случае) код, соль в алгоритме.

upd2:
Правильное решение (идея просто его догнать):
1: right
2: if (startPoint) goto 4
3: goto 1
4: right
5: right
6: goto 4

upd3: короче это всё шляпа. Товарищ, выдумавший условие про «мгновенность» придумал какое-то странное «решение»:
1. if (startPoint) goto 6
2. right
3. right
4. left
5. goto 2
6. right
7. goto 6
Мне ведь не одному оно кажется абсурдным, даже не решением?

upd4: наверное он таки имел в виду
0. right
но это ничего не меняет в контексте «мгновенности» исполнения.
Tags:
Hubs:
Total votes 15: ↑12 and ↓3+9
Comments48

Articles