Имя пользователя:
Пароль:  
Помощь | Регистрация | Забыли пароль?  | Правила  

Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Задачка...

Ответить
Настройки темы
Задачка...

Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать


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

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)


Отправлено: 22:10, 23-11-2001

 

Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать


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

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

Вот и всё

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)


Отправлено: 02:32, 28-11-2001 | #2



Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети.

Если же вы забыли свой пароль на форуме, то воспользуйтесь данной ссылкой для восстановления пароля.


Аватара для BigMac

Призрачный админ


Сообщения: 5254
Благодарности: 90

Профиль | Отправить PM | Цитировать


noname00.pas

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

-------
Истина где-то рядом...


Отправлено: 02:38, 28-11-2001 | #3


Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать


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

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)


Отправлено: 03:04, 28-11-2001 | #4


Аватара для BigMac

Призрачный админ


Сообщения: 5254
Благодарности: 90

Профиль | Отправить PM | Цитировать


noname00.pas

-------
Истина где-то рядом...


Отправлено: 03:17, 28-11-2001 | #5



Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Задачка...

Участник сейчас на форуме Участник сейчас на форуме Участник вне форума Участник вне форума Автор темы Автор темы Шапка темы Сообщение прикреплено

Похожие темы
Название темы Автор Информация о форуме Ответов Последнее сообщение
Задачка по GPO Lavrentiy Microsoft Windows NT/2000/2003 6 28-11-2008 17:55
MSFT SQL Server - Задачка ValVlaGen Программирование и базы данных 6 27-08-2008 02:15
Задачка по С++ kiri Программирование и базы данных 1 21-06-2006 02:57
Задачка VuDZ Программирование и базы данных 4 02-04-2003 17:44
Задачка noname00.pas Программирование и базы данных 6 07-12-2001 11:43




 
Переход