Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
leysanka
0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
1

Вывести количество идеальных вариантов

28.12.2010, 12:47. Просмотров 1536. Ответов 30
Метки нет (Все метки)

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

Найти количество идеальных чисел в заданном диапазоне
Находит количество идеальных чисел в заданном диапазоне. Идеальным называется...

Количество возможных вариантов и ребус
Прошу помощи 1)Перед фермером стоит задача: купить на 100 рублей 100 голов...

Просчитать количество вариантов представления числа в виде суммы натуральных цифр 1, 2 и 3
Дано натуральное число N. Необходимо просчитать количество вариантов...

Задача по нахождению идеальных чисел на заданном промежутке
почему в коде именно к/2 ??? (условие: задача по нахождению идеальных чисе в...

Отсортировать строки матрицы по сумме в них идеальных чисел
Задача: Отсортировать строки матрицы (по-убыванию), по сумме в них идеальных...

30
RUSya82
237 / 115 / 14
Регистрация: 15.10.2010
Сообщений: 395
28.12.2010, 13:27 2
это С++?
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
28.12.2010, 13:35 3
это SQL.
но можно извратиться, и реализовать циклы на C/C++
0
leysanka
0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
28.12.2010, 15:14  [ТС] 4
помогите пожалуйста..
на С вроде должно быть.
это с графами как-то связано

Добавлено через 13 минут
подскажите хотя-бы как это делать..принцип решения.. а то совсем не догоняю.
0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 15:27 5
Изначально задача кажется немного странной.
Это все условие:?
есть три множества одинаковой мощности-мужчины женщины и дома. (все по n)
между мужчинами и женщинами есть симпатии.
и мужчинам и женщинам нравятся некоторые дома.
сколько обоюдносимпатизирующих пар можно заселить в нравящийся им дом?
т.е. надо вывести кол-во идеальных вариантов..
социально важная задача, кстати!
Тогда вопросы:
- мощности-мужчины женщины и дома как нибудь связаны с симпатиями:
между мужчинами и женщинами и понравившимися домами?
- как задаются входные данные вообще?
Насчет социально важной задачи Вас обманули кстати, все решается не так (а через знакомства, взятки и т.п.)
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
28.12.2010, 15:33 6
ну, раз совсем непонятно - делай простейший вариант.
тупо перебирай всех женщин, для каждой перебирай все ее симпатии к мужчинам,
далее проверяй совпадают ли симпатии, и если совпадают - перебирай возможные домики для пары(которые обоим нравятся).
после нахождения пары с домиком, выбрасываешь их из процесса поиска, и... ищешь то-же самое среди оставшихся.
и так до тех пор, пока не кончаться все женщины с их симпатиями.
побеждает вариант, в котором число найденных домиков с парами - максимально.

по сути - типичная шахматная задача.
0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 15:43 7
Цитата Сообщение от Patch Посмотреть сообщение
делай простейший вариант
Это называется "жадный алгоритм", но пока неизвестно по какому принципу формируются входные данные этот алгоритм применять преждевременно.
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
28.12.2010, 15:51 8
Цитата Сообщение от valeriikozlov Посмотреть сообщение
но пока неизвестно по какому принципу формируются входные данные
по-моему, как раз это понятно.
принцип формирования исходных данных четко описан:
Цитата Сообщение от leysanka Посмотреть сообщение
есть три множества одинаковой мощности-мужчины женщины и дома. (все по n)
между мужчинами и женщинами есть симпатии.
и мужчинам и женщинам нравятся некоторые дома.
другое дело, что эти данные можно представить в разных форматах.
но формат исходных данных на алгоритм практически не влияет.

а еще есть вопрос, как могут заселяться дома: обязательно по одной паре на дом, или можно по нескльку?
0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 16:13 9
Цитата Сообщение от Patch Посмотреть сообщение
по-моему, как раз это понятно.
А по-моему не совсем все-таки понятно. Например если мощности и симпатии согласуются по принципу: если мощность мужчины, женщины или дома расходятся не более чем на 5 единиц, то все друг другу нравятся. А если более, то не нравятся. То тогда жадный алгоритм не применим, для достижения максимального результата.
Лучше все-таки дождаться ответа хозяйки вопроса.
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
28.12.2010, 16:26 10
Цитата Сообщение от valeriikozlov Посмотреть сообщение
если мощность мужчины, женщины или дома расходятся не более чем на 5 единиц

смысл фразы ускользает.
что в данном контексте "мощность мужчины"?
Мощность множества
Мощность множества или кардинальное число множества — это обобщение понятия количества (числа) элементов множества, которое имеет смысл для всех множеств, включая бесконечные.
ваша терминология отличается от общепринятой?
0
leysanka
0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
28.12.2010, 16:35  [ТС] 11
эм. ну. вообще это произвольная задача-задание графов делать как удобнее и как быстрее.
да,задача на перебор.
одна пара один дом.
делать можно практически все что захочется главное-решить задачу и использованием графов, ибо задача по теории графов.

я сейчас голову себе отвинчу.
мне понравился простейший вариант.как его реализовывать? простите что не сразу отвечаю-сижу получаю зачет по физике
0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 16:40 12
Цитата Сообщение от Patch Посмотреть сообщение
ваша терминология отличается от общепринятой?
Да нет, не отличается. Наоборот совпадает.
Хорошо вот еще простой пример:
Мужчине №1 нравится женщина №1 и им обоим нравятся дома номер №1 и №2.
Мужчине №2 нравится женщина №2 и им обоим нравится дом номер №1.
Если следовать жадному алгоритму (который Вы привели), то можно заселить одну пару в один дом.
А на самом деле можно заселить 2 пары.
Поэтому все-таки предлагаю:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Лучше все-таки дождаться ответа хозяйки вопроса.
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
28.12.2010, 16:43 13
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Если следовать жадному алгоритму (который Вы привели), то можно заселить одну пару в один дом.
нет.
если следовать моему алгоритму, то в перебор попадут ОБА варианта.
0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 16:45 14
А как же:
после нахождения пары с домиком, выбрасываешь их из процесса поиска
0
leysanka
0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
28.12.2010, 16:57  [ТС] 15
эм.меня кто-нибудь слыыышит?
одна пара-один дом- и выкинуть из процесса.
ибо коммуналки разводить негоже.капитализм все-таки.
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
28.12.2010, 17:11 16
Цитата Сообщение от leysanka Посмотреть сообщение
мне понравился простейший вариант.как его реализовывать?
сильно зависит от того, на какие ресурсы расчитывать(в плане вычислительной мощность и объема памяти компьютера).
если особых ограничений нет, то, опять-же, простейший вариант:

а)создать структуры:
1)женщина:
массив из n двоичных элементов(отражающий ее симпатии), по одному на каждого мужчину
значение 1 - есть симпатия, 0 - нет симпатии
еще одна переменная целого типа - номер пары, в которой состоит женщина. соответственно, 0 - не состоит.
2)мужчина
- то-же самое, что и у женщины
3)дом
одна переменная - номер заселенной пары. 0 - пары нет.

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

