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). Что соответствует выбору всех объектов рассматриваемого множества. Предположим, что мы не остановились на этом этапе и продолжили увеличивать наш массив, то есть на единицу увеличиваем последний элемент массива, при этом он обращается в двойку, мы его зануляем и переносим единицу в предыдущий разряд, и в нем получаем двойку, снова зануляем и переносим, и это продолжается до тех пор, пока мы не оказываемся в позиции первого элемента, который также обращается в двойку, которую необходимо занулить а единицу перенести в предыдущий разряд, то есть в нулевой, который в обычном используемом нами массиве не фигурирует. Следовательно, в данном случае нам необходимо определить позицию нулевого элемента массива для определения окончания перебора всех возможных вариантов формирования массива из нулей и единиц. То есть в начале мы формирует массив из всех нулей, в том числе ноль находится и в нулевом разряде, после того как нами перебраны все варианты, и единицы находятся во всех позициях кроме нулевой мы делаем следующий шаг и получаем нули во всех позициях кроме нулевой, там находится единица, вот именно эта единица и будет служить для нас окончанием перебора всевозможных вариантов. В результате перебора мы должны получить 2ⁿ вариантов, где n – количество элементов массива. Для успешной работы программы n не может быть бесконечно, при n>20 на обработку данных программе требуется уже очень много времени.

Алгоритм решения задачи с использованием двоичного перебора:

1. Ввести исходные данные (если в этом есть необходимость).

2. Сформировать нулевой вектор с номерами элементов от 0 до n.

3. Обработать этот вектор.

4. Сформировать новый вектор.

5. Если нулевой разряд вектора равен 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.

Задачи:

1. Даны n различных цифр, получить из них всевозможные числа, при условии, что в числе цифры не повторяются.

2. Даны n различных букв, получить все возможные слова из них при условии что буквы в словах не повторяются.

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

4. Имеется n камней (известна их масса), разложить эти камни на две кучки так, чтобы массы этих кучек отличались друг от друга как можно меньше (в идеале совпадали).

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

6. Известны массы n гирек. определить, можно ли заданный груз взвесить этими гирьками. Если можно, то указать наилучший (по числу используемых гирек) способ взвешивания. Задачу решить для двух случаев: а) груз на одной чаше весов, гирьки на другой; б) гирьки могут находиться на обеих чашках весов.

Контрольная работа:

1. Дан ряд цифр 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 варианта).

2. Известно количество страниц в каждом из 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) нельзя).

3. Известны массы 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<L).

Принцип работы алгоритма разъясним на примере. Допустим, необходимо воспроизвести все перестановки цифр 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<Q, так как, пересматривая эти перестановки слева направо, (P(2)=6,Q(2)=7). Пусть существует такая перестановка R, что P<R<Q. Тогда P(1)=R(1)=Q(1). По построению же Q(2) – это наименьшее во множестве Q\Q(1)={3,4,6,7} число, такое, что Q(2)>P(2). Поэтому для R(2) верно одно из двух равенств: R(2)=Q(2) или R(2)=P(2). Но так как в P элементы, начиная с P(3), убывают, то из P<R следует, что если P(2)=R(2), то и P=R. Аналогично, так как в Q элементы, начиная с Q(3), возрастают, то из R<Q следует, что если R(2)=Q(2), то и R=Q.}

Алгоритм генерации перестановок:

1. Просматриваем a₁,.., a_n с кона до тех пор, пока не попадется a_i<a_i+1. если таковых нет, значит, генерация закончена.

2. Рассматриваем a_i+1, …, a_n. Находим первый с конца a_m>a_i и меняем их местами.

3. a_i+1, a_i+2, …, a_n переставим в порядке возрастания.

4. Выводим найденную перестановку.

5. Возвращаемся к первому пункту.

