Вятский Государственный Гуманитарный Университет
Кафедра прикладной математики
Курсовая работа по информатике
Тема: Разработка системы упражнений и задач (алгоритмы-программы) по дискретной математике.
Выполнил:Студент 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 < ... < ап
в виде двоичного дерева сравнений, которое отвечает бинарному поиску.
Двоичное дерево называется деревом сравнений , если для любой его вершины
(корня дерева или корня поддерева) выполняется условие:
{Вершины левого поддерева}