0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
|
|
1 | |
Вывести количество идеальных вариантов28.12.2010, 12:47. Показов 2383. Ответов 30
Метки нет (Все метки)
есть три множества одинаковой мощности-мужчины женщины и дома. (все по n)
между мужчинами и женщинами есть симпатии. и мужчинам:cofee2: и женщинам нравятся некоторые дома. сколько обоюдносимпатизирующих пар можно заселить в нравящийся им дом? т.е. надо вывести кол-во идеальных вариантов.. социально важная задача, кстати!
0
|
28.12.2010, 12:47 | |
Ответы с готовыми решениями:
30
Найти количество идеальных чисел в заданном диапазоне Количество возможных вариантов и ребус Выведите количество идеальных свитеров Вывести количество безопасных вариантов формирования стопки из N контейнеров |
242 / 120 / 14
Регистрация: 15.10.2010
Сообщений: 395
|
|
28.12.2010, 13:27 | 2 |
это С++?
0
|
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
28.12.2010, 13:35 | 3 |
это SQL.
но можно извратиться, и реализовать циклы на C/C++
0
|
0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
|
|
28.12.2010, 15:14 [ТС] | 4 |
помогите пожалуйста..
на С вроде должно быть. это с графами как-то связано Добавлено через 13 минут подскажите хотя-бы как это делать..принцип решения.. а то совсем не догоняю.
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
28.12.2010, 15:27 | 5 |
Изначально задача кажется немного странной.
Это все условие:? - мощности-мужчины женщины и дома как нибудь связаны с симпатиями: между мужчинами и женщинами и понравившимися домами? - как задаются входные данные вообще? Насчет социально важной задачи Вас обманули кстати, все решается не так (а через знакомства, взятки и т.п.)
0
|
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
28.12.2010, 15:33 | 6 |
ну, раз совсем непонятно - делай простейший вариант.
тупо перебирай всех женщин, для каждой перебирай все ее симпатии к мужчинам, далее проверяй совпадают ли симпатии, и если совпадают - перебирай возможные домики для пары(которые обоим нравятся). после нахождения пары с домиком, выбрасываешь их из процесса поиска, и... ищешь то-же самое среди оставшихся. и так до тех пор, пока не кончаться все женщины с их симпатиями. побеждает вариант, в котором число найденных домиков с парами - максимально. по сути - типичная шахматная задача.
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
28.12.2010, 15:43 | 7 |
Это называется "жадный алгоритм", но пока неизвестно по какому принципу формируются входные данные этот алгоритм применять преждевременно.
0
|
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
28.12.2010, 15:51 | 8 |
по-моему, как раз это понятно.
принцип формирования исходных данных четко описан: другое дело, что эти данные можно представить в разных форматах. но формат исходных данных на алгоритм практически не влияет. а еще есть вопрос, как могут заселяться дома: обязательно по одной паре на дом, или можно по нескльку?
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
28.12.2010, 16:13 | 9 |
А по-моему не совсем все-таки понятно. Например если мощности и симпатии согласуются по принципу: если мощность мужчины, женщины или дома расходятся не более чем на 5 единиц, то все друг другу нравятся. А если более, то не нравятся. То тогда жадный алгоритм не применим, для достижения максимального результата.
Лучше все-таки дождаться ответа хозяйки вопроса.
0
|
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
28.12.2010, 16:26 | 10 |
смысл фразы ускользает. что в данном контексте "мощность мужчины"? Мощность множества
0
|
0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
|
|
28.12.2010, 16:35 [ТС] | 11 |
эм. ну. вообще это произвольная задача-задание графов делать как удобнее и как быстрее.
да,задача на перебор. одна пара один дом. делать можно практически все что захочется главное-решить задачу и использованием графов, ибо задача по теории графов. я сейчас голову себе отвинчу. мне понравился простейший вариант.как его реализовывать? простите что не сразу отвечаю-сижу получаю зачет по физике
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
28.12.2010, 16:40 | 12 |
Да нет, не отличается. Наоборот совпадает.
Хорошо вот еще простой пример: Мужчине №1 нравится женщина №1 и им обоим нравятся дома номер №1 и №2. Мужчине №2 нравится женщина №2 и им обоим нравится дом номер №1. Если следовать жадному алгоритму (который Вы привели), то можно заселить одну пару в один дом. А на самом деле можно заселить 2 пары. Поэтому все-таки предлагаю:
0
|
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
28.12.2010, 16:43 | 13 |
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
28.12.2010, 16:45 | 14 |
А как же:
0
|
0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
|
|
28.12.2010, 16:57 [ТС] | 15 |
эм.меня кто-нибудь слыыышит?
одна пара-один дом- и выкинуть из процесса. ибо коммуналки разводить негоже.капитализм все-таки.
0
|
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
28.12.2010, 17:11 | 16 |
сильно зависит от того, на какие ресурсы расчитывать(в плане вычислительной мощность и объема памяти компьютера).
если особых ограничений нет, то, опять-же, простейший вариант: а)создать структуры: 1)женщина: массив из n двоичных элементов(отражающий ее симпатии), по одному на каждого мужчину значение 1 - есть симпатия, 0 - нет симпатии еще одна переменная целого типа - номер пары, в которой состоит женщина. соответственно, 0 - не состоит. 2)мужчина - то-же самое, что и у женщины 3)дом одна переменная - номер заселенной пары. 0 - пары нет. б)создать массивы мужчин, женщин и домов. запихнуть все это в одну структуру. добавляем туда-же счетчик заселенных домов сделать и заполнить "рабочий" экземпляр этой главной структуры(из файла, или случайными данными - это вы сами решайте). сделать "оптимальный" экземпляр главной структуры - туда будут сохраняться наилучшие найденные варианты. далее... перебираем женщин, их симпатии( выраженные массивом двоичных элементов), для каждой проверяем незанятых мужчин, и свободные дома. если находим пару с домом : 1) увеличиваем счетчик найденных домов, сравниваем с "оптимальным" вариантом. если новый вариант лучше - копируем его в оптимальный. 2)сохраняем текущее состояние("рабочую структуру") в стек. когда все женщины/мужчины/дома заканчиваются - восстанавливаем из стека предыдущий вариант, и считаем дальше так, будто его не было. таким образом, будут рассмотрены ВСЕ возможные комбинации женщин/мужчин/домов собственно, все. по окончанию работы в "оптимальной" структуру будет наилучшее возможное сочетание. но стек, при большом n может понадобиться очень приличного размера.
1
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
29.12.2010, 23:36 | 17 |
Patch, что-то я в Вашем алгоритме не увидел:
Насчет: наверное все-таки "оптимальный" (по крайней мере, по выделяемой памяти) это когда двумерный массив размером n*3 (можно и через структуры) и в котором каждая строка примерно такая: 5 6 3 - что означает 5-ый мужчина обоюдносимпатизирует 6-ой женщине и им обоим нравится 3-ий дом.
0
|
2343 / 499 / 22
Регистрация: 01.04.2009
Сообщений: 2,200
|
|
30.12.2010, 00:53 | 18 |
это исходное условие. его нужно отдельно описывать?
нет, "оптимальный" в данном случае - наилучший с точки зрения поставленной задачи. а если говорить об оптимальности с точки зрения памяти/исполнения, то лучше списками делать не только симпатии, но и вообще всю структуру. и работать будет существенно быстрее. кроме того, можно сделать алгоритм взвешивания группы решений, кэширование найденных пар-домов и т.д. и т.п. теории баз данных и параллельных вычислений позволяют много чего сделать. я-же писал "простейший вариант". или, скажем так, наиболее понятный человеку неподготовленному.
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
30.12.2010, 01:17 | 19 |
а я почему-то считаю что с помощью графов (матрицы смежности) намного быстрее и легче узнать обоюдносимпатизирующих женщин и мужчин например.
0
|
easybudda
|
30.12.2010, 01:50
Вывести количество идеальных вариантов
#20
|
0
|
30.12.2010, 01:50 | |
Вывести количество всех возможных вариантов вывода числа в виде "ступеньки" Количество вариантов Количество вариантов бус Найти количество конечных вариантов Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |