42419

Комбинаторика. Основные комбинаторные принципы и соединения

Лабораторная работа

Математика и математический анализ

Введем некоторые важные обозначения: множества будем обозначать заглавными буквами; множества состоят из элементов которые будем обозначать малыми буквами. Такие множества будем изображать перечислением элементов заключая их в фигурные скобки. 3 Количество элементов в множестве называется мощностью и записывается как . Комбинаторные соединения Некоторая совокупность элементов данного nмножества называется выборкой.

Русский

2013-10-29

198.5 KB

102 чел.

Практическое занятие №6

Тема: Комбинаторика.

Занятие рассчитано на 2 академических часа.

Цель работы: изучить комбинаторные формулы, наиболее важных для вычислительных задач.

Теоретическая часть

Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия.

Например, сколькими способами можно расположить 50 человек в очереди в кассу за билетами в кино, сколькими способами могут быть распределены  золотая, серебряная и бронзовая медали на чемпионате Европы по футболу?

Задачи такого типа называются комбинаторными.

Введем некоторые важные обозначения:

  1.  множества будем обозначать заглавными буквами;
  2.  множества состоят из элементов, которые будем обозначать малыми буквами. Так, запись аА обозначает, что элемент а принадлежит множеству А. Такие множества будем изображать перечислением элементов, заключая их в фигурные скобки. Например, {а, b, х, у}.

3) Количество элементов в множестве называется мощностью и записывается как  |A|.

Пусть имеются два множества А и В.  

Напомним некоторые операции над множествами:

При комбинаторных расчетах часто применяются два основных комбинаторных принципа (правила).

Основные комбинаторные принципы

  1.  Правило суммы

Если А и В — несвязанные события, и существует n1 возможных исходов события А, и n2 возможных исходов события В, то возможное число исходов события «А или В» равно сумме  n1+ n2.

  1.  Правило произведения

Если дана последовательность k событий с n1 возможными исходами первого, n2  второго, и т.д., вплоть до nk возможных исходов последнего, то общее число исходов последовательности k событий равно произведению n1* n2*…* nk.

Задача 1. В небольшой кондитерской к концу рабочего дня осталось несколько пирожных: четыре ванильных, два шоколадных и три фруктовых. Один покупатель собирается купить пирожные перед закрытием кондитерской. Сколько пирожных может выбрать покупатель?

Задача 2. Необходимо выбрать смешанную команду, которая будет представлять местный теннисный клуб на соревнованиях. В спортивном клубе состоят 6 женщин и 9 мужчин. Сколько различных пар можно выбрать для участия в соревнованиях?

Задача 3. Сколько трехзначных чисел начинаются с 3 или 4?

Первая задача решается простым подсчетом. Поскольку все пирожные различны, мы просто можем сложить их количества. Это дает 4 + 2 + 3 = 9 пирожных, из которых покупатель может сделать выбор.

Во второй задаче у нас есть 6 женщин, из которых мы можем выбрать представительницу клуба, и для каждой из них мы можем подобрать партнера среди девяти мужчин. Таким образом, общее число различных пар, которые мы можем составить, равно 6*9 = 54.

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

К одному из них относятся числа, начинающиеся с 3, а ко второму с 4. Для подсчета чисел в первом классе заметим, что существует один возможный исход для первой цифры (она должна быть равна 3), 10 исходов для второй и 10 исходов для последней цифры.

По правилу произведения получаем, что всего чисел в первом классе насчитывается ровно 1*10*10 = 100. Аналогично можно подсчитать количество чисел во втором классе. Оно тоже равно 100. Наконец, по правилу суммы получаем, что существует 100 + 100 = 200 трехзначных чисел, начинающихся с 3 или 4.

Комбинаторные соединения

Некоторая совокупность элементов данного n-множества называется выборкой. Число элементов в выборке называется длиной выборки.

Пример 1. Пусть дано множество Х – множество цифр, т.е.  . Это множество состоит из 10 элементов. Любой набор цифр, состоящий, например, из 4 цифр будет являться выборкой длины 4.

Замечание. Некоторую совокупность элементов из данного конечного множества можно выбирать по-разному:

если при составлении выборки учитывается порядок следования элементов в выборке, тогда выборка называется упорядоченной; если же при составлении выборки не учитывается порядок следования элементов в ней, то выборка называется неупорядоченной;

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

Пример 2. Пусть дано множество Х – множество цифр, т.е.  . Составить из цифр пятизначное число, цифры в котором не повторяются.

Этим пятизначным числом может быть, например, число 54321. Переставим цифры в данном числе, например, так 45321, в результате получим другое число (другую выборку). Таким образом, при изменении порядка следования элементов в выборке, изменяется сама выборка, поэтому каждое пятизначное число является упорядоченной выборкой. Так как оба составленных числа не имеют в своем составе одинаковых цифр, то обе эти выборки являются выборками без повторений. Однако пятизначное число, например,  554331 является упорядоченной выборкой, но с повторениями.

