О коротких путях
Пролетала тут мимо задачка: https://avva.livejournal.com/3656270.html?style=mine
Дана игра: Алиса и Боб вместе бросают одну честную монету 100 раз. Каждый раз, когда выпадают подряд два орла (ОО), Алиса получает очко. Когда выпадает ОР, Боб получает очко. Побеждает (в игре) тот, у кого больше очков после 100 бросков.
Игра, кстати, не совсем тривиальная: хотя суммарно по всем играм Алиса и Боб получат строго поровну очков, но уже среди всех игр по 3 броска (а их 8), Алиса 1 раз победит с перевесом в 2 очка и 1 раз победит с перевесом в 1 очко (итого 2 победы в игре), а Боб 3 раза победит с перевесом в 1 очко (итого 3 победы в игре)
И было предложено соревнование: кто сможет быстрее перебрать все возможные игры из 100 бросков и точно подсчитать, в скольких из них побеждает Алиса, а в скольких - Боб.
Народ уже начал было расчехлять особо шустрые перебиралки (напоминаю: игр длины N будет 2N штук, зато у нас нынче процессоры мощные, и есть массивный параллелизЬм, а уж видеокарты такое вытворяют, так даже нынешние веб-сайты умудряются тормозить не слишком ужасно), как в комменты принесли чисто математическое решение: сколько игр длины N победит Алиса, а сколько победит Боб, с простoй рекуррентной формулой зависимости количества таких игр от N. Конечно, если совсем без ума делать, то можно и Числа Фиббоначчи за экспоненциальное время посчитать (я регулярно вижу ровно такое, под заголовками вида "Функциональное Программирование для чайников", и ничего аффтарам не жмёт), но в остальном соревноваться в скорости перебора сразу стало неинтересно, ибо это как раз тот случай, где математика предоставляет очень короткий путь. Однако, не все вычисления имеют таковой.
А ещё пролетала мимо статья на хабре про т.н. Обратную Польскую Нотацию: https://habr.com/ru/articles/811189/
Это такой удобный способ для вычисления самых обычных математических выражений, если нормальных синтаксических деревьев не завезли, а вычислять выражения надо - те самые, школьные, где умножение имеет приоритет над сложением, а ещё есть скобки, так что вычислять их тупо слева направо низзя, надо с приоритетами. Статью увидел, но чукча ж не читатель, чукча писатель: я помню, что давным-давно, ещё в XIX прошлом веке, на 2-ом курсе я это делал на голом Си, преобразуя входящий текст с арифметическим выражением в постфиксную запись, а потом вычисляя выражение уже по ней. И ведь тогда мне сразу очевидно было, как это сделать, только об доступные тогда инструменты пришлось помучаться. И вот не-читатель начал вспоминать, как это делается. Пол вечера промучился - не выходит каменный цветок. Но чукча всё равно не читатель, а писатель: статью раскуривать не стал, а вместо этого достал из ящика диск со старыми бэкапами, нашёл там тот самый код XIX прошлого века на жутком Си, долго фкуривал, что же он делает, а когда фкурил - написал то же самое, но уже с современными гораздо более удобными инструментами, минут за 15.
Однако ж, блин, годы борьбы с индусским кодом (ха-ха, если бы с индусским: у нас тут самые заводилы говнокода не индусы, и живут не в Индии) не проходят даром. Надо что-то с этим делать, а то так забуду, как пузырьком сортировать.
x-post: https://livelight.dreamwidth.org/595318.html
Дана игра: Алиса и Боб вместе бросают одну честную монету 100 раз. Каждый раз, когда выпадают подряд два орла (ОО), Алиса получает очко. Когда выпадает ОР, Боб получает очко. Побеждает (в игре) тот, у кого больше очков после 100 бросков.
Игра, кстати, не совсем тривиальная: хотя суммарно по всем играм Алиса и Боб получат строго поровну очков, но уже среди всех игр по 3 броска (а их 8), Алиса 1 раз победит с перевесом в 2 очка и 1 раз победит с перевесом в 1 очко (итого 2 победы в игре), а Боб 3 раза победит с перевесом в 1 очко (итого 3 победы в игре)
И было предложено соревнование: кто сможет быстрее перебрать все возможные игры из 100 бросков и точно подсчитать, в скольких из них побеждает Алиса, а в скольких - Боб.
Народ уже начал было расчехлять особо шустрые перебиралки (напоминаю: игр длины N будет 2N штук, зато у нас нынче процессоры мощные, и есть массивный параллелизЬм, а уж видеокарты такое вытворяют, так даже нынешние веб-сайты умудряются тормозить не слишком ужасно), как в комменты принесли чисто математическое решение: сколько игр длины N победит Алиса, а сколько победит Боб, с простoй рекуррентной формулой зависимости количества таких игр от N. Конечно, если совсем без ума делать, то можно и Числа Фиббоначчи за экспоненциальное время посчитать (я регулярно вижу ровно такое, под заголовками вида "Функциональное Программирование для чайников", и ничего аффтарам не жмёт), но в остальном соревноваться в скорости перебора сразу стало неинтересно, ибо это как раз тот случай, где математика предоставляет очень короткий путь. Однако, не все вычисления имеют таковой.
А ещё пролетала мимо статья на хабре про т.н. Обратную Польскую Нотацию: https://habr.com/ru/articles/811189/
Это такой удобный способ для вычисления самых обычных математических выражений, если нормальных синтаксических деревьев не завезли, а вычислять выражения надо - те самые, школьные, где умножение имеет приоритет над сложением, а ещё есть скобки, так что вычислять их тупо слева направо низзя, надо с приоритетами. Статью увидел, но чукча ж не читатель, чукча писатель: я помню, что давным-давно, ещё в XIX прошлом веке, на 2-ом курсе я это делал на голом Си, преобразуя входящий текст с арифметическим выражением в постфиксную запись, а потом вычисляя выражение уже по ней. И ведь тогда мне сразу очевидно было, как это сделать, только об доступные тогда инструменты пришлось помучаться. И вот не-читатель начал вспоминать, как это делается. Пол вечера промучился - не выходит каменный цветок. Но чукча всё равно не читатель, а писатель: статью раскуривать не стал, а вместо этого достал из ящика диск со старыми бэкапами, нашёл там тот самый код XIX прошлого века на жутком Си, долго фкуривал, что же он делает, а когда фкурил - написал то же самое, но уже с современными гораздо более удобными инструментами, минут за 15.
Однако ж, блин, годы борьбы с индусским кодом (ха-ха, если бы с индусским: у нас тут самые заводилы говнокода не индусы, и живут не в Индии) не проходят даром. Надо что-то с этим делать, а то так забуду, как пузырьком сортировать.
x-post: https://livelight.dreamwidth.org/595318.html