Разбить предметы на две группы так, чтобы массы в обеих группах были максимально одинаковые - Turbo Pascal

Узнай цену своей работы

Формулировка задачи:

Дано N предметов различной массы. Массы предметов записаны в массиве A [1..N]. Нужно разбить их на две группы таким образом, чтобы массы в обеих группах были максимально одинаковые.
Ввел начальную инфу и попытался задать параметры массива, а вот как всё это поделить на ровные части не пойму... какие строчки прописать нужно и т.д., да и в первом не уверен... прошу помогите(

Решение задачи: «Разбить предметы на две группы так, чтобы массы в обеих группах были максимально одинаковые»

textual
Листинг программы
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.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 4.2 из 5
Похожие ответы