A(a1,a2,..an),B(b1,b2,..bm),C(c1,c2,..,cp)-три конечные последовательности натуральных чисел.Каждая из них упорядоченна по возрастанию.
Слить три в одну D(d1,d2,..,d(n+m+p)),такую что d1<=d2<=d3<=..<=d(n+m+p)
1,2,..,n+m+p-индексы
обязательное условие слияние должно быть выполнено за n+m+p сравнений
Вот такая задачка.Помогите, пожалуйста!
HelpAusHeaven
23.05.2004 7:02
И чего тут сложного?
Пример:
A := {3,8,15,17} n=4;
B := {1,9,11} m=3;
C := {2,6,80,90} p=4;
D последовательность получаем сравниванием сначала всех первых элементов, далее вторых и т.д. кол-во сравнений при этом будет ровно 12, т.е. n+m+p....
to Дашка: Программку написать или хотите самостоятельно сообразить?
Код
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.