Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
leysanka
0 / 0 / 0
Регистрация: 23.12.2009
Сообщений: 12
#1

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

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

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

Найти количество идеальных чисел в заданном диапазоне - C++
Находит количество идеальных чисел в заданном диапазоне. Идеальным называется число, равное сумме всех его делителей, не включая его...

Количество возможных вариантов и ребус - C++
Прошу помощи 1)Перед фермером стоит задача: купить на 100 рублей 100 голов скота. Стоимость быка – 10 руб., коровы – 5 руб. и телёнка...

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

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

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

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

30
Patch
2277 / 492 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
28.12.2010, 17:11 #16
Цитата Сообщение от leysanka Посмотреть сообщение
мне понравился простейший вариант.как его реализовывать?
сильно зависит от того, на какие ресурсы расчитывать(в плане вычислительной мощность и объема памяти компьютера).
если особых ограничений нет, то, опять-же, простейший вариант:

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

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

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

далее...

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

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

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

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

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

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

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

Не по теме:

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

0
Patch
2277 / 492 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
30.12.2010, 07:03 #21
Цитата Сообщение от valeriikozlov Посмотреть сообщение
а я почему-то считаю что с помощью графов (матрицы смежности) намного быстрее и легче узнать обоюдносимпатизирующих женщин и мужчин например.
а легче, ли?
или расчитать и наложить битную маску, или просто взять следующий элемент списка.
взять элемент обычно быстрее.
кроме того, основные потери времени и памяти при большом n будут на сохранение в стек/восстановление из него(ведь расчет должен быть рекурсивным) а не на вычисление симпатий .
для сохранения текущего состояния при использовании матриц, нужно запихнуть в стек всю матрицу. а в случае списков - лишь "список изменений".
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.12.2010, 09:24 #22
Цитата Сообщение от Patch Посмотреть сообщение
для сохранения текущего состояния при использовании матриц, нужно запихнуть в стек всю матрицу. а в случае списков - лишь "список изменений
зачем всю матрицу в стек? В ответе №17 я по-моему довольно ясно написал что оптимальней запихивать в стек.
А вот при Вашем алгоритме в стек запихивается что-то очень много всего:
- все женщины, в составе каждой женщины массив всех мужчин;
- все мужчины, в составе каждого мужчины массив всех женщин;
По объему это две матрицы смежности.
0
taras atavin
3570 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
30.12.2010, 09:59 #23
Цитата Сообщение от valeriikozlov Посмотреть сообщение
мощности-мужчины
там надо дефис на двоеточие исправить.
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.12.2010, 10:06 #24
taras atavin,
Цитата Сообщение от taras atavin Посмотреть сообщение
там надо дефис на двоеточие исправить.
тогда это к автору темы. я только цитировал.
0
taras atavin
3570 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
30.12.2010, 10:14 #25
Кстати, можно и так слепить софтину, что и у домов будут симпатии. Так вот, есть ли в вашей задаче у домов симпатии?
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.12.2010, 10:18 #26
taras atavin, а можно добавить еще и симпатии женщин к женщинам, мужчин к мужчинам. Получается точно как написал easybudda настоящий Дом-2
0
taras atavin
3570 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
30.12.2010, 10:27 #27
Нет, я больший бред имел ввиду.
0
Patch
2277 / 492 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
30.12.2010, 13:02 #28
Цитата Сообщение от valeriikozlov Посмотреть сообщение
зачем всю матрицу в стек? В ответе №17 я по-моему довольно ясно написал что оптимальней запихивать в стек.
А вот при Вашем алгоритме в стек запихивается что-то очень много всего:
- все женщины, в составе каждой женщины массив всех мужчин;
- все мужчины, в составе каждого мужчины массив всех женщин;
По объему это две матрицы смежности.
а затем, что иначе нельзя восстановить исходный вариант.
и все промежуточные.
потому, что каждая найденная пара с домом - есть точка ветвления алгоритма.
не "две матрицы смежности", а все, какие есть
вот это "все женщины, в составе каждой женщины массив всех мужчин;" я не понял.
с каких это пор массив мужчины включен в состав женщины? О_о
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.12.2010, 14:47 #29
Цитата Сообщение от Patch Посмотреть сообщение
вот это "все женщины, в составе каждой женщины массив всех мужчин;" я не понял.
с каких это пор массив мужчины включен в состав женщины?
Или я плохо читать умею:
а)создать структуры:
1)женщина:
массив из n двоичных элементов(отражающий ее симпатии), по одному на каждого мужчину
taras atavin, может Вы это и имели ввиду, но более извращенный вариант: это симпатия между домами.
0
Patch
2277 / 492 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
30.12.2010, 15:56 #30
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Или я плохо читать умею
вам виднее.
но "массив из двоичных элементов" и "массив мужчин" - не совсем одно и то-же, вам не кажется?
0
30.12.2010, 15:56
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2010, 15:56
Привет! Вот еще темы с ответами:

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

Вывести имя и количество букв в фамилии. Вывести самое длинное слово - C++
Вывести имя и количество букв в фамилии.Вывести самое длинное слово,помогите сделать эту программу

Вывести имя и количество букв в фамилии. Вывести самое длинное слово - C++
Помогите сделать задачку: Вывести имя и количество букв в фамилии.Вывести самое длинное слово.На C++

Дан текстовый файл. Вывести на экран количество предложений в нём и количество слов в каждом предложении - C++
Помогите пожалуйста решить задачку, буду очень благодарен. Дан текстовый файл. Вывести на экран количество предложений в нём и количество...


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

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

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