Пример 3. Пусть имеются  открытки 6 видов. Составить из этих открыток набор, состоящий из 4 открыток.

Каждый набор из 4 открыток будет являться выборкой. Если мы поменяем в наборе местами две открытки, то от этого набор открыток не измениться, т.е. выборка останется прежней. Таким образом, при изменении порядка следования элементов в выборке выборка не меняется, следовательно, в данном случае выборка неупорядоченная. Если в составленном наборе будут одинаковые открытки, то он будет выборкой с повторениями, если же все открытки в наборе будут различными, то набор будет являться выборкой без повторений.

Замечание. Набор свойств, которыми обладает выборка (упорядоченность, неупорядоченность, с повторениями или без повторений) будем называть характером выборки. Установление характера выборки очень важно для решения комбинаторной задачи.

 

Основные виды комбинаторных соединений: размещения, перестановки и сочетания.

Определение 1. Размещением с повторениями из m элементов данного n-множества называется упорядоченная выборка с повторениями длины m из элементов данного множества.

Таким образом, если характер выборки: 1) упорядоченная; 2) с повторениями, то выборка является размещением с повторениями.  Число размещений с повторениями из m элементов данного n-множества обозначается , и вычисляется по формуле:          =           (1)

Задача 4. Секретный замок сейфа состоит из 5 дисков, на каждом из которых написано по 12 букв. Сейф открывается, если на каждом из дисков выбрана определенная буква. Сколько неудачных попыток может быть сделано человеком, не знающим кода и подбирающим его наудачу?

Решение. 1) Человек должен выбирать из 12 букв, т.е. множество из которого производится выборка, состоит из  n = 12 элементов.

2) Так как на каждом диске нужно выбрать по одной букве, а дисков всего 5, то мы должны осуществить выборку длины m = 5.

3) Определим характер выборки. Так как на каждом из дисков выбирается определенная буква, то при таком выборе появляется некоторое слово, и если хотя бы две буквы этого слова переставить местами, мы получим другое слово, т.е. другую выборку, поэтому в данном случае мы имеем дело с упорядоченной выборкой. Так как  в условии ничего не говориться о том, что буквы должны быть различными, то имеем выборку с повторениями.

4) По характеру выборки делаем вывод что, каждое набранное слово является размещением с повторениями. По формуле (1) вычислим число таких слов:

                               = 248832

5) Значит, неудачных попыток может быть 248832 – 1 =248831.

Ответ: 248831.

Определение 2. Размещением без повторений из m элементов данного n- множества называется упорядоченная выборка без повторений длины m из элементов данного множества.

Таким образом, если характер выборки: 1) упорядоченная; 2) без повторений, то выборка является размещением без повторений.  Число размещений без повторений из m элементов данного n-множества обозначается  , и вычисляется по формуле:   =           (2)

Замечание. Символ  читается как n – факториал и означает произведение первых n натуральных чисел: .

Задача 5.  Сколько различных четырехбуквенных слов можно составить из букв слова  ученик, написанных на отдельных карточках?

Решение. 1) Множество из которого производится выборка – множество букв слова ученик, в котором n = 6 букв.

2) Составляют четырехбуквенные слова, поэтому каждое такое слово есть выборка длиной m = 4.

3) Определим характер выборки: 1) так как составляем слова, в которых порядок букв существенен, то выборка является упорядоченной; 2) так как все буквы данного слова различные, то выборка происходит без повторений.

3) По характеру выборки делаем вывод что, каждое составленное слово является размещением без повторений. По формуле (2) найдем число размещений без повторений из 6 элементов по 4:  == = 360.

Ответ: из букв слова ученик можно составить 360 четырехбуквенных слов.

 

Определение 3. Перестановкой без повторений из n элементов данного n- множества называется упорядоченная выборка без повторений длины n из элементов данного множества.

Таким образом, если характер выборки: 1) упорядоченная; 2) без повторений, и выбирают все элементы n-множества, то выборка является перестановкой без повторений.  Число перестановок без повторений из n элементов обозначается  , и вычисляется по формуле:             (3)

Задача 6. Сколькими способами очередей можно составить из 10 человек.

Решение. 1) Множество из которого выбирают, состоит из n = 10 элементов;

2)Выбирают все 10 человек, поэтому длина выборки m = 10, т.е. m = n.

Определим характер выборки: выбираем упорядоченно и без повторений.

По характеру выборки делаем вывод, что каждая составленная очередь это перестановка без повторений. По формуле (3) вычислим число перестановок без повторений из n элементов:  .

Ответ: можно составить 3628800 очередей.

Используя формулу (3) можно вычислить, сколько четырехзначных цифр можно составить из цифр 1,2,3,4: . В слове мама тоже четыре буквы, поставим задачу: сколько различных четырёхбуквенных слов можно составить из букв слова мама. В отличие от предыдущего случая таких слов будет не 24, а всего 6 (мама, маам, ммаа, амам, аамм, амма). Дело в том, что в слове мама есть одинаковые буквы, т.е. при составлении слов происходит упорядоченная выборка с повторениями. Однако в отличие от размещения с повторениями, в этом случае элементы множества повторяются не произвольно, а в определенном составе: 2 раза буква м и 2 раза буква а.

