Эники Беники ели вареники
Эники Бэники клёц!
Вышел зеленый матрос.
Знакомо? 🙂
Пока я крапаю длинную статью на тему как научиться НЕ делать все самому, решил набросать коротенькую статейку/задачку. Задачка аналогично такой, которая дается на олимпиадах по программированию.
Слегка формализированные правила считалочки.
1) Пусть у нас есть N человек
2) И у нас есть считалка длинной в M слов.
3) Начинаем считать с первого человека, по одному слову на человека.
4) Человек на котором считалка закончилась выбывает.
5) Считалка продолжает считаться с следующего после выбывшего, повторяя пункт 4 и 5.
6) Оставшийся последним человек — выигрывает.
Задача:
Написать программу, которая считает порядковый номер человека который выигрывает. Входные данные N и M.
5 баллов — программа может рассчитать выигрывающего при N и M < 20.
10 баллов — программа может рассчитать при N < 20, а M порядка 1 триллиона (не фига себе считалочка), за разумное время.
25 баллов — программа может рассчитать при N порядка 1 миллиарда, M < 20, за разумное время.
50 баллов — программа может рассчитать при N и M порядка триллиона.
Если вы знаете/придумали решение на 50 баллов, прошу сразу его не бросать в комментарии, а просто написать что вы его знаете (чтобы дать остальным подумать).
Остальные решения вполне welcome в комментариях 😉
Увы, приза по рукой нет, да и как я его доставлю в произвольную точку земли тоже непонятно. Но, всем решившим большое уважение и почет.
P.S. Как оказалось, задача классическая (просто я с ней не сталкивался). На момент написания статьи, я знал решение на 5 и 10 баллов, примерно имел идею на 25 баллов и не знал, как решить на 50 баллов.
Я думаю порядка триллиона это не так уж и нереально, при современных компьютерах. В принципе это известная древняя загадка, даже в википедии есть статья:
From Victor Ronin: ссылка на статью временно удалена 🙂
Нетрудно видеть, что от M сложность алгоритма не зависит, а вот от N можно сделать линейный алгоритм по вычислениям и памяти. Т.е. на любом компьютере просто так не посчитаешь, но в принципе несколько гигабайт памяти это не так уж и нереально.
Совсем к ночи тормозить стал. Памяти много не надо, так как зависимость только от последнего элемента. Ну а прогнать цикл до триллиона с десятком-другим вычислений внутри — вообще не проблема сегодня. Как известно, правильный суперкомпьютер выполняет бесконечный цикл за пару секунд.
P.S. Извиняюсь, если кому-то испортил повод поломать голову
Кстати, я на самом деле не знал, что задача настолько классическая 😉
Отличная статья в википедии, но пока я ее убрал из вашего комментария, чтобы если кто-то захочет — то сначала повозился сам.
Кстати, я всегда утверждал, что олимпиады по программированию и информатике, на самом деле олимпиады для математиков с навыками программирования.
В принципе верно, любой программист прежде всего — математик. Не знающий математику программист — это уже эникейщик 🙂
Абсолютно не согласен.
Расскажите, мне для чего нужна математика (выше 5 класса в следующих задачах)
а) Создать website для компании торгующей мягкими игрушками
б) Написать драйвера для шифрования (использующие уже стандартный и готовый алгоритм).
в) Разработать архитектуру большого и толстого ERP приложения
и т.п.
Порядка 95% (если не больше) программистских задач не требует каких-то либо серьезных знаний математики.
Лично столкнулся:
1. Как минимум БПФ в задачах DSP
2. Как минимум пространственный преобразования в 3D графике (даже с готовым неплохим engin’ом)
3. Ну и всяких «симплекс методов» пучок.
Мне кажется что у каждого рано или поздно начинается период когда математические задачки так и прут. Обычно он дляится не очень долго, но случается у многих.
Оттолкнуть от последней фразы.
>Обычно он дляится не очень долго, но случается у многих.
Условно говоря он случается раз в 7 лет, у 30% людей и длиться скажем пол года. Итого мы имеем, что от общего количества задач — это составляет аж 2%.
Как по мне, проще (и с точки зрения компании и с точки зрения программиста) выносить эти задачи внаружу. Итого, все что индустрии нужно -это скажем несколько процентов программистов у которых серьезная математическая база.
И никак не то, что это нужно знать 100% программистов.
Тогда окажется что:
а) При разработке сейчас сайтов кода нужно кот наплакал. У нас компании вообще без программистов сайты делать могут. Завидно да?
б) При разработке такого «шифрования» оно будет сломано. А если не будет сломано, то его уже кто-то так использовал.
в) ERP? Откроем http://ru.wikipedia.org/wiki/EAM почитаем, найдем книжку по разработке САПРов и будем там искать что? Правильно. Методы оптимизации, но вот проблема, там куча теории и формул и нет готового решения.
Да конечно можно найти применение программистам незнающим математику.
Он будет заниматься тестированием и иногда писать не требующие мозгов куски кода (компания с экономит, так как знающий математику будет стоить дороже). И так года 2-3 (где-то так меняются технологии). Потом
его уволят за ненадобностьюон уйдет, так как перспектив роста у него не будет. Только вот все, что он знал давно выйдет из моды. Научится. И опять 2-3 года работает (ура! Есть постоянный приток программистов, знающих последнии технологии).Так что я полностью согласен. 100% программистам знать математику не нужно. Это выгодно и программистам знающим математику, и работодателю.
PS: заметка в тему «О тупых программистах«.
а) У вас вероятнее всего небольшой и простой сайт.
б) Берем файл, шифруем блочным алгоритмом, сохраняем файл.
Ключ к алгоритму — хэш от введено пароля. Алгоритм AES128. Вся математика написана до меня. Вперед — можете взламывать.
в) Как я и говорил, да 5% нужна.
а) У меня сайт из белой страницы. У вас сайт из кучи страниц, но я сомневаюсь, что для его создания потребовалось написать кучу кода. Сайтам компаний тоже состоят из «стандартных» элементов.
…
Хотя согласен, что сайты аля web2.0 или веб-игры требуют много кода.
б) Я же написал… Шифрующие фс уже есть.
Ждем момента расшифровки и снимает дамп. Взломано.
Если не верите то именно так расшифровывался файл с БД из истории ниже.
И так сумбурная история о написании и взломе тестов.
Сделаем тест возьмем для шифрования вопросов и ответов для этого MD5 и какой-то блочный шифр (не помню точно). Задача не дать сдающему получить вопросы. Пароли высылать будем за 3 дня до начала теста. Все тестирование займет две недели.
Что случилось: данные зашифровать зашифровали, но пароли то у всех разные. Значит надо проверять пароль и использовать зашитый мастер-пароль одинаковый для всех.
Итог: через пару дней после прихода паролей вся база вынута (хорошо ответы правильные не помечали, зато перемешать их забыли и они всегда были первыми).
Да здравствует зачет по Х.
Через год:
Давайте сделаем мастер-пароли разными и будем хранить их в базе зашифрованными совместно с паролями сдающих. А заодно перемешаем правильные ответы.
Итог: все вопросы получены через сутки после прихода паролей.
Да здравствует зачет по Y (жаль что безопасность еще в прошлом году сами сдавали).
Еще через год:
Долой программу. Используем онлайн-тесты.
Отлично. И при чем тут математика:
а) Снять дамп после расшифровки.
Чисто системная задача.
б) Вопросы usability vs secruity
Тоже никакого отношения к математике
в) Online vs offline
Тоже никакого отношения к математике
Где во всей описанной истории нужны были знания
— преобразование фурье
— интегралов
да, что там… Где в это истории нужны были знания
— дробей
— уравнений
Прекрасно понимаю отсутствие понимания.
Если бы при разработке ПО присутствовало хоть какое-то знание (немного о криптографии и логики) то ничего подобного бы не получилось.
Абсолютно не понял откуда взялись пункты а), б), в). Но предполагаю это попытка найти математику там, где показано, что случится если о ней забыть.
PS: пока помню книжка по теме: «Алгоритмические трюки для программистов«.
>Условно говоря он случается раз в 7 лет, у 30% людей и длиться скажем пол года. Итого мы имеем, что от общего количества задач – это составляет аж 2%.
Вот, собственно, если уделять 2% своего времени «на математику» то будет уже неплохо. Бесспорно, есть компании со штатными тимами математиков и алгоритмизаторов. Но пусть 2-5% математика всё-же встречается и в «повседневной жизни». Вот пишет тим какй-то аудио плеер. И куда же без БПФ? А как гистограмму нарисовать? Про 3D можно и не говорить. Там как минимум помнит нужно про матрицы.
Собственно о чём я… Программисту не нужно быть профессором математики. Но найти решение какой-либо задачи и смочь его понять (суметь применить, адаптировать) ИМХО всё-же обязательно.
Оттолкнуть от последней фразы.
Собственно о чём я… Программисту не нужно быть профессором математики. Но найти решение какой-либо задачи и смочь его понять (суметь применить, адаптировать) ИМХО всё-же обязательно.
Предположим вам нужно написать какой-то хитрный plugin для … ну скажем Firefox. Вы этого никогда не делали. По вашим прикидкам это может занять скажем 4 месяца. Что вы делаете? Вы садитесь, читаете документацию (предположим книгу по firefox framework и плагинам на 300-400 страниц). Разобравшись, пишите сначала hello world plugin, потом каркас плагина, потом обвешиваете его полнофункциональностью.
Теперь вопрос. Обязаны ли вы знать заранее как писать plugin к firefox? По моему убеждению — нет. Вы вполне можете прочесть книгу и разобраться по ходу, а не учить напереде (до того, как еще понадобится). При этом 4 месяца разработки (при 10 летней карьере) составляют как раз 3%.
Собственно говоря, мы не знаем заранее понадобятся БПФ, матрицы, интегрирование или еще что-то (а может и ничего). Почему эту информацию нужно учить заранее? Почему нельзя прочесть ту же самую 300 страничную книгу по матрицам в тот момент когда они нужны?
Отвечу знаменитой цитатой Ломоносова «Математику уже затем учить надо, что она ум в порядок приводит». Лично для меня ценность программиста не знающего математику сомнительна.
Вы идеалист 🙂 А я заядный материалист.
Меня интересует конечный результат. И конечный результат в 95% случаев не зависит от знания математики.
Математика один из многих методов тренировки ума. Не единственный и не обязательно самый лучший.
Шахматы лучше, но абсолютно бесполезны. В них нужен системный подход, а не логический.
Не могли бы вы рассказать откуда именно взялось 95%?
Единственное, что я нашел про 95% это статью http://lurkmore.ru/95%25
95% взято чисто с потолка. Точнее я чуть выше выше приводил примерный расчет, что 2% времени уходит на математические задачи. Так что 5% программистов которые хорошо подкованны в математике достаточно чтобы покрыть эти нужды.
Виктор, а Вы сами знаете решение в варианте 50 баллов?
Потому что обычный цикл до триллиона «за разумное время»
не выполняется, а придумать сокращение решения в такой
универсальной постановке лично я не смог.
P.S. Задача действительно классическая и подробно
разобрана у Кнута, но для M=2.
Может я чего-то не понимаю, но лично я живу во время, когда процессоры гигагерцовых частот и, соответственно, MIPS порядка тысяч — совсем не редкость даже в обычных «домашних» компьютерах. Соответственно, как я отмечал выше, обычный цикл до триллиона с десятком-другим вычислений внутри – вообще не проблема сегодня. Время будет вполне разумным. При некотором (правда, видимо, не малом) везении можно даже вложиться в «олимпиадный» лимит.
Для примера: мой текущий компьютер отработал простенькую программу на С#
static void Main(string[] args)
{
DateTime start = DateTime.Now;
for (uint i = 1; i != 0; i++)
{
long x = i * i + i / 3 + Math.Abs(i);
if (x == 0) Console.WriteLine(«AA {0} — {1}», i, x);
}
DateTime end = DateTime.Now;
Console.WriteLine(«It took {0}», (end — start));
}
за 47 секунд. Т.е. увеличение сложности внутренней части алгоритма на порядок оставляет время всё ещё вполне разумным.
Не хочется разводить неуместную полемику, но
>> обычный цикл до триллиона с десятком-другим
>> вычислений внутри – вообще не проблема сегодня.
>> Время будет вполне разумным.
Вы бы хоть попробовали…
>> При некотором (правда, видимо, не малом) везении
>> можно даже вложиться в “олимпиадный” лимит.
Спасибо, улыбнули. 🙂
>> Для примера: мой текущий компьютер отработал
>> простенькую программу на С# за 47 секунд.
Многовато… Тем не менее, где здесь триллион?
Я написал P.S.. В целом я не знал даже что задача классическая.
ОК, спасибо.
В таком случае, буду считать решение задачи за 50
баллов несуществующим, пока не доказано обратное. 🙂
P.S. ОФФТОП — при «сворачивании» комментариев они
съезжают т накладываются друг на друга… Баг WP.
Да, вероятнее всего нету. Я думал, что есть какое-то нерекурентное соотношение.
Похоже, что его таки нет.
Насчет P.S. А что за browser?
Насчет рекуррентного соотношения — оно, может,
и есть, но за «олимпиадное» время (<= 4 часов) его
не найти. Или сюда надо подключать мегамозги типа
Митричева, Станкевича и т.д. Если бы M было
фиксированным (особенно если << N), формулу
было бы намного проще найти.
Браузер — Maxthon на движке IE8, в FireFox
все отображается нормально.
Боюсь, что мегамозги не помогут 😉 Как я понимаю на данный момент общей нерекурентной формулы не существует.
P.S. За 25 баллов решается довольно просто.
Объясните мне, в чём разница между задачей за 25 и за 50? Для решения совсем в лоб, конечно, нужно два вложенных цикла, но, если немного подумать, несложно придумать алгоритм, сложность которого от M не зависит вообще.
Разница в основном во времени — а конкретнее, в 1000 раз.
Это если не учитывать накладные расходы на поддержку
int64 вместо uint, конечно. А от M время действительно не
зависит — правда, уже изначально. 😉
Касательно двух вложенных циклов — решение «в лоб»
(для варианта в 25 баллов) их как как раз не содержит,
там всего один цикл. Я допускаю, что можно разбить этот
длинный цикл (1е12) на два — например, 1е3 и 1е9 — но,
думаю, значительного выигрыша это не даст.
Когда Вы говорите:
«Я допускаю, что можно разбить этот длинный цикл (1е12) на два – например, 1е3 и 1е9 – но, думаю, значительного выигрыша это не даст.»
Вы имеете в виду задачу на 25 или 50 баллов? Если на 25, то откуда там 1e12. Вы же сами вроде согласны, что от M сложность не зависит. Или я что-то упустил?
Анонимному математику: разумное время это несколько секунд. На олимпиадах, чтобы уложиться в лимит, программа должна выполнять не более 100 миллионов операций (в принципе бывает, что проходит и миллиард каких-нибудь сдвигов или сложений, но это сильно зависит)
Линейный по N алгоритм даёт порядка триллиона операций, это минут 15. Ваша программа около 20 миллиардов операций целых 47 секунд делает.
Да, с олимпиадами я погорячился — сказывается недостаток опыта. А в остальном у нас просто разные критерии того, что такое «разумное время». В моём понимании для большой задачи является вполне нормальным, чтобы она считалась пару дней. Для очень больших даже месяцы могут быть приемлемы. По-моему, время является очевидно неприемлемым, если это какие-нибудь миллиарды лет или что-то в таком духе, вроде полного перебора ключа шифрования длиной во много-много бит.
Плохая особенность этой задачи в том, что я не вижу разумного пути распараллеливания вычислений.
Да, понятие «разумное время» я определил плохо. В целом анонимный программист прав. Разумное время — это секунду.
Чаще все на олимпиадах дают задачу у которой есть «плохое» решения O(N^2) и хорошее решение O(n) или O(nlogn). Поэтому фразу разумное время определять не надо. И тест дается с достаточно большим N, чтобы N^2 была уже очень большим, а N — вполне нормальным.
Тут какое-то противоречие в утверждениях:
— Разумное время порядка секунд
— O(n) или O(nlogn) — хорошее решение
— Проверяем на N порядка трилллиона
Что-то из этого нужно выкинуть/ослабить.
Для N порядка триллиона, O(N) вряд ли меньше, т.к. редко когда коэффициент при N меньше 1, обычно больше и значительно. Таким образом в оригинальных условиях требуется либо очень хороший линейный алгоритм, с коэффициентом типа 1/10000, либо алгоритм быстрее линейного, что тоже жестоко (ибо, судя по всему, простой общей формулы нету).
На олимпиадах дают гораздо меньше чем триллион. Обычно что-нибудь в виде сотен тысяч.
Насчет этой задачи (см P.S.) я не знал решения и думал, что есть решение O(1).
По поводу противоречия, забыл добавить, что тут зависимость всего лишь O(N) и не зависят от M, а ведь могло быть и O(N*M), что тоже можно трактовать как линейную сложность.
Мне одному кажется, что тупо вычисляя M по модулю N мы вычистим всех в более чем разумное время в одном цикле из N — 1 шагов?
Это решение работает на 5 и 10 баллов.
На 25 баллов уже придется повозится с тем как хранить миллиард флагов (вышел или не вышел еще), причем с достаточно быстрым доступом.
На 50 баллов не сработает, так как даже если мы организуем что-то размером триллион, то триллион шагов за разумное время фиг обработаешь.
Оооооу, Виктор, сорри, но похоже, и Вы
не знаете решение задачи за 25 баллов? 🙂
Лень проверять, но сильно сомневаюсь,
что обработка миллиарда флагов (пусть
даже с идеальным хранением) хоть как-то
уложится в разумное время. 😉 Особенно,
если учесть, что гораздо более эффективное
решение (из тех, что знаю я) решает для
миллиарда порядка 7 секунд.
Даю подсказку — для решения задачи за
25 баллов вообще не нужно хранить флаги.
Решение на 25 балов похоже таки знаю — АнонимныйМатематик ссылочку подсказал 😛
Это я комментарии по поводу того решения говорил. Я тоже не уверен, что можно не успеть вложиться в время тараня в лоб эту задачу.
Сейчас глупость сморожу.
words = words % (humans! + 1)
human = humans — words / (humans — 1) + 1
Округлять в большую сторону
Проверил совпадение только для случаев humans 2 (words до бесконечности) и 3 (words до 10).
Так что для остальных не знаю работает или нет.
Скорость вычисления полностью зависит от скорости вычисления факториала.
Идея первой формулы состоит в том, что длина считалки считалка повторяет может привести лишь к ограниченному порядку исключения элементов (а далее картинка повторяется и получается цикл).
Идея второй в том, что наблюдение показало, что результат смещается на 1 на каждые humans — 1 слов и счет начинается с конца.
Ну, увидев факториал можно дальше не рассматривать
решение, т.к. для варианта в 25 баллов уже неприменимо,
про скорость и пр. даже говорить не стоит.
А вот вторая догадка (про смещение) интересная, правда,
я ее не совсем понял. Что выдается таким способом для,
скажем, N=7, M=5?
Зато первая догадка правильная, а вторая нет. Если угодно то факториал (вернее НОК) легко убирается, главное читать… Если число людей больше числа слов, то факториал вообще вычислять не нужно. А если число слов меньше (люди * (люди — 1)) то тоже считать не нужно. И так далее.
На счет подсчетов картина там симметричная относительно НОК/2 получается что-то типа (люди + 1 — f(НОК — слова)) если слов больше НОК/2.
Правильнее то-то типа итерационой f(N, M) = (f(N-1, M) + M) % N (если 0 то N), а для 2 и 3 предыдущая формула (можно только для 2).
Эта вроде от 3 до 5 работает (но итерационная:(). дальше 5 не проверял (да и 5 в паре значений только).
Идею первой формулы вроде даже вкурил, но факторил вещь жестокая. Даже для human = 30, там будут уже выходить очень серьезные цифры. О human равных миллиардам уже и говорить нечего.
Вторую формулу таки не понял.
Вторая формула для человек 4 уже не работает.
А первой нужен не факториал (ошибочка), а Наименьшее Общее Кратное. Цикл с НОК начинается.
При миллиардах первая формула вообще не нужна (а вторая не работает, если только людей не 2 ил 3).
Как я понимаю, статья на тему «как научиться НЕ делать все самому» и есть эта статья?