Комбинаторные алгоритмы решения школьных задач по информатике

 

С = = 35.

 

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

 

С = = 15150.

 

Пример 3. Сколько наборов из 7 пирожных можно составить, если в продаже имеются 4 сорта пирожных?

Здесь получаем сочетания с повторениями С = С = С =С = = 120.

1.2. Перестановки из элементов  n

Перестановкой из n элементов называется последовательность, состоящая из всех элементов некоторого n-элементного множества, причем число элементов этой последовательности равно n.   

 Характерные особенности понятия «перестановка» (существенные признаки понятия):

1. Задано некоторое  множество из n элементов.

2. Составляется последовательность  из всех элементов этого множества.

3. Эта последовательность  содержит n элементов.    

 Различия и сходства  в определениях перестановок и размещений.

Сходства: перестановки и размещения – это последовательности элементов n-элементного подмножества. В них имеет значение порядок  следования элементов последовательности.

Различия: в размещении могут участвовать не все элементы исходного множества. В перестановке обязательно участвуют все элементы исходного множества.    

 Число перестановок  можно вычислить по формуле  Pn=n! 

Пример: В расписании сессии 3 экзамена (история, геометрия, алгебра). Сколько может быть вариантов  расписаний?

Решение:

Основное множество: {история, геометрия, алгебра} n=3

Соединение – вариант  расписания сессии

Проверим, важен ли порядок:

{история, геометрия,  алгебра} и {геометрия, история,  алгебра} – варианты расписания  сессии для разных групп порядок  важен это последовательность это размещение «из трех по три» это перестановка из трех элементов.

P3=3!=6 (вариантов)

Ответ: 6 вариантов 

Генерирование перестановок.    

 Займемся алгоритмом генерирования  всех n! перестановок n-элементного множества.  Этой проблеме посвящено много публикаций, она имеет давнюю историю, ее возникновение можно отнести к началу XVII века, когда в Англии зародилось особое искусство колокольного боя, основанного, если говорить упрощенно, на выбивании на n разных колоколах всех n! Перестановок. Перестановки эти следовало выбивать «по памяти», что способствовало разработке сторонниками этого искусства первых простых методов систематического перечисления всех перестановок (без повторений). Некоторые из этих незаслуженно забытых методов были переоткрыты в настоящее время в связи с появлением цифровых машин.    

 Сейчас опишем метод генерирования  последовательности всех n! перестановок n-элементного множества. Будем  предполагать, что элементы нашего  множества запоминаются в виде  элементов массива Р[1],..., Р[n]. В данном методе элементарной операцией, которая применяется к массиву Р, является поэлементная транспозиция, т.е. обмен значениями переменных P[i] и P[j], где 1 < i,j < n. Эту операцию будем обозначать через Р[i] :=: P[j]. Очевидно, что она эквивалентна последовательности команд

роm := Р[i]; Р[i] := P[j]; P[j] := роm,

где роm есть некоторая вспомогательная переменная.   

 Алгоритм. (Генерирование всех перестановок за минимальное число транспозиций.)

Данные: n.

Результат: Последовательность перестановок множества {1,...,n}, в котором каждая последующая перестановка образуется из предыдущей путем выполнения одной транспозиции.

1. procedure В(m, i);

2. begin

3. if (m mod 2=0) and (m > 2) then

4.  if i < m — 1 then В := i

5.  else В := m — 2

6.  else В := m — 1

7. end; (*B*)

8.    procedure PERM(m); (* массив P — глобальный*)

9.    begin

10.  if m = 1 then (*P[1],... ,P[m] — новая перестановка*)

11.  write (P[l],...,P[n])

12.  else

13.  for i := 1 to m do

14.   begin PERM(m - 1);

15.  if i < m then P[B(m,i)] :=: P[m]

16. end

17. end; (*PERM*)

18. begin (* главная программа*)

19.   for i := 1 to n do Р[i] := i;

20.    PERM(n)

21. end    

 Отметим, что для нечетного  m транспозиция в строке 15 сводится к Р[m— 1] :=: Р[m], для каждого i < m для четного m значение Р[m] меняется последовательно на значения Р[1], Р[2],..., Р[m— 3], Р[m — 2], Р[m — 1]  (Р[1] для m-2).

Рассмотрим примеры:

Пример 1. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать?   

Решение: P₇ =7! =1•2• 3• 4• 5• 6• 7 = 840.

Пример 2. Сколько слов получится при перестановке слова "толпа"? 

Решение: Р₅ = 5! = 120.

Пример 3. Сколько слов получится, если переставлять буквы в слове "топот"?

Решение: В ответе получим перестановки с повторениями

Р ( 2, 2, 1) = =30.

1.3. Размещение m элементов по n позициям

Определение. Упорядоченные k-элементные подмножества, содержащие k элементов из данного n-элементного множества, называют размещениями без повторений из n элементов по k. Их число обозначают   (A — первая буква фр. arrangement— размещение). Два размещения отличаются либо составом элементов, либо порядком следования элементов. Характерные особенности понятия «размещение» (существенные признаки понятия «размещение»):

1. Задано некоторое множество из n элементов.

2.  Выделена последовательность элементов этого множества.

3. Эта последовательность содержит m элементов.

4. Эти m  элементов различны.   

 Различие  в определениях сочетаний и  размещений.

Сочетание – это подмножество, содержащее m элементов из n.

Размещение – это последовательность, содержащая m элементов из n.

Необходимо понимать, что при  формировании последовательности, важен  порядок следования элементов, а при формировании подмножества порядок не важен. Значит, при формировании сочетания из n-элементного множества, безразличен порядок следования элементов, а при формировании размещения из n-элементного множества, порядок следования элементов важен.

Теорема 1. (о числе размещений без повторений). Число размещений без повторений из n элементов по k определяется по формуле

Данная задача имеет  решение только при k ≤ n. Отведем для элементов размещения строку ( 1;  2; ...;  k) длины k. Так как на первую позицию можно поместить любой из n элементов данного множества, а на вторую — любой из n – 1 оставшихся элементов, то, по правилу произведения, число различных способов для заполнения первых двух позиций строки равно n(n – 1). Далее аналогично: на третью можно поместить любой из n – 2 элементов, а, по правилу произведения, различных способов для заполнения первых трех позиций получается n(n – 1)(n – 2) и т.д. Окончательно получаем, что общее число строк длины k, формируемых из различных элементов n-элементного множества, равно

= n∙(n-1)∙...∙(n-k+1)

Отсюда получаем

(1)

Рассмотрим примеры:

Пример 1. Сколькими способами из 25 учеников класса можно выделить актив в следующем составе: культорг, физорг и редактор стенгазеты?

Решение: Требуется выделить упорядоченные трехэлементные подмножества множества, содержащего 25 элементов, то есть найти число размещений без повторений из 25 элементов по 3. По формуле (1) находим

Определение. Размещение из n элементов по n называется перестановкой из n элементов. Их число обозначают P_n (от фр. permutation — перестановка). Например, P₃ = 6, так как из элементов 1, 2, 3 можно составить шесть различных перестановок:

.

Для нахождения числа Pn заметим, что перестановка без повторений из n элементов — это то же самое, что размещение без повторений из n элементов по n, то есть   Поэтому для отыскания значения Pn в формуле (1) положим k = n: 

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

Способ I. Из пяти различных цифр можно составить P₅ пятизначных чисел. Эти числа не должны быть кратны 5, то есть не могут оканчиваться цифрой 5. Если же цифру 5 поставить на последнее место, то остальные цифры могут распределиться по разрядам числа P₄ способами. Поэтому условию задачи удовлетворяет P₅ – P₄ = 5! – 4! = 120 – 24 = 96 чисел.

Способ II. Как уже было отмечено в первом способе, последняя цифра в записи числа может быть любой из данных, кроме 5. Следовательно, последний разряд может быть заполнен 4 способами. Соответственно, первые четыре разряда могут быть заполнены 4! способами. Всего, по правилу произведения, получается 4х4! = 96 способов, то есть 96 чисел.

Пример 3. Сколькими способами можно выбрать из класса, насчитывающего 25 учеников, старосту, культорга и физорга?

Решение: Получаем размещения из 25 по 3:

  А  = 5•4•3 =60.

Пример 4. В конкурсе принимают участие 20 человек. Сколькими способами можно присудить первую, вторую и третью премии?

Решение: Получаем размещения из 20 по 3:     А = 20•19•18 =6840.

Пример 5. Сколько пятизначных номеров можно составить из девяти цифр 1, 2, 3, 4, 5, 6, 7, 8, 9?

Решение: Это размещения с повторениями, можно нарисовать из номеров "дерево" и убедиться, что получим  А =9⁵ =59049.

Пример 6: Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различны и нечетны?

Решение:

Основное множество: {1, 3, 5, 7, 9} – нечетные цифры n=5

Соединение – двузначное число  m=2. Проверим, важен ли порядок:  – разные двузначные числа порядок важен это последовательность это размещение «из пяти по два».

(двузначных чисел)

Ответ: 20 чисел.

 

2. Алгоритмы  перебора

2.1. Перебор сочетаний, перестановки, размещения.

Характерная примета  в задачах из области комбинаторики  – вопрос в них обычно можно  сформулировать так, чтобы он начинался со слов: «Сколькими способами...». Первые задачи такого типа встречались  уже, например, в древней и средневековой  Индии. Задача: «О друг, назови число различных ожерелий, которые можно получить из бриллиантов, сапфиров, изумрудов, кораллов и жемчугов» (Маха вира, IX в.). Условие этой задачи, возможно, не очень понятно; судя по решению, здесь речь идет об ожерельях, которые бы отличались не по количеству или расположению камней одного и того же типа, а по наличию тех или иных камней – например, ожерелье из бриллиантов, из бриллиантов и кораллов, из бриллиантов, изумрудов и жемчугов и т. д. Решение: Конечно, эту задачу можно  решить простым перебором вариантов, но можно кое-что заметить. В разных ожерельях камни каждого конкретного вида могут наличествовать либо отсутствовать. Например, бриллианты могут быть, а могут не быть – две возможности. Как при наличии бриллиантов, так и при их отсутствии сапфиры могут быть, а могут или не быть – итого четыре возможности. И при наличии, и при отсутствии бриллиантов и сапфиров изумруды могут быть, а могут не быть, – итого восемь возможностей. И т. д. Следовательно, всего вариантов 25 = 32, правда, нужно еще вычесть один вариант отсутствия всех пяти камней (такое ожерелье, с точки зрения здравого смысла, ожерельем не является). Итак, ответ в задаче – 31 возможное ожерелье. БСИКЖ БСИК БСИЖ БСИ БСКЖ БСК БСЖ БС БИКЖ БИК БИЖ БИ БКЖ БК БЖ Б СИКЖ СИК СИЖ СИ СКЖ СК СЖ С ИКЖ ИК ИЖ И КЖ К Ж –   Задача: «Повар готовит различные блюда с шестью вкусовыми оттенками: острым, горьким, вяжущим, кислым, соленым, сладким. Друг, скажи, каково число всех разновидностей» (Шридхара, IX–X вв.). Решение: Аналогично решению  предыдущей задачи получаем 26 – 1 = 64 – 1 = 63. Классическими понятиями  комбинаторики являются перестановки, размещения и сочетания. Перестановкой называется какой-либо способ упорядочения данного множества. Чтобы найти число всех перестановок множества из n предметов (это число обозначается Pn, от французского permutation – перестановка) – например, число способов, которыми можно расставить n томов на книжной полке, – обычно рассуждают таким образом. Первым можно поставить любой из n предметов, вторым – любой из (n – 1) оставшихся предметов, третьим любой из (n – 2) оставшихся предметов и т. д. В результате число перестановок будет равно произведению n множителей n (n – 1) (n – 2) ... ∙ 3 ∙ 2 ∙ 1. Рис.2.1. Перестановки (варианты размещения четырех  предметов по четырем ячейкам) Упорядоченная совокупность m предметов, выбираемых из исходных n предметов, называется размещением из n по m. С помощью рассуждений, аналогичных предыдущим, нетрудно найти, что число размещений из n по m (оно обозначается , от французского arrangement – размещение) равно произведению m множителей n (n – 1) (n – 2) ... (n – m + 2) (n – m + 1). Рис. 2.2. Размещения (варианты размещения четырех предметов по трем ячейкам) Наконец, неупорядоченная  совокупность m предметов, выбираемых из исходных n предметов, называется сочетанием из n по m. Число сочетаний обозначается , от французского combinaison – сочетание. Поскольку одному и тому же сочетанию соответствует Pm размещений (получаемых с помощью различных перестановок одного и того же набора m элементов), число сочетаний из n по m меньше числа размещений из n по m в Pm раз:   Рис. 2.3. Сочетания (неупорядоченные размещения) Впервые понятия перестановки, размещения и сочетания в их взаимосвязи  появились в написанной на древенееврейском языке арифметике (1321 г.) жившего в Провансе (Юго-Восточная Франция) Льва Герсонида, или Леви бен Гершона, однако его труд не был известен большинству последующих европейских математиков. В основном элементы комбинаторики были открыты и упорядочены математиками XVII и начала XVIII вв. Например, термин permutation – перестановка – появился в  учебнике «Теория и практика арифметика» (1656 г.) у работавшего в Лувене и Антверпене (ныне Бельгия) преподавателя математики Андре Таке, учебники которого получили большое распространение в XVII–XVIII вв. Понятие размещений и равенство вновь появились только у Я. Бернулли, давшего наиболее полное изложение комбинаторики во второй части «Искусства предположений», изданного в 1713 г. спустя четыре года после смерти автора и ставшего фундаментальной работой по теории вероятностей. А вот история сочетаний, как мы сейчас убедимся, более давняя: а именно, числа сочетаний – оказывается, ни что иное, как давно знакомые нам биномиальные коэффициенты, которые мы (вслед за Эйлером) обозначали Дело тут вот в  чем: число  – это коэффициент при an – mbm в разложении выражения (a + b)n. Когда бином (a + b) возводится в n-ую степень, т. е. перемножаются n выражений (a + b), множитель bm получается из m выражений (a + b), а an – m – из оставшихся (n – m) таких же выражений. Коэффициент равен числу, указывающему, сколько раз произведение an – mbm появляется в этом разложении, т. е. сколько раз можно выбрать m из n множителей. Слово combinaison – сочетание – употреблял уже Б. Паскаль, который, как уже было указано, уделил большое внимание свойствам биномиальных сочетаний, образующих треугольник Паскаля. Соответственно, на числа сочетаний  переносятся все уже известные  свойства биномиальных коэффициентов, в частности, свойство Это свойство можно доказать новым способом, исходя из комбинаторного смысла чисел  . Сумма – это совокупное число, которым можно выбрать последовательно из n имеющихся элементов: ноль элементов (это можно сделать только одним способом), один элемент (это, разумеется, можно сделать n способами), два элемента и т. д., наконец, n элементов (снова одним способом). Каково же это суммарное число? Обратимся к способу решения вышеприведенной задачи об ожерельях! В данном сочетании первый элемент либо присутствует, либо нет – две возможности. Независимо от первого, второй либо присутствует, либо нет – значит, для присутствия или отсутствия первого и второго четыре возможности. Независимо от первого и второго, третий может присутствовать, может не присутствовать – итого 8 возможностей и т. д. Всего получается 2n всевозможных сочетаний, где каждый элемент может присутствовать, а может и отсутствовать, вплоть до одновременного отсутствия всех n элементов (единственный возможный вариант сочетания из n по 0): правда, индийская задача как раз этот – единственный – случай и исключала: ожерелье вовсе без камней – вообще не ожерелье. Также по-новому, исходя из комбинаторного определения сочетаний, можно доказать и свойство , гарантирующее, вместе с очевидными равенствами , что числа сочетаний можно найти с помощью треугольника Паскаля. Попробуйте! По определению, число  сочетаний из n по m – это число способов, которыми можно из n предметов выбрать m, порядок которых неважен. Как-либо выделим (n – 1) предмет из данных n. Тогда составить неупорядоченную совокупность m предметов из n данных можно, либо выбрав все m лишь из выделенных (n – 1), либо взять один невыделенный предмет, а оставшиеся (m – 1) выбрать из выделенных (n – 1) предмета. Получается, что общее число способов, которым можно создать неупорядоченную совокупность m предметов из n данных, равно числу способов, которым можно из (n – 1) предметов выбрать m, плюс число способов, которым из (n – 1) предметов можно выбрать (m – 1). Таким образом, Рис. 2.5. мультипликативное представление биномиальных коэффициентов Т. н. мультипликативное представление биномиальных коэффициентов  = (n (n – 1) (n – 2) ... (n – m + 2) (n – m + 1)) / (m (m – 1) (m – 2) ... ∙ 3 ∙ 2 ∙ 1) впервые (после Леви бен Гершона) установил парижский преподаватель математики П. Эригон (1634 г.), но широкую известность оно получило благодаря работе Паскаля «Трактат об арифметическом треугольнике», опубликованной в 1665 г. после смерти автора. Пожалуй, проще всего этот результат доказывается с помощью равенства . Впрочем, мы сейчас обычно записываем «мультипликативное представление» несколько иначе, с помощью знака факториала. Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n. Факториалом 0 считается 1. Термин «факториал» впервые предложил французский математик Л. Ф. А. Арбогаст (1800 г.). Факториал числа n обозначается n! Это обозначение ввел в 1808 г. немецкий математик К. Крамп. Итак, n! = 1 ∙ 2 ∙ 3 ∙ ... ∙ n, 0! = 1. В этих обозначениях Pn = n!,   Что касается самого слова  «комбинаторика», то оно восходит к  «Рассуждению о комбинаторном искусстве» двадцатилетнего Лейбница (1666 г.), которое положило начало этому разделу математики как самостоятельной науке. «Рассуждение» Лейбница содержало ряд теорем о сочетаниях и перестановках, но, кроме того, автор провозглашал весьма широкую применимость новой науки к таким разнообразным предметам, как замки, органы, силлогизмы, смешение цветов, стихосложение, логика, геометрия, военное искусство, грамматика, юриспруденция, медицина и богословие. В дальнейшем Лейбниц продолжил вынашивать грандиозный замысел комбинаторики, полагая, что, как обычная математика занимается большим и малым, единым и многим, целым и частью, так комбинаторика должна заниматься одинаковым и различным, похожим и непохожим, абсолютным и относительным местоположением. Лейбниц предвидел приложения комбинаторики к кодированию и декодированию, к играм, статистике, теории наблюдений. Следует отметить, что, хотя ныне мы понимаем комбинаторику более узко, тем не менее, предвидения Лейбница относительно развития математических теорий, относящихся к указанным предметам, ныне вовсе не выглядят такими беспочвенными, какими казались в его время.

 

3. Большие числа

3.1. Упаковка натурального числа  в виде массива

Южные и восточные  славянские народы для записи чисел  пользовались алфавитной нумерацией. Причем у русских роль цифр играли не все буквы, а только те, которые имеются в греческом алфавите. Над буквой, обозначавшей цифру, ставился специальный значок "титло". При этом числовые значения букв возрастали в том же порядке, в каком следовали буквы в греческом алфавите (порядок букв славянского алфавита был несколько иной).

В России славянская нумерация  сохранилась до конца 17 века. При  Петре I возобладала так называемая "арабская нумерация", которой  мы пользуемся и сейчас.

В названиях чисел  также происходили изменения. Например, до 15 века число "двадцать" обозначалось как "два десяти" (два десятка), но затем сократилось для более быстрого произношения. До 15 века число "сорок" обозначалось словом "четыредесяте", а в 15-16 веках это слово было вытеснено словом "сорок", которое исходно обозначало мешок, в который помещалось 40 беличьих или соболиных шкурок. О происхождении слова "тысяча" есть два варианта: от старого названия "толстое сто" или от модификации латинского слова centum - "сто".

Название "миллион" впервые появилось в Италии в 1500 г. и образовалось добавлением увеличительного суффикса к числу "милле" - тысяча (т.е. обозначало "большую тысячу"), в русский язык оно пронило позже, а до этого то же значение в русском языке обозначалось числом "леодр". Слово "миллиард" вошло в употребление лишь со времени франко-пруссой войны (1871 г.), когда французам пришлось уплатить Германии контрибуцию в 5 000 000 000 франков. Как и "миллион" слово "миллиард" происходит от корня "тысяча" с добавкой итальянского увеличительного суффикса. В Германии и Америке некоторое время под словом "миллиард" подразумевали число 100 000 000; этим объясняется, что слово миллиардер в Америке стало использоваться до того, как у кого-либо из богачей появилось 1000 000 000 долларов. В старинной (XVIII в.) "Арифметике" Магницкого, приводится таблица названий чисел, доведенная до "квадрильона" (10^24, по системе через 6 разрядов). Перельманом Я.И. в книге "Занимательная арифметика" приводятся названия больших чисел того времени, несколько отличающиеся от сегодняшних: септильон (10^42), октальон (10^48), нональон (10^54), декальон (10^60), эндекальон (10^66), додекальон (10^72) и написано, что "далее названий не имеется".

Принципы построения названий и список больших чисел

Все названия больших  чисел построены довольно простым образом: в начале идет латинское порядковое числительное, а в конце к нему добавляется суффикс -иллион. Исключение составляет название "миллион" которое является названием числа тысяча (mille) и увеличительного суффикса -иллион. В мире существует два основных типа названий больших чисел: 
система 3х+3 (где х - латинское порядковое числительное) - эта система используется в России, Франции, США, Канаде, Италии, Турции, Бразилии, Греции; 
система 6х (где х - латинское порядковое числительное) - эта система наиболее распространена в мире (например: Испания, Германия, Венгрия, Португалия, Польша, Чехия, Швеция, Дания, Финляндия).