сделать и заполнить "рабочий" экземпляр этой главной структуры(из файла, или случайными данными - это вы сами решайте).
сделать "оптимальный" экземпляр главной структуры - туда будут сохраняться наилучшие найденные варианты.

далее...

перебираем женщин, их симпатии( выраженные массивом двоичных элементов), для каждой проверяем незанятых мужчин, и свободные дома.
если находим пару с домом :
1) увеличиваем счетчик найденных домов, сравниваем с "оптимальным" вариантом.
если новый вариант лучше - копируем его в оптимальный.
2)сохраняем текущее состояние("рабочую структуру") в стек.

когда все женщины/мужчины/дома заканчиваются - восстанавливаем из стека предыдущий вариант, и считаем дальше так, будто его не было.

таким образом, будут рассмотрены ВСЕ возможные комбинации женщин/мужчин/домов

собственно, все.

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

но стек, при большом n может понадобиться очень приличного размера.
1
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2010, 23:36 17
Patch, что-то я в Вашем алгоритме не увидел:
Цитата Сообщение от leysanka Посмотреть сообщение
и мужчинам и женщинам нравятся некоторые дома
Насчет:
Цитата Сообщение от Patch Посмотреть сообщение
"оптимальный" экземпляр главной структуры
наверное все-таки "оптимальный" (по крайней мере, по выделяемой памяти) это когда двумерный массив размером n*3 (можно и через структуры) и в котором каждая строка примерно такая:
5 6 3 - что означает 5-ый мужчина обоюдносимпатизирует 6-ой женщине и им обоим нравится 3-ий дом.
0
Patch
2336 / 492 / 22
Регистрация: 01.04.2009
Сообщений: 2,181
30.12.2010, 00:53 18
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Patch, что-то я в Вашем алгоритме не увидел:
это исходное условие. его нужно отдельно описывать?

Цитата Сообщение от valeriikozlov Посмотреть сообщение
наверное все-таки "оптимальный" (по крайней мере, по выделяемой памяти) это когда двумерный массив размером n*3 (можно и через структуры) и в котором каждая строка примерно такая:
5 6 3 - что означает 5-ый мужчина обоюдносимпатизирует 6-ой женщине и им обоим нравится 3-ий дом.
нет, "оптимальный" в данном случае - наилучший с точки зрения поставленной задачи.
а если говорить об оптимальности с точки зрения памяти/исполнения, то лучше списками делать не только симпатии, но и вообще всю структуру. и работать будет существенно быстрее.
кроме того, можно сделать алгоритм взвешивания группы решений, кэширование найденных пар-домов и т.д. и т.п. теории баз данных и параллельных вычислений позволяют много чего сделать.
я-же писал "простейший вариант".
или, скажем так, наиболее понятный человеку неподготовленному.
0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
30.12.2010, 01:17 19
Цитата Сообщение от Patch Посмотреть сообщение
а если говорить об оптимальности с точки зрения памяти/исполнения, то лучше списками делать не только симпатии, но и вообще всю структуру. и работать будет существенно быстрее.
а я почему-то считаю что с помощью графов (матрицы смежности) намного быстрее и легче узнать обоюдносимпатизирующих женщин и мужчин например.
0
easybudda
30.12.2010, 01:50     Вывести количество идеальных вариантов
  #20

Не по теме:

Цитата Сообщение от RUSya82 Посмотреть сообщение
это С++?
Это "Дом 2" :D

0
30.12.2010, 01:50
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2010, 01:50
Привет! Вот еще темы с ответами:

Создать файл, ввести символы, вывести на экран количество не латинских букв, количество цифр
Есть код к заднию , но он не правильно показывает данные - киррилицу не ищет а...

Посчитать количество знаков препинания в тексте и вывести их количество.
Текст:"Враг, что мудр и много знает, друга может быть ценней. Мудрость уважать...

Вывести имя и количество букв в фамилии. Вывести самое длинное слово
Вывести имя и количество букв в фамилии.Вывести самое длинное слово,помогите...


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

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

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