Рассмотрим общий случай. Пусть составлена упорядоченная выборка длины m из элементов множества . Причем элемент  входит в выборку раз, элемент  входит в выборку  раз, …, элемент  входит в выборку  раз, ясно, что . Набор чисел  называется составом выборки длины m. В соответствии с данным определением состав слова мама – (2, 2).

Определение 4. Перестановкой с повторениями данного состава называется упорядоченная выборка с повторениями из  элементов данного множества.

Таким образом, если характер выборки: 1) упорядоченная; 2) с повторениями данного состава , то выборка является перестановкой из m элементов с повторениями.  Число перестановок с повторений из m элементов данного состава обозначается  , и вычисляется по формуле:          (4)

Задача 7. Сколько чисел можно составить из цифр числа 55121213?

Решение. 1) Из цифр данного числа составляем составлять выборку длины m=8;

2) Так как составляем числа, то выборка упорядоченная. В данном числе есть одинаковые цифры, поэтому выборка будет с повторениями, но не произвольными: цифра 5 повторяется 2 раза, цифра 1 повторяется 3 раза, цифра 2 – 2 раза, цифра 3 – 1 раз, т.е. выборка будет иметь состав (2, 3, 2. 1). Таким образом, каждое составленное число есть размещение длины 8 с повторениями данного состава. Используя формулу (4), получим:

= 1680.

Ответ: можно составить 1680 чисел.

Определение 5. Сочетанием без повторений из m элементов данного n- множества называется любое подмножество из m элементов данного n- множества.

Таким образом, если характер выборки: 1) неупорядоченная; 2) без повторений, то выборка является сочетанием без повторений.  Число сочетаний без повторений из m элементов данного n- множества обозначается  , и вычисляется по формуле:=           (5)

Задача 8.  Сколько различных хорд можно провести через 6 точек, лежащих на данной окружности?  

Решение. 1) Будем выбирать из множества, состоящего из n = 6 элементов.

2) Хорда определяется двумя точками, поэтому будем из 6 элементов составлять выборку длиной m = 2.

3) Определим характер выборки: порядок выбора точек для построения каждой хорды не имеет значения, поэтому имеем неупорядоченную выборку; так как одну и туже точку в выборку из двух точек брать нельзя (т.к. через одну прямую проходит множество прямых), то выборка  –  без повторений. Таким образом, имеем сочетание без повторений.

По формуле (5) находим: = =15.

Ответ: через 6 точек, лежащих на окружности можно провести 15 хорд.

 

Определение 6. Сочетанием с повторениями называется неупорядоченная выборка с повторениями из m элементов данного n- множества.

Таким образом, если характер выборки: 1) неупорядоченная; 2) с повторениями, то выборка является сочетанием с повторениями.  Число сочетаний с повторениями из m элементов данного n- множества обозначается  , и вычисляется по формуле:                 (6)

Задача 9. В кондитерском магазине продаются пирожные 4 сортов: наполеоны, песочные, эклеры и слоёные. Сколькими способами можно купить 7 пирожных?

Решение. 1) Множество из которого будем выбирать – это множество пирожных 4 видов, т.е. число элементов в множестве из которого выбираем n = 4.

2) Так как надо купить 7 пирожных , то длина выборки m = 7.

3) Определим характер выборки: при покупке пирожных неважно, в каком порядке мы их будем выбирать, т.е. выборка неупорядоченная; так как мы составляем всевозможные наборы пирожных, то среди таких наборов будут и наборы, где есть одинаковые пирожные, поэтому выборка с повторениями.

4) По характеру выборки определяем комбинаторное соединение, в данном случае это сочетания с повторениями. По формуле (6) вычисляем искомое число:

= =120.

Ответ: существует 120 способов, которыми можно купить 7 пирожных.

 

Как видно из определений (1) – (6) классификация комбинаторных соединений ведётся по характеру выборки, поэтому при решении конкретной задачи очень важно определить характер выборки. Задачи, которые были разобраны после каждого определения комбинаторного соединения решались по единому алгоритму, приведем этот алгоритм в общем виде:

Определить множество, из которого производится выборка и число элементов n в этом множестве.

Определить выборку и число элементов m в выборке.

Определить характер выборки.

По характеру выборки определить, с каким комбинаторным соединением мы имеем дело, и выбрать формулу для вычисления.

По выбранной формуле произвести вычисления.

Однако есть задачи, для которых этот алгоритм решения не подходит. Например:

Задача 10.  На прямой взято 5 точек, а на параллельной ей прямой взято 3 точки. Сколько существует различных треугольников, вершинами которых являются эти точки?

Прежде чем переходить к решению этой задачи попробуем составить алгоритм решения задач такого типа. Первое, что надо заметить это то, что выбирать нам придется из двух множеств: из множества точек первой прямой и из множества точек второй прямой. Таким образом, эту задачу можно разбить на более простые задачи, в каждой из которых выбор происходит из одного множества, причем каждую такую задачу можно решить по приведённому выше алгоритму. После решения этих задач мы будем знать, сколькими способами можно выбрать элемент из каждого множества. Далее, чтобы ответить на первоначальный вопрос задачи, нужно определить по какому принципу выбираются элементы этих множеств: сначала элемент из первого множества, и после каждого такого выбора элемент из второго множества, причем нужно выбрать оба элемента или нужно выбрать из двух элементов только один, т.е. нужно определить какой комбинаторный принцип (ПрΣ или ПрП) нужно применить, для ответа на вопрос задачи.

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

 Алгоритм решения сложной комбинаторной задачи.

По условию задачи определить сложную или простую задачу мы имеем.

Разбить сложную комбинаторную задачу на несколько простых задач.

Решить каждую простую задачу по приведенному выше алгоритму.

Определить какой комбинаторный принцип нужно применить в этой задаче:

если выбираем несколько элементов по принципу «сначала… потом…», то необходимо применить ПрП;

если выбираем один элемент из нескольких по принципу или первый или второй или …, то применяем ПрΣ.

В соответствии с выбранным принципом проводим вычисления.

Теперь вернемся к решению задачи 10.

Решение (задача 10). 1) Так как в задаче дано два множества: первое – множество точек, лежащих на  первой прямой, второе – множество точек, лежащих на второй прямой, то мы имеем дело со сложной комбинаторной задачей.

2) Разобьем эту задачу на две простых. Для того чтобы составить треугольник необходимо взять три точки. На одной прямой все три точки взять нельзя, т.к. треугольника не получится, хотя бы одно точка должна лежать на другой прямой. Таким образом нужно решить две задачи:

1. Сколькими способами можно выбрать две точки из 5, лежащих на первой прямой и сколькими способами можно выбрать одну точку из 3, лежащих на второй прямой?

2. Сколькими способами можно выбрать одну точку из 5, лежащих на первой прямой и сколькими способами можно выбрать две точки из 3, лежащих на второй прямой?

3) Решим каждую сформулированную задачу:

1. 1) Так как в задаче опять речь идет о выборе из двух множеств, то это задача сложная. Разобьем её на две задачи и решим каждую из них:

1.1. Сколькими способами можно выбрать две точки из 5, лежащих на прямой?

1.2. Сколькими способами можно выбрать одну точку из 3, лежащих на прямой?

Каждая из этих задач является простой комбинаторной задачей, решим их по алгоритму.

1.1.     1) Число элементов в множестве, из которого выбираем n = 5.

2) Число элементов в выборке m = 2.

3) Характер выборки: 1) неупорядоченная (т.к. для составления треугольника неважно в каком порядке будут выбраны точки), 2) без повторений (т.к. одну и туже точку два раза выбирать нельзя)

4) Каждая пара точек является сочетанием без повторений.

5) 10.

1.2.      Так как из множества 3 точек выбираем одну, то это можно сделать 3 способами.

2) Определим принцип, который используется в задаче 1. Так как мы выбираем точки по принципу сначала 2, а потом ещё одну, то для решения этой задачи применим принцип произведения, т.е. перемножим результаты, полученные в задачах 1.1. и 1.2. Получим: 10*3=30.

2. Задачу 2 решим аналогичным образом, в результате получим: 3*5=15.

4) Теперь определим принцип, который нужно применить в первоначальной задаче. Так как вершины треугольников можно выбрать или способом, описанным в задаче 1, или способом, описанным в задача 2, то для того, чтобы посчитать число способов таких выборов воспользуемся принципом суммы. Применяя ПрΣ, получим:   30 + 15 = 45.

Ответ: существует 45 различных треугольников.

Контрольные вопросы

  1.  Сформулируйте правило суммы.
  2.  Сформулируйте правило произведения.
  3.  Дайте определение размещениям с повторениями, размещениям без повторений, сочетаниям с повторениями и без повторений, перестановкам с повторениями и без повторений.
  4.  Объясните алгоритм решения сложной комбинаторной задачи.

Индивидуальные задания

1. Сколькими способами можно разместить 5 человек за столом, на котором поставлено 5 приборов?

2. Некто забыл последние 4 цифры телефонного номера, помнит только, что все цифры разные и среди них есть 9. Какое максимальное число номеров ему придется набрать, если он попытается дозвониться до абонента?

3. В цветочном магазине продаются цветы 6 сортов. Сколько можно составить различных букетов из 7 цветов в каждом?

4. Имеется 25 российских и 15 зарубежных марок. Сколькими способами можно выбрать 3 российские и 2 зарубежные марки?

5. Сколько различных слов можно составить из букв слова колокол?

6. Сколько различных автомобильных номеров можно составить из 28 букв и 10 цифр, если каждый номер состоит из 3 букв и 3 цифр?

7. Из группы, состоящей из 7 юношей и 4 девушек надо выбрать 6 человек так, так, чтобы среди них было не менее 2 девушек. Сколькими способами это может быть сделано?

8. У Ивана 7 книг по математике, а у Дмитрия – 9 книг. Сколькими способами они могут обменять 3 книги одного на три книги другого?

9. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из 5 языков: русского, английского, французского, немецкого и итальянского, на любой другой из этих 5 языков?

10. Сколькими способами могут выпасть три игральные кости? Во скольких случаях хотя бы одна кость откроется на 6 очках? Во скольких случаях ровно одна кость откроется на 6 очках? Во скольких случаях одна кость откроется на 6 очках, а одна – на 3 очках?

11. У человека есть пять пиджаков, восемь рубашек и семь галстуков. Сколько различных костюмов можно составить из этих предметов?

12. У женщины в шкафу висит шесть платьев, пять юбок и три блузки. Сколько разных нарядов она может составить из своей одежды?

13. В холодильнике стоит мороженое шести разных наименований. На десерт можно взять одну, две или даже три порции мороженого сразу. Сколько возможностей есть у Вас для различных десертов?

14. Перевертыш — это многозначное число, которое не поменяет своего значения, если все его цифры записать в обратном порядке. Сколько существует шестизначных перевертышей? А сколько семизначных?

15. Сколько четырехзначных чисел, не превосходящих 6 000, можно составить, используя только нечетные цифры?

16. Пароль, открывающий доступ к компьютеру, состоит из шести символов. Первые два из них — строчные буквы латинского алфавита (всего 26 букв), а оставшиеся четыре могут быть как цифрами, так и строчными буквами. Сколько можно придумать различных паролей?

17. Пусть S — множество четырехзначных чисел, в чьей десятичной записи участвуют цифры: 0, 1, 2, 3, и 6, причем 0 на первом месте, естественно, стоять не может. Какова мощность множества S7?. Сколько чисел из S в своей десятичной записи не имеют повторяющихся цифр?

18. Сколько существует возможностей для присуждения первого, второго и третьего мест семнадцати участницам соревнований по икебане?

19. Комитет из 20 членов избирает председателя и секретаря. Сколькими способами это можно сделать?

20. Хоккейная команда насчитывает 18 игроков. Одиннадцать из них входят в основной состав. Подсчитайте количество возможных основных составов.

21. Жюри из 5 женщин и 7 мужчин должно быть выбрано из списка в 8 женщин и 11 мужчин. Сколько можно выбрать различных жюри?

22. Предстоит выбрать команду четырех игроков в гольф из пяти профессиональных игроков и пяти любителей. Сколько разных команд может состоять из трех профессионалов и одного любителя? Сколько команд состоит только из профессионалов или только из любителей?

23. В один из комитетов парламента нужно отобрать трех членов, причем выбирать надо из пяти консерваторов, трех лейбористов и четырех либерал-демократов. Сколько разных комитетов можно составить?

24. В небольшой фирме восемь человек работают на производстве, пятеро — в отделе сбыта, и трое — в бухгалтерии. Для обсуждения новой продукции было решено пригласить на совещание шестерых работающих. Сколькими способами это можно сделать, если

(а) необходимо пригласить по два представителя от каждого отдела;

25.(б) необходимо пригласить по крайней мере двоих представителей производства;

(в) необходимы представители каждого из трех отделов?

26. (а) Ресторан в своем меню предлагает пять различных главных блюд. Каждый из компании в шесть человек заказывает свое главное блюдо. Сколько разных заказов может получить официант?

27. Цветочница продает розы четырех разных сортов. Сколько разных букетов можно составить из дюжины роз?

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

(а) Как много наборов из пяти открыток Вы можете купить?

29. (б) Сколько наборов можно составить, если ограничиться

только двумя типами открыток из четырех, но купить

все равно пять открыток?

30. В один из комитетов парламента нужно отобрать трех членов, причем выбирать надо из пяти консерваторов, трех лейбористов и четырех либерал-демократов. Сколько разных комитетов можно составить, если в него должен входить по крайней мере один либерал-демократ?

ПРИЛОЖЕНИЕ

Методы программирования: переборные алгоритмы

Основные идеи  - ПЕРЕБОР, РЕКУРСИЯ, ПЕРЕБОР С ОТХОДОМ HАЗАД. Этими понятиями должен хорошо владеть каждый программист!!!

Порождение и перебор комбинаторных объектов

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой. Поэтому так важно для нас научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.

Схема перебора всегда будет одинакова:

- во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

- во-вторых, научиться переходить от произвольного элемента к HЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).

Hаиболее естественным способом упорядочения составных объектов является ЛЕКСИКОГРАФИЧЕСКИЙ порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать заново. Пока запишем схему перебора в таком виде:

      X:=First;

       while X<>Last do Next(X);

где First - первый элемент; Last - последний элемент; Next - процедура получения следующего элемента.

Последовательности

Напечатать все последовательности длины N из чисел 1,2,...,M.

First = (1,1,...,1) Last = (M,M,...,M)

