Форум программистов, компьютерный форум 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++ Создать файл, ввести символы, вывести на экран количество не латинских букв, количество цифр
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
30.12.2010, 07:03     Вывести количество идеальных вариантов #21
Цитата Сообщение от valeriikozlov Посмотреть сообщение
а я почему-то считаю что с помощью графов (матрицы смежности) намного быстрее и легче узнать обоюдносимпатизирующих женщин и мужчин например.
а легче, ли?
или расчитать и наложить битную маску, или просто взять следующий элемент списка.
взять элемент обычно быстрее.
кроме того, основные потери времени и памяти при большом n будут на сохранение в стек/восстановление из него(ведь расчет должен быть рекурсивным) а не на вычисление симпатий .
для сохранения текущего состояния при использовании матриц, нужно запихнуть в стек всю матрицу. а в случае списков - лишь "список изменений".
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.12.2010, 09:24     Вывести количество идеальных вариантов #22
Цитата Сообщение от Patch Посмотреть сообщение
для сохранения текущего состояния при использовании матриц, нужно запихнуть в стек всю матрицу. а в случае списков - лишь "список изменений
зачем всю матрицу в стек? В ответе №17 я по-моему довольно ясно написал что оптимальней запихивать в стек.
А вот при Вашем алгоритме в стек запихивается что-то очень много всего:
- все женщины, в составе каждой женщины массив всех мужчин;
- все мужчины, в составе каждого мужчины массив всех женщин;
По объему это две матрицы смежности.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.12.2010, 09:59     Вывести количество идеальных вариантов #23
Цитата Сообщение от valeriikozlov Посмотреть сообщение
мощности-мужчины
там надо дефис на двоеточие исправить.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.12.2010, 10:06     Вывести количество идеальных вариантов #24
taras atavin,
Цитата Сообщение от taras atavin Посмотреть сообщение
там надо дефис на двоеточие исправить.
тогда это к автору темы. я только цитировал.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.12.2010, 10:14     Вывести количество идеальных вариантов #25
Кстати, можно и так слепить софтину, что и у домов будут симпатии. Так вот, есть ли в вашей задаче у домов симпатии?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.12.2010, 10:18     Вывести количество идеальных вариантов #26
taras atavin, а можно добавить еще и симпатии женщин к женщинам, мужчин к мужчинам. Получается точно как написал easybudda настоящий Дом-2
taras atavin
Ушёл с форума.
 Аватар для 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2797 / 1573 / 246
Регистрация: 03.05.2010
Сообщений: 3,649
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     Вывести количество идеальных вариантов
Ответ Создать тему
Опции темы

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