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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Irokezer
0 / 0 / 0
Регистрация: 16.09.2013
Сообщений: 21
#1

Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) - C++

01.07.2014, 17:31. Просмотров 1239. Ответов 7
Метки нет (Все метки)

Delphi
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
UNIT1
 
unit Unit1;
 
interface
 
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls, ActnList, ExtDlgs, ExtCtrls, jpeg;
 
type
Tform1 = class(Tform)
StringGrid1: TstringGrid;
Button2: Tbutton;
Label1: Tlabel;
Edit1: Tedit;
Button1: Tbutton;
Label2: Tlabel;
Label3: Tlabel;
Button3: Tbutton;
StringGridDug: TstringGrid;
Edit3: Tedit;
StringGrid2: TstringGrid;
StringGrid3: TstringGrid;
Button4: Tbutton;
Button5: Tbutton;
Button6: Tbutton;
StringGrid4: TstringGrid;
StringGrid5: TstringGrid;
StringGrid6: TstringGrid;
Label4: Tlabel;
Label5: Tlabel;
StringGrid7: TstringGrid;
Button7: Tbutton;
Button8: Tbutton;
procedure Button1Click(Sender: Tobject);
procedure Button2Click(Sender: Tobject);
procedure FormCreate(Sender: Tobject);
procedure Button3Click(Sender: Tobject);
procedure Button4Click(Sender: Tobject);
procedure Button5Click(Sender: Tobject);
procedure Button6Click(Sender: Tobject);
procedure FormShow(Sender: Tobject);
procedure Button7Click(Sender: Tobject);
procedure Button8Click(Sender: Tobject);
 
private
{ Private declarations }
public
{ Public declarations }
end;
 
const
max = 100; { размер большего из двух множеств }
 
var
Form1: Tform1;
n, i, j, del, x, cnt, y, page, ch, s: integer;
osn, dop: array [1 .. max, 1 .. max] of string;
rez: array [1 .. max, 1 .. max] of integer;
str, stolb: array [1 .. 100] of integer;
t: TextFile;
 
implementation
 
uses Unit2;
 
{$R *.dfm}
 
/// Заполнение
procedure Tform1.Button1Click(Sender: Tobject);
begin
Button1.Visible := false;
page := 7;
StringGrid7.Visible := false;
StringGrid6.Visible := false;
StringGrid5.Visible := false;
StringGrid4.Visible := false;
StringGrid3.Visible := false;
StringGrid2.Visible := false;
StringGrid1.Visible := true;
StringGridDug.cols[1].add(‘x’);
StringGridDug.cols[2].add(‘y’);
for j := 1 to x do
begin
StringGridDug.Cells[1, j] := ‘’;
StringGridDug.Cells[2, j] := ‘’;
end;
x := strtoint(Edit1.Text);
y := strtoint(Edit3.Text);
StringGrid1.ColCount := x + 2;
StringGrid1.RowCount := y + 2;
for i := 1 to x do
StringGrid1.cols[i].add(‘х ‘ + inttostr(i));
for j := 1 to y do
StringGrid1.Rows[j].add(‘y ‘ + inttostr(j));
for i := 1 to x do
begin
for j := 1 to y do
StringGrid1.Cells[i, j] := inttostr(0);
end;
end;
 
/// Выход
procedure Tform1.Button2Click(Sender: Tobject);
begin
Form1.Close;
end;
 
/// Основное решение
procedure Tform1.Button3Click(Sender: Tobject);
label
shag2, shag3, shag4, shag5;
begin
StringGrid1.Visible := false;
StringGrid2.Visible := true;
StringGrid2.ColCount := x + 2;
StringGrid2.RowCount := y + 2;
/// //////////// шаг 0
for i := 1 to x do
StringGrid2.cols[i].add(‘х ‘ + inttostr(i));
for i := 1 to y do
StringGrid2.Rows[i].add(‘y ‘ + inttostr(i));
for i := 1 to x do
begin
for j := 1 to y do
if StringGrid1.Cells[i, j] = inttostr(0) then
StringGrid2.Cells[i, j] := ‘x’
else
StringGrid2.Cells[i, j] := ‘’
end;
/// ///////////////////
StringGrid3.ColCount := x + 2;
StringGrid3.RowCount := y + 2;
for i := 1 to x do
StringGrid3.cols[i].add(‘х ‘ + inttostr(i));
for i := 1 to y do
StringGrid3.Rows[i].add(‘y ‘ + inttostr(i));
for i := 1 to x do
begin
for j := 1 to y do
StringGrid3.Cells[i, j] := StringGrid2.Cells[i, j];
end;
for i := 1 to x do
stolb[i] := 0;
for i := 1 to y do
str[i] := 0;
/// ////////////// шаг 1
for i := 1 to x do
begin
for j := 1 to y do
if (StringGrid3.Cells[i, j] = ‘’) and (stolb[i] <> 1) and (str[j] <> 1)
then
begin
StringGrid3.Cells[i, j] := inttostr(1);
stolb[i] := 1;
str[j] := 1;
end;
end;
cnt := 0;
for i := 1 to y do
begin
if str[i] <> 1 then
StringGrid3.Cells[x + 1, i] :=-;
end;
for i := 1 to y do
begin
if str[i] = 1 then
cnt := cnt + 1;
end;
/// ////////////////
StringGrid2.Visible := false;
StringGrid3.Visible := true;
if y = cnt then
begin
showmessage(‘Максимальное паросочетание найдено’);
n := 1;
for i := n to x do
begin
for j := 1 to y do
if StringGrid3.Cells[i, j] = inttostr(1) then
begin
StringGridDug.Cells[1, n] := intto
Возможно ли перевести этот код из делфи в си?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2014, 17:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Перевод из Delphi (Алгоритм нахождения наибольшего паросочетания в двудольном графе) (C++):