В результате всех перестановок, всевозможных вариантов должно получиться 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]<a[i] do dec(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.

Задачи:

1. Вывести на экран все перестановки последовательности n различных букв: абвгд…

2. Письма на удачу вкладываются в подписанные конверты. Определить количество раскладок, когда ни одно из n писем не попадает к своему адресату.

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

4. В ряд выкладываются b белых шаров, s синих шаров и k красных шаров. Определить количество расстоновок шаров, если шары одинакового цвета не могут стоять рядом. вывести эти расстановки на экран.

5. Расстаивть n ладей на поле размером nn так, чтобы они не били друг друга. Определить количество таких расстановок.

6. Расставить n ферзей на шахматной доске размером nn так, чтобы они не били друг друга. Определить количество таких расстановок.

7. Имеется 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<yk1 do begin {пока очередь не пуста}

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;

end;

Решение комбинаторных задач.

Задачи дискретной математики, к которым относится большинство олимпиадных задач по информатике, часто сводятся к перебору различных комбинаторных конфигураций объектов и выбору среди них наилучшего, с точки зрения условия той или иной задачи. Поэтому знание алгоритмов генерации наиболее распространенных комбинаторных конфигураций является необходимым условием успешного решения олимпиадных задач в целом. Важно также знать количество различных вариантов для каждого типа комбинаторных конфигураций, так как это позволяет реально оценить вычислительную трудоемкость выбранного алгоритма решения той или иной задачи на перебор вариантов и, соответственно, его приемлемость для решения рассматриваемой задачи, с учетом ее размерности. Кроме того, при решении задач полезным оказывается умение для каждой из комбинаторных конфигураций выполнять следующие операции: по имеющейся конфигурации получать следующую за ней в лексикографическом порядке; определять номер данной конфигурации в лексикографической нумерации всех конфигураций; и, наоборот, по порядковому номеру выписывать соответствующую ему конфигурацию.

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

Большинство указанных конфигураций были подробно рассмотрены в [1-3]. Однако при генерации различных конфигураций использовались в основном нерекурсивные алгоритмы. Опытные же участники олимпиад в подобных случаях при программировании используют в основном именно рекурсию, с помощью которой решение рассматриваемых задач зачастую можно записать более кратко и прозрачно. Поэтому для полноты изложения данной темы приведем ряд рекурсивных комбинаторных алгоритмов и рассмотрим особенности применения рекурсии в комбинаторике.

Генерация k-элементных подмножеств

В комбинаторике такие подмножества называют сочетаниями из n элементов по k элементов и обозначают C_n^k . Их количество выражается следующей формулой: Однако при программировании гораздо удобнее использовать следующие рекуррентные соотношения: Объясняется это тем, что в формуле (1) числитель и знаменатель растут очень быстро, поэтому в силу особенностей компьютерной арифметики не всегда возможно точно вычислить значение C_n^k, даже когда последнее не превосходит максимально представимое целое число.

П ри фиксированном значении n максимального значения число сочетаний достигает при k = n/2 (вернее, для четного n максимум один и он указан, а для нечетного — максимум достигается на двух соседних значениях k: [n/2] и [n/2]+1). Поэтому особенно полезной оказывается следующая оценка для четных n [4] (очевидно, что при нечетных n отличия будут минимальными), основанная на формуле Стирлинга:

Если допустить, что за время, отведенное для решения задачи, мы можем перебрать около 10⁶ вариантов, то из формулы (3) следует, что генерацию всех сочетаний из n элементов для любого фиксированного k можно проводить для n  24.

Обычно генерацию всех 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

for j:=1 to k do

write(p[j]:4);

writeln

end;{print}

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 с параметрами, соответствующими постановке задачи, не вдаваясь в подробности ее решения. Такой способ будем применять и в дальнейшем.

Генерация всех подмножеств данного множества

При решении олимпиадных задач чаще всего заранее неизвестно, сколько именно элементов исходного множества должно входить в искомое подмножество, то есть необходим перебор всех подмножеств. Однако, если требуется найти минимальное подмножество, то есть состоящее как можно из меньшего числа элементов (или максимальное подмножество), то эффективнее всего организовать перебор так, чтобы сначала проверялись все подмножества, состоящие из одного элемента, затем из двух, трех и т. д. элементов (для максимального подмножества — в обратном порядке). В этом случае, первое же подмножество, удовлетворяющее условию задачи и будет искомым и дальнейший перебор следует прекратить. Для реализации такого перебора можно воспользоваться, например, процедурой cnk, описанной в предыдущем разделе. Введем в нее еще один параметр: логическую переменную flag, которая будет обозначать, удовлетворяет текущее сочетание элементов условию задачи или нет. При получении очередного сочетания вместо его печати обратимся к процедуре его проверки check, которая и будет определять значение флага. Тогда начало процедуры gen следует переписать так:

procedure gen(m,L:integer);

var i:integer;

begin

if m=0 then

begin

check(p,k,flag);

if flag then exit

end

else ...

Далее процедура дословно совпадает с предыдущей версией. В основной же программе единственное обращение к данной процедуре следует заменить следующим фрагментом:

k:=0;

flag:=false;

repeat

k:=k+1;

cnk(n,1,flag)

until flag or (k=n);

if flag then print(k)

else writeln('no solution');

Очевидно также, что в основной программе запрос значения переменной k теперь не производится.

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

Т о есть, в рамках сделанной выше оценки на количество допустимых вариантов в переборе, мы можем рассмотреть все подмножества исходного множества только при n  20.

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

Условие. Дан целочисленный массив a[1..N] (N  20) и число M. Найти подмножество элементов массива a[i1], a[i2], ...a[ik] такое, что 1  i1 < i2 < i3 < ... < ik  N и a[i1] + a[i2] + ... + a[ik] = M.

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

function check(j:longint):boolean;

var k:integer; s:longint;

begin

s:=0;

for k:=1 to n do

if ((j shr (k-1))and 1)=1 {данное условие означает, что в

k-й справа позиции числа j, в 2-й системе, стоит 1}

then s:=s+a[k];

if s=m then

begin

for k:=1 to n do

if ((j shr (k-1))and 1)=1 then write(a[k]:4);

writeln

end

end;

procedure subsets(n:integer);

var q,j:longint;

begin

q:=1 shl n; {таким образом мы помещаем в q число 2^n}

for j:=1 to q-1 do {цикл по всем подмножествам}

if check(j) then exit

end;

Заметим, что если все элементы в массиве положительные, то, изменив порядок рассмотрения подмножеств, решение приведенной выше задачи можно сделать более эффективным. Так, если сумма элементов какого-либо подмножества уже больше, чем M, то рассматривать подмножества, включающие его в себя уже не имеет смысла. Пересчет же сумм можно оптимизировать, если каждое следующее сгенерированное подмножество будет отличаться от предыдущего не более, чем на один элемент (такой способ перечисления подмножеств показан в [2]). Приведенная же программа черезвычайно проста, но обладает одним недостатком: мы не можем ни в каком случае с ее помощью перебирать все подмножества множеств, состоящих из более, чем 30 элементов, что обусловлено максимальным числом битов, отводимых на представление целых чисел в Турбо Паскале (32 бита). Но, как уже было сказано выше, на самом деле, перебор всех подмножеств у множеств большей размерности вряд ли возможен за время, отведенное для решения той или иной задачи.

Генерация всех перестановок n-элементного множества

Количество различных перестановок множества, состоящего из n элементов равно n!. В этом нетрудно убедиться: на первом месте в перестановке может стоять любой из n элементов множества, после того, как мы на первом месте зафиксировали какой-либо элемент, на втором месте может стоять любой из n – 1 оставшегося элемента и т.д. Таким образом, общее количество вариантов равно n(n – 1)(n – 2)...321 = n!. То есть рассматривать абсолютно все перестановки мы можем только у множеств, состоящих из не более, чем 10 элементов.

Рассмотрим рекурсивный алгоритм, реализующий генерацию всех перестановок в лексикографическом порядке. Такой порядок зачастую наиболее удобен при решении олимпиадных задач, так как упрощает применение метода ветвей и границ, который будет описан ниже. Обозначим массив индексов элементов — p. Первоначально он заполнен числами 1, 2, ..., n, которые в дальнейшем будут меняться местами. Параметром i рекурсивной процедуры Perm служит место в массиве p, начиная с которого должны быть получены все перестановки правой части этого массива. Идея рекурсии в данном случае следующая: на i-ом месте должны побывать все элементы массива p с i-го по n-й и для каждого из этих элементов должны быть получены все перестановки остальных элементов, начиная с (i+1)-го места, в лексикографическом порядке. После получения последней из перестановок, начиная с (i+1)-го места, исходный порядок элементов должен быть восстановлен.

{описание переменных совпадает с приведенным выше}

procedure Permutations(n:integer);

procedure Perm(i:integer);

var j,k:integer;

begin

if i=n then

begin for j:=1 to n do write(a[p[j]],' '); writeln end

else

begin

for j:=i+1 to n do

begin

Perm(i+1);

k:=p[i]; p[i]:=p[j]; p[j]:=k

end;

Perm(i+1);

{циклический сдвиг элементов i..n влево}

k:=p[i];

for j:=i to n-1 do p[j]:=p[j+1];

p[n]:=k

end

end;{Perm}

begin {Permutations}

Perm(1)

end;

begin {Main}

readln(n);

for i:=1 to n do p[i]:=i;

a:=p; {массив a может быть заполнен произвольно}

Permutations(n)

end.

Заметим, что в данной программе массив p можно было и не использовать, а переставлять непосредственно элементы массива a.

Разбиения множества

Число разбиений n-элементного множества на k блоков произвольного размера но таких, что каждый элемент множества оказывается “приписан” к одному из блоков, выражается числом Стирлинга второго рода S(n,k) [6,7]. Очевидно, что S(n,k) = 0 для k > n. Если согласиться, что существует только один способ разбиения пустого множества на нулевое число непустых частей, то S(0,0) = 1 (именно такая договоренность, как и в случае с факториалом, приводит в дальнейшем к универсальным формулам). Так как при разбиении непустого множества нужна по крайней мере одна часть, S(n,0) = 0 при n > 0. Отдельно интересно также рассмотреть случай k = 2. Если непустое множество разделили на две непустые части, то в первой части может оказаться любое подмножество исходного множества, за исключением подмножеств, включающих в себя последний элемент множества, а оставшиеся элементы автоматически попадают во вторую часть. Такие подмножества можно выбрать 2^n-1 – 1 способами, что и соответствует S(n,2) при n > 0.

Для произвольного k можно рассуждать так. Последний элемент либо будет представлять из себя отдельный блок в разбиении и тогда оставшиеся элементы можно разбить уже на k – 1 частей S(n – 1,k – 1) способами, либо помещаем его в непустой блок. В последнем случае имеется kS(n – 1,k) возможных вариантов, поскольку последний элемент мы можем добавлять в каждый блок разбиения первых n - 1 элементов на k частей. Таким образом

S(n,k) = S(n – 1, k – 1) + kS(n – 1, k), n > 0. (5)

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

Е сли же значение k теперь не фиксировать и рассмотреть все разбиения n-элементного множества, то их количество выражается числом Белла

П о формулам (7) можно подсчитать, что в рамках принятых выше допущений можно построить все разбиения множества, состоящего не более чем из 15 элементов (B₁₅=1382958545).

Перейдем теперь к рассмотрению способа генерации всех разбиений исходного множества. Прежде всего следует договориться о том, как обозначать текущее разбиение. Так как в каждом из разбиений участвуют все элементы исходного множества, будем в массиве индексов p записывать в какой блок попадает каждый из элементов в текущем разбиении. Параметр i в рекурсивной процедуре part означает, что на текущем шаге мы именно i-ый элемент будет размещать в каждом из допустимых для него блоков, а j как раз и определяет максимальный номер допустимого блока. После того, как i-ый элемент помещен в один из блоков, рекурсивно решается такая же задача уже для следующего элемента (в данном случае фактически работает универсальная схема перебора с возвратом [8]).

procedure partition(n : integer; var p:list);

procedure part(i, j: integer);

var l: integer;

begin

if i > n then print(n, p) else

for l := 1 to j do

begin

p[i] := l;

if l = j then part(i+1, j+1)

else part(i+1, j)

end

end; {part}

begin {partition}

part(1,1)

end;

Как ни странно, в данном случае процедура print оказывается совсем не тривиальной, если требуется печатать (или анализировать) элементы каждого из блоков разбиения в отдельности. Поэтому приведем возможный вариант ее реализации (как и ранее, распределяли по блокам мы индексы, а печатаем или анализуруем сами элементы исходного массива a):

procedure print(n:integer; var p:list);

var i,j,imax:integer;

begin

imax:=1;{определяем количество блоков в разбиении}

for i:=2 to n do

if p[i]>imax then imax:=p[i];

for i:=1 to imax do {цикл по блокам}

begin

for j:=1 to n do

if p[j]=i then write(a[j]:4);

write(' |') {блок напечатан}

end;

writeln {разбиение напечатано}

end;

Вложенного цикла можно избежать, если требуется, например, подсчитать сумму элементов в каждом из блоков. Тогда, используя дополнительный массив, мы, просматривая элементы массива a последовательно, будем увеличивать значения суммы для блока, соответствующего рассматриваемому элементу (аналогично операции, осуществляемой в алгоритме сортировки подсчетом).

Если при этом рассматривать массив p как n-значное число n-ричной системе счисления, то можно ввести понятие лексикографического порядка для разбиений множества и ставить задачи определения номера разбиения и обратную ей. Как и ранее (см. [1-3]), они решаются методом динамического программирования и не используют непосредственную генерацию всех разбиений.

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

Олимпиадные задачи, использующие комбинаторные конфигурации

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

Исходные данные: каждая партия и, соответственно, ее президент имеют одинаковый порядковый номер от 1 до N (4  N  150). Вам даны списки всех N партий Острова Новой Демократии. Выведите предлагаемый Вами парламент в виде списка номеров его членов. (Олимпиада стран СНГ, г. Могилев, 1992 г.)

Решение: с теоретической точки зрения, данная задача совпадает с задачей генерации всех подмножеств из множества жителей острова новой демократии. Причем наиболее подходящим кажется первый подход к решению данной задачи, связанный с генераций различных сочетаний, начиная с одного жителя. Для полноты изложения этого подхода, опишем функцию сheck, которую следует применить в данной задаче. Исходные данные следует записать в массив s:array[1..150] of set of 1..150, заполнив каждый из n первых элементов этого массива множеством тех партий, в которых состоит тот или иной житель. Тогда функция проверки сочетания из элементов этого массива примет следующий вид:

function check(var p:list;k:integer): boolean;

var i:integer; ss:set of 1..150;

begin

ss:=[];

for i:=1 to k do ss:=ss+s[p[i]];

check:=(ss=[1..n])

end;

Как видно из описания функции, использование типа “множество”, позволяет не только упростить данную программу, но и существенно ускорить ее выполнение, по сравнению с работой с массивами. Однако большая размерность данной задачи не позволяет считать приведенное решение удовлетворительным во всех случаях. Так, уже для n = 100, перебор всех сочетаний из 4-х и менее жителей приводит к рассмотрению около 4-х миллионов вариантов. Для построения кода, пригодного для решения данной задачи при любых входных данных, несколько изменим описание массива s:

s: array[1..150] of

record name,number:integer;

partys: set of 1..150

end;

Здесь поле partys совпадает по смыслу с первоначальным описанием массива s, поле name cоответствует номеру (то есть фактически имени) жителя и первоначально данное поле следует заполнить числами от 1 до n cогласно индексу элемента в массиве записей, и поле number соответствует количеству элементов во множестве из поля partys, то есть имеет смысл сразу подсчитать, в каком количестве партий состоит тот или иной житель. Теперь следует отсортировать массив s по убыванию значений поля number. Верхнюю оценку для числа членов парламента (kmax) подсчитаем, построив приближенное решение данной задачи следующим образом: во-первых, включим в парламент жителя, состоящего в максимальном количестве партий, затем исключим эти партии из остальных множеств и заново найдем в оставшемся массиве элемент с максимальным значением поля number (уже пересчитанного) и включим его в парламент, и так далее, до тех пор пока сумма значений пересчитанных полей number у жителей, включенных в парламент, не будет равна n. Найденное количество членов парламента и будет kmax.

Теперь следует рассматривать сочетания из (kmax – 1) элемента, затем из (kmax – 2) и т. д. элементов. Если для сочетаний из какого-то рассматриваемого количества элементов k, решение найдено не будет, то это означает, что точным является решение с количеством членов парламента k+1. Так как массив s упорядочен, то, если решение для того или иного значения k существует, то, скорее всего, оно будет найдено при рассмотрении в лексикографическом порядке первых же сочетаний по k элементов. Поэтому временная трудоемкость в переборе возникает, только если решения c данным значением k не существует. В такой ситуации можно воспользоваться следующим “ненаучным” приемом: на поиск решения для каждого k, меньшего, чем kmax отведем фиксированное количество времени, скажем 2-3 секунды (точнее данное время стоит определить экспериментальным путем). Если за отведенное время решение не найдено, то следует считать полный перебор невозможным и закончить выполнение программы. В любом случае, мы будем иметь какое-либо решение исходной задачи: точное или приближенное, то есть, возможно содержащее больше членов парламента, чем минимально возможно. Однако, на практике такой подход почти всегда приводит к точному решению, в силу перебора “с предпочтением”, проводимого для каждого k (невозможность проведения полного перебора для какого-либо k на практике соответствует отсутствию решения для данного k).

Пример 2. Дан автобусный билет с номером, состоящим из N цифр. Расставить между цифрами знаки арифметических операций '+', '-', '*', '/' (целочисленное деление) и скобки таким образом, чтобы значение полученного выражения было равно 100. Можно образовывать многозначные числа из стоящих рядом цифр. Выражение должно быть корректным с точки зрения арифметики. Допустимы лишние скобки, не нарушающие корректности выражения. При вычислениях используется стандартный приоритет операций, число цифр N в номере билета не больше 6. (5-ая Всероссийская олимпиада по информатике, г.Троицк, 1993 г.)

Решение. для построения универсального алгоритма решения данной задачи будем считать слияние двух соседних цифр одной из операций. Тогда между каждой парой соседних цифр может стоять одна из 5 операций. Для N цифр получаем 5^N-1 различных вариантов расстановки операций. Перебирать все варианты расстановки операций удобнее всего с помощью рассмотрения всех чисел в 5-ричной системе счисления, состоящих не более чем из N – 1 цифры, то есть для N = 6 от 00000 до 44444. Для перебора таких чисел необходимо написать процедуру прибавления 1 в 5-ричной системе счисления. Для каждого из вариантов расстановки операций перейдем от исходного массива из N цифр билета, к массиву из К чисел, где K = (N – количество операций слияния цифр в рассматриваемом варианте). Теперь мы должны рассмотреть все перестановки из K – 1 арифметической операции в данном варианте. Каждая перестановка соответствует одному из порядков выполнения арифметических операций. Так, для 4-х чисел, перестановка номеров операций 3, 1, 2 означает, что сначала нужно выполнить арифметическое действие между 3-м и 4-м числом, затем между 1-м и 2-м и затем оставшееся. Если результат выполнения действий данного варианта в порядке, соответствующем текущей перестановке, равен искомому числу 100, то задача решена и можно перейти к печати результата. Для данной задачи возможны и более эффективные решения, но в силу ее небольшой размерности, комбинаторный перебор оказывается вполне приемлемым.

Пример 3. Губернатор одной из областей заключил с фирмой "HerNet" контракт на подключение всех городов области к компьютерной сети. Сеть создается следующим образом: в области устанавливается несколько станций спутниковой связи, и затем от каждого города прокладывается кабель до одной из станций. Технология, используемая компанией требует при увеличении расстояния увеличения толщины кабеля. Таким образом, стоимость кабеля, соединяющего город со станцией, при используемой компанией технологии будет равна kL², где L - расстояние от города до станции, а k - некий коэффициент. Вам требуется написать программу, определяющую минимальные затраты компании на установку сети.

Входные данные. Во входном файле записано число n (1 ≤ n ≤ 10) - количество городов в области. Затем идут положительные вещественные числа: k - коэффициент стоимости кабеля и P - стоимость постройки одной станции. Далее следует n пар вещественных чисел, задающих координаты городов на плоскости.

Выходные данные. В первую строку выходного файла нужно вывести минимальные затраты на установку сети (с тремя знаками после десятичной точки), во вторую - количество устанавливаемых станций. Далее вывести координаты станций (с тремя знаками после десятичной точки), а затем - список из n целых чисел, в котором i-ое число задает номер станции, к которой будет подключен i-ый город. (Кировский командный турнир по программированию, 2000 г.)

Решение. В силу небольшой размерности мы можем рассмотреть все возможные варианты разбиения городов на группы, подразумевая что для каждой группы будет установлена своя станция, причем оптимальным образом (найти оптимальное местонахождение станции для одной группы городов можно по формуле, аналогичной формуле нахождения центра масс). Затем нужно из всех разбиений выбрать то, для которого общая сумма затрат на установку сети будет минимальной.

Решение геометрических задач.

Пусть даны две точки А (х₁,у₁) и В (х₂,у₂), как известно на плоскости они однозначно определяют одну единственную прямую. Давайте вспомним, как выглядит общее уравнение прямой: Ах+Ву+С=0. Тогда если считаем что наша прямая задана точками А и В, то уравнение прямой проходящей через эти две точки выглядит так: . Если пользоваться данной формулой, то нам придется постоянно делать проверку на деление на ноль, что не очень удобно, чтобы это избежать, лучше использовать такое равенство: (х-х₁)(у₂-у₁)=(у-у₁)(х₂-х₁).

Иногда бывает удобнее пользоваться уравнением прямой заданной в параметрическом виде:

, где t некий параметр, а (х₁,у₁) и (х₂,у₂) – координаты точек расположенных на рассматриваемой прямой.

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

Задача: Вычислить расстояние которое пройдет путник двигаясь из точки А в точку В (при этом необходимо вычислить кратчайшее расстояние), если известно, что от точки (-1,0) до (1,0) вырыт непроходимый ров, пересечь который нельзя, можно лишь проходить по его краю.

(Пояснение: )

Решение задачи будет несколько проще, если мы введем функцию, которая позволяет определять взаимное положение трех точек. Итак, значит, у нас есть три точки: А (х₁,у₁), В (х₂,у₂) и С (х₃,у₃). Две из них однозначно определяют одну прямую и следовательно расположены на ней, весь вопрос состоит в том, а будет ли на этой же прямой располагаться и третья точка. Пусть прямую у нас определяют точки А и В, для того чтобы определить лежит на этой прямой точка С, составим следующую функцию: . Или F=((х₃-х₁)(у₂-у₁)-(у₃-у₁)(х₂-х₁)). Если F=0, то все три точки лежат на одной прямой, если же F>0 или же F<0, то третья точка лежит по одну из сторон от исходной прямой.

Тогда наша рассмотренная ранее задача будет сводиться к следующему: необходимо определить будут ли лежать точки по разные стороны ото рва, то есть вычислить произведение функций F_А* F_В и если оно отрицательно, то точки расположены по разные стороны ото рва, но при этом необходимо еще проверить, а будут ли они пересекаться.

(Тесты: А(-3,1), В(5,4) – расстояние 8,54; А(-1,4), В(4,-4) – расстояние 9,43; А(-2,-3), В(2,5) – расстояние 8,99; А(0,0), В(4,-1) – расстояние 4,12; А(0,5), В(0,-2) – расстояние 7,34).

Рассмотрим теперь, в зависимости от того, по какую сторону от прямой будет лежать точка, какой знак будет иметь функция F? Для этого рассмотрим вполне определенный пример, а именно, пусть А(-1,0), В(1,0), а С(0,1). Вычислим F=(0-(-1))(0-0)-(1—0)(1-(-1))=0-2=-2<0, следовательно, получили, что если точка лежит слева от прямой, то функция имеет отрицательное значение, а если справа, то соответственно положительный.

Задачи:

1. В городе Глупове транспорт может делать повороты и развороты только на площадях, причем левые повороты мэр запретил. И поэтому за каждый левый поворот установлен штраф в размере 50$. Определить количество левых поворотов и размер штрафа, если известны координаты площадей, через которые проезжает автомобилист.

2. В городе Глупове транспорт может делать повороты и развороты только на площадях, причем левые повороты мэр запретил. При этом он установил такую систему штрафов, за первый левый поворот штраф 50$, за каждый последующий на 10% больше предыдущего, но любой разворот на 180 или проезд через площадь без поворота сбрасывает размер штрафа опять до 50$.

3. Известны координаты вершин многоугольника в порядке их обхода. Определить является ли данный многоугольник выпуклым.

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

Помимо того, что рассмотренная нами с вами функция F позволяет определить взаимное расположение трех точек, а так же в случае, когда эти точки не лежат на одной прямой, определить по какую сторону третья точка расположена от прямой, она удобна еще и тем, что модуль значения этой функции (в случае, когда она не равна нулю) равен двум площадям треугольника, вершины которого расположены в исходных трех точках, то есть S=1/2|F|.

Задачи:

1. Вычислить площадь произвольного четырехугольника.

2. Вычислить площадь произвольного n-угольника.

Контрольная работа.

Задача: Заданы координаты концов двух отрезков, определить взаимное расположение этих отрезков (определить лежат они параллельных, совпадающих или пересекающихся прямых, в случае совпадения прямых определить имеют отрезки общую точку, общую часть или не имеют общих точек, в случае пересечения прямых определить имеют отрезки общую точку или нет).

Приближенные методы вычислений.

Задача 1. Вычислить приближенное значение суммы

1 + x/1! + x2/2! + x3/3! + …

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

Для решения задачи мы должны выполнить следующие действия:

2. получить очередное слагаемое (назовем его а);

3. сравнить абсолютную величину слагаемого а с  и, в зависимости от результата сравнения, либо продолжить, либо прекратить вычисления.

Program p;

var a: real;

x : real;

 : real;

i : integer;

S : integer;

begin

readln(x, );

i:=1;

a:=1;

S:=0;

WHILE a> DO

begin

S:=S+a; i:=i+1; a:=a*x/i;

end;

writeln(‘приближенное значение суммы=’,S:4:2)

end.

Задача 2. Рассмотрим часто встречающуюся задачу приближенного решения уравнения f(x)=0, где f(x) – заданная функция. Решить уравнение – значит найти такое значение х*, при котором f(x*)=0. Поиск решения осуществляется на интервале [a;b], причем f(a)<0, а f(b)>0. Используем метод деления пополам. Находим точку с=(а+b)/2 – середина отрезка. Если f(c)>0, то границу b изменяем на значение с, а если f(с)<0, то изменяем а. Процесс продолжаем, пока длина интервала не будет меньше заданной точности.

Y

f(x)

0 a c b X

Пусть f(x)=x²-2, т.е. мы попытаемся найти значение квадратного корня из 2.

Program popolam;

const eps=1.0E-3;

var a,b,c:real;

Function eg(x,y:real):boolean;

begin

Eg:=Abs(x-y)<eps

end;

Function F(x:real):real;

begin

F:=Sgr(x)-2

end;

BEGIN

Writeln(‘введите интервал’); readln(a,b);

if F(a)*F(b)>0 then writeln(‘на этом интервале мы не можем

найти решение уравнения’)

else begin

while Not Eg(a,b) do

begin c:=(a+b)/2;

if F(c)>0 then b:=c else a:=c

end;

writeln(‘Результат ’,a)

end;

readln

end.

Можно с помощью этой программы решить уравнения :

x2-6x+5=0 x-cosx=0 x-lnx-2=0 2x3-9x2-60x+1=0

Метод итераций

Пусть нужно решить уравнение f(х)=0, из которого мы получаем уравнение следующего вида: х=u(х), для решения этого уравнения методом итераций необхдимо составить последовательность приближений, причем надо учитывать что далеко не каждая последовательность приведет нас к нахождению корня, необходимым и достаточным условием для использования метода итераций является u’(x)<1. Итак, для нахождения последовательности выбираем произвольно х0, вплоть до случайного числа, вычисляем х1=U(х0), х2=U(х1) х3=U(х2) и т.д. опка не будет выполнено неравенство |х_i-x_i+1|<e.

Y

0 a x1 x2…..... xn-2 xn X

Задача 3. Пусть непрерывная положительная на отрезке [a,b] (a<b) функция. Вычислим площадь фигуры, ограниченную графиком функции f(x), осью х и прямыми х=а и х=b. Для этого разобьем отрезок [a,b] на n равных отрезков одинаковой длины x=(b-a)/n a=x0<x1<…<xi<xi+1<….<xn=b

На каждом из отрезков [xi,xi+1] как на основании, построим прямоугольник с высотой f(xi).

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

Sприб=(b-a)/n*(f(x0)+….f(xn-1))

Естественно, что чем мельче будет разбиение, тем точнее мы подсчитаем площадь фигуры.

Для отладки программы возьмем функцию f(x2) на отрезке [1,2]. Площадь фигуры равна 2,333….

program trapez;

const eps=1.0E-3;

var a,b,s,dx :real;

i,n : integer;

Function eg(x,y:real):boolean;

begin

Eg:=Abs(x-y)<eps

end;

Function F(x:real):real;

begin

F:=Sgr(x)

end;

BEGIN

Writeln(‘введите интервал и число частей для разбивки’); readln(a,b,n);

x:=a; dx:=(b-a)/n; s:=0;

For i:=1 to n-1 do

begin

s:=s+F(x);

x:=x+dx;

end;

writeln(‘Результат = ’,(b-a)/n*s);

readln;

end.

Вычислить площадь криволинейных трапеций для следующих функций: f(x)=1/(1+x) [0,1] f(x)=1/x [1,3]

f(x)=sinx [0,/2]

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

Задача 4. Для вычисления элементарных функций в математике широко распространено представление этих функций в виде некоторых бесконечных сумм. Не вдаваясь в обоснование таких представлений, приведем некоторые их них :

ex=1 + x + x2/2! + x3/3! + … + xn/n! + …

sinx=x – x3/3! + x5/5! – x7/7! +…+ (-1)nx2n-1/(2n+1)! +….

cosx= 1 – x2/2! + x4/4! – x6/6! +…+ (-1)nx2n/(2n)! +….

ln(1+x)=x – x2/2 + x3/3 – x4/4 + …+ (-1)n+1xn/n + ….. (-1<x<=1)

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

Вычисли функцию sinx.

Program rad;

const eps=1.0E-3;

var x,sn,ss : real;

p, n : integer;

{p – используется для чередования знака слагаемого}

Function Eg(x,y;real):boolean;

begin

Eg:=Abs(x-y)<eps

end;

Function F(n:integer;var x:real):real;

var i:integer;

s:longint;

begin

s:=1;

for i:=2 to n do s:=s*i;

x:=x*sqr(x); F:=x/s

end;

BEGIN

writeln(‘Введите значение х’);

readln(x);

ss:=0; sn:=x; n:=1; p:=1;

Repeat

ss:=sn; {предыдущее значение слагаемого}

{ новое значение слагаемого}

n:=n+2; p:=-1*p; sn:=ss+p*F(n,x)

Until Eq(ss,sn) or (n>=12);

Writeln(‘Результат=’,sn); readln

end.

Задача 5. Метод Монте-Карло для приближенного вычисления площади.

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

Пусть про любую точку квадрата мы можем быстро узнать, попадает ли эта точка внутрь фигуры или нет.

Для выбора точек используют случайные числа Random(x)

Если вызвать функцию много раз подряд, то множество полученных чисел будет равномерно распределено по отрезку [0,a]

Program ss;

var n: integer; {количество точек}

a : integer; {длина стороны квадрата}

m, i : integer;

x,y : real;

begin

writeln(‘введите кол-во точек и сторону квадрата’);

readln(n,a);

m:=0;

for i:=1 to n do

begin

x:=Rondom(a); y:=Random(a);

if точка(x,y) внутри квадрата then m:=m+1

end;

S:=(m/n)*a*a

writeln(‘Результат ’,s);

end.