Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті
Решая котрольную для студентки программистки наткнулся на настоящий хит:
«Из колоды берут n карт пронумерованных 1,..., n. Сколькими способами можно можно разложить их
в рядок так, чтобы ни одна карта с номером i не занимала
Я попоплню счет любому (на 30) кто решит эту задачу в формульном виде в течение суток.
Слово патриота. И объявлю победителя разумеется. Можно считать это конкурсом.
+1 и все таки она вертиться en.wikipedia.org/.../Gamma_function
Лично для меня 0! = бесконечность, потому что Г (0) = бесконечность, вот такая религия; -)
Все таки, 0! =Г (1) =1.
2Киянуш
Тогда следует и Вам поднять ЗП... в 1, 2*i раз
боюсь что в той стране где получает ЗП ваш собеседник:) так не принято
Тогда следует и Вам поднять ЗП... в 1, 2*i раз
Лично для меня 0! = бесконечность, потому что Г (0) = бесконечность, вот такая религия; -)
2crypto5! 0 = 1поэтому все сходиться:)
Ну за то что вспомнили что 0! =1 (! 0=1) уже надо ЗП на 20% поднимать.
2crypto5
типа сейлс мен решаеться за O (e^n) и т.д., и никакой комбинаторики не нужно было
для задач аки TSP Есть куча эвристик, которые позволяют свести перебор к меньшему числу вариантов или отсеят не нужные пути рекурсии, и там кстати полезно применять комбинаторику что бы сделать Min-Max эстимейты эвристик
дальше просто уже точности дабла показать как целое число не хватило
написал программу и кстати проверил с вашей формулой для ряда числе дабы не смущать и не косячить:)
}
2crypto5 — неужели вы хотя бы в голове ни разу не прикидывали сложность алгоритма? или решения? там же сплошная комбинаторика
Все алгоритмы которые мне попадались, всегда раскладывались на простейшие кирпичи вроде сортировки сравнения O (nlogn) и т.д., ну и известные проблемы из алгоритмики — типа сейлс мен решаеться за O (e^n) и т.д., и никакой комбинаторики не нужно было.
То что ты описываешь как круги называеться en.wikipedia.org/...usion_principle и как раз и применяеться Сергеем и википедией. Но что ты дальше делаешь, откуда ты берешь все эти (n-i)! я к примеру понять не могу. Если хочешь попробуй выведи общую формулу, и мы ее проверим для случая к примеру n=6.
это как например если есть 3 круга которые пересекаються то прощать которая у них «не общая» можно расчитать через отнять от каждого из них пересечения, а потом добавить пересечение 3х подряд и потом отнять 4х итд... жаль рисовать нельзя:), а то бы схемку нарисовал, там все сразу проще становиться и с пониманием формулы тоже
2crypto5 — неужели вы хотя бы в голове ни разу не прикидывали сложность алгоритма? или решения? там же сплошная комбинаторика
Это как раз к вопросу о том используют ли программисты в работе матемактику. Я могу точно сказать что за всю свою программистскую карьеру, комбинаторику никогда не использовал; -)
Вообще я не знаю есть ли в твоем подходе рациональное зерно, потому что твое обьяснение не сильно понятно, но он (подход) вообще то отличаеться от того как это доказываеться например в википедии, а в википедии оно доказываеться так же как доказал Сергей.
ааа се сорри, увидел знак в теореме... что-то сегодня уже внимательности нету...
Но программисты?! Математикой ведь в повседневной жизни занимаетесь, че так мало постов?!
2Sergey Leonenko — Просто из теоремы не ясно, покажите пожалуйста как знак меняеться, хотя учитывая что я получил теже перестановки в развернутом виде мне это понятно, но мне интересно как вы это выведете через теорему
C (4) = N! — (N-1)! — (N-1)! + (N-2)! — (N-1)! + (N-2)! + (N-2)! — (N-3)! — (N-1)! + (N-2)! + (N-2)! + (N-2)! — (N-3)! — (N-3)! — (N-3)! + (N-4)! = 24 — 6 — 4 — 3 — 2 = 9
C (3) = N! — (N-1)! — (N-1)! + (N-2)! — (N-1)! + (N-2)! + (N-2)! — (N-3)! = 6 — 2 — 2 + 1 — 2 + 1 + 1 — 1 = 2 и это правда как мы уже знаем, теперь вопрос с 4ками
вместо «Ответ: n!/2! — n!/3! + n!/4! — n!/5! +... + (-1) {в степени n+1} n!/n! » читать Ответ: «n!/2! — n!/3! + n!/4! — n!/5! +... + (-1) {в степени n} n!/n»!
Думаю дальше ясно как получилась формула которая в ответе.
C (4) = 4! — 3! — (3! — 2!) — (3! — 2! — 1!) — (3! — 2! — 1! — 0!) = 24 — 6 — (6 — 2) — (6 — 2 — 1) — (6 — 2 — 1 — 0) = 24 — 6 — 4 — 3 — 3 = 8 Я правильно продолжил мысль?
C (3) = N! — (N-1)! — ((N-1)! — (N-2)!) — ((N-1)! — (N-2)! — (N-3)!) = 6 — 2 — (2 — 1) — (2 — 1 — 0) = 2
C = Count — количество
способами можно можно разложить ихв рядок так, чтобы ни одна карта с номером i не занимала
i-е место"
то есть имеем C = N! — N! / N = N! — (N-1)! ...C = N! — (N-1)! — ((N-1)! — (N-2)!)
А что конкретно ты обозначаешь буквой С в данном случае?
N! — 1 = 5
ПыПыСы: только сейчас заметил тему, до этого распознаванием занимался:) и на 30 грн я не претендую
Кстати, отличный пример того как математический подход может положить на лопатки брут форс, пусть даже у Россомахи был бы кластер от гугла. Чем то напомнило недавнюю историю вычисления числа пи, когда французский математик-программист обошел на своей персоналке в два раза самый крупный в японии кластер.
Ну что же, похоже приз от Киянуша уходит тебе; -) Поздравляю!
Та да, а человек даже не представился...
Это известная задача о беспорядках про которую можно почитать тут
Ну что же, похоже приз от Киянуша уходит тебе; -) Поздравляю!
О! и эта задача хорошо квантуется, значит можно использовать параллельное программирование, MPI вам в помощь.Или на GRID структуре реализовать:)
Ну вот если у тебя будет кластер из 10 компов, то у тебя перебор навернеться при н не 15, а 16, поможет?...
Это известная задача о беспорядках про которую можно почитать тут
тогда просто перебор, может с какими-то доп. граничными условиями.
Перебор по вышислительной сложности = рекурсия. Ну, а если еть мысли про правильные граничные условия, то было бы интересно послушать.
Или на GRID структуре реализовать:)
если программно решать эту задача, то это просто.Как поиск счастливого билета, просто перебором или с использованием рекурсии. Зачем подключать сюда комбинаторику?
Наверное потому что наивная рекурсия навернется уже при н = 15 из за экспоненциальной сложности.
Как поиск счастливого билета, просто перебором или с использованием рекурсии. Зачем подключать сюда комбинаторику?
В императивных языках решением будет рекурсия, как сказал eugene_n, а в функциональных языках решение, по сути, будет в формульном виде.так ведь студентам-програмистам предлагают решать ее с использованием ЭВМ, а не в формульном виде
P.S. Действительно, страшно жить.
В конкретной математике много теории о решениях рекуррентных задач.
счас попробую вспомнить)
так ведь студентам-програмистам предлагают решать ее с использованием ЭВМ, а не в формульном виде
(n-1)! — так как если 4 карты — получается 6 варинтов, а их 6*3
:) так це ж нескладно... певно комусь треба чийсь номер телефону
2Guest: для 3 карт по Вашей формуле получается всего 2 варианта, а их 5...
crypto5
anonymous
Александр Колосов
Сашко
Oleg Babii
Владимир Dzoba
Batter
53 коментарі
Додати коментар Підписатись на коментаріВідписатись від коментарів