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

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

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] попарно различных чисел. Напечатать все перестановки этих чисел.

Решение

Program perestanowki;

uses WinCrt;

const

mm = 100;

var

m, i, j, k, n : integer;

a, p : array[1..mm] of integer;

begin

write('Введите число эл. для перестановки '); readln(m);

writeln('Введите элементы массива a[1..m]');

for i := 1 to m do

begin

write('Введите ', i, '-й элемент '); readln(a[i]);

p[i] := i

end;

for i := 1 to m do write(a[i], ' '); writeln;

for i := m - 1 downto 1 do

if p[i] < p[i+1] then

begin

n := p[i];

for j := m downto i do

if n < p[j] then

begin

p[i] := p[j]; p[j] := n;

k := 1;

while i + k < m - k + 1 do

begin

n := p[i+k];

p[i+k] := p[m+1-k];

p[m+1-k] := n;

k := k + 1

end;

j := i

end;

for i := 1 to m do write(a[p[i]]:4);

writeln

end

end.

Задача 26. На доске расставить n ладьи неугрожающих друг другу.

Решение

Program Problem26;

uses WinCrt;

const

n = 8;

label 1;

type

u = array[1..n] of longint;

f = array[1..n] of u;

var

p : u;

a : f;

i, z, v, y, l, j : longint;

{----------------------------------------------------------------------------------------}

Procedure output_p(p : u; y, n : longint);

var

i, j : longint;

begin

writeln(y, '-й способ расстановки ладьей');

for i := 1 to n do

begin

a[i][p[i]] := p[i];

for j := 1 to n do

begin

if a[i][j] <> p[i] then a[i][j] := 0; write(a[i][j]:4)

end;

writeln

end

end;

{----------------------------------------------------------------------------------------}

begin

for i := 1 to n do p[i] := n + 1 - i;

z := 1;

for i := 1 to n do z := z*i;

y := 1;

output_p(p, y, n);

for y := 2 to z do

begin

i := 2; j := 1;

while p[i - 1] <= p[i] do i := i + 1;

while p[j] <= p[i] do j := j + 1;

v := p[i]; p[i] := p[j]; p[j] := v;

if i = 2 then goto 1;

for l := 1 to (i - 1) div 2 do

begin

v := p[l]; p[l] := p[i - l]; p[i - l] := v

end;

1: output_p(p, y, n)

end

end.

Задача 27. Процедура определения наибольшей стоимости груза m при заданном его весе z.

Решение

Procedure gen_comb(n, k : integer; z : real; var m : real);

var

i, j, q, b : integer;

begin

for j := 1 to k do

begin

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

end;

i := 0; q := 0; b := 0;

while i<=k do

begin

q := q + 1; s[q] := 0;

for j := k downto 1 do s[q] := s[q] + p[x[j]];

if s[q] = z then

begin

b := b + 1; s1[b] := 0;

for j := k downto 1 do

begin

s1[b] := s1[b] + c[x[j]];

if m < s1[b] then m := s1[b]

end

end;

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

end;