Всего таких последовательностей будет M^N (докажите!). Чтобы понять. как должна действовать процедура Next, начнем с примеров. Пусть N=4,M=3. Тогда:

Next(1,1,1,1) -> (1,1,1,2) Next(1,1,1,3) -> (1,1,2,1) Next(3,1,3,3) -> (3,2,1,1)

Теперь можно написать общую процедуру Next:

 procedure Next;

   begin

     {найти i: X[i]<M,X[i+1]=M,...,X[N]=M};

     X[i]:=X[i]+1;

     X[i+1]:=...:=X[N]:=1

   end;

Если такого i найти не удается, то следующей последовательности нет - мы добрались до последней (M,M,...,M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа на Паскале выглядит так:

   program Sequences;

     type Sequence=array [byte] of byte;

     var M,N,i:byte;

  X:Sequence;

  Yes:boolean;

     procedure Next(var X:Sequence;var Yes:boolean);

 var i:byte;

     begin

i:=N;

 {поиск i}

while (i>0)and(X[i]=M) do begin X[i]:=1;dec(i) end;

if i>0 then begin inc(X[i]);Yes:=true end

else Yes:=false

     end;

   begin

     write('M,N=');readln(M,N);

     for i:=1 to N do X[i]:=1;

     repeat

for i:=1 to N do write(X[i]);writeln;

Next(X,Yes)

     until not Yes

   end.

Перестановки

Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).

First = (1,2,...,N) Last = (N,N-1,...,1)

Всего таких перестановок будет N!=N*(N-1)*...*2*1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>...>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],...,X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,...,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

   procedure Next;

   begin

     {найти i: X[i]<X[i+1]>X[i+2]>...>X[N]};

     {найти j: X[j]>X[i]>X[j+1]>...>X[N]};

     {обменять X[i] и X[j]};

     {X[i+1]>X[i+2]>...>X[N]};

     {перевернуть X[i+1],X[i+2],...,X[N]};

   end;

Теперь можно написать программу:

   program Perestanovki;

     type Pere=array [byte] of byte;

     var N,i,j:byte;

  X:Pere;

  Yes:boolean;

     procedure Next(var X:Pere;var Yes:boolean);

var i:byte;

procedure Swap(var a,b:byte);  {обмен переменных}

  var c:byte;

begin c:=a;a:=b;b:=c end;

     begin

i:=N-1;

{поиск i}

while (i>0)and(X[i]>X[i+1]) do dec(i);

if i>0 then

  begin

    j:=i+1;

    {поиск j}

    while (j<N)and(X[j+1]>X[i]) do inc(j);

    Swap(X[i],X[j]);

    for j:=i+1 to (N+i) div 2 do Swap(X[j],X[N-j+i+1]);

    Yes:=true

  end

else Yes:=false

     end;

   begin

     write('N=');readln(N);

     for i:=1 to N do X[i]:=i;

     repeat

for i:=1 to N do write(X[i]);writeln;

Next(X,Yes)

     until not Yes

   end.

  Разбиения

Перечислить все разбиения целого положительного числа N на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно).

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

First = (1,1,...,1) - N единиц Last = (N)

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?

Во-первых, должно быть X[i-1]>X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:

   procedure Next;

     begin

{найти i: (i<L) and ( (X[i-1]>X[i]) or (i=1) )}

 X[i]:=X[i]+1;

{ L:= i + X[i+1]+...+X[L] - 1 }

 X[i+1]:=...:=X[L]:=1

     end;

Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:

 program Razbieniya;

   type Razb=array [byte] of byte;

   var N,i,L:byte;

 X:Razb;

   procedure Next(var X:Razb;var L:byte);

     var i,j:byte;

  s:word;

   begin

     i:=L-1;s:=X[L];

     {поиск i}

     while (i>1)and(X[i-1]<=X[i]) do begin s:=s+X[i];dec(i) end;

     inc(X[i]);

     L:=i+s-1;

     for j:=i+1 to L do X[j]:=1

   end;

 begin

   write('N=');readln(N);

   L:=N; for i:=1 to L do X[i]:=1;

   for i:=1 to L do write(X[i]);writeln;

   repeat

     Next(X,L);

     for i:=1 to L do write(X[i]);writeln

   until L=1

 end.

Подсчет количеств

Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя таблицу значений функции С по формулам:

C(n,0) = C(n,n) = 1 (n>=1) C(n,k) = C(n-1,k-1) + C(n-1,k) (n>1, 0<k<n);

или по формуле n!/(k!*(n-k)!) (первый способ эффективнее, если надо вычислить много значений С(n,k)).

Попробуем посчитать таким способом количество разбиений из пункта 1.3. Обозначим через R(N,k) (при N>=0, k>=0) число разбие- ний N на целые положительные слагаемые, не превосходящие k (при этом R(0,k) считаем равным 1 для всех k>=0). Очевидно, что число R(N,N) и будет искомым. Все разбиения N на слагаемые, не превосходящие k, разобьем на группы в зависимости от максимального слагаемого (обозначим его i).

