10 класс
Повторение: Решить следующую задачу: Существует фирма, которая организует работу на контрактной основе, то есть если для какого-либо специалиста есть работа он нанимается, по окончания работы он увольняется, причем буквально на следующий день его могут нанять снова. Дан файл в котором хранится вся информация по рабочим за год, причем общее количество рабочих неизвестно. Она выглядит следующим образом: в первой строке записана фамилия рабочего, на следующей строке день и месяц его найма, на третьей – день и месяц окончания работы. Необходимо:
а) вывести на экран список рабочих напротив каждой фамилии каждого указано количество дней его работы, причем если рабочий был нанят несколько раз, то и в списке его фамилия фигурирует несколько раз.
б) вывести на экран список рабочих и у каждого указать общее количество рабочих дней за год.
в) сформированный в предыдущем пункте список отсортировать по убыванию количества рабочих дней.
Двоичный и к-ичный перебор.
Метод двоичного перебора применяется в тех случаях, когда требуется организовать перебор всевозможных подмножеств данного множества (множество в Паскале представляет собой набор различных элементов одного типа). То есть если есть набор каких-либо элементов, то из него мы можем выбирать элементы в любых сочетаниях, и в любых количествах (например, группа людей в количестве ну для определенности пяти человек, собирается на прогулку, при этом они в итоге могут пойти все, а если вдруг испортилась погода, то может не пойти вообще никто, а могут собраться двое, трое и т.д.).
Очевидно, что каждый элемент из рассматриваемого множества может иметь только два состояния (включен или не включен, активен или не активен, есть или нет). Получаем, что каждый элемент может иметь только два значения именно поэтому данный метод, и является двоичным.
В качестве модели рассмотрим массив из n элементов, каждый из которых может принимать только два значения (каждый элемент массива соответствует какому-то одному объекту множества), следовательно, получаем, что элемент массива может принимать только два значения: 0 – не выбран или 1 - выбран, то есть данный объект множества включен в подмножество.
Задача сводится к тому, чтобы перебрать все возможные комбинации 0 и 1, в результате чего учитываются все варианты, при этом они не должны повторяться. Для определенности рассмотрим множество, состоящее из пяти элементов. Вначале в массив запишем пять нулей: (0, 0, 0, 0, 0). Эти нули соответствуют начальному состоянию множества, заключающееся в том, что выбранных объектов нет (то есть пустое множество).
На первом шаге обработки массива, увеличим на единицу последний элемент массива, то есть, получаем следующее подмножество (0, 0, 0, 0, 1). Тем самым мы получили новый возможный вариант комплектации массива, в котором выбран последний пятый элемент.
На втором шаге снова увеличиваем последний элемент массива на единицу, при этом получаем что он равняется двойке, что невозможно по условию формирования массива, следовательно последний элемент необходимо занулить, а на единицу увеличиваем предыдущий элемент, то есть четвертый, получаем (0, 0, 0, 1, 0). Этот вариант соответствует тому, что выбран только четвертый объект множества.
На третьем шаге снова увеличиваем последний элемент массива на единицу, получаем (0, 0, 0, 1, 1). Что соответствует тому, что выбраны уже четвертый и пятый объект некоторого множества.
На четвертом шаге снова увеличиваем последний элемент массива на единицу, и он у нас в итоге равняется двойке, что невозможно, поэтому мы его зануляем, а на единицу увеличиваем предыдущий разряд, при этом он так же обращается в двойку, необходимо и его занулить, а на единицу увеличить третий элемент массива, в результате получаем такой вариант (0, 0, 1, 0, 0). Следовательно, во множестве выбран только третий объект.
И таким образом происходит перебор всех возможных вариантов формирования множества состоящего из нулей и единиц. Последний возможный вариант для нашего множества, это все единицы (1, 1, 1, 1, 1). Что соответствует выбору всех объектов рассматриваемого множества. Предположим, что мы не остановились на этом этапе и продолжили увеличивать наш массив, то есть на единицу увеличиваем последний элемент массива, при этом он обращается в двойку, мы его зануляем и переносим единицу в предыдущий разряд, и в нем получаем двойку, снова зануляем и переносим, и это продолжается до тех пор, пока мы не оказываемся в позиции первого элемента, который также обращается в двойку, которую необходимо занулить а единицу перенести в предыдущий разряд, то есть в нулевой, который в обычном используемом нами массиве не фигурирует. Следовательно, в данном случае нам необходимо определить позицию нулевого элемента массива для определения окончания перебора всех возможных вариантов формирования массива из нулей и единиц. То есть в начале мы формирует массив из всех нулей, в том числе ноль находится и в нулевом разряде, после того как нами перебраны все варианты, и единицы находятся во всех позициях кроме нулевой мы делаем следующий шаг и получаем нули во всех позициях кроме нулевой, там находится единица, вот именно эта единица и будет служить для нас окончанием перебора всевозможных вариантов. В результате перебора мы должны получить 2n вариантов, где n – количество элементов массива. Для успешной работы программы n не может быть бесконечно, при n>20 на обработку данных программе требуется уже очень много времени.
Алгоритм решения задачи с использованием двоичного перебора:
-
Ввести исходные данные (если в этом есть необходимость). -
Сформировать нулевой вектор с номерами элементов от 0 до n. -
Обработать этот вектор. -
Сформировать новый вектор. -
Если нулевой разряд вектора равен 0, то повторить третий пункт, иначе закончить.
Задача 1: Вывести на экран всевозможные наборы 0 и 1 и их порядковые номера.
program primer;
uses crt;
var p: array [0..30] of byte;
n, i, k: integer;
procedure vector;
begin
i:=n;
while p[i]=1 do begin
p[i]:=0;
dec(i);
end;
p[i]:=1;
end;
procedure work;
begin
inc(k);
write (k:3,’: ‘);
for i:=1 to n do
write (p[i]);
writeln;
end;
begin
clrscr;
writeln (‘Введите n’);
readln (n);
k:=0;
for i:=0 to n do p[i]:=0;
repeat
work;
vector;
until p[0]=1;
readln;
end.
Задачи:
-
Даны n различных цифр, получить из них всевозможные числа, при условии, что в числе цифры не повторяются. -
Даны n различных букв, получить все возможные слова из них при условии что буквы в словах не повторяются. -
Имеется n монет разного достоинства, определить, можно ли получить задуманную сумму денег, данными монетами. Если вариантов несколько, то вывести их все на экран, а если их нет, то сообщить об этом. -
Имеется n камней (известна их масса), разложить эти камни на две кучки так, чтобы массы этих кучек отличались друг от друга как можно меньше (в идеале совпадали). -
Даны две строки, определить может ли первая строка быть получена путем зачеркивания элементов второй. -
Известны массы n гирек. определить, можно ли заданный груз взвесить этими гирьками. Если можно, то указать наилучший (по числу используемых гирек) способ взвешивания. Задачу решить для двух случаев: а) груз на одной чаше весов, гирьки на другой; б) гирьки могут находиться на обеих чашках весов.
Контрольная работа:
-
Дан ряд цифр 1, 2, 3, 4, 5, 6, 7, 8, 9. Можно ли получить данное число s, расставляя между цифрами знаки + и -. Если можно то указать способ расстановки знаков. ( Тесты: s=45 1+2+3+4+5+6+7+8+9; s=2 нельзя (любое четное нельзя); s=1 1-2-3-4+5-6-7+8+9 (12 вариантов); s=47 нельзя; s=31 1+2+3+4+5+6-7+8+9 (3 варианта). -
Известно количество страниц в каждом из n произведений. определить можно ли распределить эти произведения на 3 тома так, чтобы все тома оказались одинаковыми. Если можно, то вывести один из вариантов распределения. (Тесты: n=6 (7, 10, 4, 8, 2, 5) можно (7+5, 8+4, 10+2); n=5 (5, 4, 6, 3, 8) нельзя; n=3 (5, 5, 5) можно (5, 5, 5); n=8 (5, 4, 3, 4, 2, 1, 6, 5) можно (по 10); n=6 (3, 3, 3, 3, 3, 5) нельзя). -
Известны массы n камней. Распределить камни на три кучки так, чтобы массы самой легкой и самой тяжелой кучки отличались минимально. в идеале совпадали.
Генерация перестановок.
Предположим, что нам дана такая задача: Вывести на экран все перестановки чисел 1..n (то есть последовательности длины n, в каждую из которых каждое из чисел 1..n входит по одному разу).
Для определенности рассмотрим пример при n=5.
Изначально имеем такую расстановку чисел 1 2 3 4 5.
На первом шаге поменяем местами два последних элемента, получим 1 2 3 5 4.
Дальше начнем искать первый с конца элемент, который будет меньше следующего за ним (5>4, а вот 3<5). Следовательно, таким элементом будет тройка, стоящая на третьей позиции. Теперь необходимо найти самый правый элемент больший, чем этот ( 5>3, но правее стоит 4, и она тоже больше тройки), следовательно таким элементом будет четверка стоящая на пятой позиции. Меняем их местами. Получили такую перестановку: 1 2 4 5 3. при этом хвост массива, то есть элементы, стоящие на двух последних местах оказались упорядоченными по убыванию, поэтому если мы ничего не изменим, то они так и останутся навсегда на своих местах, и тем самым мы потеряем некоторые варианты, для того чтобы этого не произошло, переставим их в порядке возрастания, и только после этого будем считать, что мы нашли новый, третий по счету вариант перестановки: 1 2 4 3 5.
Теперь опять начинаем просматривать массив с конца в поисках первой пары элементов, из которых левый меньше правого, а также самый правый элемент больший этого левого (3<5, и при этом 5 самый правый), следовательно, необходимо поменять их местами
{Этот алгоритм хорошо известен и достаточно подробно изложен. Опишем его (при N=5), от чего рассуждения не утратят общности. Алгоритм составлен так, что в процессе его исполнения перестановки N чисел располагаются лексикографически (в словарном порядке). Это значит, что перестановки сравниваются слева направо поэлементно. Больше та, у которой раньше встретился элемент, больше соответствующего ему элемента во второй перестановке. (Например, если S=(3,5,4,6,7), а L=(3,5,6,4,7), то S Принцип работы алгоритма разъясним на примере. Допустим, необходимо воспроизвести все перестановки цифр 3,4,5,6,7. Первой перестановкой считаем перестановку (3,4,5,6,7). Последней воспроизводимой перестановкой будет (7,6,5,4,3). Предположим, что на некотором шаге работы алгоритма получена перестановка
P=(5,6,7,4,3). Для того чтобы определить непосредственно следующую за ней перестановку, необходимо, пересматривая данную перестановку справа налево, следить за тем, чтобы каждое следующее число было больше предыдущего, и остановиться сразу же, как только это правило нарушится. Место останова указано стрелкой:
(5,6,7,4,3).
Затем вновь просматриваем пройденный путь ( справа налево ) до тех пор, пока не дойдем до первого числа, которое уже больше отмеченного. Ниже место второго останова отмечено двойной стрелкой.
(5,6,7,4,3).
Поменяем местами, отмеченные числа:
(5,7,6,4,3).
Теперь в зоне, расположенной справа от двойной стрелки, упорядочим все числа в порядке возрастания. Так как до сих пор они были упорядочены по убыванию, то это легко сделать, перевернув указанный отрезок. Получим: Q=(5,7,3,4,6).
Q и есть та перестановка, которая должна воспроизводиться непосредственно после P.
Действительно, P Алгоритм генерации перестановок:
Просматриваем a1,.., an с кона до тех пор, пока не попадется ai
Рассматриваем ai+1, …, an. Находим первый с конца am>ai и меняем их местами.
ai+1, ai+2, …, an переставим в порядке возрастания.
Выводим найденную перестановку.
Возвращаемся к первому пункту.
В результате всех перестановок, всевозможных вариантов должно получиться n!, где n – количество элементов рассматриваемого массива.
Первой должна быть перестановка 1 2 3 …n, а последней n n-1…2 1.
program perest;
uses crt;
var
a: array [1..20] of byte;
i, j, k, n, kol, z: integer;
procedure form;
begin
i:=n-1;
while (i>0) and (a[i]>a[i+1]) do dec(i);
if i>0 then begin
j:=n;
while a[j]
z:=a[i]; a[i]:=a[j]: a[j]:=z;
for k:=i+1 to (i+1+n) div 2 do begin
z:=a[k];
a[k]:=a[n-k+i+1];
a[n-k+i+1]:=z;
end;
end;
end;
procedure obr;
begin
for i:=1 to n do
write (a[i], ‘ ‘ );
writeln;
inc(i);
end;
begin
clrscr;
writeln(‘Введите количество элементов');
readln(n);
for i:=1 to n do
a[i]:=i;
repeat
obr;
form;
until i=0;
writeln(‘Количство вариантов’, kol);
readln;
end.
Задачи:
-
Вывести на экран все перестановки последовательности n различных букв: абвгд… -
Письма на удачу вкладываются в подписанные конверты. Определить количество раскладок, когда ни одно из n писем не попадает к своему адресату. -
Вывести на экран все перестановки из n различных букв при условии, что гласные буквы не могут стоять рядом. Определить количество таких перестановок. -
В ряд выкладываются b белых шаров, s синих шаров и k красных шаров. Определить количество расстоновок шаров, если шары одинакового цвета не могут стоять рядом. вывести эти расстановки на экран. -
Расстаивть n ладей на поле размером nn так, чтобы они не били друг друга. Определить количество таких расстановок. -
Расставить n ферзей на шахматной доске размером nn так, чтобы они не били друг друга. Определить количество таких расстановок. -
Имеется n юношей и n девушек. Некоторые юноши знакомы с некотрыми девушками. Определить максимальное число возможных браков между ними, если известно, что браки могут заключаться только между знакомыми людьми, а многоженство и многомужество запрещены.
Поиск в графе.
Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V,E). Мощности множеств V и E будем обозначать буквами N и M. Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.
Способы описания. Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.
Матрица смежности - это двумерный массив размерности N*N.
A[i,j]=
Для хранения перечня ребер необходим двумерный массив R
размерности M*2. Строка массива описывает ребро.
Множество алгоритмов на графах требует просмотра вершин графа. Рассмотрим их.
Поиск в глубину
Идея метода. Поиск начинается с некоторой фиксированной вершины v. Рассматривается вершина u, смежная с v. Она выбирается. Процесс повторяется с вершиной u. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не рассмотренных ранее (новых), то возвращаемся из вершины q к вершине, которая была до нее. В том случае, когда это вершина v, процесс просмотра закончен. Очевидно, что для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа:
Nnew : array[1..N] of boolean.
Пример. Пусть граф описан матрицей смежности A. Поиск начинается с первой вершины. На левом рисунке приведен исходный граф, а на правом рисунке у вершин в скобках указана та очередность, в которой вершины графа просматривались в процессе поиска в глубину.
Логика.
procedure Pg(v:integer);{Массивы Nnew и A глобальные}
var j:integer;
begin
Nnew[v]:=false; write(v:3);
for j:=1 to N do if (A[v,j]<>0) and Nnew[j] then Pg(j);
end;
Фрагмент основной логики.
...
FillChar(Nnew,SizeOf(Nnew),true);
for i:=1 to N do if Nnew[i] then Pg(i);
...
В силу важности данного алгоритма рассмотрим его нерекурсивную реализацию. Глобальные структуры данных прежние: A - матрица смежностей; Nnew - массив признаков. Номера просмотренных вершин графа запоминаются в стеке St, указатель стека - переменная yk.
procedure PG1(v:integer);
var St:array[1..N] of integer;yk:integer;t,j:integer;pp:boolean;
begin
FillChar(St,SizeOf(St),0); yk:=0;
Inc(yk);St[yk]:=v;Nnew[v]:=false;
while yk<>0 do begin {пока стек не пуст}
t:=St[yk]; {выбор “самой верхней“ вершины из стека}
j:=0;pp:=false;
repeat
if (A[t,j+1] <>0) and Nnew[j+1] then pp:=true
else Inc(j);
until pp or (j>=N); {найдена новая вершина или все вершины, связанные с данной вершиной, просмотрены}
if pp then begin
Inc(yk);St[yk]:=j+1;Nnew[j+1]:=false;{добавляем в стек}
end
else Dec(yk); {“убираем” вершину из стека}
end;
end;
Поиск в ширину
Идея метода. Суть (в сжатой формулировке) заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины - выбирается та, которая была раньше рассмотрена. Для реализации данного принципа необходима структура данных “очередь”.
Пример. Исходный граф на левом рисунке. На правом рисунке рядом с вершинами в скобках указана очередность просмотра вершин графа.
Приведем процедуру реализации данного метода обхода вершин графа.
Логика просмотра вершин.
procedure PW(v:integer);
var Og:array[1..N] of 0..N; {очередь}
yk1,yk2:integer; {указатели очереди, yk1 - запись; yk2 - чтение}
j:integer;
begin
FillChar(Og,SizeOf(Og),0);yk1:=0;yk2:=0;{начальная инициализация}
Inc(yk1);Og[yk1]:=v;Nnew[v]:=false;{в очередь - вершину v}
while yk2 Inc(yk2);v:=Og[yk2];write(v:3);{“берем” элемент из очереди} for j:=1 to N do {просмотр всех вершин, связанных с вершиной v}
if (A[v,j]<>0) and Nnew[j] then begin{если вершина ранее не просмотрена} Inc(yk1);Og[yk1]:=j;Nnew[j]:=false;{заносим ее в очередь}
end;
end;
Задачи дискретной математики, к которым относится большинство олимпиадных задач по информатике, часто сводятся к перебору различных комбинаторных конфигураций объектов и выбору среди них наилучшего, с точки зрения условия той или иной задачи. Поэтому знание алгоритмов генерации наиболее распространенных комбинаторных конфигураций является необходимым условием успешного решения олимпиадных задач в целом. Важно также знать количество различных вариантов для каждого типа комбинаторных конфигураций, так как это позволяет реально оценить вычислительную трудоемкость выбранного алгоритма решения той или иной задачи на перебор вариантов и, соответственно, его приемлемость для решения рассматриваемой задачи, с учетом ее размерности. Кроме того, при решении задач полезным оказывается умение для каждой из комбинаторных конфигураций выполнять следующие операции: по имеющейся конфигурации получать следующую за ней в лексикографическом порядке; определять номер данной конфигурации в лексикографической нумерации всех конфигураций; и, наоборот, по порядковому номеру выписывать соответствующую ему конфигурацию. Перечисленные подзадачи в программировании обычно рассматривают для следующих комбинаторных конфигураций: перестановки элементов множества, подмножества множества, сочетания из n элементов множества по k элементов (k-элементные подмножества множества, состоящего из nk элементов), размещения (упорядоченные подмножества множества, то есть отличающиеся не только составом элементов, но и порядком элементов в них), разбиения множества (множество разбивается на подмножества произвольного размера так, что каждый элемент исходного множества содержится ровно в одном подмножестве), разбиения натуральных чисел на слагаемые, правильные скобочные последовательности (различные правильные взаимные расположения n пар открывающихся и закрывающихся скобок).
Большинство указанных конфигураций были подробно рассмотрены в [1-3]. Однако при генерации различных конфигураций использовались в основном нерекурсивные алгоритмы. Опытные же участники олимпиад в подобных случаях при программировании используют в основном именно рекурсию, с помощью которой решение рассматриваемых задач зачастую можно записать более кратко и прозрачно. Поэтому для полноты изложения данной темы приведем ряд рекурсивных комбинаторных алгоритмов и рассмотрим особенности применения рекурсии в комбинаторике. В П Обычно генерацию всех k-элементных подмножеств проводят в лексикографическом порядке, тем более что в данном случае это не приводит ни к усложнению алгоритма, ни к увеличению его вычислительной трудоемкости. Напомним, что порядок подмножеств называется лексикографическим, если для любых двух подмножеств справедливо, что раннее должно быть сгенерировано то из них, из индексов элементов которого можно составить меньшее k-значное число в n-ричной системе счисления (или в десятичной, для n < 10). Так, для n = 6 и k = 3 сочетание из третьего, первого и пятого элемента должно быть сгенерировано раньше, чем из второго, третьего и четвертого, так как 135 < 234. Рассмотрим рекурсивный алгоритм решения данной задачи. Идея сведения данной задачи к задаче меньшей размерности следующая. Первым элементом подмножества может быть любой элемент, начиная с первого и заканчивая (n – k + 1)-м элементом. После того, как индекс первого элемента подмножества зафиксирован, осталось выбрать k – 1 элемент из элементов с индексами, большими, чем у первого. Далее поступаем аналогично. Когда выбран последний элемент, то мы достигли конечного уровня рекурсии и выбранное подмножество можно обработать (проанализировать или распечатать). В предлагаемой ниже программе массив a содержит значения элементов исходного множества и может быть заполнен произвольным образом. В массиве p будем формировать очередное сочетание из k элементов.
const nmax = 24; type list = array[1..nmax] of integer;
var k,i,j,n,q : integer; a,p : list;
procedure print(k : integer); var i:integer;
begin
write(p[j]:4); writeln
end;{print}
end;
Решение комбинаторных задач.
Генерация k-элементных подмножеств
комбинаторике такие подмножества называют сочетаниями из n элементов по k элементов и обозначают Cnk . Их количество выражается следующей формулой:
Однако при программировании гораздо удобнее использовать следующие рекуррентные соотношения:
Объясняется это тем, что в формуле (1) числитель и знаменатель растут очень быстро, поэтому в силу особенностей компьютерной арифметики не всегда возможно точно вычислить значение Cnk, даже когда последнее не превосходит максимально представимое целое число.
ри фиксированном значении n максимального значения число сочетаний достигает при k = n/2 (вернее, для четного n максимум один и он указан, а для нечетного — максимум достигается на двух соседних значениях k: [n/2] и [n/2]+1). Поэтому особенно полезной оказывается следующая оценка для четных n [4] (очевидно, что при нечетных n отличия будут минимальными), основанная на формуле Стирлинга:
Если допустить, что за время, отведенное для решения задачи, мы можем перебрать около 106 вариантов, то из формулы (3) следует, что генерацию всех сочетаний из n элементов для любого фиксированного k можно проводить для n 24.
for j:=1 to k do
procedure cnk(n,k : integer);
procedure gen(m,L : integer);
var i:integer;
begin
if m=0 then print(k) else
for i:=L to n-m+1 do
begin
p[k-m+1]:=a[i];
gen(m-1,i+1)
end
end;{gen}
begin {cnk}
gen(k,1)
end;{cnk}
begin {main}
readln(n,k);
for i:=1 to n do
a[i]:=i;{заполнить массив можно и по-другому}
cnk(n,k)
end.
Заметим, что собственно генерация сочетаний производится в рекурсивной подпрограмме gen. Она имеет следующие параметры: m - сколько элементов из множества нам еще осталось выбрать и L - начиная с какого элемента исходного множества, следует выбирать эти m элементов. Обратите внимание, что именно вложенная структура описания процедур cnk и gen позволяет не передавать при рекурсивных вызовах значения n и k, а из основной программы обращаться к процедуре cnk с параметрами, соответствующими постановке задачи, не вдаваясь в подробности ее решения. Такой способ будем применять и в дальнейшем.