IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Три последовательности.
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


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

Заранее благодарен.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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



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:

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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)


P.S.
klem4, в задании 3 (!!!) массива...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


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

Код
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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Ну, и что не устраивает? Правда, потребовались незначительные изменения 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, иначе не сработает...)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


А сравнений точно не будет больше 30?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Не уверен... Скорее всего будет больше... Но насколько я помню, нельзя сделать это за 30 сравнений. Ни один алгоритм сортировки не отсортирует тебе 30 элементов за 30 сравнений. Если уж на то пошло, то тебе надо просто "склеить" все массивы и пройтись по ним RadixSort-ом (FAQ: Сортировки - RadixSort), там по-моему элементы вообще не сравниваются.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Я наверно тебе уже надоел. Ноесли не сложно, можешь нарисовать блок-схему? Мне завтра прогу сдавать, а я в схемах не понимаю! Пожалуйста!!!!!!!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Врялдли кто-то будет рисовать такую блок - схему, могу посоветовать только вот это : Программа для построения блок-схем


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:24
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name