- •Оценка эффективности алгоритмов
- •Целочисленная арифметика
- •Дано натуральное число. Выяснить является ли оно палиндромом, то есть читается справа налево и слева направо одинаково
- •Дано натуральное число. Выяснить соотношение между количествами двоек и пятерок в этом числе
- •Найти самую большую и самую маленькую цифры данного натурального числа
- •Выяснить образуют ли цифры натурального числа возрастающую последовательность
- •Формат выходного файла
- •Формат входного файла
- •Формат выходного файла
- •Формат входного файла
- •Формат входного файла
- •Формат выходного файла
- •Длинная арифметика
- •Выходные данные
- •Задачи Задача 52 Иностранные земли
- •Входные данные.
- •Выходные данные.
- •Формат входного файла
- •Формат выходного файла
- •Задачи Задача 56 Уравнение
- •Решение
- •Одномерные массивы
- •Базовые задачи на массивы
- •Задача 15 Сокращение одночленов
- •Входные данные:
- •Задача 16 Школьный субботник
- •Входные данные:
- •Входные данные:
- •Выходные данные:
- •Примеры
- •Задача 27 Решение систем линейных уравнений на Pascal
- •Двумерные массивы
- •Описание массива
- •Способы создания массива
- •Задачи:
- •Задача 5 Малыш играет в "Морской бой 2" Малыш играет в "Морской бой". Поле для игры представляет собой квадрат
- •Входные данные
- •Выходные данные
- •Задача 26 Шарик в лабиринте
- •Примечание
- •Задача 27 Блохи
- •В первой строке входного файла Input.Txt находится 5 чисел, разделенных пробелом: n, m, s, t, q.
- •Входные данные
- •Выходные данные
- •Примеры
- •Задача 34 Магический квадрат
- •Формат входного файла
- •Формат выходного файла
- •Входные данные
- •Выходные данные
- •Входные данные
- •Выходные данные
- •Рекурсия
- •Комбинаторика
- •2.5. Генерация комбинаторных объектов
- •Множество всех подмножеств
- •Перестановки
- •Размещения
- •Перестановки с повторениями
- •Сочетания с повторениями
- •Перебор
- •Символ o()
- •Отсечение по времени
- •Рассмотрим несколько олимпиадных задач.
- •Шарик в лабиринте
- •Задача 1. Шарик в лабиринте
- •Задача 3 Цепочка слов
- •Входные данные
- •Выходные данные
- •Примеры
- •Формат входного файла
- •Формат выходного файла
- •Примеры
- •Динамическое программирование
- •Задача 8 Гвоздики
- •Задача 13 Лесенки
- •Задача 18 Свинья-копилка
- •Входные данные
- •Выходные данные
- •Задача 13 Лесенки Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий.
- •Задача 18 Свинья-копилка
- •Формат входного файла:
- •Формат выходного файла:
- •Примеры
- •Решение
- •Входные данные:
- •Выходные данные:
- •Формат входа
- •Формат выхода
- •Задача 39 Лесенка-2
- •Входные данные
- •Выходные данные
- •Примеры
- •Системы счисления
- •Задача 11 Троичная сбалансированная система счисления
- •Алгоритм перевода
- •Процедуры и функции для работы с символами и строками
- •Определить количество слов в строке
- •Получите строковой массив из всех слов данной строки
- •Получите строковой массив из всех слов данной строки и
- •Получите строковой массив из всех слов данной строки и
- •Составьте программу, определяющую, является ли введенное слово изображением числа
- •Введите 2 целых числа. Преобразуйте числа в две строки, объедините их в одну строку и выведите результат на экран.
- •Вычислите длину самого короткого и самого длинного слов в строке
- •Подсчитайте количество букв в каждом слове данной строки
- •Дана строка. Определить количество слов этой строки, в которых есть ровно две буквы «е»
- •Составьте программу, удаляющую все лишние пробелы из введенной строки
- •Напишите программу, сортирующую символы введенной с клавиатуры строки в порядке возрастания их номеров в ascii-таблице. Например, если введено: 'cba', в результате надо получить ‘abc’.
- •В тексте, состоящем из маленьких латинских букв , подсчитайте количество гласных букв
- •Заданы фамилия, имя и отчество учащегося, разделенные пробелом. Напечатайте его фамилию и инициалы.
- •Сложное слово состоит из двух частей одинаковой длины и соединительной гласной. Найдите обе части этого слова.
- •Вычеркните из слова х те буквы, которые встречаются в слове z
- •Подсчитайте число различных букв в слове
- •Даны два слова. Составьте программу, определяющую можно или нет из букв слова а составить слово в.
- •Даны два слова. Являются ли они анаграммами
- •Является ли данная строка палиндромом?
- •Задача 4. Сокращение одночленов
- •Входные и выходные данные
- •Это чисто техническая задача на аккуратное программирование.
- •Задача 6 Текст
- •Входной файл Input.Txt в первой строке входного файла находится 5 чисел,разделенных пробелом: n, m, s, t, q.
- •Бинарные деревья. Алгоритм HeapSort
- •Поиск в глубину в графе
- •Алгоритм Флойда поиска кратчайших расстояний и кратчайших путей
- •Бинарные деревья. Алгоритм HeapSort
- •Графызадачи Двоичная куча
- •Примеры задач, которые решаются с помощью двоичной кучи
- •Поиск максимального потока методом Форда-Фалкерсона на Pascal
- •Графызадачи Поиск сильно связанных компонент на Pascal
- •Поиск точек раздела, мостов и двусвязных компонент
- •Идеи алгоритмов
- •Точки раздела
- •Двусвязные компоненты
- •Задача 21 Моя Столица
- •Вычислительная геометрия
- •3. Уравнение прямой 2
- •4. Уравнение прямой проходящей через точку м(х0у0)
- •Формат входного файла
Алгоритм Флойда поиска кратчайших расстояний и кратчайших путей
Известна стоимость проезда из каждого города в каждый. Hайти наименьшую стоимость проезда из города 1 до всех остальных и путь из одной вершины в другую за время O(n3).
program floid;
const k=10;
var a,d,m:array[1..k,1..k] of integer;
i,j,t,n,nach,kon:integer;
procedure init; инициализация исходных данных
begin
assign(input,'input.txt');
reset(input);
read(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
read(nach,kon);
for i:=1 to n do
for j:=1 to n do
m[i,j]:=i;
end;
procedure distanse; построение матрицы путей
var i,j,t:integer;
begin
for i:=1 to n do
for j:=1 to n do
d[i,j]:=a[i,j];
for i:=1 to n do d[i,i]:=0;
for t:=1 to n do
for i:=1 to n do
for j:=1 to n do
if d[i,j]>d[i,t]+d[t,j] если путь из i в j через вершину t короче
then
begin
d[i,j]:=d[i,t]+d[t,j]; то изменяем d[i,j]
m[i,j]:=m[t,j]; и заносим вершину t в путь
end;
end;
procedure allway(i,j:integer); рекурсивная процедура вывода пути i из в j
begin
if m[i,j]=i then
if i=j then write(i) else write (i,'-',j,' ')
else
begin
allway(i,m[i,j]); allway(m[i,j],j);
end;
end;
procedure out; вывод матрицы кратчайших расстояний
begin
assign(output,'output.txt');
rewrite(output);
for i:=1 to n do
begin
writeln;
for j:=1 to n do
write(d[i,j],' ');
end;
writeln;
end;
begin
init;
distanse;
out;
allway(nach,kon);
end.
Пример файла Input.txt
4 размеры матрицы
0 1 2 1 сама матрица
2 0 7 32767
6 5 0 2
1 32767 4 0
3 2 начальная и конечная вершины
Пример файла Output.txt
матрица кратчайших расстояний
0 1 2 1
2 0 4 3
3 4 0 2
1 2 3 0
3-4 4-1 1-2 путь из 3 во 2
Время работы алгоритма: O(n3)
графызадачи
Алгоритм Форда-Беллмана нахождения длин кратчайших путей из первой вершины во все
Алгоритм работает и в случае, когда в графе есть и отрицательные веса ребер.
Обозначим через МинСт(1,s,к) наименьшую длину пути из 1 в s такую, что путь содержит не более чем k ребер. Тогда выполняется такое соотношение:
МинСт (1,s,k+1) = наименьшему из чисел МинСт(1,s,k) и МинСт(1,i,k) + a[i][s] (i=1..n). Как отмечалось выше, искомым ответом является МинСт(1,i,n) для всех i=1..n.
Program bellman;
const nmax=100;
besk=maxint div 2;
var k,i,j,s,n:integer;
a:array[1..nmax,1..nmax] of integer;
x:array[1..nmax] of integer;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(n);
for i:=1 to n do
for j:=1 to n do
begin
read(a[i,j]);
if a[i,j]=0 then a[i,j]:=besk;
end;
k:= 1; ребро одно
for i := 1 to n do копируем первую строку матрицы
смежности в массив x
x[i] := a[1,i];
while k <> n do begin пока в рассматриваемом пути не все ребра
for j := 1 to n do перебираем вершины, в которые идем
begin
for i := 1 to n do перебираем промежуточные вершины
begin
if x[j] > x[i]+a[i,j] then если длина пути из 1 в вершину j через
begin вершину i короче, чем из 1 в j
x[j] := x[i]+a[i,j]; запоминаем ее
end;
end;
end;
k := k + 1; добавляем еще одно ребро
end;
end.
графызадачи
Это - алгоритм динамического программирования, или алгоритм Форда - Беллмана. Алгоритм может быть улучшен в двух отношениях: можно за то же время O(n3) найти наименьшую стоимость проезда из i в j для всех пар i,j (а не только с i=1), а можно сократить время работы до O(n2). Правда, в последнем случае нам потребуется, чтобы все веса a[i,j] были неотрицательны.
Алгоритм Краскала . Построение минимального остовного дерева.
Алгоритм получения минимального каркаса будет следующим:
1. Упорядочить ребра графа в порядке неубывания их весов.
2. Начав с первого ребра в этом перечне, добавлять ребра в новый граф , соблюдая условие: добавление не должно приводить к появлению цикла.
3. Повторять шаг 2 до тех пор, пока число ребер в новом графе не станет равным N-1. Получившееся дерево является каркасом минимального веса
На рисунке приведен пример получения минимального остовного дерева.
Program kraskal;
const nmax=10;
var v:array[1..3,1..nmax*nmax div 2] of integer; v[1,i] -номер 1 вершины ребра
c:array[1..nmax] of integer; v[2,i]-номер 2 вершины ребра
a:array[1..nmax,1..nmax] of integer; v[3,i]-вес ребра
i,j,n,t:integer;
Procedure Init;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(n);
for i:=1 to n do считывание матрицы смежности
for j:=1 to n do
read(a[i,j]);
end;
Procedure Solve;
begin
t:=1;
for i:=1 to n do заполнение массива v
for j:=i+1 to n do
if a[i,j]<>0
then
begin
v[1,t]:=i;
v[2,t]:=j;
v[3,t]:=a[i,j];
inc(t);
end;
for i:=1 to n*n div 2-1 do упорядочение массива v по неубыванию
for j:=i+1 to n*n div 2 do по весу ребер
if v[3,i]>v[3,j] then
begin
t:=v[3,i];
v[3,i]:=v[3,j];
v[3,j]:=t;
t:=v[1,i];
v[1,i]:=v[1,j];
v[1,j]:=t;
t:=v[2,i];
v[2,i]:=v[2,j];
v[2,j]:=t;
end;
for i:=1 to n do c[i]:=i; заполнение массива цветов
t:=0; счетчик количества ребер в минимальном
каркасе
for j:=1 to n*n div 2 do проверка всех ребер
begin
if t=n-1 then halt(0); если все ребра минимального каркаса
получены, то конец
if c[v[1,j]]<>c[v[2,j]] если цвета концов ребра различны
then
begin
writeln(v[1,j],' ',v[2,j]); выводим ребро
c[v[2,j]]:= c[v[1,j]]; меняем цвет конца ребра в цвет начала
inc(t); считаем ребро
end;
end;
close(output);
end;
Begin Init; Solve;end.
графызадачи
Нахождение Эйлерова цикла
Опр. Эйлеровым циклом называется цикл, который проходит по каждому ребру один раз.
Для выяснения того факта есть ли в данном графе Эйлеров цикл будем использовать следующую теорему.
Теорема: Связанный неориентированный граф содержит Эйлеров цикл тогда и только тогда, когда число вершин нечетной степени равно нулю.
Граф, содержащий Эйлеров цикл можно нарисовать на бумаге, не отрывая от нее карандаш. Для нахождения Эйлерова цикла используется обход в глубину, при этом ребра удаляются, для того, чтобы не проходить по ребру более одного раза. Порядок просмотра вершин запоминается. При обнаружении вершины, из которой не выходят ребра, ее номер записывается в стек, и просмотр продолжается от предыдущей вершины. Обнаружение вершин с нулевым числом ребер говорит о том, что найден цикл. Его можно удалить, так как четность вершин (количество выходящих ребер) при этом не изменится. Процесс продолжается до тех пор пока есть ребра. В стеке будут записаны номера вершин графа в порядке, соответствующем Эйлерову циклу.
Program Eiler_Cycle;
const
nmax=100;
var
a:array[1..nmax,1..nmax]of integer; матрица смежности графа
d:array[1..nmax]of integer; содержит вершины входящие в
Эйлеров цикл
n,kol,i:integer;
Procedure Init;
var i,j:integer;
Begin
assign(input,'input.txt');reset(input);
read(n);
for i:=1 to n do for j:=1 to n do read(a[i,j]);
close(input);
fillchar(d,sizeof(d),0);kol:=0
End;
Procedure Out;
var i:integer;
Begin
assign(output,'output.txt');rewrite(output);
for i:=1 to kol do write(d[i],' ');
close(output)
End;
Procedure Rec(v:integer); рекурсивная процедура поиска Эйлерова
цикла
var i:integer;
Begin
for i:=1 to n do ищем вершину связанную с вершиной v
if a[v,i]<>0 then если такую нашли
begin
a[v,i]:=0;a[i,v]:=0; удаляем ребро
Rec(i); запускаем рекурсию от найденной вершины
end;
inc(kol); на подъеме из стека вершину считаем
d[kol]:=v и заносим в Эйлеров цикл
End;
Begin
Init;
Solve(1);
Out
End.
графызадачи
Нахождение Гамильтонова цикла в графе методом backtreckinga
Опр. Цикл графа, проходящий через каждую его вершину, называется гамильтоновым циклом.
Алгоритм нахождения гамильтонова цикла следующий:
Начиная с вершины с номером 1 будем продвигаться впнред по графу, включая очередное ребро в гамильтонов цикл.
При найденных первых К компонентах решения рассматриваем ребра, которые выходят из последней вершины. Если находим ребро, которое ведет в непосещенную ранее вершину, добавляем новую вершину в цикл и она становится просмотренной.
При отсутствии такой вершины возвращаемся к предыдущей и ищем другие вершины, смежные с ней.
Program gamilton;
const maxn=100;
var
a:array[1..maxn,1..maxn] of integer; матрица смежности
st:array[1..maxn] of integer; массив для хранения порядка
просмотра вершин
used:array[1..maxn] of boolean; массив признаков использована вершина или нет
n:integer;
procedure init;
var i,j:byte;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
close(input);
fillchar(used,sizeof(used),false);
fillchar(st,sizeof(st),0);
end;
procedure out;
var i:integer;
begin
for i:=1 to n do write(st[i],' ');write('1');
close(output);
end;
procedure rec(k:integer); к- номер просматриваемой вершины
var v,i:integer;
begin
v:=st[k-1]; номер последней просмотренной вершины
for i:=1 to n do цикл по всем вершинам
if a[v,i]<>0 then если вершины v и i связаны
begin
if (k=n+1)and(i=1) если дошли до последней вершины
then out выводим путь
else иначе
if not used[i] если вершина i не использована
then тогда
begin
st[k]:=i; заносим ее в путь
used[i]:=true; отмечаем как пройденную
rec(k+1); переходим к следующей
used[i]:=false; возвращаемся на один шаг назад, снимаем
отметку
end;
end;
end;
procedure solve;
begin
st[1]:=1; заносим первую вершину в путь
used[1]:=true; отмечаем как пройденную
rec(2); запускаем рекурсию со второй вершины
end;
begin init; solve; out; end.
графызадачи
Максимальное паросочетание
Пусть есть граф G=(V, E). Подмножество его ребер, такое что никакие два ребра из этого подмножества не инцидентны какой-либо одной вершине из V, называется паросочетанием. Задача определения максимального подмножества таких ребер называется задачей нахождения максимального паросочетания. Полным паросочетанием называется паросочетание, в котором участвуют (в качестве концов ребер) все вершины графа. Очевидно, что любое полное паросочетание является также максимальным паросочетанием.
Данный алгоритм поиска максимального паросочетания использует метод, известный как "чередующиеся цепи". Пусть M — паросочетание в графе G. Вершину v будем называть парной, если она является концом одного из ребер паросочетания M. Путь, соединяющий две непарные вершины, в котором чередуются ребра, входящие и не входящие в множество M, называется чередующейся (аргументальной) цепью относительно M. Очевидно, что чередующаяся цепь должна быть нечетной длины, начинаться и заканчиваться ребрами, не входящими в множество M. Также ясно, что имея чередующуюся цепь P, мы можем увеличить паросочетание M, удалив из него те ребра, которые входят в цепь P, и вместо удаленных ребер добавить ребра из цепи P, которые первоначально не входили в паросочетание M. Это новое паросочетание можно определить как M^P, где ^ обозначает симметрическую разность множеств M и P, т. е в новое множество паросочетаний войдут те ребра, которые входят или в множество M, или в множество P, но не в оба сразу.
Паросочетание M будет максимальным тогда и только тогда, когда не будет существовать чередующейся цепи относительно M.
Теперь можно описать алгоритм нахождения максимального паросочетания M для графа G=(V, E).
Сначала положим M=0
Далее ищем чередующуюся цепь P относительно M, и множество M заменяется на множество M^P
Шаг 2 выполняется до тех пор, пока существуют чередующиеся цепи относительно M Если таких цепей нет, то M — максимальное паросочетание.
графызадачи
Поиск компонент связности
Пусть G — граф. Разобъем множество его вершин на компоненты связности по следующему принципу: две вершины лежат в одной компоненте связности, когда есть путь из одной вершины в другую.
Если выполнить DFS(a) при условии, что все вершины изначально не помечены, то алгоритм посетит все вершины, достижимые из a. Поэтому его можно применять для поиска связных компонент. Для этого будем для каждой помеченной вершины хранить номер ее компоненты связности, который будем также называть цветом. Непройденные вершины считаем непокрашенными. Алгоритм работает так:
DFS(a,c)
Покрасить вершину a в цвет c
Для любого ребра (a,b)
Если вершина b не покрашена, то
DFS(b,c)
Нахождение сомпоненты
Изначально все вершины не покрашены
c := 0
Для любой вершины a,
Если a не покрашена, то
c := c+1
DFS(a,c)
Топологическая сортировка
Пусть задан ориентированный граф G без циклов. Топологической сортировкой в нем называется такое упорядочение его вершин, что для любого ребра (a,b), вершина a расположена раньше вершины b в этом упорядочении. Ясно, что может существовать несколько топологических сортировок нашего графа.
Для того, чтобы найти топологическую сортировку графа, упорядочим вершины в порядке убывания времени выхода, т. е. момента, в который алгоритм поиска в глубину закончил обработку вершины. Это и будет топологической сортировкой.
DFS(a)
Пометить вершину a
Для любого ребра (a,b),
Если вершина b не помечена, то
DFS(b)
Добавить a в начало списка вершин
TOPOLOGICAL_SORT
Изначально список вершин пуст, никакая вершина не помечена
Для любой вершины a,
Если a не помечена, то
DFS(a)
