четверг, 13 января 2011 г.

Задачка

Давайте я загадаю вам загадку, задачку?

Условия:
Поезд, число вагонов не бесконечно. Закольцован.
В каждом вагоне есть лампочка. горит или не горит. Из одного вагона состояние других вагонов не видно.
Находясь в вагоне можно включить или выключить лампочку.
Одновременно в двух вагонах находиться нельзя.
Требуется определить/найти алгоритм определения числа вагонов.

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

Те, у кого мозги стекают с кончиков пальцев пусть бегут к поисковикам, но мы то с вами не такие, мы будем пользоваться своей, а не виртуальной головой, не так ли, дорогие мои?

P.S. Мне ее давали на испытательном сроке, я не решил. то ли дурак, то ли времени не хватило.

P.P.S. Комментарии скринятся. Но неправильные ответы открою с превеликим удовольствием.

Альбом: randompics4lj


Удачи.

19 комментариев:

  1. включаю в своем вагоне свет В.
    иду в следующий вагон В+1.
    Выключаю свет. Возвращаюсь в свой В и смотрю горит / не горит. Не горит - мой
    горит - идем обратно в В+2.

    как то так )

    ОтветитьУдалить
  2. помоему была у тебя уже выложена такая задачка...

    Считаем вагон в котором мы находимся изначально начальным.
    Выключаем в нём свет.
    1) n=1
    2) Идем на n вагонов вперёд.
    3) Выключаем в нём свет.
    4) n=n+1
    5) Идём на n вагонов назад.
    - следим чтобы до (n-1)-го вагона свет везде был погашен. Если свет горит (до (n-1)-го вагона), переходим к пункту 9.
    6) Выключаем в нём свет.
    7) n=n+1
    8) переход к пункту 2.
    9) ответ: n-2

    вроде так...

    ОтветитьУдалить
  3. Расширяем сознание: в каждом вагоне лампочку нужно просто выкручивать ;)

    ОтветитьУдалить
  4. Не, вагоны еще советские, сделаны из ракетоупорного чугуния с противовандальной защитной арматурой на лампах. Вагон даже поцарапать не получится.

    ОтветитьУдалить
  5. а оставленная весчь в вагоне тоже исчезнет?

    ОтветитьУдалить
  6. Неудержима страсть к халяве!

    Задача - логическая, а вы - голый, с обритыми волосами, вырванными ногтями, и кровью, которая заменена на бесцветную, легкоиспаряющуюся жидкость без запаха

    :)

    ОтветитьУдалить
  7. 1) если считать, что во всех вагонах лампочки не горели, то зажечь и бежать по кругу до зажженного вагона.
    2) если считать, что во всех вагонах лампочки горят, то потушить и бежать по кругу до потушенного вагона.
    3) если же хз как лампочки горят, то немного сложнее, придется видимо туда-сюда бегать (т.е. сперва в одну сторону на один вагон, потом назад на один вагон в "первый", потом в другую на два, потом возвращаешься, потом на три вагона и т.д.). Когда в первом вагоне свет окажется выключен, значит по кругу проскакал все. По идее работает, т.к. гарантированно известно где тот самый "первый" вагон, если в темноте видно, где границы вагонов:)

    ОтветитьУдалить
  8. Ужас, гуманоиды в городе О_о

    Почему же вариант с выключением света не подходит? Идем все выключаем, потом в одном включаем и считаем от него пока не наткнемся на включенный. Для проверки, что прошли все можно обойти этот круг ада дважды.

    ОтветитьУдалить
  9. Любая последовательность включенных\выключенных ламп может повториться. И не раз.

    Не указано, как выяснить, что выключено все.

    ОтветитьУдалить
  10. забыл написать, что при ходьбе надо тушить свет, если он зажжен.

    ОтветитьУдалить
  11. лан, тогда возможно так: доходим до этой самой горящей лампочки выключаем ее проходим тоже самое кол-во вагонов убеждаемся, что света нет... для полной проверки еще раз включаем там свет опять идем на тоже кол-во вагонов убеждаемся что свет есть(так можно несколько раз)...так пойдет?

    Тут конечно уже по пути хождения по этим вагонам, можно довольно точно сказать rjk-dj, но если и так не все вагоны пройдены...то можно вспомнить теорию вероятности и тогда это анреальная задачка:)

    P.S. хотя чую, что есть либо сильно просто решение, либо мега%

    ОтветитьУдалить
  12. я не знаю ответа, целый час думала, не надумала ничего.. а гуглить не хочу, стыдно.
    можно подсказку еще какую-нибудь? :)

    ОтветитьУдалить
  13. Возможно, мне ее давали два года назад

    Ответ верный

    ОтветитьУдалить
  14. Если я правильно понял формулировку, то ответ верный. Ну или сравни с комментариями выше

    ОтветитьУдалить
  15. Третий вариант - правильный.

    ОтветитьУдалить
  16. блииин, я бы и не додумалась до правильного ответа :)
    пасиб за хорошую загадку!

    ОтветитьУдалить
  17. и автоматчики на вышках
    и вообще, ты не сам идешь, а тебя ведут

    ОтветитьУдалить