ВВЕДИТЕ РАЗМЕР МАТРИЦЫ

0 1 1 5 2

1 0 2 4 2

1 2 0 1 2

5 4 1 0 3

2 2 2 3 0

ВВЕДИТЕ НОМЕР ГОРОДА, ИЗ КОТОРОГО

НАЧИНАЕТСЯ МАРШРУТ

COST = 8

2 1 3 4 5 2

Рис. 13.1. Результат работы программы PRG13_3

Задача 13.4 Дано множество из N чисел (1, 2,..., N). Постро­ить рекурсивную процедуру (генератор перестано­вок), которая порождает все возможные пере­становки без повторений из этих чисел (N < 11). Например, для N = 3 существует 6 перестановок:

123 1 32 23 1 2 1 3 3 1 2 32 1.

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

PR - множество чисел, из которых выполняется перестановка;

К - позиция, которая заполняется в перестановке;

J - число, которое заполняет К-ю позицию.

В самой процедуре используется множество S1, которое умень­шается на каждом шагу перестановки.

PROGRAM PRG13_4;

{ГЕНЕРАТОР ПЕРЕСТАНОВОК}

CONST M=5;

TYPE SS=SET OF 1..M;

VAR

S:SS;

I,N:INTEGER;

MAS:ARRAY[1..M] OF INTEGER;

PROCEDURE PER(VAR PR:SS;K,J:INTEGER);

{Генерация перестановки в массиве MAS}

VAR I:INTEGER;

S1:SS;

BEGIN

MAS[K]:=J;

S1:=PR-[J];

FOR l:=1 TO N DO

IF I IN S1 THEN

PER(S1,K+1,I);

IF K=N THEN

BEGIN

FOR l:=1 TO N DO

WRITE(MAS[I]:5);

WRITELN

END;

END;

BEGIN

READLN(N);

S:=[1-N];

FOR I:= 1 TO N DO

PER(S,1,I);

END.

Для решения задачи:

- формируем тело программы и описьгеаем переменные;

- создаем описание процедуры IN_METR для формирование матрицы расстояний METR;

- создаем описание рекурсивной процедуры PER(PR, К, J) для порождения всех возможных перестановок и вывода их на экран;

- в основной программе считываем размер множества чисел;

- вызываем процедуру PER для порождения и вывода перестав новок на экран.

Переменные:

в процедуре PER:

I - переменная цикла;

S1 - множество чисел, которое может участвовать в перестановке;

в основной программе:

S - множество чисел для перестановки;

I - переменная цикла;

N-количество чисел;

MAS - очередная перестановка чисел.

 

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Рис. 13.2. Результат работы программы PRG13_4

Задача 13.5 Дано множество из N городов (N < 11), между которыми проложены дороги, длина дорог из­вестна. В каком порядке должен посетить их коммивояжер, чтобы путь его был самым ко­ротким? Маршрут начинается в городе i и кончается в этом же городе. Для решения за­дачи использовать генератор перестановок.