Мегамозг на краю обрыва, Возьму на себя смелость предложить задачу, кажется, подходящую для раз |
Добро пожаловать, гость ( Вход | Регистрация )
Публикующим:
1. Задачу можно опубликовать двумя способами:
- создав для нее отдельную тему с информативным названием;
- добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
2. Правильность решения можно проверить, написав личное сообщение автору.
Мегамозг на краю обрыва, Возьму на себя смелость предложить задачу, кажется, подходящую для раз |
L0st |
16.4.2017, 23:14
Сообщение
#1
|
Новичок Группа: Пользователи Braingames Сообщений: 7 Регистрация: 7.11.2009 Пользователь №: 17 549 |
Нашел эту задачку на одном из англоязычных каналов ютуба (пардон, если баян).
В общем, оккупанты опять издеваются над Мегамозгом. На этот раз его поставили на краю обрыва: два шага назад - он упадет, два шага вперед - будет съеден голодными туземцами. Оккупанты сохранят Мегамозгу жизнь, если он составит алгоритм из определенного количества команд вперед/назад, последовательно выполнив которые он бы не упал и не был съеден. К тому же, подлые оккупанты могут заставит выполнять команды не последовательно, а, к примеру, каждую 2ую, либо каждую 3ью, либо каждую 4ую и т.д. Каково максимальное количество команд в наборе, с помощью которого Мегамозгу гарантированно выживание? ЗЫ Кажется, более логично спросить "каково минимальное количество команд, выполнение которого наверняка бы погубило Мегамозга?", но это противоречит духу сайта |
Owen |
19.4.2017, 14:41
Сообщение
#2
|
Kорифей Группа: Администраторы Braingames Сообщений: 2 817 Регистрация: 6.3.2013 Пользователь №: 43 989 |
Каждую 2ю, 3ю и т.д. - начиная с первой?
Т.е. возможны наборы команд "1, 2, 3, 4, ...", "1, 3, 5, ...", "1, 4, 7, ..."? Или как-то иначе? |
L0st |
21.4.2017, 6:30
Сообщение
#3
|
Новичок Группа: Пользователи Braingames Сообщений: 7 Регистрация: 7.11.2009 Пользователь №: 17 549 |
|
fiviol |
21.4.2017, 7:20
Сообщение
#4
|
Участник Группа: Пользователи Braingames Сообщений: 131 Регистрация: 28.3.2009 Из: г. Трехгорный, Челяб. обл. Пользователь №: 13 681 |
11 получается.
|
L0st |
21.4.2017, 20:43
Сообщение
#5
|
Новичок Группа: Пользователи Braingames Сообщений: 7 Регистрация: 7.11.2009 Пользователь №: 17 549 |
|
fiviol |
25.4.2017, 9:16
Сообщение
#6
|
Участник Группа: Пользователи Braingames Сообщений: 131 Регистрация: 28.3.2009 Из: г. Трехгорный, Челяб. обл. Пользователь №: 13 681 |
А ответ для трех шагов известен? Уже больше 120 команд проскочил, конца пока не видно.
|
L0st |
25.4.2017, 10:19
Сообщение
#7
|
Новичок Группа: Пользователи Braingames Сообщений: 7 Регистрация: 7.11.2009 Пользователь №: 17 549 |
|
fiviol |
25.4.2017, 14:41
Сообщение
#8
|
Участник Группа: Пользователи Braingames Сообщений: 131 Регистрация: 28.3.2009 Из: г. Трехгорный, Челяб. обл. Пользователь №: 13 681 |
Нет, случай 4 шагов и уж тем более обобщенная задача - это заведомо грех на душу по отношению к работе.
Для трех шагов уперся в 164 команды. |
Nikita146 |
7.5.2017, 16:14
Сообщение
#9
|
Kорифей Группа: Администраторы Braingames Сообщений: 1 501 Регистрация: 21.9.2015 Пользователь №: 54 896 |
В общем виде это гипотеза Эрдёша о расходимости, и, согласно этой статье (третий абзац), для радиуса в 2 шага известен пример на 1124 команды, но неизвестно, есть ли более длинные такие последовательности.
|
VitalyKolobkov |
12.5.2017, 22:01
Сообщение
#10
|
Участник Группа: Пользователи Braingames Сообщений: 244 Регистрация: 18.2.2011 Пользователь №: 23 171 |
Драма "Erdős discrepancy problem".
На форуме. L0st: Нашел эту задачку на одном из англоязычных... Я: Хмм, интересно, надо попробовать решить. Через неделю. Я: Эх, что-то я забыл, там же какая-то вроде забавная задачка была. Что там еще раз? Открывается форум. fiviol: 11 получается. L0st: Верно. Для трех шагов вперед/назад предлагать не буду - не хочу грех на душу брать Я: Да, на самом деле, получается 11. Все довольно просто, дерево небольшое. Надо бы сделать для трех шагов. Через 10 минут, исписав целую страницу. Я: Не, на бумаге слишком долго получается. Проще запрогать. Что-то лень с++ проект создавать, сделаю ка я прямо на джава скрипте, в браузере запущу. Внутренний голос (ВГ): Ой, неужели! Там же надо будет хитрую структуру в памяти строить, возможно оптимизировать придется. В плюсах ты через указатели все раскидаешь, если что, а в джава скрипте справишься? Я: Да, это хороший аргумент, ладно, так и быть, создам проект в плюсах. После нескольких часов кодинга и отладок всех мелочей. Я: Ага, вроде все работает, на двух шагах 11 получается, на деструктор пока наплевать, там памяти кот наплакал, запускаем для трех шагов. ВГ: Ну-ну Я: Пошло дело! Пойду домой. На следующий день. Я: Что? Кончилась память? Никогда такой ошибки не видел. Что значит, кончилась память. ВГ: Лол, лошара Я: Подожди, эта штука реально съела 12 гигов оперативы что ли?! ВГ: А ты перед тем, как запускать хоть прикинул, как эта штука растет, сколько памяти надо, сколько операций на каждый шаг потребуется? Я: Ок, щас все будет. Запускается код с ограничение по количеству шагов, строится зависимость количества элементов в дереве от глубины, фиттится с очень хорошей точностью на exp(0.5*n). Я: Эмммм... ВГ: Ну, что дальше? Я: Нда, экспоненту так просто не победишь. Ладно, придется переписать половину кода и сделать дерево, которое само себя удаляет на ходу, но запоминает самую длинную ветку. ВГ: Го фор ит! После нескольких часов кодинга и отладок. Я: Ок, вроде работает. Смотри в таск менеджере: память не растет. ВГ: Молодец! Посиди минут 20, посмотри, как эта музыка работает. Я: Ок. ВГ: Ну чё? Я: Что-то оно заглохло как-то подозрительно на длине 258 шагов. ВГ: Подожди еще. Я: О! Новая длина 269, уже 272. ВГ: На ночь оставь, может досчитает. На следующий день. Я: А ну ка! Чта? Всего 318? Что за фигня? А комп точно ночью пахал, а не спал? ВГ: А сколько операций на каждый шаг тратится? Я: Порядка exp(0.5n)*n^2, там проверка лобовая, то есть n/3 сумм считается каждый раз. ВГ: Может n^2 можно как-то улучшить? Я: Я об этом еще в самом начале думал, но... сложная какая-то задача уже становится. Я ее третий раз переписываю. ВГ: А кто-то на джава скрипте вообще хотел в браузере запускать... Я: Заткнись! Через несколько часов кодинга. Я: Все, теперь это, грубо говоря, exp(0.5n)*log(n). Ну, от экспоненты я никак не уйду. Мне же придется пройтись по всем веткам дерева. ВГ: Запускай на ночь. Утром: Комп: Привет, тут ночью питание отключали, добро пожаловать, введи логин, пароль, все дела Я: #%$%@#$@#$^%&^*$@ ВГ: Лол, лошара Может быть надо в файл делать вывод, а? Я: Ок... ВГ: Еще кое-что: запусти стразу на два ядра, пусть одно с +1+1 начнет, а второе с +1-1. Я: Это хорошая мысль. Запускаю. Примерно через сутки. Я: Посмотрим, что там. Вы серьезно? Глубина 389 при количестве элементов 2861030146 при заходе от +1+1 и глубина 379 при количестве элементов 1079400871 при заходе +1-1. Нда, такими темпами он будет еще долго считать. Если там искомая глубина 500, например, то я и за месяц до нее не доберусь. Тут придется на 1000 процессоров раскидывать. Ладно, проверим форум, может там кто-нибудь уже решил. На форуме. Nikita146: В общем виде это гипотеза Эрдёша о расходимости, и, согласно этой статье (третий абзац), для радиуса в 2 шага известен пример на 1124 команды, но неизвестно, есть ли более длинные такие последовательности. Я: 1124! Ничесе! А что скажет Википедия? А она говорит, что длина 1161 (https://arxiv.org/pdf/1402.2184.pdf). 1161, Карл! ВГ: Все, приплыли на барже... Я: Обидно, да? ВГ: Обидно. Иди лучше работой займись. Я: И то верно. Ушел -------------------------------------------------- Мораль: если что-то делаете, то делайте сразу хорошо и правильно, а не кое-как на коленке... или не делайте вообще. Сообщение было отредактировано VitalyKolobkov: 12.5.2017, 22:08 |
Nikita146 |
13.5.2017, 0:49
Сообщение
#11
|
Kорифей Группа: Администраторы Braingames Сообщений: 1 501 Регистрация: 21.9.2015 Пользователь №: 54 896 |
Да уж, темп роста функции впечатляет
|
Упрощённая версия | Сейчас: 20.4.2024, 6:08 |