Var I,j:integer;

BEGIN

FOR l:=1 TO N DO

FOR J:=l TO N DO

IF I=J THEN METR[I,J]:= 0

ELSE

BEGIN

METR[I,J]:=1 + RANDOM(N);

METR[J,I]:=METR[I,J];

END;

END;

PROCEDURE OUT_METR;

{Вывод матрицы на экран}

Var I,j:integer;

BEGIN

FOR l:=1 TO N DO

BEGIN

FOR J:=1 TO N DO

WRITE (METR[I,J]:4);

WRITELN;

END;

END;

BEGIN

WRITELN('BBEДИTE РАЗМЕР МАТРИЦЫ');

READLN(N);

In_metr;

OUT_METR;

WRITELN('BBEДИTE НОМЕР ГОРОДА, ИЗ КОТОРОГО НАЧИНАЕТСЯ МАРШРУТ');

READLN(X);

М:=[Х];

STR[1]:=X;

А:=Х;

FOR J:=1 TO N-1 DO

BEGIN

MIN:= MAXINT;Y:=1;

FOR l:=1 TO N DO

IF (METR[X,I]<MIN)AND NOT(I IN M)AND(METR[X,l]<>0) THEN

BEGIN

MIN:=METR[X,I];

Y:=l;

END;

COST:=COST+MIN;

M:=M+[Y];

STR[J+1]:=Y;

X:=Y

END;

WRITELN('COST =', COST + METR[A,X]);

FOR l:=1 TO N DO

WRITE(STR[I]:5);

WRITELN(' ',A);

END.

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

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

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

- создаем описание процедуры OUTMETR для вывода мат­рицы расстояний на экран;

- в основной программе вызываем процедуры IN_METR и OUT_METR, вводим город X, из которого начинаем движение;

- организуем два вложенных цикла, с помощью которых нахо­дим самый короткий маршрут;

- выводим результат на экран.

Переменные:

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

I, J - переменные циклов.

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

I, J - переменные циклов.

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

М - множество городов, которые посетил коммивояжер;

STR - последовательность городов в самом коротком маршруте;

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

А - первый город, из которого коммивояжер начинает маршрут;

L, X, Y, MIN - вспомогательные переменные;

J, I - переменные циклов;

COST - стоимость наименьшего маршрута, т. е. его длина;

METR - матрица расстояний.

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

5

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

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

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

2

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 - очередная перестановка чисел.

3

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 и кончается в этом же городе. Для решения за­дачи использовать генератор перестановок.

PROGRAM PRG13_5;

{ПЕРЕБОРНЫЙ АЛГОРИТМ}

TYPE SS=SET OF 1..10;

VAR

S:SS;

MAS, PATH:ARRAY[1..1O] OF INTEGER;

M, N, X, J, I, MIN :INTEGER;

METR : ARRAY [1-10, 1.-10] OF BYTE;

PROCEDURE IN_METR;

{Формирование матрицы}

VAR l,J:INTEGER;

BEGIN

FOR l:=1 TO N DO

FOR J:=l TO N DO

IF I=J THEN METR[I,J]:= 0

ELSE

BEGIN

METR[I,J]:=1 + RANDOM(N);

METR[J,I]:=METR[I,J];

END;

END;

PROCEDURE OUT_METR;

{Вывод матрицы на экран}

VAR I,J:INTEGER;

BEGIN

FOR l:=1 TO N DO

BEGIN

FOR J:=1 TO N DO

WRITE (METR[I,J]:4);

WRITELN;

END;

END;

FUNCTION COST:INTEGER;

{Определение стоимости маршрута}

VAR I,T,A,B HNTEGER;

BEGIN

T:=0;

FOR l:=1 TO N-1 DO

BEGIN

A:= MAS[I];

B:= MAS[I+1];

T:=T+ METR[A,B];

END;

A:= MAS[1];

B:=MAS[N];

COST:=T+ METR[A,B];

END;

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

{Генератор маршрутов}

VAR I,G,C: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

C:=COST;

IF MIN>C THEN

{ОПРЕДЕЛЕНИЕ НАИМЕНЬШЕЙ СТОИМОСТИ МАРШРУТА}

BEGIN

MIN:=C;

FOR G:=1 TO N DO

PATH[G]:=MAS[G];

END;

END;

END;

BEGIN

WRITELN('BBEДИTE РАЗМЕР МАТРИЦЫ');

READLN(N);

IN_METR;

OUT_METR;

S:=[1..N];

MIN:=MAXINT;

{ПОРОЖДЕНИЕ ВСЕХ ВОЗМОЖНЫХ МАРШРУТОВ И ПОИСК НАИМЕНЬШЕГО}

FOR l:=1 TO N DO

PER(S,1,I);

WRITELN('BBEДИTE НОМЕР ГОРОДА, ИЗ КОТОРОГО НАЧИНАЕТСЯ МАРШРУТ');

READLN(X);

FOR l:=1 TO N DO

IF PATH[I]=X THEN M:=l;

FOR l:= M TO N DO

WRITE (PATH[I]:4);

WRITE(' ');

FOR l:=1 TO M DO

WRITE (PATH[I]:4);

WRITELN(' COST =', MIN);

END.

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

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

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

- создаем описание процедуры OUTJMETR для вывода мат­рицы расстояний на экран;

- в основной программе вызываем процедуры IN_METR и OUT_METR, вводим город X, из которого начинаем движе­ние;

- организуем два вложенных цикла, с помощью которых нахо­дим самый короткий маршрут;

- выводим результат на экран.

Переменные:

в процедуре TN_METR;

I, J - переменные циклов;

в процедуре OUT_METR;

I, J - переменные циклов;

в функции COST;

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

Т, А, В - вспомогательные переменные;

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

I, J - переменные циклов;

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

С - вспомогательная переменная;

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

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

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

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

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

MAS - очередная перестановка из городов (маршрут);

PATH - последовательность городов в самом коротком маршруте;

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

X, MIN - вспомогательные переменные;

J, I - переменные циклов;

METR - матрица расстояний.

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

5

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

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

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

2

2 5 4 3 1 2 COST = 8

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