Дано:
- область памяти начиная с адреса A содержащая N чисел (CELLS) последовательно;
- первые N1<N чисел упорядочены по возрастанию;
- следующие N2=N-N1 чисел тоже упорядочены по возрастанию;
- размеры областей могут быть в пределах: 0<N1<2^29; 0<N2<2^29.
Пример последовательности для N1=5, N2=4: 3, 9, 23, 23, 41, 21, 22, 93, 112
Требуется:
- разместить все N чисел в порядке возрастания.
Для вышеприведенного примера результат должен быть: 3, 9, 21, 22, 23, 23, 41, 93, 112
Ресурсы:
- алгоритм представить на Форте в соответствии с http://fforum.winglion.ru/viewtopic.php?p=7402#7402 ;
- не допускается применение ассемблера;
- можно использовать дополнительные области памяти (переменные, буферы, и т.д.) только фиксированного размера, независимого от N и суммарным обьемом не более 1024Кб.
Критерий оценки:
- решение должно быть более эффективным за представленный ниже пример;
- достижение максимальной скорости выполнения (на уровне алгоритма);
- использование минимальных ресурсов.
Пример тривиального решения задачи (ANSI):
Код:
\ a1 - адресс первой области, равен A
\ n1 - количество чисел в первой последовательности
\ a2 - адресс второй области, равен: a1 n1 CELLS +
\ n2 - количество числе во второй последовательности, равно N-N1
: MERGE ( a1 n1 a2 n2 )
LOCALS| N2 A2 N1 A1 | \ используются локальные переменные для наглядности
BEGIN
A1 @ A2 @ < \ смотрим откуда брать минимальное число
IF \ если оно в первой последовательности, просто его пропускаем
A1 CELL+ TO A1
N1 1- TO N1
ELSE \ если оно во второй, делаем ротацию:
A2 @ \ читаем число из второй последовательности
\ перемещаем остаток первой последовательности на одно число вверх:
A1 DUP DUP CELL+ DUP TO A1 N1 CELLS MOVE
! \ сохраняем минимальное число в освободившееся место
\ переходим к следующему числу второй последовательности:
A2 CELL+ TO A2
N2 1- TO N2
THEN
N1 0= N2 0= OR \ завершаем работу по исчерпанию любой последовательности
UNTIL
;
\ n1 - количество чисел в первой последовательности
\ a2 - адресс второй области, равен: a1 n1 CELLS +
\ n2 - количество числе во второй последовательности, равно N-N1
: MERGE ( a1 n1 a2 n2 )
LOCALS| N2 A2 N1 A1 | \ используются локальные переменные для наглядности
BEGIN
A1 @ A2 @ < \ смотрим откуда брать минимальное число
IF \ если оно в первой последовательности, просто его пропускаем
A1 CELL+ TO A1
N1 1- TO N1
ELSE \ если оно во второй, делаем ротацию:
A2 @ \ читаем число из второй последовательности
\ перемещаем остаток первой последовательности на одно число вверх:
A1 DUP DUP CELL+ DUP TO A1 N1 CELLS MOVE
! \ сохраняем минимальное число в освободившееся место
\ переходим к следующему числу второй последовательности:
A2 CELL+ TO A2
N2 1- TO N2
THEN
N1 0= N2 0= OR \ завершаем работу по исчерпанию любой последовательности
UNTIL
;
Этот вариант в худшем случае выполняет копирование N1*N2 чисел. Требуется более быстрое решение.
Желаю удачи!
]