Комбинаторные задачи, приёмы и методы их решения.

Комбинаторика – это раздел математики, в котором изучают, сколько комбинаций, подчиненных тем или иным условиям, можно составить из данных объектов

Комбинаторные задачи обладают общей особой приметой. Этой приметой является вопрос задачи, который всегда можно сформулировать так, что он будет начинаться словами:

 «Сколько … ?», «Сколькими способами …?».

Комбинаторные задачи различаются по подходам к решению. Рассмотрим некоторые основные комбинаторные идеи, лежащие в основе решения некоторых из них.

правило произведения:

Пусть нам даны k множеств по n₁, n₂, n₃, n₄,... ,n_k элементов каждое, и нам нужно произвести выбор по одному в каждом из множеств, тогда число возможных способов находим так:

N = n₁ n₂ n₃ n₄ ...n_k.

Обобщение:на каждое из m мест может быть поставлен элемент n – элементного множества. Тогда количество способов расположения элементов можно найти по формулеmⁿ.

Перестановкойиз n элементов называют упорядоченный набор этих элементов. ОбозначаютP_n=n!

Размещениемиз n элементов по k называется упорядоченное подмножество из n элементов множества, имеющего k элементов. Обозначается

Cочетаниемиз n элементов по k называется неупорядоченное подмножество из n элементов множества, имеющего k элементов. Обозначается .

 

Задача Эйлера о мостах. Обход лабиринтов.

Эйлеровы графы
Задача о Кёнигсбергских мостах.

Кёнигсберг (теперь Калининград) расположен на обоих берегах реки Преголя и на двух островах этой реки. Берега реки и два острова соединены семью мостами. Вопрос (поставленный в 1736 г.) состоит в том, можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.

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

Алгоритм решения:

1) Нарисовать граф, вершины – острова и берега, ребра – мосты

2) Определить степень вершин (количество инцидентных ребер)

3) Подсчитать количество нечетных вершин

4) Обход возможен: если все вершины имеют четную степень, обход можно начать с любой вершины; если 2 вершины имеют нечетную степень, то обход нужно начать с одной из нечетных вершин

5) Обход невозможен, если нечетных вершин больше двух

6) Сделать вывод

7) Указать схему пути

Лабиринты
Задача обхода лабиринта состоит в том, чтобы обойти лабиринт и найти путь из одной вершины, в другую.
Существуют несколько методов обхода:

1. Метод левой/правой руки

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

2. Метод замазывания тупиков

В методе замазывания тупиков, мы заходим в тупик, помечаем его как тупик, и возвращаемся на шаг назад.

3. Волновой метод

Волновой метод.Каждый уровень помечается числом, на 1 больше предыдущего. Реализуется такой метод с помощью очереди.

 

---

Дата добавления: 2018-05-13; просмотров: 464; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!