ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка из "собеседования". Про черепашку.
20 сообщений из 20, страница 1 из 1
Задачка из "собеседования". Про черепашку.
    #38164551
Фотография Школа с философским уклоном.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Школа с философским уклоном.
Участник
Робот-черепашка сначала смотрит на север. За один шаг может двинуться на N (N >= 1) клеток туда, куда смотрит, после чего сразу поворачивается на 90 грд. по часовой стрелке.

Входная программа — ряд целых чисел любой длины. Например: 1,7,3,4,5,1. (1 на север, 7 на восток, 3 на юг, 4 на запад, 5 на север, 1 на восток). Каждый шаг — не менее 1.

Написать код, который бы возвращал ближайший номер шага (от начала программы), на котором черепашка проедется по собственному пути. То есть, по клетке, на которой она уже была. Стоимость алгоритма по процу — не более O(N), стоимость алгоритма по памяти — постоянная ( O(1) ).

Нарисовал картинку, из которой видно одно свойство алгоритма — если черепашка когда-либо наезжает на собственный путь на неком шаге M, то этот наезд всегда происходит на ту линию, которая была построена на шаге M-3, либо M-5. Всё.

1. Это наколеночное решение, выведенное умозрительно, без доказательств.
2. История про робота-черепашку — боян 40-летней давности (или больше), над которым бились все великие бородатые изобретатели алгоритмов, поэтому любое своё решение просто психологически идёт в корзину.

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

Картинка, из которой видны свойства шагательного алгоритма (красным показаны линии, на которые совершается наезд). Зелёная точка — возможные альтернативы развития событий для рассмотрения разных вариантов.
...
Рейтинг: 0 / 0
25.02.2013, 13:06
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38164812
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
Школа с философским уклоном.2. История про робота-черепашку — боян 40-летней давности (или больше), над которым бились все великие бородатые изобретатели алгоритмов, поэтому любое своё решение просто психологически идёт в корзину.Можно перевести для тупых? Это означает, что нужно найти существующее решение в дебрях Гугла?

Тем не менее, "своё" решение, вчерне:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
typedef int Box[4];

Box b = {0};
bool inner = false;
int stepNum = 0;
int stepLength;
while(scanf("%d", &stepLength) == 1){
  if(stepLength - b[(stepNum-2)%4] < b[stepNum%4]) inner = true; //Случай равенства - попадание на периметр, не рассмотрено

  if(inner){
    if(stepLength - b[(stepNum-2)%4] > b[stepNum%4]){
      return stepNum;
    }
  }
  b[stepNum%4] = stepLength - b[(stepNum-2)%4];
  ++stepNum;
}

Реально прямоугольников нужно два, второй - для предыдущего "витка".
...
Рейтинг: 0 / 0
25.02.2013, 14:44
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38165707
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Странная черепашка. Это не язык Лого а просто какая-то хрень.
Вобщем по сложности напоминает Malbolge. Вобщем кто
мозохист тому и оно самое то.
...
Рейтинг: 0 / 0
26.02.2013, 01:40
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38165717
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
mayton,

поэтому и вышеприведенное решение Абстракшена дано не на Лого-тортилку, а по условиям задачки...
...
Рейтинг: 0 / 0
26.02.2013, 02:08
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166348
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну чтож. Побольше-б таких задач
...
Рейтинг: 0 / 0
26.02.2013, 13:55
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166570
madbear
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
madbear
Участник
У нас одно время уже после собеседования, когда сотрудника приняли, предлагали размяться задачкой про черепашек:
Ползут по пустыне три черепашки. Первая говорит: "Впереди меня никого, а позади две черепашки". Вторая говорит: "Впереди меня одна черепашка и сзади одна черепашка". Третья говорит: "Впереди меня одна черепашка и сзади одна черепашка". Как это возможно?Долгое время я думал, что существует только одно решение)
...
Рейтинг: 0 / 0
26.02.2013, 15:16
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166579
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
madbear,

