Три последовательности. Опции

[SANCTUS]

Помогите решить!!!
Пусть A=(a1,a2,…,an), B=(b1,b2,…,bm), C=(c1,c2,…,cp) – три конечные последовательности натуральных чисел. Допустим, что каждая отдельно взята последовательность упорядочена по возрастанию. Объедините три последовательности в одну последовательность D=(d1,d2,…,dn+m+p), являющуюся списком всех чисел из А, В, С, такую, что d1≤d2≤…≤dn+m+p.
Обязательным условием является то, что слияние должно быть выполнено за m+n+p действий, т.е. число сравнений должно быть не больше m+n+p.

Заранее благодарен.

[klem4]

Да, я уже заметил и покаялся выше
хотя по такому принципу можно довести до трех массивов я думаю.

Сообщение отредактировано: klem4 - 5.07.2005 17:42

[SANCTUS]

Вот это я нашел на форуме:

Код

program sliyati_tri_mas;
const maxn=1000;
var a,b,c:array[1..maxn+1]of integer;
  d:array[1..3*maxn]of integer;
  ia,ib,ic,id:integer;
  n,m,p:integer;

begin
 read(n);
 for ia:=1 to n do read(a[ia]);
 a[n+1]:=maxint;
 read(m);
 for ib:=1 to m do read(b[ib]);
 b[m+1]:=maxint;
 read(p);
 for ic:=1 to p do read(c[ic]);
 c[p+1]:=maxint;
 ia:=1;
 ib:=1;
 ic:=1;
 id:=0;
 while id<n+m+p do
 begin
    if a[ia]<b[ib] then
    begin
       if a[ia]<c[ic] then
          begin
             inc(id);
             d[id]:=a[ia];
             inc(ia);
          end else
             begin
                inc(id);
                d[id]:=c[ic];
                inc(ic);
             end;
    end else
       begin
          if  b[ib]<c[ic] then
             begin
                inc(id);
                d[id]:=b[ib];
                inc(ib);
             end else
                begin
                   inc(id);
                   d[id]:=c[ic];
                   inc(ic);
                end;
       end;
 end;
 for id:=1 to n+m+p do
    write(d[id],' ');
end.

Я пробовал "вручную" выполнять эту программу. У меня вроде бы не получилось m+n+p сравнений. Может быть я неправильно делал? Попробуйте сами!

Тегами [CОDE] пользуемся ...

Сообщение отредактировано: volvo - 5.07.2005 18:35