Разбить предметы на две группы так, чтобы массы в обеих группах были максимально одинаковые - Turbo Pascal
Формулировка задачи:
Решение задачи: «Разбить предметы на две группы так, чтобы массы в обеих группах были максимально одинаковые»
const n=10; type mas=array[1..n] of integer; var a,b,c:mas; ia,ib,ic,sb,sc:integer; jb,jc:integer; maxbol:integer; tmp:integer; procedure zmas(var x:mas;razm:integer);{задание массива размерности razm} var i:integer; begin for i:=1 to razm do x[i]:=random(51) end; procedure v(x:mas;razm:integer);{вывод массива размерности razm} var i:integer; begin for i:=1 to razm do write(x[i],' '); writeln end; procedure sort(var x:mas);{сортировка} var i,j:integer; begin for i:=1 to n-1 do for j:=1 to n-i do if a[j]<a[j+1] then begin a[j]:=a[j]+a[j+1]; a[j+1]:=a[j]-a[j+1]; a[j]:=a[j]-a[j+1] end end; {поиск 2 элементов в массивах, разность которых "максимально не больше чем половина разностей их сумм", например если сумма первого = 200, сумма второго = 180 в первом есть элементы 20 25 во втором - 10 19, то будут найдены 20 и 10(200-180)div2} function naib(bx,cx:mas;rb,rc:integer;mraz:integer;var xb,xc:integer):boolean; {bx,cx массивы;rb,rc их размерности;mraz максимальная разность; xb,xc номера элементов если они найдены(true)} var i,j,raz:integer; f:boolean; begin f:=false; raz:=0; for i:=1 to rc do for j:=1 to rb do if (cx[i]>bx[j])and(abs(cx[i]-bx[j])<=mraz)and(abs(cx[i]-bx[j])>raz) then begin raz:=abs(cx[i]-bx[j]); xb:=j; xc:=i; f:=true end; naib:=f end; begin randomize; zmas(a,n); v(a,n); sort(a); sb:=a[1];b[1]:=a[1];sc:=a[2];c[1]:=a[2];ib:=1;ic:=1; for ia:=3 to n do{раскидываем элементы отсортированного массива} if sb>sc{сумма которого меньше } then begin sc:=sc+a[ia]; inc(ic); c[ic]:=a[ia]{добавляем элемент к нему} end else begin sb:=sb+a[ia]; inc(ib); b[ib]:=a[ia] end; repeat maxbol:=(abs(sb-sc))div 2; jb:=0;jc:=0; if sb<sc {ищем больший в c} then begin if naib(b,c,ib,ic,maxbol,jb,jc) then begin tmp:=c[jc]; c[jc]:=b[jb]; b[jb]:=tmp; sb:=sb+abs(c[jc]-b[jb]); sc:=sc-abs(c[jc]-b[jb]); end end else if sc<sb {ищем больший в b} then if naib(c,b,ic,ib,maxbol,jc,jb) then begin tmp:=c[jc]; c[jc]:=b[jb]; b[jb]:=tmp; sb:=sb-abs(c[jc]-b[jb]); sc:=sc+abs(c[jc]-b[jb]); end; until (jb=0)and(jc=0); writeln('1 массив'); v(b,ib); writeln('его сумма ',sb); writeln('2 массив'); v(c,ic); writeln('его сумма ',sc); readln end.
Объяснение кода листинга программы
const n = 10; type mas = array[1..n] of integer; var a, b, c: mas; var ia, ib, ic, sb, sc: integer; var jb, jc: integer; var maxbol: integer; var tmp: integer; procedure zmas(var x: mas; razm: integer); var i: integer; begin for i := 1 to razm do x[i] := random(51); end; procedure v(x: mas; razm: integer); var i: integer; begin for i := 1 to razm do write(x[i], ' '); writeln; end; procedure sort(var x: mas); var i, j: integer; begin for i := 1 to n-1 do for j := 1 to n-i do if a[j] < a[j+1] then begin a[j] := a[j] + a[j+1]; a[j+1] := a[j] — a[j+1]; a[j] := a[j] — a[j+1]; end end; end; function naib(bx, cx: mas; rb, rc: integer; mraz: integer; var xb, xc: integer): boolean; var i, j, raz: integer; f: boolean; begin f := false; raz := 0; for i := 1 to rc do for j := 1 to rb do if (cx[i] > bx[j]) and (abs(cx[i] — bx[j]) <= mraz) and (abs(cx[i] — bx[j]) > raz) then begin raz := abs(cx[i] — bx[j]); xb := j; xc := i; f := true; end; naib := f; end; begin randomize; zmas(a, n); v(a, n); sort(a); sb := a[1]; b[1] := a[1]; sc := a[2]; c[1] := a[2]; ib := 1; ic := 1; repeat maxbol := (abs(sb — sc)) div 2; jb := 0; jc := 0; if sb < sc then begin if naib(b, c, ib, ic, maxbol, jb, jc) then begin tmp := c[jc]; c[jc] := b[jb]; b[jb] := tmp; sb := sb + abs(c[jc] — b[jb]); sc := sc — abs(c[jc] — b[jb]); end; end else if begin if naib(c, b, ic, ib, maxbol, jc, jb) then begin tmp := c[jc]; c[jc] := b[jb]; b[jb] := tmp; sb := sb — abs(c[jc] — b[jb]); sc := sc + abs(c[jc] — b[jb]); end; until (jb = 0) and (jc = 0); writeln('1 массив'); v(b, ib); writeln('его сумма ', sb); writeln('2 массив'); v(c, ic); writeln('его сумма ', sc); readln; end.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д