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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ fscanf(stream,"%s",s) читает до первого пробела? http://www.cyberforum.ru/cpp-beginners/thread221726.html
как прочитать строку из текстового файла целиком? (до \n)
C++ Односвязный кольцевой список. Ребят, подскажите как реализовать односвязный кольцевой список с ключами. Без ключей я знаю как, а что делают эти самые ключи? http://www.cyberforum.ru/cpp-beginners/thread221725.html
кириллица C++
Подскажите, как сделать ,чтобы в Borland C вывод был русскими буквами. Я написал setlocale(LC_ALL, "Russian"); вывод стал на кириллице,а вот информацию которую вводишь - нет
удаление символов из строки! C++
написать функцию удаления из строки s всех символов ASCIIкоды которых попадают в диапозон от н1 до н2 включительно 0<=н1<=255,0<=н2<=255, н1<=н2 помогите!
C++ Блок схема http://www.cyberforum.ru/cpp-beginners/thread221712.html
Люди помогите! =( Написал программу на Паскале и не могу схему алгоритма начертить, запутываюсь постоянно..Нарисуйте кто может и залейте куда нибудь, оч прошу =). Вот программа: uses crt; var a, b, col: array of integer; i, j, k: integer; begin for i := 1 to 20 do begin
C++ Построение центра дерева (графы) Задача состоит в том, что нужно найти центр дерева, и при этом алгоритм должен учитывать особенность графов этого типа (центр содержит одну или две смежные вершины). Пробовал через матрицу смежности (искал сумму элементов строки, если она равна единице, то обнуляем соответсвующие строку и столбец), но возникла проблема - как остановить алгоритм в нужном месте? подробнее

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

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

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

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

далее...

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

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

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

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

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

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