0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
|
|
1 | |
Вывести количество идеальных вариантов28.12.2010, 12:47. Показов 2386. Ответов 30
Метки нет (Все метки)
есть три множества одинаковой мощности-мужчины женщины и дома. (все по n)
между мужчинами и женщинами есть симпатии. и мужчинам:cofee2: и женщинам нравятся некоторые дома. сколько обоюдносимпатизирующих пар можно заселить в нравящийся им дом? т.е. надо вывести кол-во идеальных вариантов.. социально важная задача, кстати!
0
|
28.12.2010, 12:47 | |
Ответы с готовыми решениями:
30
Найти количество идеальных чисел в заданном диапазоне Количество возможных вариантов и ребус Выведите количество идеальных свитеров Вывести количество безопасных вариантов формирования стопки из N контейнеров |
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
30.12.2010, 07:03 | 21 |
а легче, ли?
или расчитать и наложить битную маску, или просто взять следующий элемент списка. взять элемент обычно быстрее. кроме того, основные потери времени и памяти при большом n будут на сохранение в стек/восстановление из него(ведь расчет должен быть рекурсивным) а не на вычисление симпатий . для сохранения текущего состояния при использовании матриц, нужно запихнуть в стек всю матрицу. а в случае списков - лишь "список изменений".
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
30.12.2010, 09:24 | 22 |
зачем всю матрицу в стек? В ответе №17 я по-моему довольно ясно написал что оптимальней запихивать в стек.
А вот при Вашем алгоритме в стек запихивается что-то очень много всего: - все женщины, в составе каждой женщины массив всех мужчин; - все мужчины, в составе каждого мужчины массив всех женщин; По объему это две матрицы смежности.
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
30.12.2010, 09:59 | 23 |
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
30.12.2010, 10:06 | 24 |
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
30.12.2010, 10:14 | 25 |
Кстати, можно и так слепить софтину, что и у домов будут симпатии. Так вот, есть ли в вашей задаче у домов симпатии?
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
30.12.2010, 10:18 | 26 |
taras atavin, а можно добавить еще и симпатии женщин к женщинам, мужчин к мужчинам. Получается точно как написал easybudda настоящий Дом-2
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
30.12.2010, 10:27 | 27 |
Нет, я больший бред имел ввиду.
0
|
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
30.12.2010, 13:02 | 28 |
а затем, что иначе нельзя восстановить исходный вариант.
и все промежуточные. потому, что каждая найденная пара с домом - есть точка ветвления алгоритма. не "две матрицы смежности", а все, какие есть вот это "все женщины, в составе каждой женщины массив всех мужчин;" я не понял. с каких это пор массив мужчины включен в состав женщины? О_о
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
30.12.2010, 14:47 | 29 |
Или я плохо читать умею:
0
|
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
30.12.2010, 15:56 | 30 |
вам виднее.
но "массив из двоичных элементов" и "массив мужчин" - не совсем одно и то-же, вам не кажется?
0
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
30.12.2010, 18:05 | 31 | |||||
0
|
30.12.2010, 18:05 | |
30.12.2010, 18:05 | |
Помогаю со студенческими работами здесь
31
Вывести количество всех возможных вариантов вывода числа в виде "ступеньки" Количество вариантов Количество вариантов бус Найти количество конечных вариантов Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |