Помогите решить!!!
Пусть 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.
Заранее благодарен.
Полная версия: Три последовательности.
Вот есть такой метод :
ps к модераторам : можно его в faq я думаю.
Это не то, извиняюсь :molitva:
type
TArr = array[1..100] of integer;
procedure sliyanie(var Arr1,Arr2,Result:TArr; size1,size2:integer);
var
i,i1,i2,ny:integer;
begin
i1:=1; i2:=1;
ny:=0;
while(i1<=size1)and(i2<=size2) do begin
inc(ny);
if arr1[i1]<=arr2[i2] then begin
result[ny]:=arr1[i1];
inc(i1);
end
else begin
result[ny]:=arr2[i2];
inc(i2);
end;
end;
if i1<=size1 then
for i:=i1 to size1 do begin
inc(ny);
result[ny]:=arr1[i];
end
else
for i:=i2 to size2 do begin
inc(ny);
result[ny]:=arr2[i];
end;
end;
ps к модераторам : можно его в faq я думаю.
Это не то, извиняюсь :molitva:
Попробуй поискать по форуму, по-моему, где-то это уже встречалось (можешь поискать сортировку слияниями)... Но сам алгоритм примерно такой:
P.S.
klem4, в задании 3 (!!!) массива...
Цитата
делать
если i < n то
Пока a[i] < min(b[j], c[k]) добавлять в результат a[i], и inc(i);
если j < m то
Пока b[j] < min(a[i], c[k]) добавлять в результат b[j], и inc(j);
если k < m то
Пока c[k] < min(a[i], b[j]) добавлять в результат c[k], и inc(k);
пока (i+j+k) < (n+m+p)
если i < n то
Пока a[i] < min(b[j], c[k]) добавлять в результат a[i], и inc(i);
если j < m то
Пока b[j] < min(a[i], c[k]) добавлять в результат b[j], и inc(j);
если k < m то
Пока c[k] < min(a[i], b[j]) добавлять в результат c[k], и inc(k);
пока (i+j+k) < (n+m+p)
P.S.
klem4, в задании 3 (!!!) массива...
Да, я уже заметил и покаялся выше 
хотя по такому принципу можно довести до трех массивов я думаю.
хотя по такому принципу можно довести до трех массивов я думаю.
Вот это я нашел на форуме:
Я пробовал "вручную" выполнять эту программу. У меня вроде бы не получилось m+n+p сравнений. Может быть я неправильно делал? Попробуйте сами!
Тегами [CОDE] пользуемся ...
Код
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.
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] пользуемся ...
Ну, и что не устраивает? Правда, потребовались незначительные изменения 
... Вот проверка: частный случай (n = m = p = maxn)...
Вот результат:
Чем не устраивает? (Только не забывай добавлять последним элементом в каждом из 3-х массивов maxInt, иначе не сработает...)
... Вот проверка: частный случай (n = m = p = maxn)...program sliyati_tri_mas;
const
maxn = 10;
type
arr_type = array[1..maxn+1] of integer;
const
a: arr_type = (2, 3, 4, 6, 8, 9, 11, 23, 25, 28, maxint);
b: arr_type = (5, 6, 7, 11, 12, 17, 19, 20, 21, 22, maxint);
c: arr_type = (15, 16, 17, 21, 22, 27, 29, 30, 31, 42, maxint);
function min(i, j: integer): integer;
begin
min := i; if j < i then min := j
end;
var
d: array[1..3*maxn]of integer;
ia,ib,ic,id:integer;
n,m,p:integer;
begin
n := maxn; m := maxn; p := maxn;
ia:=1; ib:=1; ic:=1; id:=0;
while id<n+m+p do begin
while (a[ia] <= min(b[ib], c[ic])) and (ia <= n) do begin
inc(id); d[id]:=a[ia]; inc(ia);
end;
while (b[ib] <= min(a[ia], c[ic])) and (ib <= m) do begin
inc(id); d[id]:=b[ib]; inc(ib);
end;
while (c[ic] <= min(a[ia], b[ib])) and (ic <= p) do begin
inc(id); d[id]:=c[ic]; inc(ic);
end;
end;
for id:=1 to n+m+p do
write(d[id],' ');
end.
Вот результат:
Цитата(Result)
2 3 4 5 6 6 7 8 9 11 11 12 15 16 17 17 19 20 21 21 22 22 23 25 27 28 29 30 31 42
Чем не устраивает? (Только не забывай добавлять последним элементом в каждом из 3-х массивов maxInt, иначе не сработает...)
А сравнений точно не будет больше 30?
Не уверен... Скорее всего будет больше... Но насколько я помню, нельзя сделать это за 30 сравнений. Ни один алгоритм сортировки не отсортирует тебе 30 элементов за 30 сравнений. Если уж на то пошло, то тебе надо просто "склеить" все массивы и пройтись по ним RadixSort-ом (FAQ: Сортировки - RadixSort), там по-моему элементы вообще не сравниваются.
Я наверно тебе уже надоел. Ноесли не сложно, можешь нарисовать блок-схему? Мне завтра прогу сдавать, а я в схемах не понимаю! Пожалуйста!!!!!!!!
Врялдли кто-то будет рисовать такую блок - схему, могу посоветовать только вот это : Программа для построения блок-схем
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.