Алгоритм Габова для поиска максимального паросочетания в произвольном графе за O(V^3) - C++
Прокомментируйте каждую строку. Очень нужно. Спасибо! #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;queue&gt; using namespace std;...

Рекурсивный алгоритм Евклида нахождения наибольшего общего делителя - C++
Даны натуральные числа n, m. Найти НОД(n,m). Рекурсивный алгоритм Евклида нахождения наибольшего общего делителя основан на соотношении...

Составить алгоритм нахождения суммы наибольшего и наименьшего из заданных чисел - C++
:(:(

Написать алгоритм нахождения наибольшего общего делителя трех чисел - C++
Написать алгоритм нахождения наибольшего общего делителя трех чисел C++ помогите пожалуйста, желательно с объяснением

Алгоритмы нахождения наибольшего числа - C++
Доброго времени суток, форумчане! Мне тут по структурам и алгоритмам выдали интересное задание, и я никак не могу придумать пару алгоритмов...

Макрос для нахождения наибольшего числа - C++
Не могу разобраться с макросами, но страсть как хочется, помогите написать макрос. #define MAX(x, y, r) /* присвоить в r максимум из x и...

7
volvo
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
24008 / 15989 / 4836
Регистрация: 22.10.2011
Сообщений: 28,287
Записей в блоге: 5
01.07.2014, 17:53 #2
В какой Си? Каким компилятором пользуешься?
0
Irokezer
0 / 0 / 0
Регистрация: 16.09.2013
Сообщений: 21
01.07.2014, 19:11  [ТС] #3
Dev-C++ там встроенный компилятор
0
volvo
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
24008 / 15989 / 4836
Регистрация: 22.10.2011
Сообщений: 28,287
Записей в блоге: 5
01.07.2014, 22:46 #4
Тема перенесена в правильный раздел. Теперь увидеть бы код на Дельфи полностью, а не этот огрызок, и, если можно, задачу, которую код призван решать.
0
Irokezer
0 / 0 / 0
Регистрация: 16.09.2013
Сообщений: 21
01.07.2014, 22:51  [ТС] #5
Алгоритм нахождения наибольшего паросочетания в двудольном графе

Мы опишем сейчас алгоритм выбора наибольшего сочетания в двудольном графе, опираясь на только что введенное понятие матрицы двудольного графа.

Шаг 0. По матрице M=(mij), i=1,...,p, j=1,2,...,q данного двудольного графа строим рабочую таблицу: она представляет собой матрицу тех же размеров; в клетку с номером (i,j) поместим символ "x" и назовем ее недопустимой, если в матрице двудольного графа mij=0 ; если же mij=1, то в клетку рабочей таблицы не запишем ничего и назовем такую клетку допустимой. Слева от рабочей таблицы расположим для удобства номера ее строк, а сверху над таблицей расположим номера ее столбцов.

Шаг 1. Просмотрим слева направо первую строку и в первую же допустимую клетку первой строки поставим символ "1". Если в первой строке все клетки недопустимы, то перейдем ко второй строке и в первую же (при просмотре слева направо) допустимую клетку поставим "1". Если же нет допустимых клеток и во второй строке, то проставим указанным выше способом "1" в третьей строке. Если окажется, что во всей таблице все клетки недопустимы, то на этом все действия заканчиваются и выдается ответ: "в графе нет ребер". Если же все-таки удастся поставить первую "1", то после этого просмотрим все остальные строки таблицы в порядке возрастания их номеров. В каждой очередной строке просматриваем ее клетки слева направо и фиксируем первую по ходу просмотра допустимую клетку такую, которая является независимой по отношению к допустимым клеткам, в которых уже стоит символ "1", и проставляем в эту клетку "1", после чего переходим к тем же действиям в следующей строке. Если в строке такой клетки не окажется, то переходим к следующей строке и выполняем в ней ту же проверку.
Фиксируем набор ребер в графе, соответствующих проставленным в таблице символам "1". (Под ребром, соответствующим символу "1" в рабочей таблице, подразумевается следующее: если "1" стоит в клетке с номером (i,j), то соответствующим будет ребро xi,yj .) Легко заметить, что этот набор ребер - максимальное паросочетание.

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

Шаг 2. Просмотрим все помеченные строки в порядке возрастания их номеров. Просмотр очередной строки состоит в следующем: в строке отыскиваются допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются номером просматриваемой строки. При этом соблюдается принцип (φ ): если пометка уже стоит, то на ее место вторая не ставится. Пометки, о которых только что было сказано, физически выставляются внизу, под таблицей.

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

Шаг 3. Просмотрим помеченные столбцы в порядке возрастания их номеров. Просмотр столбца состоит в следующем: в столбце отыскивается символ "1" и строка, в которой он расположен, помечается номером просматриваемого столбца.

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

Если в результате этих действий по
01.07.14
Шагу 2 не возникнет новых помеченных столбцов, то это означает, что имеющееся паросочетание является искомым и процесс останавливается. Если же среди помечаемых столбцов возникнут новые помеченные столбцы, то следует повторить Шаг 3 с новым набором помеченных столбцов. Если в результате этих действий не возникнет новых помеченных строк, то это означает, что имеющееся паросочетание является искомым.

Шаг 4. Рассматривается столбец, имеющий пометку и не содержащий символа "1". Мы сейчас изменим набор символов "1", расположенных в рабочей таблице.

В рассматриваемый столбец поставим символ "1" в строку, номер которой равен пометке этого столбца. Затем в этой строке отыщем "старый" символ "1" и переместим его по его столбцу в строку, номер которой равен пометке при этом столбце. (Можно доказать, что описанное действие реально всегда осуществимо.) Затем в строке, куда попал последний символ "1" отыщем "старый" символ "1" и с ним проделаем то же самое. В конце концов очередной перемещаемый "старый" символ "1" окажется в строке, где больше символов "1" нет. Возник новый набор символов "1", в котором уже элементов на один больше, чем в исходном наборе символов "1". По этому новому набору можно построить паросочетание так же, как это делалось в самом начале и после этого повторить все сначала.

В конце концов возникнет одно из указанных выше условий прекращения действий по алгоритму и наибольшее паросочетание будет найдено.
4. Пример

Рассмотрим пример. Найти наибольшее паросочетание в следующем двудольном графе со следующей матрицей:

Сам двудольный граф в этом примере выглядит так:

Будем проводить шаг за шагом описанный выше алгоритм. Рабочая таблица:

Выполняем первый шаг: расставляем независимые единицы и отмечаем строки, в которые единицы не попали:

Паросочетание, которое соответствует выбранным единицам:
Далее столбцы допустимых клеток помеченных строк пометим номерами этих строк, следуя принципу (φ):

Далее в помеченных столбцах отыщем единицы и их строки пометим номерами их столбцов:

Теперь снова пометим столбцы, отправляясь от помеченных строк и соблюдая принцип (φ):

Теперь снова просмотрим помеченные столбцы и пометим строки:

Теперь снова пометим столбцы (при принципе (φ)):

Теперь снова пометим строки:

Сложилась ситуация, когда в столбце №5 с пометкой "4" нет единицы. Следовательно, набор единиц можно увеличить на одну
(старые единицы остаются черными, новые - красные):

Мы получили новый набор независимых единиц:

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

Затем в помеченных столбцах найдем единицы и их строки пометим
номерами столбцов:

Затем столбцы допустимых клеток помеченных строк:

Затем снова строки:

Затем снова столбцы:

Сложилась ситуация, когда расстановка пометок "зациклилась". Это означает, что искомое паросочетание состоит из ребер, соответствующих проставленным единицам.
0
Irokezer
0 / 0 / 0
Регистрация: 16.09.2013
Сообщений: 21
02.07.2014, 18:25  [ТС] #6
UI, Весь код не влезает,поэтому кину в архиве:
0
Вложения
Тип файла: rar Листинг.rar (3.0 Кб, 48 просмотров)
Mekan
0 / 0 / 0
Регистрация: 24.12.2014
Сообщений: 35
24.12.2014, 20:59 #7
дайте пжл вес код
0
Sofia22
0 / 0 / 0
Регистрация: 13.04.2015
Сообщений: 1
24.04.2015, 13:29 #8
Где можно увидеть программу к данной задаче на Си ++?
0
24.04.2015, 13:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2015, 13:29
Привет! Вот еще темы с ответами:

Написать функцию для нахождения наибольшего числа - C++
В текстовом файле записана непустая последовательность действительных чисел, разделенных пробелами (пробелов может быть больше одного)....

Составить программу нахождения наибольшего из трех чисел - C++
Язык программирования С++. Составить программу нахождения наибольшего из трех чисел

Нужно немного переделать программу нахождения компонент сильной связности в графе - C++
В общем задание такое, нужно переделать эту программу, я не знаю как это сделать, помогите люди добрые)) #include &lt;iostream&gt; ...

Написать программу нахождения наибольшего и наименьшего значения функции - C++
Написать программу нахождения наибольшего и наименьшего значения функции y=3x*x+x-4 на интервале c шагом 0.1!!! очень нужно пожалуйста...


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

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

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