Про кольцевой поезд

Логические задачи

Модераторы: Азарапетыч, Администрация

Аватара пользователя
ЛевК
Популярный автор
Популярный автор
Сообщения: 1560
Зарегистрирован: 29 ноя 2004, 20:33
Пол: Мужской
Откуда: Израиль

Re: Про кольцевой поезд

Сообщение ЛевК »

Чива Ротсен писал(а):Свежак
Есть поезд, закольцованный по кругу...
Сегодня моя дочка представляла эту задачу перед четырехсотенной аудиторией детей и их родителей (она преподает математику в школе для особо одаренных детей, и это было что-то вроде торжественного завершения сезона). Задача имела огромный успех. Так что еще раз спасибо Чиве :!:
(Внизу один из слайдов этой презентации с надписью - "ты находишься здесь". А всего слайдов было тридцать!).
Вложения
Кольцевой поезд
Кольцевой поезд
Poezd.jpg (12.01 КБ) 4040 просмотров

kknop
Читатель
Читатель
Сообщения: 6
Зарегистрирован: 04 май 2007, 17:25
Пол: Мужской

Re: Про кольцевой поезд

Сообщение kknop »

Чива Ротсен писал(а):Свежак

Есть поезд, закольцованный по кругу. То есть первый вагон так же соединяется с последним, как и со вторым. Окон нет. Из вагона в вагон переходить можно. В каждом вагоне можно включать или выключать лампочку. Никаких пометок на стенах или где-либо еще в вагоне делать нельзя. Определить количество вагонов.
Чива, - вообще это, конечно, НЕ СВЕЖАК. Свежаком является только формулировка про поезд. Скажем, в формулировке про циклический конвейер мы ту же самую задачу давали еще в 1994 году. А на самом деле она намного более старая - восходит к классическим книжкам по информатике (Кнут, Дэвид Грис, Дейустра и т.д.), просто очень лениво искать, в какой именно книжке она была впервые.

Вот еще версия очень похожей задачи. Юзер открывает веб-браузер на своей любимой страничке и начинает играть в такую игру: попав на очередную страничку, он переходит с нее по первой встретившейся там ссылке (предположим, что на каждой страничке есть хотя бы одна ссылка). Ясно, что рано или поздно такая игра приведет его на ту страничку, на которой он уже побывал, а после этого начнется цикл. Как (с минимальными издержками - что это такое, более-менее понятно, а конкретику я специально не навожу) найти длину этого цикла?

Аватара пользователя
ЛевК
Популярный автор
Популярный автор
Сообщения: 1560
Зарегистрирован: 29 ноя 2004, 20:33
Пол: Мужской
Откуда: Израиль

Re: Про кольцевой поезд

Сообщение ЛевК »

kknop писал(а): просто очень лениво искать...
Вот потому и свежак :)

Аватара пользователя
Алика
Популярный автор
Популярный автор
Сообщения: 2514
Зарегистрирован: 03 июн 2006, 13:21
Пол: Женский
Откуда: Аддис-Абеба

Сообщение Алика »

А можно выкрутить лампочку и потом пройтись посчитать вагоны? :)
Думать - удел избранных

Аватара пользователя
Versus
Литератор-любитель
Литератор-любитель
Сообщения: 404
Зарегистрирован: 12 май 2006, 13:36

Сообщение Versus »

Можно. Но тогда ни кто не гарантирует, что неизвестные вандалы не выкрутили ещё пару лампочек в других местах:)

А вообще интересно, изменится ли решение, если лампочка имеет 3 положения: ВКЛ, ВЫКЛ и ВЫКР :)

Аватара пользователя
Рыжик
Популярный автор
Популярный автор
Сообщения: 3235
Зарегистрирован: 05 фев 2007, 19:41
Пол: Мужской
Откуда: Калининград
Контактная информация:

Сообщение Рыжик »

Versus писал(а):А вообще интересно, изменится ли решение, если лампочка имеет 3 положения: ВКЛ, ВЫКЛ и ВЫКР :)
Ага. А к двум положениям выключателей ВКЛ и ВЫКЛ добавить третье: НЕ ПЕРЕКЛ :)
Опыт истории учит, что люди ничему не научаются на опыте истории.(с)