ползают по кругу?
...
Рейтинг: 0 / 0
26.02.2013, 15:19
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166589
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Тогда бы у всех черепашек были-бы одинаковые условия.
...
Рейтинг: 0 / 0
26.02.2013, 15:22
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166616
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
madbearДолгое время я думал, что существует только одно решение)А какое второе?
...
Рейтинг: 0 / 0
26.02.2013, 15:31
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166668
Gwa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gwa
Участник
madbear,
средняя черепашка ползёт в другую сторону ?
...
Рейтинг: 0 / 0
26.02.2013, 15:51
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166677
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
может, третья высказалась, когда обогнала вторую?
...
Рейтинг: 0 / 0
26.02.2013, 15:53
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166724
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я тоже подумал о факторе времени в задаче.
...
Рейтинг: 0 / 0
26.02.2013, 16:11
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166725
Фотография Школа с философским уклоном.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Школа с философским уклоном.
Участник
Яростный Мечможет, третья высказалась, когда обогнала вторую?
Да, тоже подумал - гетеросинхронность, т.е. не одновременность описанных событий )
...
Рейтинг: 0 / 0
26.02.2013, 16:11
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166752
Фотография Школа с философским уклоном.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Школа с философским уклоном.
Участник
Ползут по пустыне три черепашки. Первая говорит: "Впереди меня никого, а позади две черепашки". Вторая говорит: "Впереди меня одна черепашка и сзади одна черепашка". Третья говорит: "Впереди меня одна черепашка и сзади одна черепашка". Как это возможно?
1. Сказать можно вообще что угодно при желании, рот всё стерпит.
2. Черепашки не умеют говорить, поэтому это никак не возможно.
3. Между произнесёнными фразами проходит время, за которое черепашки перемещаются относительно друг друга. Не сказано, что высказывания произносятся синхронно.
...
Рейтинг: 0 / 0
26.02.2013, 16:25
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166757
Stupid_BOT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Stupid_BOT
Участник
madbearУ нас одно время уже после собеседования, когда сотрудника приняли, предлагали размяться задачкой про черепашек:
Ползут по пустыне три черепашки. Первая говорит: "Впереди меня никого, а позади две черепашки". Вторая говорит: "Впереди меня одна черепашка и сзади одна черепашка". Третья говорит: "Впереди меня одна черепашка и сзади одна черепашка". Как это возможно?Долгое время я думал, что существует только одно решение)
...
Рейтинг: 0 / 0
26.02.2013, 16:29
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166763
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Черепашки двигаются в непрерывном дифференцируемом и искривлённом
и многомерном пространстве где понятия "перед" и "зад" имеют более
широкий смысл нежели в обычном представлении.
...
Рейтинг: 0 / 0
26.02.2013, 16:30
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166765
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Через три точки плоскости, не лежащие на одной прямой можно провести окружность и "три радиуса".
Одна черепашка движется по радиусу от центра такой окружности, а две другие - перпендикулярно "своим" радиусам.

P.S. Какое, всё-таки, второе решение?
...
Рейтинг: 0 / 0
26.02.2013, 16:32
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166786
Stupid_BOT
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Stupid_BOT
Участник
Basil A. Sidorov,
это как раз второе.
...
Рейтинг: 0 / 0
26.02.2013, 16:40
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166811
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Stupid_BOT, если мы спроецируем решение на рисунке на прямую
(ориентацию найдете сами) то мы получим первое решение.

Верно?
...
Рейтинг: 0 / 0
26.02.2013, 16:55
| Ответить | Цитировать | Написать  
Задачка из "собеседования". Про черепашку.
    #38166915
madbear
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
madbear
Участник
 
Правильные варианты ответов
1. Как минимум одна из черепашек врет.
2. Пока вторая черепашка говорит, третья обгоняет вторую.
3. Условия задачи невыполнимы при условиях, что геометрия евклидова, время не движется и черепашки не являются мутантами.
3.1 (Частный случай 3): рассказчик разводит вас на поиск новых решений, хотя сам не утверждал, что эти варианты существуют :)

Про черепашек, двигающихся в непрерывном дифференцируемом и искривлённом и многомерном пространстве ничего не могу сказать, не специалист)
...
Рейтинг: 0 / 0
26.02.2013, 17:50
| Ответить | Цитировать | Написать  
20 сообщений из 20, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка из "собеседования". Про черепашку.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?desktop=1&fid=16&tid=1341905]:
 0ms
get settings:
 8ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 166ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 33ms
get tp. blocked users:
 1ms
others: 202ms
total:  441ms
созд. / загр.: 441ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]