Задача о двух роботах. |
Задача о двух роботах. |
klem4 |
1.02.2010 21:35
Сообщение
#1
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Всем привет. Коллега рассказал одну задачу, которую ему задали на одном из собеседований, мне она очень понравилась. Возможно многие ее знают, тем не менее выкладываю условие:
Имеем одномерную планету. Над ней летит самолет, десантирует сначала первого робота, затем второго. Роботы ничего не знают ни друг о друге ни о самолете (в какую сторону летел, кого сбросил первым, на каком расстоянии, в общем ничего). Робот может двигаться вправо или влево (назад и вперед то есть), при этом он может оценить что находится в той точке, на которую он встал, а это может быть 1) просто земля 2) парашют (свой от чужого не отличает) 3) другой робот Задача: написать алгоритм перемещения (который будет применен к обоим роботам одновременно после высадки последнего) робота, таким образом, чтобы они встретились со 100% вероятностью. Я задачу решил, если понадобится выложу ответ. Задача легкая, но по мне очень забавная. Удачи. Решения просьба оформлять в спойлер. Сообщение отредактировано: klem4 - 1.02.2010 21:37 -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Unconnected |
1.02.2010 22:09
Сообщение
#2
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Интересно. А "одномерная планета" - границы, начала координат имеются или она бесконечная во все стороны? Самолёт, я так понял, сбросил их на одной "линии", раз они только вперёд-назад ходят. И ещё вопрос, вот когда робот только приземлился, это считается за событие, что он наступил на парашют?)
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
klem4 |
1.02.2010 22:20
Сообщение
#3
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Цитата Интересно. А "одномерная планета" - границы, начала координат имеются или она бесконечная во все стороны? Бесконечная прямая. Цитата Самолёт, я так понял, сбросил их на одной "линии", раз они только вперёд-назад ходят. Именно так. Цитата И ещё вопрос, вот когда робот только приземлился, это считается за событие, что он наступил на парашют?) Пожалуй нет. Не знаю. Это не существенно . Алгоритм (одинаковый у обоих) включается как только приземлится второй из них. -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Unconnected |
1.02.2010 22:38
Сообщение
#4
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Я придумал) Может, немного извращенно, но всё же:
Жди меня (Показать/Скрыть)
Сообщение отредактировано: Unconnected - 1.02.2010 22:48 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Lapp |
1.02.2010 23:09
Сообщение
#5
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Приятная задачка. как раз для программерских мозгов .
У меня есть несколько вопросов.. Думаю, их нет смысла прятать. Не совсем ясно, что умеет робот. Ясно, например что он должен уметь двигаться на определенное расстояние, иначе задача не очень осмыслена. Наверняка он может менять направление на противоположное. А вот может ли он, скажем, измерить пройденное расстояние, а затем произвести с ним математические действия (умножить/поделить на 2, например). Может он запомнить, что уже нашел один парашют и отличить другой найденный от первого? Может он запомнить, где был парашют и вернуться к нему? И еще один очень важный вопрос: могут два парашюта лежать в одной точке? Если да, то может ли робот распознать такую ситуацию? Может он хотя бы запомнить, что уже нашел один парашют? В зависимости от ответов на эти вопросы алгоритм может меняться.. Два возможных алгоритма (Показать/Скрыть)
Добавлено через 5 мин. Решение, требующее минимум предположений (как мне кажется)) (Показать/Скрыть)
Добавлено через 6 мин. Unconnected, так не пойдет )). Опровергающий пример (Показать/Скрыть)
Добавлено через 8 мин. Я очень извиняюсь, спутал ники . Видел ник Rathar'а в теме, ну и автоматически распространил его на сообщение.. Исправлено. Извините, буду внимательнее )). -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Unconnected |
1.02.2010 23:30
Сообщение
#6
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Пойдёт-пойдёт (Показать/Скрыть)
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Lapp |
1.02.2010 23:37
Сообщение
#7
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Ответ на Пойдёт-пойдёт (Показать/Скрыть)
-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
-Unconnected- |
2.02.2010 10:00
Сообщение
#8
|
Гость |
Не исправленная, а дополненная
|
SKVOZNJAK |
2.02.2010 17:00
Сообщение
#9
|
Профи Группа: Пользователи Сообщений: 930 Пол: Мужской Репутация: 11 |
Запутанное условие, только сейчас дошло что планета не абсолютно круглый шар. Опять же возможности роботов не известны, предположу что это всё таки роботы а не тачка с камнями на вечном двигателе.
Спойлер (Показать/Скрыть)
Сообщение отредактировано: SKVOZNJAK - 2.02.2010 17:52 |
SKVOZNJAK |
2.02.2010 17:26
Сообщение
#10
|
Профи Группа: Пользователи Сообщений: 930 Пол: Мужской Репутация: 11 |
ыыыы
Сообщение отредактировано: SKVOZNJAK - 2.02.2010 17:53 |
TarasBer |
2.02.2010 18:52
Сообщение
#11
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Спойлер (Показать/Скрыть)
-------------------- |
Lapp |
3.02.2010 4:22
Сообщение
#12
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Не исправленная, а дополненная Ага. Напиши универсальную программу:begin- и дополняй ее.. А можно еще и всех в плагиате обвинить: взяли твой код и дополнили! И ведь даже изменить не попытались, наглые такие )) -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
klem4 |
3.02.2010 20:55
Сообщение
#13
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Решение 1.
Спойлер (Показать/Скрыть)
Решение 2. Спойлер (Показать/Скрыть)
Задача #2 на подходе. -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Lapp |
3.02.2010 23:01
Сообщение
#14
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
мужик с гаечным ключом и они встретятся на местном радио рынке. Одномерный ключ на 12? Мужик будет о двадцати семи пальцах с одиннадцатью суставами каждый, растущими из шеи.. Но тоже одномерный! Цитата Робот ... считает сколько парашютов Есть решение, не требующее подсчета парашютов! см. пост #5.Цитата Задача #2 на подходе. Ждем с нетерпением! klem4 +1 -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Unconnected |
3.02.2010 23:45
Сообщение
#15
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Цитата Решение, требующее минимум предположений (как мне кажется)) (Показать/Скрыть)
Lapp, так не пойдёт )) Робот делает шаг вперёд, потом шаг назад, находит парашют и опять сначала, делает шаг вперёд... Если, конечно, под "начальной амплитудой" подразумевалась постоянная величина. Да-да, klem4, спасибо, может, теперь на работу возьмут..)) Сообщение отредактировано: Unconnected - 3.02.2010 23:53 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Lapp |
4.02.2010 0:05
Сообщение
#16
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Lapp, так не пойдёт )) робот помнит последний найденный парашют (то есть место, где он найден) и игнорирует его. Я согласен, это некая фича, которая может быть не реализована в его прошивке..Робот делает шаг вперёд, потом шаг назад, находит парашют и опять сначала, делает шаг вперёд... Если, конечно, под "начальной амплитудой" подразумевалась постоянная величина. Я не знаю, что лучше: считать парашюты или помнить, где нашел)). Добавлено через 17 мин. Собственно, это практически эквивалентно подсчету. Признаю )). -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
klem4 |
4.02.2010 20:03
Сообщение
#17
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Спойлер (Показать/Скрыть)
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Unconnected |
4.02.2010 22:01
Сообщение
#18
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Спойлер (Показать/Скрыть)
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
SKVOZNJAK |
6.02.2010 4:42
Сообщение
#19
|
Профи Группа: Пользователи Сообщений: 930 Пол: Мужской Репутация: 11 |
klem4, со вторым твоим решеним не всё ясно. В задании говорится о 100% вероятности встречи, но если они высадятся на кольце симметрично в нужное время, то и действовать станут симметрично - могут и не встретиться.
|
Unconnected |
6.02.2010 12:33
Сообщение
#20
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Кольца нет, есть
Цитата Бесконечная прямая. -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Текстовая версия | 23.10.2024 1:10 |