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

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

рассмотрим данную классификацию с точки зрения методики преподавания информатики. выбор неверного способа. В этом заключается актуальность данного курсового проекта. Цель: Разработать собственную классификацию для задач по дискретной математике. Для достижения этой цели были поставлены следующие задачи: 1)    Разработать собственную систему задач и упражнений по дискретной математике. 2)    Определить способы

решения данных задач, используя теоретический материал курса дискретной математики. 3)    Составить алгоритм – программу для каждой задачи, реализующий выбранный способы решения. 4)    Разработать систему критериев классификации данной системы задач. Глава 1 Теоретический материал. Перебор с возвратом. Общая схема Даны N упорядоченных множеств U1 U2,..., Un (N - известно), и требуется построить вектор А=(а1 а2, ..., аn), где

a1€U1, a2€U2, ..., an€Un, удовлетворяющий заданному множеству условий и ограничений. Начало Выборы для А1 Выборы для А2 при А1 Выборы для А3 при данных А1 и А2 В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (к-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 <вычислить Si>; for a€Si do Васкtrаск(вектор| | a,i+l); {| | - добавление к вектору компоненты} end; end; Оценка временной сложности алгоритма. Данная схема