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

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

Вятский Государственный Гуманитарный Университет

Кафедра прикладной математики

Курсовая работа по информатике

Тема: Разработка системы упражнений и задач (алгоритмы-программы) по

дискретной математике.

Выполнил:Студент 4 курса

факультета информатики

Лепешкин Антон Геннадъевич

Проверила: Ашихмина Татьяна Викторовна

Киров 2004

Содержание.

Содержание. 2

Введение. 3

Глава 1 Теоретический материал. 4

Перебор с возвратом. 4

Поиск данных. 5

Логарифмический(бинарный) поиск 5

Методы сортировки. 6

Сортировка слияниями. 6

Быстрая сортировка Хоара. 6

Графы. 6

Представление графа в памяти компьютера 6

Достижимость 7

Кратчайшие пути. 8

Алгоритм Дейкстры 8

Алгоритм Флойда (кратчайшие пути между всеми парами вершин). 9

Глава 2 Система задач и упражнений. 9

Классификация задач. 9

Комнаты музея. 12

Пират в подземелье. 13

Диспетчер и милиция. 14

Задача о футболистах. 15

Задача о семьях. 16

Метро. 16

Роботы. 17

Вожатый в лагере 20

Егерь. 21

Игра «Найди друга». 22

Приложение. 22

1 22

2 25

3 27

4 30

5 32

6 32

7 34

8 39

9 41

10 43

Заключение. 45

Литература 45

Введение.

Несмотря на то, что для решения задач в основном используются общие методы,

все-таки мышление каждого конкретного человека немного отличается от

мышления других людей, если он обладает достаточной базой знаний. Таким

образом, при решении задач «начиная с нуля» можно зайти в тупик, если

выбрать неверный путь решения задачи. В данном курсовом проекте мы

разработаем собственную классификацию задач, позволяющую определить

наиболее подходящий способ решения, чтобы облегчить процесс моделирования и

составления алгоритма и предотвратить выбор неверного способа, также

рассмотрим данную классификацию с точки зрения методики преподавания

информатики. выбор неверного способа. В этом заключается актуальность

данного курсового проекта.

Цель: Разработать собственную классификацию для задач по дискретной

математике. Для достижения этой цели были поставлены следующие задачи:

1) Разработать собственную систему задач и упражнений по дискретной

математике.

2) Определить способы решения данных задач, используя теоретический

материал курса дискретной математики.

3) Составить алгоритм – программу для каждой задачи, реализующий

выбранный способы решения.

4) Разработать систему критериев классификации данной системы задач.

Глава 1 Теоретический материал.

Перебор с возвратом.

Общая схема

Даны N упорядоченных множеств U1 U2,..., Un (N - известно), и требуется

построить вектор А=(а1 а2, ..., аn), где a1€U1, a2€U2, ..., an€Un,

удовлетворяющий заданному множеству условий и ограничений.

В алгоритме перебора вектор А строится покомпонентно слева

направо. Предположим, что уже найдены значения первых (к-1)

компонент, A=(a1, a2, ..., a(k-1)), ?, ..., ?), тогда заданное множество

условий ограничивает выбор следующей компоненты аk некоторым

множеством SkCUk. Если Sk<>[ ] (пустое), мы вправе выбрать в

качестве ак

наименьший элемент Sk и

перейти к выбору ^/^ "^выборы п«я»,

(к+1) компоненты и

