На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Страницы: (62) « Первая ... 2 3 [4] 5 6 ...  61 62  ( Перейти к последнему сообщению )  
> Интересные задачки
    Alexander N, правильно. тока есть два замечания:
    1. по существу: под спойлер прятать надо.
    2. придирка: есть решение короче, но оно не вполне логичное. до него можно было бы додуматься после моей подсказки.

    а подсказка такая: в условии написано, что каждое действие выполняется в один такт. т е паровоз либо едет(FORWARD/BACKWARD) один такт, либо проверяет условие один такт, и т п.

    таким образом, решение:
    Скрытый текст
    едем вперёд, проверяя наличие парашута. когда нашли- просто едем вперёд, ничего не проверяя.


    Добавлено
    а так да- нормальный паровоз, получив команду FORWARD, мог бы ехать всё время, пока не поступит команда STOP или BACKWARD. но конкретно эти тормознутные паровозы в команде STOP не нуждаются.

    Добавлено
    --

    --

    есть ещё такая программистская загадка.. точнее это- старая загадка, переделанная под программистскую))

    итак:

    Однажды админ Windows поспорил с админом Linux, чья система проработает дольше, не зависнув и не рухнув с BSOD или Kernel Panic. Оба приступили к соревнованию, запустив одновременно свои компьютеры.

    Однако, чтобы не спровоцировать крах системы, оба админа сидели, не шевелясь, и не запускали никаких программ, даже не прикасались к клавиатуре. Стало понятно, что соревнование может затянуться на долгие месяцы.

    Мимо проходила старый, мудрый бухгалтер. Увидев необычно тихих и неподвижных админов, она поинтересовалась, в чём дело. Узнав о споре, бухгалтер сделала предложила им выполнить какое-то простое действие. После выполнения оного админы весело защёлкали мышками и начали запускать на компьютерах всё что только можно.

    Что сказала бухгалтер админам?
      Скрытый текст
      Пересесть за компьютеры оппонентов? :D
        Serafim, именно так. ответ- верный.
        Скрытый текст
        т е - поменяться компьютерами. т е пересесть с места на место.
          ыЁ! :thanks:
            Цитата ya2500 @
            Что сказала бухгалтер админам?
            Вообще-то, эта загадка про всадников.

            Поспорили два всадника, чья лошадь придет к финишу позже. Ну и естественно никто так со старта и не уехал. Ну вот прохожий им и посоветовал (что-то), так что вскоре они галопом неслись к финишу.

            Ну с лошадьми просто. Цель поменялась с придти последним на придти первым.

            А с админами, при пересаживании соревнование немного меняет смысл. Поскольку превращается в состязание, кто быстрее уронит машину соперника. И, по-моему, админу линукса сделать это будет несколько проще, с большой вероятностью он о Виндовс знает больше, чем админ винды о линуксе.
              Цитата amk @
              Вообще-то, эта загадка про всадников.

              именно так:

              Цитата ya2500 @
              есть ещё такая программистская загадка.. точнее это- старая загадка, переделанная под программистскую))

              итак:

              Однажды админ Windows поспорил с админом Linux,


              Цитата amk @
              превращается в состязание, кто быстрее уронит машину соперника.

              ну, да))
                эту задачку я читал когда-то давным-давно:

                перед генералом, плечом к плечу, стоят по стойке смирно конечное количество новобранцев.

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

                доказать, что рано или поздно верчение прекратится.

                имеется простое доказательство.

                я его подзабыл, и мне было интересно построить его заново:
                Скрытый текст

                обозначим всех новобранцев, смотрящих на запад нулём, а всех смотрящих на восток- единицей.

                получится что-то вроде этого:
                01100..10110
                запад - восток

                тогда на следующем ходу произойдёт то, и только то, что все пары 10 превратятся в 01.

                если рассмотреть весь строй солдат, как одно большое число, то ясно, что на каждом ходу может произойти одно из двух:
                1. будет совершён хотя бы один поворот и число уменьшится.
                2. не будет совершено ни одного поворота и повороты прекратятся окончательно.

                ну и поскольку наше число всегда целое и всегда >=0 и имеет конечное количество цифр, то ясно, что оно может уменьшаться только в течении конечного числа шагов.

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

                  Добавлено
                  Кстати, прочитал тему.
                  Цитата ya2500 @
                  а вот ЗАДАЧКА именно для программистов: нужно написать прогу(а лучше- алгоритм).

                  Это же проблема остановки :D
                    Цитата OpenGL @
                    Можно проще - новобранцы с краев шеренги, повенувшись к ней спиной, больше вертеться не будут, а значит их можно "выкинуть" из шеренги. Собственно, все

                    если на этом попытаться построить строгое доказательство, то не факт, что оно будет хотя бы таким же простым или коротким.

                    вот, как доказать, что крайние повернутся спиной к шеренге через конечный промежуток времени и т д? особенно с учётом того, что могут ведь и вообще не повернуться: один из вариантов остановки- вся шеренга смотрит в одну сторону. в этом случае с одного из краёв новобранец так ни разу и не повернулся.

                    а вот выложенный мной вариант действительно сводится к паре простых фраз, но я предпочёл расписать его детально, чтобы не осталось недосказанностей. и всё равно получилось очень кратко и понятно.

                    пара простых фраз:
                    Скрытый текст
                    обозначим всех новобранцев, смотрящих на запад нулём, а всех смотрящих на восток- единицей.
                    при каждом повороте полученное двоичное число будет убывать.


                    очень просто же.

                    Добавлено
                    Цитата OpenGL @
                    Это же проблема остановки

                    ну да- та задачка практически свелась к полному перебору. красивого решения не нашлось(((
                    Сообщение отредактировано: ya2500 -
                      Цитата ya2500 @
                      вот, как доказать, что крайние повернутся спиной к шеренге через конечный промежуток времени и т д

                      А зачем доказывать это? Если они никогда не повернутся, то значит их уже можно выкинуть. Если повернутся, то дождемся, когда повернутся спиной и тоже выкинем.
                      Цитата ya2500 @
                      пара простых фраз:

                      Да, тоже просто. Но зато мое доказательство на многомерный случай легко распространяется :) Как, например, в этой игре.
                        Цитата OpenGL @
                        Если они никогда не повернутся, то значит их уже можно выкинуть. Если повернутся, то дождемся, когда повернутся спиной и тоже выкинем.
                        мне кажется, что тут "доказательство" опирается на "аксиому", что верчение закончится за конечный промежуток времени. а если нет, и если крайние повернутся через бесконечный промежуток времени, то тогда их нельзя выкинуть, и- ?

                        Цитата OpenGL @
                        Но зато мое доказательство на многомерный случай легко распространяется :) Как, например, в этой игре.

                        это, конечно, супер-универсальное доказательство, но оно совсем не кажется мне доказательством.

                        т е из написанного не следует, что верчение закончится через конечное количество шагов. ведь бывают такие повороты, после которых мы не можем выкинуть ни одного солдата. что особенно хорошо видно в той игре)))
                        Сообщение отредактировано: ya2500 -
                          Цитата ya2500 @
                          а если нет, и если крайние повернутся через бесконечный промежуток времени

                          Что такое "повернутся через бесконечный промежуток времени?"
                          Цитата ya2500 @
                          но оно совсем не кажется мне доказательством.

                          Что не мешает ему быть верным :)
                            Цитата OpenGL @
                            Что такое "повернутся через бесконечный промежуток времени?"

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

                            Цитата OpenGL @
                            Что не мешает ему быть верным

                            верное утверждение и доказательство- это разные вещи.

                            Добавлено
                            Цитата ya2500 @
                            требовалось построить доказательство того, что верчение закончится за конечное время

                            т е за конечное количество итераций.
                            Сообщение отредактировано: ya2500 -
                              Цитата ya2500 @
                              в твоём доказательстве выше ты опираешься на предположение о том, что верчение закончится за конечное время как на доказанный факт или как на аксиому, и исходя из этого строишь "верное" доказательство того, что верчение закончится за конечное время. вот на эту-то некорректность в "доказательстве" я и указал в предыдущем своём сообщении.

                              А где ответ на мой вопрос? :D Верчение либо есть, либо его нет, это строго детерминированное событие и оно либо произойдет через конечный промежуток времени, либо не произойдет никогда. Все, третьего не дано. Впрочем, раз так не считаешь, то спрошу еще раз - что такое "повернется через бесконечный промежуток времени"?
                                Цитата OpenGL @
                                Верчение либо есть, либо его нет, это строго детерминированное событие и оно либо произойдет через конечный промежуток времени, либо не произойдет никогда. Все, третьего не дано. Впрочем, раз так не считаешь, то спрошу еще раз - что такое "повернется через бесконечный промежуток времени"?
                                "повернётся через бесконечный промежуток времени" в той моей фразе можно перевести как "не повернётся ни за какое конечно число итераций". И до тех пор, пока мы не докажем, что верчение закончится за конечное число итераций, мы не сможем утверждать, что солдат, который не повернётся ни за какое конечное число итераций, не повернётся никогда. ведь верчение всё ещё будет продолжаться. как-то так. впрочем, если это тебе кажется необоснованной придиркой, то я пробовал объяснить иначе:

                                Цитата ya2500 @
                                т е из написанного не следует, что верчение закончится через конечное количество шагов. ведь бывают такие повороты, после которых мы не можем выкинуть ни одного солдата. что особенно хорошо видно в той игре)))


                                т е если после каждого поворота мы гарантированно выкидывали бы из рассмотрения не менее одного солдата, а солдат конечное количество, то да- вопросов нет. НО бывают такие повороты, после которых каждый из оставшихся солдат имеет шанс повернуться, и не может быть выкинут из рассмотрения. и поэтому остаётся не ясным, действительно ли они все выйдут из рассмотрения за конечное количество итераций.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (62) « Первая ... 2 3 [4] 5 6 ...  61 62


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0471 ]   [ 16 queries used ]   [ Generated: 27.07.21, 15:16 GMT ]