Старый тест для начинающих программистов :-)
Последний мой пост вызвал вполне предсказуемую реакцию. 🙂 Точнее, целый набор легко предсказуемых реакций. Из которых я хотел бы затронуть лишь одну.
Типичным мнением старшеклассников и первокурсников является следующее: дело математиков формулы выводить, а мы, крутые программёры, будем их прогать. Математики всё равно в программёрстве не шарят нифига, полвека уже застряли на своём допотопном фортране, ну да ведь и нам их математика нужна лишь ровно настолько, чтоб эти формулы понимать.
Я думаю, не очень ошибусь, если предположу, что почти каждый современный школьник, написав первую в своей жизни программу, и решив учиться на программёра, хоть раз в жизни, да подумал нечто подобное. 😉 Другое дело, что у большинства хватает ума не ляпать такое вслух, а из них значительная часть в процессе учёбы быстро понимает, что к чему. 🙂
Заблуждение это настолько старо, глупо и дремуче, что уже давно перестало вызывать улыбку, и тем более — желание с ним спорить. Но я в этой связи вспомнил один тест, который некогда предлагали студентам младших курсов — будущим программистам.
Вот он весь: необходимо написать программу для нахождения так называемого числа сочетаний (оно же — биномиальный коэффициент) по следующей формуле:
Не нужно даже компьютера, вполне достаточно написать на бумаге. И не стоит тратить время на проверку условий относительно n,m — будем считать, что входные данные задаются всегда корректно. На всякий случай напоминаю, что 0!=1.
Желающие могут попробовать, а я обещаю через пару дней разобрать этот тест. 🙂
Только не надо исходники и алгоритмы в комментарии. 😉
Сибирский белк. Интересное вокруг 
Странно, у меня таких мыслей не возникает… Не знаю насчет всех, но очень многие преподаватели на нашем факультете запросто могут что-нибудь эдакое и запрограммировать 🙂 Плюс, один хороший знакомый, работающий в одной из крупнейших компаний мира, сказал: "Учи математику. А кодить и обезьяну можно научить" 🙂
Так то преподаватели, и человек с карьерой. 🙂 А речь-то о неофитах агрессивного толка. 🙂 Над задачкой подумать всё же рекомендую, интересная вещь… 😉
Ну если формулу в другом виде переписать, то легче жить становится 🙂 Хотя возможно, что там что-то более изящное применить можно
Ну если не бросать исходники и алгоритмы, то тогда можно использовать треугольник Паскаля. Другое на ум пока не приходит, как быстро это сделать (вариант с рекурсией в лоб не считается :))
Ну у меня тоже была такая идея. Только я не понял как мне это сильно может помочь… Глупый я 🙂
Ну даf(i,j) = f(i-1,j-1)*i/j(ответ к задаче — f(n,m); начальные условия — f(i,0)=1 для всех i)
Владимир: очень хорошо (без всякой иронии). Но есть два обстоятельства. Первое — в те времена, когда этот тест придумали, абсолютному большинству практических программистов рекурсия ещё не была доступна. Да она и сейчас вполне может отсутствовать в том или ином конкретном языке. Так что это не есть «истинно самурайское» решение. ;)Второе — в этой рекуррентной зависимости наличествует один тонкий момент… Математически на бумаге всё абсолютно верно, а вот в реализации при неаккуратности может привести к непредсказуемым последствиям, доводящим при отладке до белого каления. Это как раз немаловажная часть теста, в разборе упомяну.
Ну так можно нерекурсивно писать, просто сделать массив f, и по строчке его считать. Более того, можно хранить только последнюю и предпоследнюю строчки, потому что никуда раньше функция f не обращается. Более-менее стандартная задача на динамическое программирование 🙂
Хотя, наверное, есть способ быстрее. По крайней мере Mathematica 7 посчитала f(10^6,10^5) примерно за пять секунд. Если действовать, как я предложил, нужно выполнить по крайней мере 10^11 операций (без учёта умножения длинных чисел), а в секунду ориентировачно выполняется 10^8. А если ещё и учесть, что умножение выполняется не за O(1), а как минимум за O(n)…
некропост, но все же…
если расписать формулу то получим: n! / [m! * (n — m)!] = [(m + 1) * (m + 2) *…*n] / [1 * 2 *…* (n — m)] … итерационное решение… а, ну и тривиальные решения: если m равно 0 или n то единичка