Задача 98820
|
|
 |
Условие
Напечатать все последовательности длины 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-ичной системе счисления.
