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

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

Условие

Напечатать все последовательности длины k из чисел 1..n.

Решение

Будем печатать их в лексикографическом порядке (последовательность a предшествует последовательности b, если для некоторого s их начальные отрезки длины s равны, а (s+1)-ый член последовательности a меньше). Первой будет последовательность <1,1,...,1>, последней — последовательность <n,n,...,n>. Будем хранить последнюю напечатанную последовательность в массиве x[1]..x[k].

        ...x[1]...x[k] положить равными 1
        ...напечатать x
        ...last[1]...last[k] положить равным n
        {напечатаны все до x включительно}
        while x <> last do begin
        | ...x := следующая за x последовательность
        | ...напечатать x
        end;
Опишем, как можно перейти от x к следующей последовательности. Согласно определению, у следующей последовательности первые s членов должны быть такими же, а (s+1)-ый — больше. Это возможно, если x[s+1] меньше n. Среди таких s нужно выбрать наибольшее (иначе полученная последовательность не будет непосредственно следующей). Соответствующее x[s+1] нужно увеличить на 1. Итак, надо, двигаясь с конца последовательности, найти самый правый член, меньший n (он найдётся,  —к по предположению x<>last), увеличить его на 1, а идущие за ним члены положить равными 1.
        p:=k;
        while not (x[p] < n) do begin
        | p := p-1;
        end;
        {x[p] < n, x[p+1] =...= x[k] = n}
        x[p] := x[p] + 1;
        for i := p+1 to k do begin
        | x[i]:=1;
        end;

Замечание. Если членами последовательности считать числа не от 1 до n, а от 0 до n-1, то переход к следующему соответствует прибавлению единицы в n-ичной системе счисления.

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

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

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

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