добразить схему доріг з однієї станції в іншу. Таким чином можна застосувати один з алгоритмів пошуку найкоротших шляхів, в даному випадку найбільш зручно використовувати
алгоритм Флойда , який дозволить не тільки знайти мінімальний час, який буде потрібно напарникові, а й сам шлях. Тимчасова складність даного алгоритму пропорційна О (N 3 ).
(Текст програми див. Додаток 9)
Гра В«Знайди одного В». Всім хлопцям видаються картки з номерами, вони шикуються в ряд, по зростанню номерів. Дитині, яка водить, також видається картка з номером. Вважається, що дитина знайшла одного, якщо номер на його картці збігається з номером людини, до якого він підходить. Написати алгоритм - програму, яка дозволить дитині знайти друга так, щоб дитина підходив до мінімального кількістю учасників. У разі якщо неможливо знайти друга програма виводить результат В«NoВ», якщо ж це можливо, то програма повинна виводити кількість дітей, до яких підходив В«вожанВ». p> Примітка: номери дітей визначаються за допомогою датчика випадкових чисел, а номер дитини, який водить, вводиться з клавіатури. p> Рішення . Так як ми знаємо, що хлопці розташовані по зростанню номерів на картці, то найбільш швидкий спосіб знайти друга можна реалізувати за допомогою бінарного пошуку.
(Текст програми див. Додаток 10)
Додаток.
1 Кімнати музею.
Uses crt;
Const n = 100;
X: array [0 .. 3] of -1 .. +1 = (0, -1,0,1); {масив координат переміщення по
Y: array [0 .. 3] of -1 .. 1 = (-1,0,1,0); клітинам. Індекс елемента масиву
Type Mas = array [0 .. n, 0 .. n] of Integer; відповідає ступеню двійки}
var A: mas;
B: array [0 .. n, 0 .. n] of Boolean;
m, p, col, rooms, indexX, indexY: integer;
procedure Init (Z: string); {Заповнення з вхідного файлу масиву, що представляє цифрову карту музею}
Var f: text;
i, j: integer;
Begin
Assign (f, z);
Reset (f);
ReadLn (f, m, p);
For i: = 1 to m do
begin
For j: = 1 to p do
Read (f, A [i, j]);
ReadLn (f);
end;
FillChar (B, SizeOf (B), true);
For i: = 1 to m do
For j: = 1 to p do
B [i, j]: = false;
Close (f);
end;
function Degree2 (i: integer): integer; {функція, обчислює i-ую ступінь двійки}
var j, t: integer;
begin
t: = 1;
For j: = 1 to i do
t: = t * 2;
Degree2: = t;
end;
Procedure Solve (i, j: integer);
Var k: integer;
begin
k: = 3;
While k> = 0 do
begin
If A [i, j]
begin
If not B [i + X [k], j + Y [k]] then {визначаємо, заходили ми в клітку раніше}
begin
Inc (col); {Враховуємо клітку ...