Аватара пользователя
Ангелотти
Популярный автор
Популярный автор
Сообщения: 1873
Зарегистрирован: 21 июл 2006, 11:43
Пол: Мужской
Откуда: оттуда

Сообщение Ангелотти »

А кто-нибудь правильный ответ дал уже здесь на форуме?

Чива Ротсен
Ультраантипатриот
Ультраантипатриот
Сообщения: 8892
Зарегистрирован: 29 сен 2003, 14:48
Пол: Мужской
Откуда: СПб
Контактная информация:

Сообщение Чива Ротсен »

Фидаиль писал(а):А кто-нибудь правильный ответ дал уже здесь на форуме?
Да, и много.

Аватара пользователя
Ангелотти
Популярный автор
Популярный автор
Сообщения: 1873
Зарегистрирован: 21 июл 2006, 11:43
Пол: Мужской
Откуда: оттуда

Сообщение Ангелотти »

У! и не лень ходить?! :o

Аватара пользователя
Гном
Акула пера
Акула пера
Сообщения: 5768
Зарегистрирован: 17 сен 2003, 00:07
Откуда: СПб

Сообщение Гном »

Рыжик писал(а):
Versus писал(а):А вообще интересно, изменится ли решение, если лампочка имеет 3 положения: ВКЛ, ВЫКЛ и ВЫКР :)
Ага. А к двум положениям выключателей ВКЛ и ВЫКЛ добавить третье: НЕ ПЕРЕКЛ :)
А также РАЗБИТ и ПЕРЕГОР :))
Гном

Аватара пользователя
Versus
Литератор-любитель
Литератор-любитель
Сообщения: 404
Зарегистрирован: 12 май 2006, 13:36

Сообщение Versus »

Гном писал(а):А также РАЗБИТ и ПЕРЕГОР :))
Комбинация ВЫКЛ лампочки и РАСКРУЧ переключателя приводит к поражению электрическим током неосторожного поездатого исследователя :)

Аватара пользователя
Ангелотти
Популярный автор
Популярный автор
Сообщения: 1873
Зарегистрирован: 21 июл 2006, 11:43
Пол: Мужской
Откуда: оттуда

Сообщение Ангелотти »

Фидаиль писал(а):У! и не лень ходить?! :o
Это я к тому что если вагонов будет штук 100, то исследователь будет выглядеть как аватара Рыжика :D . Это еще в лучшем случае.

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Сообщение Dendr »

Versus писал(а):
Гном писал(а):А также РАЗБИТ и ПЕРЕГОР :))
Комбинация ВЫКЛ лампочки и РАСКРУЧ переключателя приводит к поражению электрическим током неосторожного поездатого исследователя :)
А еще могут быть:
ЗАЛЯП, МУХ_ЗАГАЖ и, если это современный вариант - ГАЛОГ...

Аватара пользователя
Ангелотти
Популярный автор
Популярный автор
Сообщения: 1873
Зарегистрирован: 21 июл 2006, 11:43
Пол: Мужской
Откуда: оттуда

Сообщение Ангелотти »

Dendr писал(а): ЗАЛЯП, МУХ_ЗАГАЖ и, если это современный вариант - ГАЛОГ...
ГАЛОГ... - это от галогеновый?

Все просто: идешь по вагонам и в каждом оставляешь что-нибудь (можно даже частичку себя :D ). А потом идешь второй раз и собираешь :D Но вдвоем с напарником интереснее и не так скучно. И не страшно.
Можно даже наперегонки устроить: один бежит в одну сторону выворачивать лампы, а другой в другую :D . И кто больше соберет.

Аватара пользователя
Рыжик
Популярный автор
Популярный автор
Сообщения: 3235
Зарегистрирован: 05 фев 2007, 19:41
Пол: Мужской
Откуда: Калининград
Контактная информация:

Сообщение Рыжик »

Фидаиль писал(а):... исследователь будет выглядеть как аватара Рыжика :D . Это еще в лучшем случае.
Я не устал. Конкретно не прёт. Это можно прочесть по глазам. :)
Опыт истории учит, что люди ничему не научаются на опыте истории.(с)

Ответить

Вернуться в «Задачки»