Головоломная задача

Решая котрольную для студентки программистки наткнулся на настоящий хит:

«Из колоды берут n карт пронумерованных 1,..., n. Сколькими способами можно можно разложить их

в рядок так, чтобы ни одна карта с номером i не занимала i-е место»

Я попоплню счет любому (на 30) кто решит эту задачу в формульном виде в течение суток.

Слово патриота. И объявлю победителя разумеется. Можно считать это конкурсом.

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Лично для меня 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 эстимейты эвристик

1 0 0
2 1 1
3 2 2
4 9 9
5 44 44
6 265 265
7 1854 1854
8 14833 14833
9 133496 133496
10 1334961 1334961
11 14684570 14684570
12 176214841 176214841
13 2290792932 2290792932
14 32071101049 32071101049
15 481066515734 481066515734
16 7697064251745 7697064251745
17 130850092279664 130850092279664

дальше просто уже точности дабла показать как целое число не хватило

Формула после всех упрощений
C (N) = Sum by i [1, n] (i — 1) x (N-2)! — Sum by j [2, i −1] (-1) ^j Combination (j, i-1) x (N — 1 — j)!

написал программу и кстати проверил с вашей формулой для ряда числе дабы не смущать и не косячить:)

я как раз те круги и имел ввиду:)
мой алгоритм вот:
static double MyEstimate (int n)
{
double result = 0;
for (int i = 1; i < = n; i++)
{
result += (i — 1) * Factorial (n — 2);
for (int j = 2; j < = i — 1; j++)
result -= Math.Pow (-1, j) * Combination (j, i — 1) * Factorial (n — 1 — j);
}
return result;

}

2crypto5 — неужели вы хотя бы в голове ни разу не прикидывали сложность алгоритма? или решения? там же сплошная комбинаторика

Все алгоритмы которые мне попадались, всегда раскладывались на простейшие кирпичи вроде сортировки сравнения O (nlogn) и т.д., ну и известные проблемы из алгоритмики — типа сейлс мен решаеться за O (e^n) и т.д., и никакой комбинаторики не нужно было.

То что ты описываешь как круги называеться en.wikipedia.org/...usion_principle и как раз и применяеться Сергеем и википедией. Но что ты дальше делаешь, откуда ты берешь все эти (n-i)! я к примеру понять не могу. Если хочешь попробуй выведи общую формулу, и мы ее проверим для случая к примеру n=6.

2crypto5! 0 = 1
поэтому все сходиться:) ну я просто теорему дискреты не вспомнил давно это было, а идея как раз таже если ты не заметил через исключения дополнения множеств считаеться не пересекаемая площадь

это как например если есть 3 круга которые пересекаються то прощать которая у них «не общая» можно расчитать через отнять от каждого из них пересечения, а потом добавить пересечение 3х подряд и потом отнять 4х итд... жаль рисовать нельзя:), а то бы схемку нарисовал, там все сразу проще становиться и с пониманием формулы тоже

2crypto5 — неужели вы хотя бы в голове ни разу не прикидывали сложность алгоритма? или решения? там же сплошная комбинаторика

Сашко

Это как раз к вопросу о том используют ли программисты в работе матемактику. Я могу точно сказать что за всю свою программистскую карьеру, комбинаторику никогда не использовал; -)

Шо та ты опять накосячил:
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 — 6 + 2 — 6 + 2 + 2 — 1 — 6 + 2 + 2 + 2 — 1 — 1 — 1 + 0 = 8

Вообще я не знаю есть ли в твоем подходе рациональное зерно, потому что твое обьяснение не сильно понятно, но он (подход) вообще то отличаеться от того как это доказываеться например в википедии, а в википедии оно доказываеться так же как доказал Сергей.

ааа се сорри, увидел знак в теореме... что-то сегодня уже внимательности нету...

Ну-ну...
Есть у меня подозрение, что в математическом виде эта задачка тянет на максимум областную олимпиаду среди десятиклассников...
Решать ее не берусь, т.к. забыл давно уже эти факториалы и пр.

Но программисты?! Математикой ведь в повседневной жизни занимаетесь, че так мало постов?!

2Sergey Leonenko — Просто из теоремы не ясно, покажите пожалуйста как знак меняеться, хотя учитывая что я получил теже перестановки в развернутом виде мне это понятно, но мне интересно как вы это выведете через теорему

C (4) = N! — (N-1)! — (N-1)! + (N-2)! — (N-1)! + (N-2)! + (N-2)! — (N-3)! снова забраем всех [email protected] — (N-1)! возвращаем с пересечениями @1, @2, @3 + (N-2)! x3 забираем ситуации когда у нас @2 и @3 пересеклись с @1 (@1, @2; @1, @3; @2, @3) — (N-3)! — (N-3)! — (N-3)! и снова возвращаем общее пересечение со всеми (N+4)!

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

не совсем, но это я накосячил, приношу свои извинения, там что-то типа биномиального ряда, идея таже, только вид сложнее итак начнем сначала
всего у нас есть N!
C (1) = N! — (N — 1)! тут все понятно наверное 1! — 0! = 0
С (2) = N! — (N — 1)! забираем всех первых на первых ([email protected]), далее забираем всех 2х на 2х ([email protected]) — (N — 1)!, но нужно еще вернуть тех кто попал на пересечение между [email protected] и [email protected], а это + (N-2)! итого
C (2) = N! — (N — 1)! — (N — 1)! + (N — 2)! = 2! — 1! — 1! + 0! = 1 и это правда (case 2, 1)
теперь С (3) действуем по индукции C (3) = N! — (N-1)! — (N-1)! + (N-2)! и теперь нужно грохнуть [email protected] это у нас снова (N-1) всего + (N — 2)! которые мы грохнули вовремя [email protected] и еще + (N-2)! когда мы гронули @2, но где же справедливость спросите вы и будете правы, мы 2жды вернули 3ки которые попали под пересечение [email protected] & [email protected] и мы их снова отнимем — (N-3)! итого имеем:

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»!

Мысль, наверно, правильно, но резульатат, то выходит не верный (верный = 9, проверьте руками если не верите)
Это стандартная задача дискретной математики.
Ответ: n!/2! — n!/3! + n!/4! — n!/5! +... + (-1) {в степени n+1} n!/n!
Как думать: Ответ будет равен количеству всех расстановок (т.е. n!) минус количество расстановок, когда хотя бы одна карта на своем месте.
Теорема:
Пусть A1, A2,..., Аn — конечные множества. Тогда|A1 U A2 U... U An| =|A1| +|A2| +... +|An| - — (|A1 ∩ A2| +|A2 ∩ A3| +... +|An−1 ∩ An|) +
(|A1 ∩ A2 ∩ A3| +... +|An−2 ∩ An−1 ∩ An|) +... + (−1) n−1|A1 ∩ A2 ∩... ∩ An|.
Отсюда
Аі — i-ая карта точно на своем месте, кол-во вариантов = (С из n по 1) * (n-1)! = n!
Ai ∩ Aj — i-ая и j-ая карты точно на своем месте, кол-во вариантов = (С из n по 2) * (n-2)! = n!/2!
и т.д.|A1 U A2 U... U An| — количество вариантов, когда хотя бы одна карта на своем месте

Думаю дальше ясно как получилась формула которая в ответе.

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 Я правильно продолжил мысль?

Например для N = 3

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)!)

А что конкретно ты обозначаешь буквой С в данном случае?

2Олег Бабий:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
подходят только 2:
2 3 1
3 1 2
N = 3

N! — 1 = 5

ну если это мат задачка, то скорее всего попросили вывести формулу, а не написать ответ:)
выводиться это просто:
всего вариантов у нас N!
далее начинаем методично уничтожать тех кто на своей позиции для первого числа это будут все кто начинаються с 1, а именно N! / N
то есть имеем C = N! — N! / N = N! — (N-1)!
далее убиваем всех кто на позиции 2, а это практически теже что и на 1й (N-1)! только минус тех кого мы убили в первом цикле (N-1)! / (N-1) = (N-2)! итого имеем хвост
C = N! — (N-1)! — ((N-1)! — (N-2)!) далее рекурсивно можно продолжить ряд до всех позиций ака (N-1)! — (N-2)! -... (N-i)! если раскрыть скобки и сделать преобразования то будет та формула,
ПыСы: возможно Женя имел ввиду эту рекурсию, тогда врядли она загнеться на 15 шаге, если у нас только стек не в 2 килобайта:)

ПыПыСы: только сейчас заметил тему, до этого распознаванием занимался:) и на 30 грн я не претендую

Кстати, отличный пример того как математический подход может положить на лопатки брут форс, пусть даже у Россомахи был бы кластер от гугла. Чем то напомнило недавнюю историю вычисления числа пи, когда французский математик-программист обошел на своей персоналке в два раза самый крупный в японии кластер.

Ну что же, похоже приз от Киянуша уходит тебе; -) Поздравляю!

Та да, а человек даже не представился...

Это известная задача о беспорядках про которую можно почитать тут

Ну что же, похоже приз от Киянуша уходит тебе; -) Поздравляю!


О! и эта задача хорошо квантуется, значит можно использовать параллельное программирование, MPI вам в помощь.

Или на GRID структуре реализовать:)

Ну вот если у тебя будет кластер из 10 компов, то у тебя перебор навернеться при н не 15, а 16, поможет?...

Это известная задача о беспорядках про которую можно почитать тут

тогда просто перебор, может с какими-то доп. граничными условиями.

Перебор по вышислительной сложности = рекурсия. Ну, а если еть мысли про правильные граничные условия, то было бы интересно послушать.

тогда просто перебор, может с какими-то доп. граничными условиями.
О! и эта задача хорошо квантуется, значит можно использовать параллельное программирование, MPI вам в помощь.

Или на GRID структуре реализовать:)


если программно решать эту задача, то это просто.

Как поиск счастливого билета, просто перебором или с использованием рекурсии. Зачем подключать сюда комбинаторику?

Наверное потому что наивная рекурсия навернется уже при н = 15 из за экспоненциальной сложности.

если программно решать эту задача, то это просто.

Как поиск счастливого билета, просто перебором или с использованием рекурсии. Зачем подключать сюда комбинаторику?

так ведь студентам-програмистам предлагают решать ее с использованием ЭВМ, а не в формульном виде

В императивных языках решением будет рекурсия, как сказал eugene_n, а в функциональных языках решение, по сути, будет в формульном виде.

P.S. Действительно, страшно жить.

В конкретной математике много теории о решениях рекуррентных задач.

:) це не теор. ім., а комбінаторика

эээ, если мне не изменяет память, то это теория вероятности.

счас попробую вспомнить)

Это же Рекурсия... Как страшно жить: (

так ведь студентам-програмистам предлагают решать ее с использованием ЭВМ, а не в формульном виде

(n-1)! * (n-1)

(n-1)! — так как если 4 карты — получается 6 варинтов, а их 6*3

:) так це ж нескладно... певно комусь треба чийсь номер телефону

2Guest: для 3 карт по Вашей формуле получается всего 2 варианта, а их 5...

Підписатись на коментарі