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 - матрица расстояний.