Задачка...

[noname00.pas]

Как найти количество циклов в полном графе (то есть из любой вершину в любую другую существует ребро)? Циклы не направленные. т.е. цикл 1-2-3-4 и 4-3-2-1 это одно и то же.

[noname00.pas]

All

Ну вот.. Как вы меня огорчили. Такая простая задачка, и ни одного поста... А решение такое...

Давайте попробуем определить, сколько существует таких циклов длины X. Во-первых сколько подмножеств длины X мы можем составить из N вершин? Это есть ни что иное, как количество сочетаний. Так вот это количество сочетаний умножим на (X-1)! (количество перестановок из X-1, так как в условии сказано, что ни один цикл не должен быть получен из ругого сдвигом, будем считать, что первая позиция в перестановки занята например наименьшим числом) и поделим на 2 (учтём таким образом то, что ни один цикл не должен быть получен из другого переворотом)



А теперь осталовь только просуммировать все эти суммы для X от 2 до N



Вот и всё

[BigMac]

noname00.pas



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

[noname00.pas]

BigMac

О да... На это пожалуй много времени ушло бы -

[BigMac]

noname00.pas