ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 76251
Тема:    [ Одномерные массивы ]
Сложность: 2
Классы:
В корзину
Прислать комментарий

Условие

Даны два массива 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, массивы соединены}

Замечание. Этот процесс можно пояснить так. Пусть у нас есть две стопки карточек, отсортированных по алфавиту. Мы соединяем их в одну стопку, выбирая каждый раз ту из верхних карточек обеих стопок, которая идёт раньше в алфавитном порядке. Если в одной стопке карточки кончились, берём их из другой стопки.

Источники и прецеденты использования

книга
Автор А.Шень
Название Программирование: теоремы и задачи
Издательство МЦНМО
Издание второе
Год издания 2004
глава
Номер 1
Название Переменные, выражения, присваивания
параграф
Номер 2
Название Массивы
задача
Номер 1.2.20

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .