Adabiyot Tomas X. Kormen, Charlz I. Leyserson, Ronald L. Rivest, Klifford Shtayn. Algoritmlar: Qurilish va tahlil, 3-nashr = Algoritmlarga kirish, Uchinchi Nashr. M.: "Uilyams", 2013. 1328 b. Okulov S

Kurs uchun tavsiya etilgan o'qishlar ro'yxati
Adabiyot
1. Tomas X. Kormen, Charlz I. Leyserson, Ronald L. Rivest, Klifford Shtayn. Algoritmlar: Qurilish va tahlil, 3-nashr = Algoritmlarga kirish, Uchinchi Nashr. M .: "Uilyams", 2013.1328 b.
2. Okulov S.M. Algoritmlarda dasturlash. M .: BINOM. Bilim laboratoriyasi, 2002,341 s.
3. Shen A. Dasturlash. Teoremalar va muammolar. 2-nashr, Rev. va qo'shing. Moskva: 2004 yil. 296 s.
Internet resurslari
1. http://codeforces.ru/ saytida Codeforces ishlaydi. Onlayn bo'lgan platforma musobaqalar, muammolar arxivi, muammolar tahlili, sportga oid bloglar mavjud dasturlash.
2. http://www.topcoder.com/tc Competitions TopCoder dasturlash.
3. http://acm.timus.ru/ Timus Onlayn Sudyasi. Ural federal universitet. Avtomatik tekshirish bilan vazifalar arxivi.
4.http: //acm.sgu.ru/ Saratov davlat universiteti sayti. Bilan vazifalar arxivi avtomatik tekshirish.
5.http: //acm.ssau.ru/ Samara dasturlash olimpiadalari.
6.http: //neerc.ifmo.ru/school/ Informatika fanidan maktab olimpiadalari sayti.
7.http: //acm.baylor.edu/icpc/ ACM xalqaro kollej dasturlash tanlovi. ACM talabalar jahon chempionati rasmiy sayti ICPC.
8. http://e-maxx.ru/ Algoritmlar sayti, ularni amalga oshirish misollari bilan.

1.1. Перебор всех возможных строк из заданных символов

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

Мы разберем как реализовывать перебор для решения разных задач. 
Начнем совсем элементарной задачи, 
пусть нужно перебирать все строки длины 3, 
состоящие из строчных латинских букв a, 
b и c. Каждую букву можно использовать несколько раз или не использовать совсем. 
Нетрудно посчитать, что будет всего 27 вариантов, 
вот они все представлены. 
Можно заметить, что удобно перебирать строки в определенном порядке: сначала идут строки, 
начинающийся с буквы а, 
затем начинающийся с буквы b и затем с буквы c. Если первая буква у строк совпадает, 
то они упорядочены по второй букве, 
а если совпадают первые две буквы, то по третьей. 
Такой порядок перебора строк называется лексикографический. 
Дадим строгое определение: пусть имеются две строки s и t одинаковой длины. 
Будем говорить, что строка s меньше t, 
если первые k символов этих строк совпадают, 
мы считаем, что в строках нуль индексация, 
а следующий символ у строки s меньше, 
чем у строк t. В этом определении k может быть равным нулю, 
то есть совпадающих символов у строк может и не быть совсем. 
Например, строка aba меньше чем baa. 
Они уже различаются по первому символу, 
а в следующих двух строках первые два символа совпадают, 
но зато третий символ у первой строке меньше чем у второй, 
а меньше с. Будем говорить, что строки, 
расположенные в лексикографическом порядке, 
если каждая строка меньше следующие за ней в смысле данного определения. 
Лексикографический порядок удобно использовать для перебора строк, 
потому что так проще отследить, 
что мы ничего не пропустили и не перебрали одну и ту же строку несколько раз. 
Подумаем как решать задачу о переборе строк из трех символов a, 
b и c. Это можно сделать таким вот образом, тремя возможными циклами. 
Перед вами код программы на языке С++. 
Во внешнем цикле переменная символьного типа С1 принимает значения от а до с, 
то есть последовательно а, b, 
c. Это будет первый символ в нашей строке. 
Во втором цикле мы аналогично перебираемся 2, 
второй символ нашей строки, 
и в третьем цикле, 
третий символ - С3. 
Дальше мы выводим все три символа и выводим перевод строки. 
Этот код выведет нам все необходимые строки в лексикографической порядке. 
Но что делать, если нужно решать более общую задачу, 
перебрать все строки длины n, 
состоящих из первых латинских букв. 
Сколько тогда вложенных циклов нам понадобится? 
Для большей общности мы будем перебирать не строки, 
а последовательности чисел от 1 до m, 
при этом каждое число может использоваться в 
последовательности несколько раз или не использоваться совсем. 
Напишем программу, которая решает эту задачу. 
Для этого нам понадобится вектор целых чисел а для хранения последовательности. 
Если вы не сталкивались раньше с вектором, 
то вектор - это аналог массива с некоторыми дополнительными возможностями. 
В С++ вектор содержатся в пространстве имен 
STD и для его использования нужно подключить заголовок файл - vector. 
Сейчас функцией main создается вектор целых чисел типа int 
размера n. Дальше мы будем использовать вектор а как обычный массив. 
Как я уже сказала, мы будем хранить в нем нашу 
последовательность и последовательность будет изменяться по ходу выполнения программы. 
Для перебора последовательности мы будем использовать функцию 
rec и передается 1 целочисленный параметр idx. 
Это индекс вектора а. Сначала мы вызываем функцию rec с idx, равным нулю. 
В самой функции rec, у нас будет цикл по i от 1 до m, 
в котором мы будем перебирать числа, 
когда мы фиксировали очередное число, 
мы пытаемся его поставить в позицию idx, 
то есть а от idx присваиваем i и дальше переходим к следующей позиции idx+1, 
то есть у нас для каждой позиции будут перебираться все возможные числа, 
как будто бы у нас несколько вложенных циклов. 
Добавим условие выхода из ракурсия: в векторе а у нас нуль индексация. 
Те элементы, которые нужно заполнить, 
имеют индексы от нуля до n-1, 
поэтому если индекс стал равен n, 
нам уже ничего не надо делать, 
мы вызываем функцию out, 
эта функция будет выводить содержимое вектора а, 
то есть нашу последовательность. 
Ее вам предстоит реализовать самостоятельно, 
и дальше выполняется return, 
выход из функции rec. 
Таким образом мы разобрали рекурсивную функцию, 
которая решает наша задача о переборе всех последовательностей. 
На следующей лекции мы разберем работу этой функции на примере.

1.2. Рекурсивный перебор на примере

На прошлой лекции мы написали рекурсивную функцию rec, 

которая перебирает все последовательности длины n из чисел от одного до 
м. На этой лекции мы разберем по шагам работу этой функции на примере. 
Пусть n равно двум, 
а м равно трем, то есть, 
нам нужно перебирать все последовательности длины 2, 
состоящие из чисел 1, 2 и 3. 
Сначала мы заходим в функцию rec, 
с индексом равным нулю. 
Индекс пока не равен n, 
то есть if не выполнится, 
и мы переходим сразу к циклу i равно единице. 
Мы в ячейку а {idx} то есть а нулевое, 
помещаем единичку и переходим на следующий уровень рекурсии. 
Теперь idx равен единице, 
idх пока что не равно N, 
условие не выполняется и мы снова переходим к циклу. 
Снова i равно единице. 
Мы помещаем эту единицу в ячейку а idх, 
то есть а первое. 
И переходим на следующий уровень рекурсии. 
Теперь idх равен двум, 
то есть выполняется условие idх равно N. Вызывается функция int, 
которая выводит содержимое вектора а, последовательность 1:1. 
И выполняется return, выход из рекурсии. 
Мы оказываемся на предыдущем уровне рекурсии с idх равным единице и i равна единице. 
На следующей итерации цикла i увеличивается до двойки. 
Мы помещаем в ячейку а idх, 
то есть а первое двойку, 
и переходим на следующий уровень рекурсии. 
Снова idх равен двум, вызывается функция out, 
которая нам выводит текущую последовательность 1, 
2 и выполняется return, выход из рекурсии. 
Мы возвращаемся на предыдущий уровень ракурсии с idх равным единице и равным двойке. 
Заменим двойку на тройку и выведем последовательность 1, 3. 
Дальше выполнение цикла при idх равном единице 
у нас завершится и мы вернемся на самый первый уровень рекурсии с idх равным нулю. 
В ячейку а idх, то есть а нулевое, 
мы поместим значение 2 заметим, 
что в ячейке а1 у нас сейчас находится тройка, 
которая осталась с предыдущих шагов, 
на следующем уровне рекурсии она заменится сначала на единицу, потом на двойку, 
потом на тройку и мы выведем три следующих последовательности 2:1, 
2: 2, 2: 3. 
Дальше то же самое повторится с первой цифрой тройкой. 
И мы получим ответ на задачу: все возможные последовательности длины 2 из чисел 1, 2 и 3. 
Работу функции rec можно представить себе как обход вот такого дерева. 
В каждой вершине этого дерева содержится последовательность, 
вершина на верхнем уровне, 
пустая последовательность при переходе от вершины к ее 
потомкам в последовательности добавляется число 1 два или три. 
Наша задача вывести все последовательности на нижнем уровне, 
состоящие из двух чисел. 
Функция rec будет обходить 
вершины этого дерева и idх будет соответствовать уровню вершины. 
Итак, мы с вами разобрали работу функции rec на примере. 
После лекции вам будет дан код этой программы полностью, 
с подключением всех необходимых библиотек, 
объявлением переменных файлов, вводам, 
выводам, чтобы у вас был хотя бы один рабочий образец. 
Я думаю, что вот этот алгоритм рекурсивного перебора, 
он все таки довольно сложный для новичков. 
Поэтому не расстраивайтесь, если вы что-то не допоняли. 
Попробуете еще раз поотлаживать эту программу на каких-то примерах, 
посмотреть как она работает. 
Если вы сейчас в этом разберитесь, 
вам дальше будет проще, 
потому что реализация остальных задач на 
перебор в наших лекциях будет основана на тех же самых идеях. 
И мы уже остальные решения будем разбирать не столь подробно.

Код программы

#include 

#include 

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int n, m;

vector a;

void out()

{
for (int i = 0; i < n; i++)
{
if (i)
cout << " ";
cout << a[i];
}
cout << endl;
}

void rec(int idx)

{
if (idx == n)
{
out();
return;
}
for (int i = 1; i <= m; i++)
{
a[idx] = i;
rec(idx + 1);
} 
}

int main()

{
cin >> n >> m;
a = vector(n);
rec(0);

return 0;

}

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

Masala: вывести все последовательности чисел от 1 до n в которых каждый числа встречается ровно один раз

Давайте немного изменим задачу. 
Пусть нам теперь нужно перебрать все последовательности чисел от 1 до n, 
в которых каждое число встречается ровно один раз. 
Такие последовательности называются перестановками. 
Например, вот все перестановки для n = 3 в лексикографическом порядке. 
Итак, нам нужно перебрать все возможные перестановки. 
Для этого мы будем использовать рекурсивную функцию rec. 
Здесь я в ней сразу заменила в цикле m на n, потому что теперь мы можем 
использовать числа от 1 до n, то есть до размера перестановки. 
Что эта функция у нас будет делать неправильно? 
Она будет использовать одни и те же числа по нескольку раз. 
Нужно запретить каким-то образом ей это делать. 
Для этой цели мы создадим вектор used со значениями логического типа bool. 
used в английском языке означает «использованный». 
Мы также будем идти по вектору a и добавлять в него числа, при этом в векторе 
used мы будем помечать, какие числа у нас уже использованы, а какие еще нет. 
Значение в ячейке i вектора used будет true, если число i уже занято, 
и used [i] будет false, если это число свободно. 
Сначала мы создаем вектор used размера n + 1 и заполняем его ложными значениями. 
Размер n + 1, потому что можно использовать числа от 1 до n, 
и нам может понадобиться n-ная ячейка вектора used. 
Посмотрим, какие изменения нужно будет внести в функцию rec. 
Во-первых, когда мы перебираем число i, нам нужно будет понимать, 
использовано оно уже или нет. 
Мы добавляем проверку. 
Проверяем значение used [i], и если оно равно true, то выполняем continue, 
то есть переход к следующему числу. 
Далее, если это число не использовано, то мы помещаем его в ячейку a [idx]. 
И второе, что нам нужно будет сделать, это присвоить used [i] = true, 
то есть пометить, что это число теперь использовано. 
Дальше выполняется переход на следующий уровень рекурсии, 
и после возврата из рекурсии нам нужно будет обязательно освободить это число, 
то есть в векторе used присвоить значение used [i] = false. 
Посмотрим, как будет работать новая функция rec на примере. 
Пусть n = 2, то есть нам нужно перебрать все перестановки из двух элементов. 
Мы заходим в функцию rec с idx = 0 и вектором used, 
заполненным ложными значениями. 
Выполняем проверку. 
idx пока что не равен n, поэтому мы переходим к циклу. 
Значение i = 1. 
Мы проверяем, использовано ли уже это значение. 
used [i] пока что false. 
Поэтому мы переходим к следующей строчке, и в ячейку a [idx], 
то есть в a0 мы помещаем значение 1. 
Помечаем, что единица у нас уже использована, 
то есть used [1] присваиваем значение true. 
Переходим на следующий уровень рекурсии. 
Теперь idx = 1. 
idx не равен n, поэтому снова переходим к циклу, и снова у нас i = 1. 
Проверяем. 
Использована единица? 
Теперь она использована. 
used [1] = true, поэтому выполняется continue. 
Переход к следующей итерации цикла. 
На следующей итерации цикла у нас i = 2. 
Теперь это значение не использовано, поэтому мы продолжаем выполнять цикл. 
Мы ячейку a [idx], то есть в a1, помечаем значение 2. 
Отмечаем, что двойка у нас использована, 
used [2] присваиваем true и переходим на следующий уровень рекурсии. 
Теперь idx =2, то есть выполняется условие idx = m, условие выхода из рекурсии. 
Вызывается функция out, 
она выводит содержимое вектора a последовательность 1 2. 
И выполняется return, выход из функции rec, 
мы возвращаемся на предыдущий уровень рекурсии с idx = 1 и i = 2. 
Мы освобождаем двойку, говорим, что used [2] присваивается false. 
Заметим, что двойка у нас осталась в векторе a, 
но это рудимент из предыдущих шагов, то есть можно считать, что у нас ее там нет. 
После этого цикл заканчивает выполняться, потому что i становится больше n. 
И мы возвращаемся на предыдущий уровень рекурсии с idx = 0 и i = 1. 
Мы освобождаем 1, то есть used [1] присваиваем false, 
и давайте мы на этом остановимся. 
На следующей итерации цикла мы поместим в ячейку a0 значение 2. 
И на следующем уровне рекурсии в ячейку a1 поместим 1. 
Выведем последовательность 2 1. 
Заметим, что у нас всего две перестановки из двух элементов: 1 2 и 2 1. 
Мы их обе вывели. 
Таким образом, мы модифицировали функцию rec, добавили в нее вектор used, 
чтобы она теперь нам генерировала все возможные перестановки из n элементов.