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

Вятский Державний Гуманітарний Университет.

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

Курсова робота з информатике.

Тема: Розробка системи вправ і завдань (алгоритмы-программы) по дискретної математике.

Выполнил:Студент 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| вузлів дерева. Якщо значення P. S; обмежена деякою константою З, то отримуємо порядку CN узлов.

Пошук данных.

Логарифмический (бинарный) поиск Логарифмический (бінарний чи метод розподілу навпіл) пошук даних застосуємо до сортированному безлічі елементів а1 < А2 < … < аз, розміщення якого виконано на суміжною пам’яті. Для більшої ефективності пошуку елементів треба, щоб шляху доступу до них стали короткими, ніж просто послідовний перебір. Найочевидніший метод: розпочати пошук зі середнього елемента, тобто. виконати порівнювати з елементом а. Результат порівняння дозволить визначити, як і половині послідовності а{, А2,…, а, 1+" ,…, аз продовжити пошук, застосовуючи до неї таку ж процедуру, тощо. Основна ідея бінарного пошуку досить просте, проте «багатьом хороших програмістів жодна спроба написати правильну програму закінчилася невдачею». Щоб детально дати раду алгоритмі, найкраще уявити дані ох < А2 < … < аз як двоичного дерева порівнянь, який відповідає бінарному пошуку. Двоичное дерево називається деревом порівнянь, для кожен її вершини (деревокореня чи кореня поддерева) виконується условие:

{Вершини лівого поддерева}.