Задача 76251
|
|
 |
Условие
Даны два массива x[1]≤...≤x[k] и y[1]≤...≤y[l]. "Соединить" их в массив z[1]≤...≤z[m] ( m = k + l; каждый элемент должен входить в массив z столько раз, сколько раз он входит в общей сложности в массивы x и y). Число действий порядка m.Решение
k1 := 0; l1 := 0;
{инвариант: ответ получится, если к z[1]..z[k1+l1] добавить
справа соединение массивов x[k1+1]..x[k] и y[l1+1]..y[l]}
while (k1 <> k) or (l1 <> l) do begin
| if k1 = k then begin
| | {l1 < l}
| | l1 := l1 + 1;
| | z[k1+l1] := y[l1];
| end else if l1 = l then begin
| | {k1 < k}
| | k1 := k1 + 1;
| | z[k1+l1] := x[k1];
| end else if x[k1+1] <= y[l1+1] then begin
| | k1 := k1 + 1;
| | z[k1+l1] := x[k1];
| end else if x[k1+1] >= y[l1+1] then begin
| | l1 := l1 + 1;
| | z[k1+l1] := y[l1];
| end else begin
| | { такого не бывает }
| end;
end;
{k1 = k, l1 = l, массивы соединены}
Замечание. Этот процесс можно пояснить так. Пусть у нас есть две
стопки карточек, отсортированных по алфавиту. Мы соединяем
их в одну стопку, выбирая каждый раз ту из верхних карточек
обеих стопок, которая идёт раньше в алфавитном порядке.
Если в одной стопке карточки кончились, берём их из другой
стопки.
