Разработка системы задач (алгоритмы-программы) по дискретной математике — страница 12

  • Просмотров 5607
  • Скачиваний 210
  • Размер файла 88
    Кб

написать алгоритм-программу, которая укажет станции, через которые напарнику придется пройти, чтобы очутиться в нужной станции за минимальное время. Начальная и конечная станции вводятся с клавиатуры. Решение. Данную таблицу можно рассматривать как матрицу смежности и построить по ней граф, который наглядно отобразит схему дорог из одной станции в другую. Таким образом можно применить один из алгоритмов поиска кратчайших

путей, в данном случае наиболее удобно использовать алгоритм Флойда, который позволит не только найти минимальное время, которое потребуется напарнику, но и сам путь. Временная сложность данного алгоритма пропорциональна О(N3). (Текст программы см. Приложение 9) Игра «Найди друга». Всем ребятам выдаются карточки с номерами, они выстраиваются в ряд, по возрастанию номеров. Ребенку, который водит, также выдается карточка с номером.

Считается, что ребенок нашел друга, если номер на его карточке совпадает с номером человека, к которому он подходит. Написать алгоритм – программу, которая позволит ребенку найти друга так, чтобы ребенок подходил к минимальному количеству участников. В случае если невозможно найти друга программа выводит результат «No», если же это возможно, то программа должна выводить количество детей, к которым подходил «вожа». Примечание:

номера детей определяются с помощью датчика случайных чисел, а номер ребенка, который водит, вводится с клавиатуры. Решение. Так как мы знаем, что ребята расположены по возрастанию номеров на карточке, то наиболее быстрый способ найти друга можно реализовать с помощью бинарного поиска. (Текст программы см. Приложение 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]<Degree2(k)then {смотрим имеет ли клетка стену в заданном направлении} begin If not B[i+X[k],j+Y[k]] then {определяем, заходили ли мы в клетку ранее} begin Inc(col); {учитываем клетку в общей площади комнаты} B[i,j]:=true; {отмечаем, что в текущей клетке мы уже были} Solve(i+X[k],j+Y[k]); {переходим в следующую клетку} B[i,j]:=False; {делаем клетку, в которой последний раз были не просмотренной, чтобы рассмотреть другие