Решение. Program Generator_combination; {Генератор сочетаний}

Program Generator_combination; {Генератор сочетаний}

uses WinCrt;

const

n = 5; k = 3; n1 = 100;

type

t = array [1..n1] of integer;

var

x, min, max: t;

i, j, r: integer;

begin

for j: = 1 to k do

begin

max[j]: = n - j + 1; min[j]: = k - j + 1; x[j]: = min[j]

end;

writeln('Сочетания из ', n, ' элементов по ', k, ' элементов');

while i < = k do

begin

for j: = k downto 1 do write(x[j], ' '); writeln;

r: = r + 1; i: = 1;

while (i < = k) and (x[i] = max[i]) do i: = i + 1;

if i < = k then x[i]: = x[i] + 1;

for j: = i - 1 downto 1 do

begin

min[j]: = x[j + 1] + 1;

x[j]: = min[j]

end

end;

writeln('Общее число сочетаний равно r = ', r)

end.

Работа программы

С помощью цикла:

for j: = 1 to k do

Begin

max[j]: = n - j + 1; min[j]: = k - j + 1; x[j]: = min[j]

end;

задаются первоначальные значения max[j], min[j] и x[j], которые получают следующие значения (для n = 5, k = 3):

max[1] = 5, max[2] = 4, max[3] = 3;

min[1] = 3, min[2] = 2, min[3] = 1;

x[1] = 3, x[2] = 2, x[3] = 1.

Начинается основной цикл " пока ", (while i < = k do). Первым оператором цикла является вывод на экран первой тройки значений x[j]. Это делается с помощью цикла:

for j: = k downto 1 do write(x[j]: 8); writeln;

С помощью этого же цикла будут выводиться на экран и следующие сочетания.

Итак, первоначальный вывод элементов будет таким:

1 2 3

Счетчик числа сочетаний - r получает первое значение - 1. Что делается следующим циклом?

i: = 1;

while (i < = k) and (x[i] = max[i]) do i: = i + 1;

Во-первых, он проверяет значение i, выполняется, если i < = k и При первом шаге значение i = 1, что меньше 3, x[1] = 3, max[1] = 5, значит равенство x[i] = max[i] не выполняется, а значит цикл выполняться не будет и значение i остается равным 1.

Следуем дальше по программе. Мы видим условие:

if i < = k then x[i]: = x[i] + 1;

Условие i < = k выполняется (1 < = 3), тогда значение x[1] становится равным:

x[1]: = x[1] + 1, x[1]: = 3 + 1 = 4.

Итак, в результате работы этого оператора последний элемент множества увеличивается на 1.

Следующий цикл:

for j: = i - 1 downto 1 do

Begin

min[j]: = x[j+1] + 1; x[j]: = min[j]

End

будет выполняться только тогда, когда значение i будет больше 1. В данном случае i = 1, первоначальное значение j равно 0 и цикл выполняться не будет.

Основной цикл while i < = k do (1 < = 3) повторяется.

На экран выдается следующая группа сочетаний:

1 2 4.

r = 2,

i = 1, x[1] = 4, max[1] = 5, x[1] = 5.

Основной цикл выполняется, на экран выдается:

1 2 5.

r = 3.

Цикл while (i < = k) and (x[i] = max[i]) do i: = i + 1; будет выполняться, так как (1 < = 3) и (5 = 5). Он будет выполнен только один раз. Почему? Значение i при первом его выполнении получит значение: i: = i + 1, i = 2. При последующей проверке условия этого цикла оказывается, что оно не выполняется. В самом деле: (2 < = 3), но x[2] = 2 не равно max[2] = 4.

Следующий оператор: if i < = k then x[i]: = x[i] + 1 будет выполняться, но уже x[2] увеличиться на 1 и станет равным: x[2] = 2 + 1 = 3. Как видите, когда последний элемент сочетания стал наибольшим, начинает увеличиваться на 1 предпоследний элемент.

Здесь мы видим словарный принцип построения сочетаний.

Далее будет выполнен и цикл по j только один раз (j: = i - 1, j = 2 - 1 = 1). В результате выполнения этого цикла, нижняя граница min[1] станет равна:

min[1] = [2] + 1 = 3 + 1 = 4, а x[1] = min[1] = 4.

В результате, при последующем выполнением основного цикла на экран будут выданы элементы:

1 3 4.

Все остальные операторы основного цикла, кроме условного выполняться не будут. В результате выполнения условного оператора if i < = k then x[i]: = x[i] + 1, x[1] получит значение: x[1]: = 4 + 1 = 5.

Дальнейший процесс повторяется и на экран последовательно будут выданы сочетания:

1 3 5, 1 4 5, 2 3 4, 2 3 5, 2 4 5, 3 4 5.

Задача 25. Задан массив a[1..m] попарно различных чисел. Напечатать все перестановки этих чисел.