|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
04.06.2009, 00:41 | #1 |
Пользователь
Регистрация: 12.05.2009
Сообщений: 30
|
Задачи о назначениях. Венгерский алгоритм.
Помогите реализовать решение задачи на Pascal'е:
Пять человек должны выполнить четыре работы, причём каждый из работников с разной производительностью может выполнить любую из этих работ. Предусматривается, что каждый работник в состоянии сделать только одну работу. Производительность работников задана матрицей: 3 4 2 2 1 4 5 3 1 3 4 3 1 1 1 3 1 2 2 2 0 0 0 0 0 Распределить людей так, чтобы выполнить её с максимальной производительностью. Я начал реализововать венгерский метод, можно продолжить мой пример, можно зделать по своему. Program m; Var t,st1,st2,st3,st4,st5,sb1,sb2,sb3,s b4,sb5,minsrsb,imax,jmax,i,j,max,su m:integer; a:array[1..5,1..5] of integer; //исходная матрица b:array[1..5] of integer; //массив суммы нулей в строках c:array[1..5] of integer; //массив суммы нулей в столбцах Begin //значения элементов исходной матрицы a[1,1]:=3; a[1,2]:=4; a[1,3]:=2; a[1,4]:=2; a[1,5]:=1; a[2,1]:=4; a[2,2]:=5; a[2,3]:=3; a[2,4]:=1; a[2,5]:=3; a[3,1]:=4; a[3,2]:=3; a[3,3]:=1; a[3,4]:=1; a[3,5]:=1; a[4,1]:=3; a[4,2]:=1; a[4,3]:=2; a[4,4]:=2; a[4,5]:=2; a[5,1]:=0; a[5,2]:=0; a[5,3]:=0; a[5,4]:=0; a[5,5]:=0; //исходно-условное количество нулей по строкам в редуцированной матрицы b[1]:=0; b[2]:=0; b[3]:=0; b[4]:=0; b[5]:=0; //исходно-условное количество нулей по столбцам в редуцированной матрицы c[1]:=0; c[2]:=0; c[3]:=0; c[4]:=0; c[5]:=0; begin //вывод исходной матрицы writeln('Исходная матрица'); for i:=1 to 5 do begin for j:=1 to 5 do Write(a[i,j]); writeln; end; end; begin //поиск и вывод максимального элемента в матрице imax:=1; jmax:=1; for i:=1 to 5 do for j:=1 to 5 do if a[imax,jmax]<a[i,j] then begin imax:=i; jmax:=j; end; writeln; writeln('максимальный элемент: ',a[imax,jmax]); end; begin //умнажение элементов матрицы на (-1) и сложение с максимальным элементом for i:=1 to 5 do for j:=1 to 5 do a[i,j]:=a[i,j]*(-1)+5; begin //вывод полученной матрицы writeln; writeln('полученная матрица после преобразования решения задачи на максимум:'); for i:=1 to 5 do begin for j:=1 to 5 do Write(a[i,j]); writeln; end; end; end; begin //определение минимальных элементов строк writeln(); for i:=1 to 5 do begin minsrsb:=a[i,1]; for j:=1 to 5 do if minsrsb>a[i,j]then minsrsb:=a[i,j]; begin for j:=1 to 5 do a[i,j]:=a[i,j]-minsrsb; end; writeln('миниальный элемент строки ',i,'= ',minsrsb); end; end; begin //вывод редуцированной матрицы по строкам writeln(); writeln('матрица редуцированная по строкам'); for i:=1 to 5 do begin for j:=1 to 5 do Write(a[i,j]); writeln; end; end; begin //определение минимальных элементов столбцов writeln(); for j:=1 to 5 do begin minsrsb:=a[j,1]; for i:=1 to 5 do if minsrsb>a[i,j]then minsrsb:=a[i,j]; begin for i:=1 to 5 do a[i,j]:=a[i,j]-minsrsb; end; writeln('миниальный элемент столбца ',j,'= ',minsrsb); end; end; begin //вывод редуцированной матрицы по строкам writeln(); writeln('матрица редуцированная по столбцам'); for i:=1 to 5 do begin for j:=1 to 5 do Write(a[i,j]); writeln; end; end; begin //определение количества нулей в строках writeln(); for i:=1 to 5 do begin for j:=1 to 5 do if a[i,j]=0 then b[i]:=b[i]+1; writeln('количество нулей в строке'#32,i,'-',#32,b[i]); end; end; begin //определение количества нулей в стобцах writeln(); for j:=1 to 5 do begin for i:=1 to 5 do if a[i,j]=0 then c[j]:=c[j]+1; writeln('количество нулей в столбце'#32,j,'-',#32,c[j]); end; end; End. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм для задачи. | MoxFalder | Помощь студентам | 5 | 19.01.2011 14:04 |
Задача о назначениях -- Delphi7 | NeAlSe | Помощь студентам | 2 | 04.06.2009 00:45 |
Задача о назначениях на Pascal'е | PSix1_73 | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 22.05.2009 23:08 |