IPB
ЛогинПароль:

> Задача о двух роботах.
сообщение
Сообщение #1


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Всем привет. Коллега рассказал одну задачу, которую ему задали на одном из собеседований, мне она очень понравилась. Возможно многие ее знают, тем не менее выкладываю условие:

Имеем одномерную планету. Над ней летит самолет, десантирует сначала первого робота, затем второго. Роботы ничего не знают ни друг о друге ни о самолете (в какую сторону летел, кого сбросил первым, на каком расстоянии, в общем ничего). Робот может двигаться вправо или влево (назад и вперед то есть), при этом он может оценить что находится в той точке, на которую он встал, а это может быть
1) просто земля
2) парашют (свой от чужого не отличает)
3) другой робот

Задача: написать алгоритм перемещения (который будет применен к обоим роботам одновременно после высадки последнего) робота, таким образом, чтобы они встретились со 100% вероятностью.

Я задачу решил, если понадобится выложу ответ. Задача легкая, но по мне очень забавная. Удачи.



Решения просьба оформлять в спойлер.

Сообщение отредактировано: klem4 -


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
Ответов(1 - 19)
сообщение
Сообщение #2


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Интересно. А "одномерная планета" - границы, начала координат имеются или она бесконечная во все стороны? Самолёт, я так понял, сбросил их на одной "линии", раз они только вперёд-назад ходят. И ещё вопрос, вот когда робот только приземлился, это считается за событие, что он наступил на парашют?)


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Цитата
Интересно. А "одномерная планета" - границы, начала координат имеются или она бесконечная во все стороны?


Бесконечная прямая.

Цитата
Самолёт, я так понял, сбросил их на одной "линии", раз они только вперёд-назад ходят.


Именно так.

Цитата
И ещё вопрос, вот когда робот только приземлился, это считается за событие, что он наступил на парашют?)


Пожалуй нет. Не знаю. Это не существенно smile.gif. Алгоритм (одинаковый у обоих) включается как только приземлится второй из них.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Я придумал) Может, немного извращенно, но всё же:

Жди меня (Показать/Скрыть)


Сообщение отредактировано: Unconnected -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Приятная задачка. как раз для программерских мозгов smile.gif.
У меня есть несколько вопросов.. Думаю, их нет смысла прятать.
Не совсем ясно, что умеет робот. Ясно, например что он должен уметь двигаться на определенное расстояние, иначе задача не очень осмыслена. Наверняка он может менять направление на противоположное. А вот может ли он, скажем, измерить пройденное расстояние, а затем произвести с ним математические действия (умножить/поделить на 2, например). Может он запомнить, что уже нашел один парашют и отличить другой найденный от первого? Может он запомнить, где был парашют и вернуться к нему? И еще один очень важный вопрос: могут два парашюта лежать в одной точке? Если да, то может ли робот распознать такую ситуацию? Может он хотя бы запомнить, что уже нашел один парашют? В зависимости от ответов на эти вопросы алгоритм может меняться..

Два возможных алгоритма (Показать/Скрыть)


Добавлено через 5 мин.
Решение, требующее минимум предположений (как мне кажется)) (Показать/Скрыть)


Добавлено через 6 мин.
Unconnected, так не пойдет )).

Опровергающий пример (Показать/Скрыть)


Добавлено через 8 мин.
Я очень извиняюсь, спутал ники sad.gif. Видел ник Rathar'а в теме, ну и автоматически распространил его на сообщение..
Исправлено. Извините, буду внимательнее )).


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Пойдёт-пойдёт (Показать/Скрыть)


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Ответ на Пойдёт-пойдёт (Показать/Скрыть)



--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Не исправленная, а дополненная rolleyes.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Профи
****

Группа: Пользователи
Сообщений: 930
Пол: Мужской

Репутация: -  11  +


Запутанное условие, только сейчас дошло что планета не абсолютно круглый шар. Опять же возможности роботов не известны, предположу что это всё таки роботы а не тачка с камнями на вечном двигателе.
Спойлер (Показать/Скрыть)



Сообщение отредактировано: SKVOZNJAK -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Профи
****

Группа: Пользователи
Сообщений: 930
Пол: Мужской

Репутация: -  11  +


ыыыы

Сообщение отредактировано: SKVOZNJAK -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Спойлер (Показать/Скрыть)


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(-Unconnected- @ 2.02.2010 10:00) *
Не исправленная, а дополненная rolleyes.gif
Ага. Напиши универсальную программу:
begin
end.
- и дополняй ее.. А можно еще и всех в плагиате обвинить: взяли твой код и дополнили! И ведь даже изменить не попытались, наглые такие ))




--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Решение 1.

Спойлер (Показать/Скрыть)


Решение 2.
Спойлер (Показать/Скрыть)


Задача #2 на подходе.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(klem4 @ 3.02.2010 20:55) *
мужик с гаечным ключом и они встретятся на местном радио рынке.
lol.gif Одномерный ключ на 12? smile.gif Мужик будет о двадцати семи пальцах с одиннадцатью суставами каждый, растущими из шеи.. Но тоже одномерный! smile.gif

Цитата
Робот ... считает сколько парашютов
Есть решение, не требующее подсчета парашютов! см. пост #5.

Цитата
Задача #2 на подходе.
Ждем с нетерпением! yes2.gif

klem4 +1


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Цитата
Решение, требующее минимум предположений (как мне кажется)) (Показать/Скрыть)



Lapp, так не пойдёт ))

Робот делает шаг вперёд, потом шаг назад, находит парашют и опять сначала, делает шаг вперёд... Если, конечно, под "начальной амплитудой" подразумевалась постоянная величина.

Да-да, klem4, спасибо, может, теперь на работу возьмут..))

Сообщение отредактировано: Unconnected -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Unconnected @ 3.02.2010 23:45) *
Lapp, так не пойдёт ))

Робот делает шаг вперёд, потом шаг назад, находит парашют и опять сначала, делает шаг вперёд... Если, конечно, под "начальной амплитудой" подразумевалась постоянная величина.
smile.gif робот помнит последний найденный парашют (то есть место, где он найден) и игнорирует его. Я согласен, это некая фича, которая может быть не реализована в его прошивке..
Я не знаю, что лучше: считать парашюты или помнить, где нашел)).

Добавлено через 17 мин.
Собственно, это практически эквивалентно подсчету. Признаю )).


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Спойлер (Показать/Скрыть)


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Спойлер (Показать/Скрыть)


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Профи
****

Группа: Пользователи
Сообщений: 930
Пол: Мужской

Репутация: -  11  +


klem4, со вторым твоим решеним не всё ясно. В задании говорится о 100% вероятности встречи, но если они высадятся на кольце симметрично в нужное время, то и действовать станут симметрично - могут и не встретиться.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Кольца нет, есть
Цитата
Бесконечная прямая.


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 2.12.2020 22:34
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name