Кодинг
★ Рубрика: Кодинг
★ Тема: Алгоритмы

Возрастающие последовательности чисел

Задача. Напечатать все возрастающие последовательности длины k, элементами которых являются натуральные числа от 1 до n. Предполагается, что k не превосходит n - иначе таких последовательностей не существует. Решение. Программа оперирует с массивом a[1]..a[k] и целой переменной t. Предполагая, что a[1]..a[t] - возрастающая последовательность чисел натуральных чисел из отрезка 1..n, рекурсивно определенная процедура generate печатает все ее возрастающие продолжения длины k.
procedure generate;
 | var i: integer;
 begin
 | if t = k then begin
 | | печатать a[1]..a[k]
 | end else begin
 | | t:=t+1;
 | | for i:=a[t-1]+1 to t-k+n do begin
 | | | a[t]:=i;
 | | | generate;
 | | end;
 | | t:=t-1;
 | end;
 end;
Замечание. Цикл for мог бы иметь верхней границей n (вместо t-k+n). Наш вариант экономит часть работы, учитывая тот факт, что предпоследний (k-1-ый) член не может превосходить n-1, k-2-ой член не может превосходить n-2 и т.п. Основная программа теперь выглядит так:
t:=1;
 for j:=1 to 1-k+n do begin
 | a[1]:=j;
 | generate;
 end;
Можно было бы добавить к массиву a слева еще и a[0]=0, положить t=0 и ограничиться единственным вызовом процедуры generate.
 Похожие публикации: Алгоритмы

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]