Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Три последовательности.

Автор: SANCTUS 5.07.2005 17:17

Помогите решить!!!
Пусть 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 5.07.2005 17:31

Вот есть такой метод : 



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:

Автор: volvo 5.07.2005 17:37

Попробуй поискать по форуму, по-моему, где-то это уже встречалось (можешь поискать сортировку слияниями)... Но сам алгоритм примерно такой:

Цитата
делать
  если 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 (!!!) массива...

Автор: klem4 5.07.2005 17:41

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

Автор: SANCTUS 5.07.2005 18:23

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

Код
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:33

Ну, и что не устраивает? Правда, потребовались незначительные изменения rolleyes.gif ... Вот проверка: частный случай (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, иначе не сработает...)

Автор: SANCTUS 5.07.2005 19:13

А сравнений точно не будет больше 30?

Автор: volvo 5.07.2005 19:25

Не уверен... Скорее всего будет больше... Но насколько я помню, нельзя сделать это за 30 сравнений. Ни один алгоритм сортировки не отсортирует тебе 30 элементов за 30 сравнений. Если уж на то пошло, то тебе надо просто "склеить" все массивы и пройтись по ним RadixSort-ом (http://forum.pascal.net.ru/index.php?showtopic=3065&view=findpost&p=32464), там по-моему элементы вообще не сравниваются.

Автор: SANCTUS 5.07.2005 19:57

Я наверно тебе уже надоел. Ноесли не сложно, можешь нарисовать блок-схему? Мне завтра прогу сдавать, а я в схемах не понимаю! Пожалуйста!!!!!!!!

Автор: klem4 5.07.2005 20:45

Врялдли кто-то будет рисовать такую блок - схему, могу посоветовать только вот это : http://forum.pascal.net.ru/index.php?showtopic=4270