Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
Sarmak
58 / 57 / 5
Регистрация: 01.12.2009
Сообщений: 177
1

Размещения с пожеланиями.

25.03.2011, 14:11. Просмотров 595. Ответов 4
Метки нет (Все метки)

Есть N гостей, для каждого известно с кем бы он хотел сидеть рядом или наоборот не хотел.
Необходимо посчитать количество вариантов размещения гостей за круглым столом.

если кто-то предложит алгоритм - буду благодарен.

Просто рассадка гостей за круглый стол:
n!/ (2*n)
n! - количество размещений.
делим на n - исключаем повторения при повороте по часовой стрелки n раз.
делим на 2 - исключаем симметрию.

пожелания гостей вводится в динамический массив в виде:
+2 -хочет сидеть со вторым.
-3 - не хочет сидеть с третьим.
то есть если N = 4 гостя, то массив будет выглядеть например так: a[0]: +2, a[1]: -3, a[2]: +1, a[3]: -2.

Собственно как-то посчитать количество размещений, удовлетворяющих массиву. (вводится с клавиатуры)
Подскажет кто?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.03.2011, 14:11
Ответы с готовыми решениями:

Генетический алгоритм размещения вершин графа
Привет всем.Тут решение одной задачи. Кто может объясните откуда из p1 -1 2 3 4...

Проверка возможности размещения товара в ячейке
Здравствуйте. Помогите придумать алгоритм. У меня есть ячейка заданных...

Алгоритм размещения коробок в ящике
<DIV id=post_message_149237>Подскажите кто знает где найти и почитать про...

Размещения
Народ, помогите с задачей! Условие на фотке. Заранее спасибо!

размещения
помогите с задачей ввожу слово например: ab прога должа вывести: a b ab...

4
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
25.03.2011, 19:01 2
Варианты, переходящие друг в друга при зеркальном отражении, считаются одинаковыми?
Из формулы общего количества вариантов "n!/ (2*n)" вроде как следует, что да, но мало ли.

Ограничения на N есть? Задача вообще олимпиаданая и нужен нормальный алгоритм, или просто показать преподу и лишь бы работало?
0
Sarmak
58 / 57 / 5
Регистрация: 01.12.2009
Сообщений: 177
25.03.2011, 22:40  [ТС] 3
делим на n - исключаем повторения при повороте по часовой стрелки n раз.
делим на 2 - исключаем симметрию.

писал же... исключение симметрии и есть ваше "зеркальное отражение"

желательно не тупой перебор.
из идей: хотеть с одним человеком могут не больше двух. если больше двух, то размещение невозможно.
если все НЕ хотят сидеть с одним человеком, то опять такое размещение невозможно.
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
25.03.2011, 23:07 4
Мда, я внимательно читаю...
0
Sarmak
58 / 57 / 5
Регистрация: 01.12.2009
Сообщений: 177
26.03.2011, 22:42  [ТС] 5
ну так поможет кто-то с размышлениями или нет? =)
0
26.03.2011, 22:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.03.2011, 22:42

Размещения
Пропустил первое занятие по комбинаторике и теперь приходится догонять. Дали...

размещения
размещение из n по k -это набор из k различных чисел, каждое из которых...

Размещения
Всем привет! Помогите написать программу которая выводит размещения из n по m.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru