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