Три последовательности. |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Три последовательности. |
SANCTUS |
Сообщение
#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. Заранее благодарен. |
klem4 |
Сообщение
#2
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Вот есть такой метод :
ps к модераторам : можно его в faq я думаю. Это не то, извиняюсь :molitva: Сообщение отредактировано: klem4 - -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
volvo |
Сообщение
#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 (!!!) массива... |
klem4 |
Сообщение
#4
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Да, я уже заметил и покаялся выше
хотя по такому принципу можно довести до трех массивов я думаю. Сообщение отредактировано: klem4 - -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
SANCTUS |
Сообщение
#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 - |
volvo |
Сообщение
#6
|
Гость |
Ну, и что не устраивает? Правда, потребовались незначительные изменения ... Вот проверка: частный случай (n = m = p = maxn)...
program sliyati_tri_mas; Вот результат: Цитата(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 |
Сообщение
#7
|
Группа: Пользователи Сообщений: 4 Пол: Мужской Репутация: 0 |
А сравнений точно не будет больше 30?
|
volvo |
Сообщение
#8
|
Гость |
Не уверен... Скорее всего будет больше... Но насколько я помню, нельзя сделать это за 30 сравнений. Ни один алгоритм сортировки не отсортирует тебе 30 элементов за 30 сравнений. Если уж на то пошло, то тебе надо просто "склеить" все массивы и пройтись по ним RadixSort-ом (FAQ: Сортировки - RadixSort), там по-моему элементы вообще не сравниваются.
|
SANCTUS |
Сообщение
#9
|
Группа: Пользователи Сообщений: 4 Пол: Мужской Репутация: 0 |
Я наверно тебе уже надоел. Ноесли не сложно, можешь нарисовать блок-схему? Мне завтра прогу сдавать, а я в схемах не понимаю! Пожалуйста!!!!!!!!
|
klem4 |
Сообщение
#10
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Врялдли кто-то будет рисовать такую блок - схему, могу посоветовать только вот это : Программа для построения блок-схем
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Текстовая версия | 15.05.2024 9:47 |