Число R(N,k) равно сумме (по всем i от 1 до k) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i. А разбиения N на слагаемые не более k с первым слагаемым, равным i, по существу представляют собой разбиения n-i на слагаемые, не превосходящие i (при i<=k). Так что

R(N,k) = R(N-1,1)+R(N-2,2)+...+R(N-k,k).

Остальное вы сделаете сами в домашнем задании.


  Рекурсия

Вы уже знаете, что рекурсивными называются процедуры и функции, которые вызывают сами себя. Рекурсия позволяет очень просто (без использования циклов) программировать вычисление функций, заданных рекуррентно, например факториала f(n)=n!:

f(0)=1 f(n)=n*f(n-1).

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

Примечание: рекурсия, безусловно, весьма удобна, однако часто требует громадное количество ресурсов. В частности, программа для факториала на 7-мом десятке завесит самый быстрый Pentium - III+. Из-за времени выполнения. О том, как этого избежать, можно изучив Динамическое программирование.

Факториал

Еще раз напомним рекурсивный алгоритм вычисления факториала:

 program Factorial;

   var N:word;

   function F(n:word):longint;

   begin

     if n=0 then F:=1 else F:=n*F(n-1)

   end;

 begin

   write('N=');readln(N);

   writeln('N!=',F(N))

 end.


 
Ханойская башня

Игра "Ханойская башня" состоит в следующем. Есть три стержня. Hа первый из них надета пирамидка из N колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия.

Hапишем рекурсивную процедуру перемещения M верхних колец с A-го стержня на B-ый в предположении, что остальные кольца больше по размеру и лежат на стержнях без движения:

   procedure Move(M,A,B:integer);

     var C:integer;

   begin

     if M=1 then begin writeln ('сделать ход ',A,'->',B) end

     else

begin

  C:=6-A-B; {C - третий стержень: сумма номеров равна 6}

  Move(M-1,A,C);

  Move(1,A,B);

  Move(M-1,C,B)

end

   end;

Сначала переносится пирамидка из M-1 колец на третий стержень C. После этого M-ое кольцо освобождается, и его можно перенести на B. Остается перенести пирамиду из N-1 кольца с C на B. Чем это проще первоначальной задачи? Тем, что количество колец стало на единицу меньше. Теперь основную программу можно записать в несколько строк:

   program Hanoi;

     var N:integer;

     procedure Move(M,A,B:integer);

    .............

   begin

     write('N=');readln(N);

     Move(N,1,2)

   end.

Если вы владеете основами компьютерной графики, можете попробовать "нарисовать" каждый ход на экране.

Таким образом, ОСHОВHАЯ ИДЕЯ любого рекурсивного решения - свести задачу к точно такой же, но с меньшим значением параметра. При этом какое-то минимальное значение параметра (например, 1 или 0) должно давать решение без рекурсивного вызова - иначе программа "зациклится" (последовательность рекурсивных вызовов будет бесконечной). Это напоминает метод математической индукции в математике. В некоторых задачах удобно наоборот, увеличивать значение параметра при рекурсивном вызове. Тогда, естественно, "безрекурсивное" решение должно предусматриваться для некоторого максимального значения параметра. Попробуем использовать эту идею для перебора комбинаторных объектов.

  Последовательности (рекурсивный алгоритм)

Задача та же, что в пункте 1.1. Опишем рекурсивную процедуру Generate(k), предъявляющую все последовательности длины N из чисел 1,...,M, у которых фиксировано начало X[1],X[2],...,X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность - это она сама. При k<N будем сводить задачу к k+1:

  procedure Generate(k:byte);

    var i,j:byte;

  begin

    if k=N then

      begin for i:=1 to N do write(X[i]);writeln end

    else

      for j:=1 to M do

 begin X[k+1]:=j; Generate(k+1) end

  end;

Основная программа теперь выглядит очень просто:

 program SequencesRecursion;

  type Sequence=array [byte] of byte;

  var M,N:byte;

      X:Sequence;

  procedure Generate(k:byte);

       ............

begin

  write('M,N=');readln(M,N);

  Generate(0)

end.

  Перестановки (рекурсивный алгоритм)

Задача та же, что в пункте 1.2. Опишем рекурсивную процедуру Generate(k), предъявляющую все перестановки чисел 1,...,N, у которых фиксировано начало X[1],X[2],...,X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом (это существенно!). Понятно, что при k=N мы снова имеем только тривиальное решение - саму перестановку. При k<N будем сводить задачу к k+1:

  procedure Generate(k:byte);

    var i,j:byte;

    procedure Swap(var a,b:byte);

      var c:byte;

    begin c:=a;a:=b;b:=c end;

  begin

    if k=N then

      begin for i:=1 to N do write(X[i]);writeln end

    else

      for j:=k+1 to N do

 begin

   Swap(X[k+1],X[j]);

   Generate(k+1);

   Swap(X[k+1],X[j])

 end

  end;

Основная программа:

program PerestanovkiRecursion;

  type Pere=array [byte] of byte;

  var N,i,j:byte;

      X:Pere;

  procedure Generate(k:byte);

      ...............

