- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Перший варіант розв’язку
Досить простий шлях з точки зору теоретичної підготовки та реалізації програми – це аналог пошуку найменшого елементу в масиві. Тобто ми розглядаємо наші зсуви як незалежні l стрічок, для пошуку найменшої з яких ми робимо l‑1=O(l) порівнянь поточної найменшої з поточною, що розглялається.
Коректність алгоритму не викликає сумнівів, хоча її можна строго довести індукцією за кількістю розглянутих стрічок.
Алгоритм при вдалому методі зберігання даних використовує O(l) пам’яті, причому крім вхідної стрічки займається лише O(1) пам’яті.
А от з часом буде гірше. Коли стрічки мало схожі одна на одну (наприклад, мають різні початки), то l порівнянь займає O(l) часу. Але якщо стрічки схожі (наприклад, вхідна стрічка має досить короткий період), то часу на порівняння буде використовуватись уже O(l2) – по O(l) на O(l) порівнянь.
Ось програма на Паскалі, яка реалізує вищеописаний алгоритм.
(Програма читає дані з файлу b.in, в якому перша цифра – кількість тестів, а кожний тест містить цифру – кількість символів у стрічці, а за нею саму стрічку. Результати у порядку, відповідному до порядку тестів, віводяться на екран.)
PROGRAM Minlex1;
var c0:array[0..62499] of byte;{Given string.}
t,u:longint;{Number of all tests and of current test.}
l:longint;{Length of the string.}
i,i1,i2:longint;{Indices for cycles.}
ch0:char; {Char, which is used for reading the data.}
idend:byte; {Indicator of the end of the cycle.}
{Gets the order of i-th char of the (2l-1)-char string,
which has our l-char string as a period.}
FUNCTION c(i:longint):byte;
var k:longint;
j:word;
d:byte;
Begin
if (i>=l) then i:=i-l;
c:=c0[i];
End;
BEGIN
assign(input,'b.in');
reset(input);
read(t);
{This cycles passes once per each test.}
for u:=1 to t do begin
{Getting the input data.}
read(l);
if (l<=0) then writeln(0);
if (l>0) then begin
read(ch0);
while (ch0 in [#10,#13,#32]) do read(ch0);
c0[0]:=ord(ch0);
for i:=1 to (l-1) do begin
read(ch0);
c0[i]:=ord(ch0);
end;
i1:=0;
for i2:=1 to (l-1) do begin
idend:=0;
i:=0;
while ((idend=0)and(i<l)) do begin
if (c(i2+i)<>c(i1+i)) then idend:=1;
if (idend=0) then Inc(i);
end;
if (idend=1) then
if (c(i2+i)<c(i1+i)) then i1:=i2;
end;
writeln(i1);
end;
end;
close(input);
END.
Другий варіант розв’язку.
Другий варіант виграє за часом в порівнянні з першим, оскільки він використовує взаємозв’язок між стрічками і цим відмітає багато завідомо непотрібних порівнянь.
Розв’язок даної задачі зводиться до знаходження найпершого з тих символів, з якого починається одна з лексикографічно найменших підстрічок довжини l у стрічці довжиною 2l‑1, яка має задану нам l‑символьну стрічку в якості періоду. Пошук потрібної l‑символьної підстрічки, тобто позиції, з якої вона починається, здійснюється за наступним принципом.
Спочатку шукається найменший символ у стрічці (лексикографічно найменша стрічка може починатися тілький з найменшого символа). Номер найпершого представника найменшого символа позначимо через i1 – він і буде першим кандидатом на роль початку шуканої підстрічки.
Після цього відбувається прохід (2l‑1)‑символьної стрічки де номер j поточного символа, що перевіряється, пробігає значення від i1+1 до 2l‑2. У процесі перевірки значення j може повертатися назад, але це порушує лінійності алгоритму. На кожному кроці може бути другий кандидат на роль початку шуканої стрічки – i2. При цьому виконується наступне. Коли i2 існує (у програмі це відповідає стану idi2=1) – то початок шуканої стрічки не може бути під номером, меншим за i2 та відмінним від i1. А коли коли i2 не існує (idi2=0) – то початок шуканої стрічки не може бути під номером, меншим за j та відмінним від i1.
Якщо i2 не існувало та j<l ми призначаємо i2=j, за умови, що j‑ий символ дорівнює i1‑ому. Після цієї перевіркив незалежності від її результату j збільшується на 1. Якщо ж було j≥l (та i2 не існувало), то ми закінчуємо пошук з висновком, що i1 – шуканий розв’язок.
Якщо i2 існувало, ми порівнюємо j‑ий символ з (j‑i2+i1)‑им, розглядаючи наступні варіанти. Якщо ці символи рівні, ми просто збільшуємо j на 1. Якщо j‑ий символ виявляється більшим, ми відміняємо i2 та збільшуємо j на 1. Якщо j‑ий символ виявляється меншим, ми призначаємо i1=i1+((j‑1‑i1) div (i2‑i1))(i2‑i1); якщо при цьому стало було i1≥l, то ми закінчуємо пошук з висновком, що шуканий розв’язок – i1(попереднє)+((l‑1‑i1(попереднє)) div (i2‑i1(попереднє)))(i2‑i1(поперенднє)), якщо ж i1<l – ми відміняємо i2 та покладаємо j=i1+1.
Якщо цикл не закінчився у зв’язку з попередніми умовами завершення пошуку, але стало j≥2l‑1, ми закінчуємо пошук з висновком, що i1 – шуканий розв’язок. У протилежному випадку ми повертаємось до перевірки поточного j‑го символа.
Для обгрунтування коректності алгоритму доводиться індукцією за номером кроку наступне твердження: відповіддю на поставлену задачу не може бути номер, який менший за i2 та не дорівнює i1. У доведенні використовується те, що стрічка, що починаєть з символу з номером i1 та закінчується (j‑1)‑м символом, має період (i2‑i1).
Як і попередній, цей алгоритм при вдалому методі зберігання даних використовує O(l) пам’яті, причому крім вхідної стрічки займається лише O(1) пам’яті.
Лінійність алгоритму за часом слідує хоча б з того, що після кожного циклу вираз (2i1+j) збільшується принаймні на 1, а його максимальне значення є O(l).
Ось програма на Паскалі, яка реалізує вищеописаний алгоритм.
(Формати вводу та втводу – такі самі, як і в першому випадку.)
PROGRAM Minlex2;
var c0:array[0..62499] of byte;{Given string.}
cmin:byte;{Minimal order of the char in the string.}
cj,c2:byte; {Multi-used orders of chars.}
t,u:longint;{Number of all tests and of current test.}
l:longint;{Length of the string.}
i,i0,i1,i2,j,d:longint; {Indices for cycles.}
ch0:char; {Char, which is used for reading the data.}
idend,idi2,idproc:byte; {Indicators of events:
1 if such event is present, 0 if else.}
{Gets the order of i-th char of the (2l-1)-char string,
which has our l-char string as a period.}
FUNCTION c(i:longint):byte;
var k:longint;
j:word;
d:byte;
Begin
if (i>=l) then i:=i-l;
c:=c0[i];
End;
BEGIN
assign(input,'b.in');
reset(input);
read(t);
{This cycles passes once per each test.}
for u:=1 to t do begin
{Getting the input data.}
read(l);
if (l<=0) then writeln(0);
if (l>0) then begin
read(ch0);
while (ch0 in [#10,#13,#32]) do read(ch0);
c0[0]:=ord(ch0);
for i:=1 to (l-1) do begin
read(ch0);
c0[i]:=ord(ch0);
end;
{Finding the minimal order of the char in the string.}
i1:=0;
cmin:=c(0);
for i:=1 to (l-1) do begin
c2:=c(i);
if (c2<cmin) then begin
i1:=i;
cmin:=c2;
end;
end;
idend:=0;
idi2:=0;
j:=i1+1;
{Main cycle, which finds the best first position.}
while (idend=0) do begin
if (j>l*2-2) then idend:=1;
if (idend=0) then begin
idproc:=0;
cj:=c(j);
if (idi2=0) then begin
idproc:=1;
if (j>l-1) then idend:=1;
if ((idend=0)and(cj=cmin)) then begin
i2:=j;
idi2:=1;
end;
end;
if ((idi2=1)and(idproc=0)) then begin
d:=i2-i1;
c2:=c(j-d);
if (cj<>c2) then idi2:=0;
if (cj<c2) then begin
i0:=i1+(j-1-i1)-(j-1-i1) mod d;
if (i0>=l) then begin
i0:=i1+(l-1-i1)-(l-1-i1) mod d;
idend:=1;
end;
i1:=i0;
j:=i1;
end;
end;
end;
Inc(j);
end;
writeln(i1);
end;
end;
close(input);
END.
Також цей алгоритм легко узагальнити для пошуку лексикографічно найменшої підстрічки довжини b у стрічці довжини a (звісно, за час, лінійний від a).
