Форум программистов, компьютерный форум CyberForum.ru

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

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

C++ Посчитать количество знаков препинания в тексте и вывести их количество.
C++ Дан текстовый файл. Вывести на экран количество предложений в нём и количество слов в каждом предложении.
C++ Задача по нахождению идеальных чисел на заданном промежутке
C++ Дан текстовый файл. Вывести на экран количество предложений в нём и количество слов в каждом предложении
C++ Количество возможных вариантов и ребус
как вывести на экран через запятую энное количество членов прогрессии, если это количество я ввожу с клавиатуры? C++
C++ Создать файл, ввести символы, вывести на экран количество не латинских букв, количество цифр
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
28.12.2010, 13:27     Вывести количество идеальных вариантов #2
это С++?
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
28.12.2010, 13:35     Вывести количество идеальных вариантов #3
это SQL.
но можно извратиться, и реализовать циклы на C/C++
leysanka
 Аватар для leysanka
0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
28.12.2010, 15:14  [ТС]     Вывести количество идеальных вариантов #4
помогите пожалуйста..
на С вроде должно быть.
это с графами как-то связано

Добавлено через 13 минут
подскажите хотя-бы как это делать..принцип решения.. а то совсем не догоняю.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 15:27     Вывести количество идеальных вариантов #5
Изначально задача кажется немного странной.
Это все условие:?
есть три множества одинаковой мощности-мужчины женщины и дома. (все по n)
между мужчинами и женщинами есть симпатии.
и мужчинам и женщинам нравятся некоторые дома.
сколько обоюдносимпатизирующих пар можно заселить в нравящийся им дом?
т.е. надо вывести кол-во идеальных вариантов..
социально важная задача, кстати!
Тогда вопросы:
- мощности-мужчины женщины и дома как нибудь связаны с симпатиями:
между мужчинами и женщинами и понравившимися домами?
- как задаются входные данные вообще?
Насчет социально важной задачи Вас обманули кстати, все решается не так (а через знакомства, взятки и т.п.)
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
28.12.2010, 15:33     Вывести количество идеальных вариантов #6
ну, раз совсем непонятно - делай простейший вариант.
тупо перебирай всех женщин, для каждой перебирай все ее симпатии к мужчинам,
далее проверяй совпадают ли симпатии, и если совпадают - перебирай возможные домики для пары(которые обоим нравятся).
после нахождения пары с домиком, выбрасываешь их из процесса поиска, и... ищешь то-же самое среди оставшихся.
и так до тех пор, пока не кончаться все женщины с их симпатиями.
побеждает вариант, в котором число найденных домиков с парами - максимально.

по сути - типичная шахматная задача.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 15:43     Вывести количество идеальных вариантов #7
Цитата Сообщение от Patch Посмотреть сообщение
делай простейший вариант
Это называется "жадный алгоритм", но пока неизвестно по какому принципу формируются входные данные этот алгоритм применять преждевременно.
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
28.12.2010, 15:51     Вывести количество идеальных вариантов #8
Цитата Сообщение от valeriikozlov Посмотреть сообщение
но пока неизвестно по какому принципу формируются входные данные
по-моему, как раз это понятно.
принцип формирования исходных данных четко описан:
Цитата Сообщение от leysanka Посмотреть сообщение
есть три множества одинаковой мощности-мужчины женщины и дома. (все по n)
между мужчинами и женщинами есть симпатии.
и мужчинам и женщинам нравятся некоторые дома.
другое дело, что эти данные можно представить в разных форматах.
но формат исходных данных на алгоритм практически не влияет.

а еще есть вопрос, как могут заселяться дома: обязательно по одной паре на дом, или можно по нескльку?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 16:13     Вывести количество идеальных вариантов #9
Цитата Сообщение от Patch Посмотреть сообщение
по-моему, как раз это понятно.
А по-моему не совсем все-таки понятно. Например если мощности и симпатии согласуются по принципу: если мощность мужчины, женщины или дома расходятся не более чем на 5 единиц, то все друг другу нравятся. А если более, то не нравятся. То тогда жадный алгоритм не применим, для достижения максимального результата.
Лучше все-таки дождаться ответа хозяйки вопроса.
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
28.12.2010, 16:26     Вывести количество идеальных вариантов #10
Цитата Сообщение от valeriikozlov Посмотреть сообщение
если мощность мужчины, женщины или дома расходятся не более чем на 5 единиц

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

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

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

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

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

далее...

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

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

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

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

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

но стек, при большом n может понадобиться очень приличного размера.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2010, 23:36     Вывести количество идеальных вариантов #17
Patch, что-то я в Вашем алгоритме не увидел:
Цитата Сообщение от leysanka Посмотреть сообщение
и мужчинам и женщинам нравятся некоторые дома
Насчет:
Цитата Сообщение от Patch Посмотреть сообщение
"оптимальный" экземпляр главной структуры
наверное все-таки "оптимальный" (по крайней мере, по выделяемой памяти) это когда двумерный массив размером n*3 (можно и через структуры) и в котором каждая строка примерно такая:
5 6 3 - что означает 5-ый мужчина обоюдносимпатизирует 6-ой женщине и им обоим нравится 3-ий дом.
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
30.12.2010, 00:53     Вывести количество идеальных вариантов #18
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Patch, что-то я в Вашем алгоритме не увидел:
это исходное условие. его нужно отдельно описывать?

Цитата Сообщение от valeriikozlov Посмотреть сообщение
наверное все-таки "оптимальный" (по крайней мере, по выделяемой памяти) это когда двумерный массив размером n*3 (можно и через структуры) и в котором каждая строка примерно такая:
5 6 3 - что означает 5-ый мужчина обоюдносимпатизирует 6-ой женщине и им обоим нравится 3-ий дом.
нет, "оптимальный" в данном случае - наилучший с точки зрения поставленной задачи.
а если говорить об оптимальности с точки зрения памяти/исполнения, то лучше списками делать не только симпатии, но и вообще всю структуру. и работать будет существенно быстрее.
кроме того, можно сделать алгоритм взвешивания группы решений, кэширование найденных пар-домов и т.д. и т.п. теории баз данных и параллельных вычислений позволяют много чего сделать.
я-же писал "простейший вариант".
или, скажем так, наиболее понятный человеку неподготовленному.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.12.2010, 01:17     Вывести количество идеальных вариантов #19
Цитата Сообщение от Patch Посмотреть сообщение
а если говорить об оптимальности с точки зрения памяти/исполнения, то лучше списками делать не только симпатии, но и вообще всю структуру. и работать будет существенно быстрее.
а я почему-то считаю что с помощью графов (матрицы смежности) намного быстрее и легче узнать обоюдносимпатизирующих женщин и мужчин например.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2010, 01:50     Вывести количество идеальных вариантов
Еще ссылки по теме:

Найти количество идеальных чисел в заданном диапазоне C++
Вывести имя и количество букв в фамилии. Вывести самое длинное слово C++
Вывести имя и количество букв в фамилии. Вывести самое длинное слово C++
C++ Просчитать количество вариантов представления числа в виде суммы натуральных цифр 1, 2 и 3
Отсортировать строки матрицы по сумме в них идеальных чисел C++

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

Или воспользуйтесь поиском по форуму:
easybudda
30.12.2010, 01:50     Вывести количество идеальных вариантов
  #20

Не по теме:

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

Yandex
Объявления
30.12.2010, 01:50     Вывести количество идеальных вариантов
Ответ Создать тему
Опции темы

Текущее время: 02:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru