Страница 1 из 2 1 2 ПоследняяПоследняя
Показано с 1 по 20, из 36.

Тема: Растолкуйте мне задачку про циклический поезд...

Hybrid View

  1. #1
    Регистрация
    17-05-2008
    Возраст
    46
    Сообщения
    70
    Благодарность
    19
    Поблагодарили 43 раз в 20 сообщениях

    Растолкуйте мне задачку про циклический поезд...

    ... что-то меня на ней переклинило)

    Есть поезд, состоящий из некоторого количества вагонов. Вы находитесь в одном из них. Это очень странный поезд, потому что его вагоны сцеплены в кольцо. В каждом вагоне есть лампочка, которую вы можете включать и выключать. Ваша задача заключается в том, чтобы определить количество вагонов в поезде. Опишите алгоритм решения этой задачи. Других людей и прочих живых или неживых существ в поезде нет. Лампочки нельзя выкручивать, они не перегорают и не нагреваются, рисовать на стенах мелом нельзя, окон у вагонов нет. В общем, состояние поезда — это только лампочки. Кстати, начальное состояние поезда неизвестно, то есть изначально какие-то лампочки могут гореть, а какие-то не гореть. Единственный способ узнать, горит ли лампочка в определенном вагоне — это войти в него и посмотреть. Источник: https://eax.me/interview-questions/


    Что-то мне кажется, что тут в формулировке забыли про максимум, т.е. количество вагонов надо ограничить сверху. Иначе под любой алгоритм, ищущий повторяющиеся периоды и включающий/выключающий лампочки для выяснения кратности можно построить очень длинный поезд, на котором этот алгоритм выдаст неверный ответ. Или я ошибаюсь?

  2. гм она чот нерешаемая по идее... там же подряд в неопределнном кол-ве вагонов может гореть лампочка и ты не знаешь кончился поезд или нет ( вернулся ты в стартовую точку или нет ) и кол-во вагонов неизвестно....
    да был бы известен максимум можно было бы пару кругов навернуть на крайняк считая вагоны и все, а так ХЗ чот...
    а тут еще и задача найти кол-во вагонов в поезде....

  3. Не ту задачу выбрал. Твоя со скобочками же.

  4. Одну разбить. Оставить свой ботинок.
    Последний раз редактировалось Andruxa_N, 13-06-2018 в 18:00

  5. #5
    Регистрация
    31-03-2008
    Адрес
    Нижний Новгород
    Возраст
    35
    Сообщения
    8,838
    Благодарность
    5,261
    Поблагодарили 3,467 раз в 2,006 сообщениях
    1. Идём и включаем все лампочки, пока нам не перестанут попадаться выключенные. Попутно считаем. Численное значение - ну х.з., ну пусть, например, сколько прошли и включили штук, столько же надо чтобы потом подряд было включенных.
    2. После этого начинаем идти и выключать лампочки, пока не дойдём до выключенной. Считаем. Если получилось примерно столько же, сколько и в п.1 (на момент, пока мы не решили, что что выключенные нам больше не попадаются) - значит, считаем, что мы получили ответ.
    3. Поскольку у нас нет достоверного ограничения количества вагонов "сверху", т.е., грубо говоря, мы насчитали таким методом 25 вагонов, а на самом деле их миллиард, т.е. нам тупо повезло, то и результатом задачи является не нахождение точного значения, а всего лишь оценка. А значит, теперь надо сделать проверку. Любую. Например, прогнать алгоритм по кругу, исходя из найденного ответа, заданное число раз (чтобы общее число пройденных в ходе теста вагонов было на порядки больше полученного в п. 2 ответа), и чтобы при этом не было ни одной ошибки (т.е. каждое включение всех и последующее выключение всех подтверждало полученный ответ).
    Таким образом, можно получить достаточно качественную оценку.

  6. Одобрили:
    Tankist  (14-06-2018)  

  7. Т.е. до первой включенной? Ок.=N 2N+1-все вкл. 2N +2-выкл. вагонов - XN

  8. Ответ: 1. Включаем свет в первом вагоне, если он еще не включен.
    2. Идем по вагонам вперед, считая N = количество пройденных вагонов (первый не в счет), до тех пор, пока не войдем в очередной вагон с включенным светом. Поскольку поезд циклический, рано или поздно это случится.
    3. Выключаем свет и идем на N вагонов назад.
    4. Если по возвращению в начальный вагон свет оказывается выключенным, значит мы нашли ответ — в поезде N вагонов.
    5. Перейти к шагу 2.


    Чот не совсем понял.....

  9. Одобрили:
    Adrenalin  (14-06-2018),   Demige  (13-06-2018),   rsx  (15-06-2018),   Sun  (13-06-2018)  

  10. а ну в прцинипе да если вот так туда сюда помотаться жоска то да....

  11. а если в N+1 назад лампочка горит?
    Порядочная свинюшка всегда грязь найдет
    Порядочный джипер всегда найдет где застрять
    (с) Jikanana - порядочная свинюшка-джипер

  12. Тупанул, понял
    Порядочная свинюшка всегда грязь найдет
    Порядочный джипер всегда найдет где застрять
    (с) Jikanana - порядочная свинюшка-джипер

  13. оптимизация 1: переходим от N^2 к (log N / m + N) - каждый следующий шаг длиннее предыдущего в m раз
    оптимизация 2: как 1, но если лампа в вагоне не горит, то повторяем шаг. но здесь я чёт пока не соображу какая сложность получается
    Порядочная свинюшка всегда грязь найдет
    Порядочный джипер всегда найдет где застрять
    (с) Jikanana - порядочная свинюшка-джипер

  14. #12
    Регистрация
    17-05-2008
    Возраст
    46
    Сообщения
    70
    Благодарность
    19
    Поблагодарили 43 раз в 20 сообщениях
    А можно поподробнее для тупых? "Следующий шаг" - это какие именно действия?

  15. Имеем N > 8 вагонов, стоим в 0-м, m == 2:
    1. Шаг 1: смотрим вагон 0+ (m^0 == 1) = 1
    2. Шаг 2: смотрим вагон 0+(m^1 == 2) = 2
    3. Шаг 3: смотрим вагон 0+(m^2 == 4) = 4
    4. Шаг 4: смотрим вагон 0+(m^3 == 8) = 8
    таким образом идём до потухшей лампочки в 0-м вагоне и за max(m^k -1) вычисляем кол-во вагонов
    Порядочная свинюшка всегда грязь найдет
    Порядочный джипер всегда найдет где застрять
    (с) Jikanana - порядочная свинюшка-джипер

  16. #14
    Регистрация
    17-05-2008
    Возраст
    46
    Сообщения
    70
    Благодарность
    19
    Поблагодарили 43 раз в 20 сообщениях
    При N=12, нумерация вагонов начинается с 0.
    2^4=(3+1)*2^2=12+2^2 - попадаем в 4й вагон
    2^5=(3+1)*2^3=12*2+2^3 - 8й вагон
    2^6=(3+1)*2^4=12*2^2+2^4=12*2^2+12+2^2=12(2^2+1)+2 ^2 - 4й вагон
    2^7=(3+1)*2^5=12*2^3+2^5=12*2^3+12*2+2^3=12(2^3+2) +2^3 - 8й вагон
    и т.д., согласно принципу индукции, шагая по степеням двойки, мы всегда будем попадать либо в 4й либо в 8й вагон. И чего нам это даст? Или я не так вас поняла?

  17. по пути выключаем лампы в каждом вагоне, соответственно на шаге N все лампы будут выключены (и в 0 вагоне тоже) -> значит мы пошли по кругу -> возвращаемся назад в 0 вагон, включаем лампу -> идём на 2^(N-1) вагонов вперёд и дальше последовательно до горящей лампочки -> бинго!
    Порядочная свинюшка всегда грязь найдет
    Порядочный джипер всегда найдет где застрять
    (с) Jikanana - порядочная свинюшка-джипер

  18. #16
    Регистрация
    17-05-2008
    Возраст
    46
    Сообщения
    70
    Благодарность
    19
    Поблагодарили 43 раз в 20 сообщениях
    По-вашему на каком шаге надо возвращаться в 0 вагон?

  19. на каждом
    Порядочная свинюшка всегда грязь найдет
    Порядочный джипер всегда найдет где застрять
    (с) Jikanana - порядочная свинюшка-джипер

  20. #18
    Регистрация
    17-05-2008
    Возраст
    46
    Сообщения
    70
    Благодарность
    19
    Поблагодарили 43 раз в 20 сообщениях
    Ок. N=12. На четвертом шаге выключили все лампочки до 8 вагона, кроме нулевой. На пятом мы проходим нулевой вагон, но мы этого не знаем, т.к. не знаем, что N=12. Гасим лампочку в нулевом вагоне и, по вашему алгоритму, далее до 4го вагона (по нашему линейному счету 16-го) - и возвращаемся на 16 вагонов назад. Света нет - вывод - количество вагонов 16? Или 15? Или сколько от 8 до 16?

  21. На 5 шаге мы гасим лампу в 0 вагоне (не зная что он 0) -> возвращаемся назад на 16 шагов в 0 вагон -> видим что лампа погашена -> включаем её -> идем на 2^4=8 шагов и еще 4 шага до включённой лампы -> 0 вагон найден -> кол-во вагонов равно 8 + 4 == 12
    Порядочная свинюшка всегда грязь найдет
    Порядочный джипер всегда найдет где застрять
    (с) Jikanana - порядочная свинюшка-джипер

  22. #20
    Регистрация
    17-05-2008
    Возраст
    46
    Сообщения
    70
    Благодарность
    19
    Поблагодарили 43 раз в 20 сообщениях
    поняла, спасибо

Страница 1 из 2 1 2 ПоследняяПоследняя

Информация о теме

Users Browsing this Thread

Пользователей, читающих тему - 1. (зарегистрированных - 0, гостей - 1)

Пользователей, прочитавших эту тему : 1

Ваши права в разделе

  • Вы не можете создавать новые темы
  • Вы не можете отвечать на сообщения
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •