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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

как вывести на экран через запятую энное количество членов прогрессии, если это количество я ввожу с клавиатуры? - C++
подскажите


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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
3042 / 1687 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
30.12.2010, 18:05     Вывести количество идеальных вариантов #31
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
//////////////////////////////////////////////////////////////////////////////////////
//есть три множества одинаковой мощности-мужчины женщины и дома. (все по n)
//между мужчинами и женщинами есть симпатии.
//и мужчинам и женщинам нравятся некоторые дома.
//сколько обоюдносимпатизирующих пар можно заселить в нравящийся им дом?
//т.е. надо вывести кол-во идеальных вариантов.
//////////////////////////////////////////////////////////////////////////////////////
//Задача решена с помощью алгоритма Куна.
//////////////////////////////////////////////////////////////////////////////////////
#include <deque>
#include <iostream>
#include <map>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::map<int, bool>       T_adj_row;
typedef std::map<int, T_adj_row>  T_adj_matr;
typedef std::deque<bool>          T_use;
typedef std::deque<int>           T_matching;
//////////////////////////////////////////////////////////////////////////////////////
T_adj_matr  input_bipartite_graph(int  couples_total)
{   
    T_adj_matr  adj_matr;
    const int   HOUSE_NUM_MIN  = 1;
    const int   BREAK_NUMBER   = HOUSE_NUM_MIN - 1;
    std::cout << "Для каждой пары мужчина-женщина введите "
              << "номера нравящихся им домов "
              << std::endl
              << "из диапазона "
              << HOUSE_NUM_MIN
              << ".."
              << couples_total
              << " ("
              << BREAK_NUMBER
              << " - конец ввода): "
              << std::endl;    
 
    for(int  couple_ind = 0; couple_ind < couples_total; ++couple_ind)
    {        
        std::cout << std::endl
                  << "Пара "                  
                  << couple_ind + 1
                  << ": "
                  << std::endl;
 
        std::cout << '\t'
                  << "номера нравящихся домов: "
                  << std::endl;
        
        for(;;)
        {
            std::cout << '\t'
                      << "-> ";
 
            int  house_ind = 0;
            std::cin >> house_ind;
            if(house_ind == BREAK_NUMBER)
            {
                break;
            }
            else if(   house_ind < HOUSE_NUM_MIN 
                    || couples_total < house_ind)
            {
                std::cout << '\t'
                          << "допустимы только номера из диапазона "
                          << HOUSE_NUM_MIN
                          << ".."
                          << couples_total
                          << std::endl;                          
            }
            else
            {
                house_ind += couples_total - 1;
                adj_matr[couple_ind][house_ind] = adj_matr[house_ind][couple_ind] = true;
            }
        }        
    }
    return  adj_matr;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  find_matching
    (
        int          couple_ind,
        int          couples_total,
        T_use&       use_couple,
        T_adj_matr&  adj_matr,
        T_matching&  couple_of,
        int          empty_couple_ind
    )
{
    use_couple[couple_ind] = true;
    for(int  house_ind = couples_total; house_ind < couples_total * 2; ++house_ind)
    {
        if(!adj_matr[couple_ind][house_ind])  continue;
 
        if(                
               couple_of[house_ind] == empty_couple_ind 
           ||    !use_couple[couple_of[house_ind]]
              && find_matching
                     (
                         couple_of[house_ind],
                         couples_total,
                         use_couple,
                         adj_matr,
                         couple_of,
                         empty_couple_ind
                     )                  
          )
        {
            couple_of[house_ind] = couple_ind;
            return  true;
        }
    }
    return  false;
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_couples_settling(int  couples_total, T_adj_matr&  adj_matr)
{
    const int   EMPTY_COUPLE_IND = -1;
    T_use       use_couple  (couples_total);                                            
                                            
    T_matching  couple_of   (couples_total * 2, EMPTY_COUPLE_IND);//Размер двойной, так как
                                                                  //номера домов начинаются
                                                                  //с couples_total.
    //Пробегаемся по парам:
    for(int  couple_ind = 0; couple_ind < couples_total; ++couple_ind)
    {
        //Обнуляем использованные вершины.
        use_couple.assign(couples_total, false);
        find_matching
            (
                couple_ind, 
                couples_total, 
                use_couple, 
                adj_matr, 
                couple_of,
                EMPTY_COUPLE_IND
            );
    }
 
    //Печатаем найденное максимальное паросочетание:
    std::cout << std::endl
              << "Максимальное паросочетание:"
              << std::endl;
    for(int  house_ind = couples_total; house_ind < couples_total * 2; ++house_ind)
    {
        if(couple_of[house_ind] != EMPTY_COUPLE_IND)
        {
            std::cout << '\t'
                      << "дом "
                      << house_ind - (couples_total - 1)
                      << " - пара "
                      << couple_of[house_ind] + 1
                      << std::endl;
        }
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите количество пар мужчина-женщина: ";
    int  couples_total = 0;
    std::cin >> couples_total;
 
    T_adj_matr  adj_matr(input_bipartite_graph(couples_total));
    print_couples_settling(couples_total, adj_matr);
}
Yandex
Объявления
30.12.2010, 18:05     Вывести количество идеальных вариантов
Ответ Создать тему
Опции темы

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