так далее. Однако /[ + Д Jfcv при данном а,

если условия условия

а,, ^иаз

таковы, что Sk оказалось пустым, то мы возвращаемся к выбору

(к-1) компоненты, отбрасываем

а(k-1) и выбираем в качестве нового a(k-1) тот элемент S(k-i), который

непосредственно следует за только что отброшенным. Может оказаться, что для

нового a(k-1) условия задачи допускают непустое Sk, и тогда мы пытаемся

снова выбрать элемент ак. Если невозможно выбрать a(k-1), мы возвращаемся

еще на шаг назад и выбираем новый элемент а(к-2) и так далее.

Графическое изображение - дерево поиска. Корень дерева (0 уровень)

есть пустой вектор. Его сыновья суть множество кандидатов для выбора а1 и,

в общем случае, узлы k-го уровня являются кандидатами на выбор ак при

условии, что а1, а2, ..., a(k-1) выбраны так, как указывают предки этих

узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются

ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим

получить все такие узлы.

Рекурсивная схема реализации алгоритма,

procedure Backtrack(Beктop,i);

begin

if then

else begin ;

for a€Si do Васкtrаск(вектор| | a,i+l);

end; end;

Оценка временной сложности алгоритма. Данная схема реализации перебора

приводит к экспоненциальным алгоритмам. Действительно, Пусть все решения

имеют длину N, тогда исследовать требуется порядка | Si| *| S2| *...*| SN|

узлов дерева. Если значение S; ограничено некоторой константой С, то

получаем порядка CN узлов.

Поиск данных.

Логарифмический(бинарный) поиск

Логарифмический (бинарный или метод деления пополам) поиск данных применим

к сортированному множеству элементов а1 < а2 < ... < ап, размещение

которого выполнено на смежной памяти. Для большей эффективности поиска

элементов надо, чтобы пути доступа к ним стали более короткими, чем просто

последовательный перебор. Наиболее очевидный метод: начать поиск со

среднего элемента, т.е. выполнить сравнение с элементом а. Результат

сравнения позволит определить, в какой половине последовательности а{,

а2,..., а, 1+„ ,,..., ап продолжить поиск,

применяя к ней ту же процедуру, и т.д. Основная идея бинарного поиска

довольно проста, однако «для многих хороших программистов не одна попытка

написать правильную программу закончилась неудачей». Чтобы досконально

разобраться в алгоритме, лучше всего представить данные ах < а2 < ... < ап

в виде двоичного дерева сравнений, которое отвечает бинарному поиску.

Двоичное дерево называется деревом сравнений , если для любой его вершины

(корня дерева или корня поддерева) выполняется условие:

{Вершины левого поддерева}, s - вершина источник; матрица смежности

A (A:array[1..n,1..n] of integer); для любых u, v€V вес дуги

неотрицательный (А[u,v]>=0). Результат. Массив кратчайших расстояний - D.

В данном алгоритме формируется множество вершин Т, для которых еще не

вычислена оценка расстояние и, это главное, минимальное значение в D по

множеству вершин, принадлежащих Т, считается окончательной оценкой для

вершины, на которой достигается этот минимум. С точки зрения здравого

смысла этот факт достаточно очевиден. Другой "заход" в эту вершину возможен

по пути, содержащему большее количество дуг, а так как веса неотрицательны,

то и оценка пути будет больше.

Пример

Его матрица смежности:

| ? 3 7 ? ? ? |

|1 ? 2 ? ? 1 |

|А= ? 1 ? 4 4 ? |

|? ? ? ? 1 5 |

|? ? 1 ? ? 3 |

|? ? ? 2 ? ? |

В таблице приведена последовательность шагов (итераций) работы алгоритма.

На первом шаге минимальное значение D достигается на второй вершине. Она

исключается из множества Т, и улучшение оценки до оставшихся вершин

(3,4,5,6) ищется не по всем вершинам, а только от второй.

| | | | | | | |

| | | | | | | |

| | | | | | | |

11. 6 11 6 3 10 6

7 9 6 13 5 7 5

1 10 12 7 13 13 5

13 11 10 8 10 14 13

Цифровая карта

Площадь музея состоит из клеток: m рядов и p столбцов. В каждой клетке

такой матрицы (цифровая карта) проставляется число, в котором кодируется

наличие стен у данной клетки. Значение числа в каждой клетке является

суммой чисел: 1 (клетка имеет стену на западе), 2 (клетка имеет стену на

севере), 4 (клетка имеет стену на востоке), 8 (клетка имеет стену на

юге). Например, если в клетке стоит число 11 (11=8 + 2 + 1), то клетка

имеет стену с южной стороны, с северной и с западной.

Исходные данные представляются в текстовом файле со следующей

структурой. Первая строка: m, p – размерность сетки. Вторая строка,

третья и следующие строки содержат описание матрицы цифровой карты по

строкам. Расчетные данные вывести на экран в следующем порядке: первая

строка – площадь каждой комнаты музея, вторая строка – количество комнат

в музее.

Пример файла исходных данных:

4. 7

11 6 11 6 3 10 6

7 9 6 13 5 7 5

1 10 12 7 13 13 5

13 11 10 8 10 14 13

Пример выходных данных:

9 3 8 2 6

5

Идея решения:

Данную задачу можно решить используя метод перебора с возвратом.

Используя массив координат перемещения, смотрим, где отсутствуют стены,

для каждой клетки, и последовательно двигаемся в ту клетку, в которую

возможно, предварительно помечая клетку, в которой уже были. Если мы

зашли в тупик, то возвращаемся в клетку, из которой вышли. Одновременно

считаем количество клеток в каждой комнате. Когда происходит возврат в

начальную точку движения, делаем всю комнату просмотренной (при помощи

массива логического типа). Затем ищем клетку, в которой ещё не были и

делаем её начальной точкой движения.

(Текст программы см. Приложение 1)

Пират в подземелье. В поисках драгоценных камней пират проваливается в

подземелье. План подземелья – матрица N*M комнат с драгоценными камнями.

Камни из одной комнаты имеют одинаковую стоимость. Пирату в каждой

комнате разрешается взять всего лишь один камень с собой и следовать в

любую другую соседнюю с ней комнату. Каждую из комнат пират может

посещать всего лишь один раз. Требуется составить алгоритм-программу

определения маршрута посещения пиратом К комнат лабиринта таким образом,

чтобы он набрал камней на максимально возможную сумму. Входные и выходные

данные: В первой строке входного файла содержатся числа N,M,K. В

следующих N строках располагается матрица N*M лабиринта. Каждый элемент

матрицы представляется стоимостью камня соответствующей комнаты. Маршрут

начинается с левой верхней угловой комнаты лабиринта. Выходные данные:

содержат единственное число, равное общей стоимости взятых с собой

камней.

Пример файла исходных данных:

3 4 7

1 1 1 1

1 1 2 1

1 1 2 3

Выходные данные для данного примера:

12

Идея решения: Данную задачу можно решить используя метод перебора с

возвратом. Двигаясь последовательно по комнатам считаем общую стоимость

камней и выбирая наибольшую перебираем все возможные варианты

передвижения пирата по комнатам.

(Текст программы см. Приложение 2)

Диспетчер и милиция. У диспетчера имеется схема города, на которой

изображены районы и дороги, связывающие данные районы. На схеме указаны

расстояния от одного пункта к другому и направление движения, которое

разрешено. Схема выглядит следующим образом:

Диспетчеру поступают запросы из патрульных машин милиции, патрульные

сообщают район, где они находятся и район, в который им необходимо

попасть на вызов. Требуется составить алгоритм – программу, которая бы

помогла диспетчеру найти минимальное расстояние, которое предстоит

покрыть патрульной машине. Необходимо учесть направление движения,

которое разрешено на данном участке пути.

Решение. Входные и выходные данные:

Первая строка входного файла содержит количество районов города. Затем

идет матрица смежности, где занесены все пути из одной вершины в другую с

расстоянием:

6

0 3 7 0 0 0

1 0 2 0 0 1

0 1 0 4 4 0

0 0 0 0 1 5

0 0 1 0 0 3

0 0 0 2 0 0

Номер района, из которого выехала милицейская машина и в который ей

необходимо попасть вводятся с клавиатуры.

Выходные данные:

Единственное число, которое представляет собой минимальный путь, который

предстоит покрыть милицейской машине.

Идея решения: данную задачу можно решить с помощью алгоритма поиска

кратчайших путей в графе (алгоритм Дейкстры).

(Текст программы см. Приложение 3)

Задача о футболистах. Футбольная команда поехала на выездную игру, так

как команда большая, то все игроки залезли в два автобуса, в произвольном

порядке и в разных количествах. В автобусах игроки по привычке

построились по возрастанию номеров и сели. Необходимо составить алгоритм

– программу, помогающую игрокам, на выходе из двух автобусов, сразу же

вставать по возрастанию номеров.

Исходные и выходные данные:

Входной файл содержит три строки. В первой строке находятся два числа –

количество игроков в первом и втором автобусах. Вторая строка содержит

номера игроков, находящихся в первом автобусе. Третья строка содержит

номера игроков, находящихся во втором автобусе:

5 8

4 7 9 15 23

1 2 3 5 6 8 10 17

Выходные данные: номера футболистов, вышедших из автобусов в порядке

возрастания. Выходные данные для данного примера:

1 2 3 5 6 7 8 9 10 15 17 23

Идея решения:

Оптимального решения данной задачи можно добиться, используя метод

сортировки слияниями.

(Текст программы см. Приложение 4)

Задача о семьях. На сельской улице живут Ивановы и Петровы. Необходимо,

используя минимальное число обменов, расселить их так, чтобы Ивановы жили с

одного конца улицы, а Петровы – с другого.

Исходные и выходные данные. С клавиатуры вводится n - количество человек,

проживающих на данной улице. Затем вводится массив А[1..n], состоящий из 0

и 1, где 0 – Петров, 1 – Иванов. Выходными данными является число обменов.

Идея решения:

Задача по методам сортировки. Один из способов её решения заключается в

следующем. Пусть Ивановы должны жить в начале улицы, а Петровы – в конце.

По индексу i (i=0 do

begin

If A[i,j]sum1 then {сравниваем текущую стоимость набранных камней со

стоимотью набранных ранее, с целью увеличения стоимости}

sum1:=sum;

end

Else begin

For i:=1 to 4 do

If (A[x+dx[i],y+dy[i]]>0)and B[x+dx[i],y+dy[i]] then

{просматриваем варианты перехода пирата в другую комнату, проверяя не был

ли пират в ней до этого}

begin

sum:=sum+A[x+dx[i],y+dy[i]]; {прибавляем стоимость камня,

находящегося в данной комнате к суммарной стоимости}

B[x+dx[i],y+dy[i]]:=false; {отмечаем, что в данной комнате мы уже

были}

Solve(x+dx[i],y+dy[i],p-1);

sum:=sum-A[x+dx[i],y+dy[i]];

B[x+dx[i],y+dy[i]]:=true;

end;

end;

end;

begin

clrscr;

Init('A:241.txt');

sum1:=0; sum:=A[1,1];

Solve(1,1,col);

WriteLn('Result= ',sum1);

readkey;

end.

3 Диспетчер и милиция.

Uses crt;

Const n=100;

Type mas=array[1..n,1..n]of Integer;

mas1=array[1..n]of Integer;

mn=Set of 1..n;

Var m,first,last:integer;

D:mas1;

A:mas;

procedure Init(z:string); {инициализация входных данных}

Var i,j:integer;

f:text;

begin

Assign(f,z);

Reset(f);

ReadLn(f,m);

For i:=1 to m do

begin

For j:=1 to m do

Read(f,A[i,j]);

ReadLn(f);

end;

Close(f);

end;

function MinZn(R:mn):integer; {вычисляет номер района, путь до которого

из района отправления минимален}

var i,minn:integer;

Begin

minn:=MaxInt;

For i:=1 to m do

If (D[i]0)and(i in R) then

begin

MinZn:=i;

minn:=D[i];

end;

End;

Function Min(i,j:integer):integer;{возвращает минимальное значение из

двух возможных}

Begin

If i<>0 then

begin

If j<>0 then

begin

If j[] do