begin

  write('N=');readln(N);

  for i:=1 to N do X[i]:=i;

  Generate(0)

end.

Чтобы до конца разобраться в этой непростой программе, советуем выполнить ее на бумаге при N=3. Обратите внимание, что порядок вывода перестановок не будет лексикографическим!

Перебор с отходом назад

Как вы уже поняли, перебор комбинаторных объектов - задача весьма трудоемкая даже для компьютера. Hапример, перестановок из восьми чисел будет 8! = 40320 - число немаленькое. Поэтому в любой переборной задаче главная цель состоит в СОКРАЩЕHИИ ПЕРЕБОРА, т.е. в исключении тех объектов, которые заведомо не могут стать решением задачи. Предположим, что нам требуется рассмотреть только те перестановки, для которых сумма |X[i]-i| равна 8. Понятно, что их будет гораздо меньше: например, все перестановки, начинающиеся на 8,7,... рассматривать не нужно! Как можно модифицировать наш переборный алгоритм в этом случае? Если на каком-то этапе сумма

|X[1]-1| + |X[2]-2| + ... + |X[k]-k|

уже больше 8, то рассматривать все перестановки, начинающиеся на X[1],...,X[k] уже не нужно - следует вернуться к X[k] и изменить его значение ("отойти назад" - отсюда название метода).

Для такой ситуации мы рассмотрим один общий метод, который почти всегда позволяет значительно сократить перебор. Пусть искомое решение находится среди последовательностей вида

X[1],...,X[N],

где каждое X[i] выбирается из некоторого множества вариантов A[i]. Предположим мы уже построили начало этой последовательности X[1],...,X[k] (k<N) и хотим продолжить его до решения.

Предположим также, что у нас есть некоторый простой метод P(X[1],...,X[k]), который позволяет получить ответ на вопрос: можно продолжить X[1],...,X[k] до решения (true) или нет (false). Заметим, что значение true еще HЕ ГАРАHТИРУЕТ существование такого продолжения, но зато значение false ГАРАHТИРУЕТ непродолжаемость ("не стоит дальше и пробовать"). Получаем простую рекурсивную процедуру ПЕРЕБОРА С ОТХОДОМ HАЗАД:

      procedure Backtracking(k);

      begin

 for (y in A[k]) do

   if P(X[1],...,X[k-1],y) then

     begin

       X[k]:=y;

       if k=N then {X[1],...,X[N] -решение}

       Backtracking(k+1)

     end

      end;

PAGE  1


 

А также другие работы, которые могут Вас заинтересовать

70459. Развитие групп 27.5 KB
  Формирование стадия на которой происходит отбор членов группы в соответствии с их функциональным или техническим опытом для выполнения целей стоящих перед группой. Члены группы знакомятся обмениваются официальной информацией друг о друге вносят предложения о работе группы например...
70460. Руководство и лидерство как формы социальной власти в группе 28.5 KB
  Лидерство и руководство рассматриваются в социальной психологии как групповые процессы связанные с социальной властью в группе. Под лидером и руководителем понимается человек оказывающий ведущее влияние на группу: лидер в системе неформальных отношений руководитель...
70461. Конфликт как форма социального взаимодействия 30 KB
  Понятие конфликт характеризуется исключительной широтой содержания и употребляется в разнообразных значениях. Самым общим образом конфликт можно определить как предельное обострение противоречий. В специальной литературе конфликты рассматриваются на социальном...
70462. Основные модели конфликта 44.5 KB
  Любые организационные изменения противоречивые ситуации деловые и личностные отношения между людьми нередко порождают конфликтные ситуации которые субъективно сопровождаются серьезными психологическими переживаниями.
70463. Проблема оптимального и эффективного поведения в конфликт 48 KB
  Методы прекращения конфликта. Уклонение Такой стиль поведения обычно выбирают в тех случаях когда: проблема вызвавшая столкновение не представляется субъекту конфликта существенной; предмет расхождения по его мнению мелочный основан на вкусовых различиях не заслуживает траты времени и сил...
70465. Общение в единстве процессов обмена информации, восприятия и понимания людьми друг друга, воздействия и взаимодействия 50 KB
  Из определения общения вытекает что это сложный процесс в который входят три составляющие: коммуникативная сторона общения обмен информацией между людьми; интерактивная сторона организация взаимодействия между индивидами; перцептивная сторона процесс восприятия друг друга партнерами...
70466. Социально-психологические закономерности формирования первого впечатления о человеке 29.5 KB
  Среди факторов которые определяют характер формирующегося у нас впечатления о человеке которого мы встречаем в своей жизни впервые важнейшее значение имеют особенности внешнего облика и поведения человека о котором у нас формируется мнение.
70467. Механизмы межличностного восприятия 27.5 KB
  Значительное число исследований восприятия межличностного посвящено изучению формирования первого впечатления о человеке. В них выясняются закономерности достраивания образа другого человека на основе наличной обычно ограниченной информации о нем а также при выявлении...