Библиотечка алгоритмов
Библиотека разных алгоритмов: классических, оригинальных,
красивых, любопытных…
Источники:
[Knuth] :: Дональд Кнут Искусство программирования
[Wirth] :: Никлаус Вирт Алгоритмы и структуры данных
[Bentley] :: Джон Бентли Жемчужины программирования
Содержание
ПОИСК
Здесь собраны алгоритмы поиска в массивах.
Линейный поиск
[Wirth, 1.12.1]
a: ARRAY[0..N-1] OF item;
i:=0; WHILE (i<N)&(a[i]#x) DO i:=i+1 END
Линейный поиск с барьером
[Wirth, 1.12.1]
a: ARRAY[0..N] OF item;
a[N]:=x; i:=0; WHILE a[i]#x DO i:=i+1 END
Бинарный поиск
[Wirth, 1.12.2]
a: ARRAY[0..N] OF item
Условие: массив упорядочен:
A k : 1 <= k < N : a[k-1] <= a[k]
Вариант 1
L:=0; R:=N-1; found:=FALSE;
WHILE (L<=R) & ~found DO
m:=AnyValueBetween(L,R);
IF a[m]=x THEN found:=TRUE
ELSIF a[m]<x THEN L:=m+1
ELSE R:=m-1
END
END
Вариант 2
L:=0; R:=N;
WHILE L<R DO
m:=(L+R) DIV 2;
IF a[m]<x THEN L:=m+1 ELSE R:=m END
END
(R < N)&(a[R]=x) фиксирует совпадение
Вариант 3
Псевдокод:
[Bentley L.4.3]
l = 0; u = n - 1
loop
{ t mustbe(l, u) }
if l > u
p = -1; break
m = (l + u) / 2
case
x[m] < t: l = m + 1
x[m] == t: p = m; break
x[m] > t: u = m - 1
Программа на C:
[Bentley L.5.1]
typedef int DataType;
int n;
DataType x[MAXN];
int binarysearch(DataType t)
/* возвращает любое вхождение t в отсортированный
массив x[0..n-1] либо -1 в случае отсутствия
вхождений */
{
int l, u, m;
l = 0;
u = n - 1;
while (l <= u)
{
m = (l + u) / 2;
if (x[m] < t)
l = m + 1;
else if (x[m] == t)
return m;
else /* x[m] > t */
u = m - 1;
}
return -1;
}
Поиск строк
[Wirth, 1.12.3]
String = ARRAY[0..M-1] OF CHAR (* ASCIIZ-строка *)
Отношение порядка для строк:
(x=y) = (A j: 0 <= j < M : x[j] =y[j] )
(x < y) = $ i: 0 <= i < N :
((A j: 0 <= j < i : x[j] =y[j] )&(x[i] < y[i] ))
Сравнение строк
i:=0;
WHILE (x[i]=y[i])&(x[i])#0C) DO i:=i+1 END
Поиск строки методом деления пополам
T: ARRAY[0..N-1] OF String;
x: String;
L:=0; R:=N;
WHILE L<R DO
m:=(L+R) DIV 2; i:=0;
WHILE (T[m,i]=x[i])&(x[i]#0C) DO i:=i+1 END;
IF T[m,i]<x[i] THEN L:=L+1 ELSE R:=m END
END
IF R<N THEN
i:=0;
WHILE (T[R,i]=x[i])&(x[i]#0C) DO i:=i+1 END
END
(R < N)&(T[R,i]=x[i]) фиксирует совпадение
Прямой поиск строки
[Wirth, 1.12.4]
Пусть задан массив s из N элементов и массив p из M элементов, причем 0 < M <= N. Описаны они так:
s: ARRAY[0..N-1] OF item;
p: ARRAY[0..M-1] OF item;
Поиск обнаруживает первое вхождение p в s.
i:=1;
REPEAT i:=i+1; j:=0;
WHILE (j<M)&(s[i+j]=p[j]) DO j:=j+1 END
UNTIL (j=M)OR(i=N-M)
(* j=M - found; i=N-M - not found *)
Хеширование
[Bentley, 15.1]
typedef struct node *nodeptr;
typedef struct node {
char *word;
int count;
nodeptr next;
} node;
#define NHASH 29989
#define MULT 31
nodeptr bin[NHASH]; /* хеш-таблица */
/* хеш-функция */
unsigned int hash(char *p)
{
unsigned int h = 0;
for ( : *p; p++)
h = MULT * h + *p;
return h % NHASH;
}
СОРТИРОВКА
СОРТИРОВКА МАССИВОВ
Сортируем массивы “на месте”:
TYPE index = INTEGER;
VAR a: ARRAY[1..n] OF item;
StraightInsertion - Сортировка прямым включением
[Wirth, 2.1]
PROCEDURE StraightInsertion;
VAR i, j: index; x: item;
BEGIN
FOR i:=2 TO n DO
x:=a[i]; a[0]:=x; j:=i;
WHILE x<a[j-1] DO a[j]:=a[j-1]; j:=j-1 END;
a[j]:=x
END
END StraightInsertion;
BinaryInsertion - Сортировка методом деления пополам
[Wirth, 2.2]
PROCEDURE BinaryInsertion;
VAR i, j, m, L, R: index; x: item;
BEGIN
FOR i:=2 TO n DO
x:=a[i]; L:=1; R:=i;
WHILE L<R DO
m:=(L+R) DIV 2;
IF a[m]<=x THEN L:=m+1 ELSE R:=m END
END;
FOR j:=i TO R+1 BY -1 DO a[j]:=a[j-1] END;
a[R]:=x
END
END BinaryInsertion;
StraightSelection - Сортировка методом прямого выбора
[Wirth, 2.3]
PROCEDURE StraightSelection;
VAR i, j, k: index; x: item;
BEGIN
FOR i:=1 TO n-1 DO
k:=i; x:=a[i];
FOR j:=i+1 TO n DO
IF a[j]<x THEN k:=j; x:=a[k] END
END;
a[k]:=a[i]; a[i]:=x
END
END StraightSelection;
BubbleSort - Пузырьковая сортировка
[Wirth, 2.4]
PROCEDURE BubbleSort;
VAR i, j: index; x: item;
BEGIN
FOR i:=2 TO n DO
FOR j:=n TO i BY -1 DO
IF a[i-1]>a[j] THEN
x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x
END
END
END
END BubbleSort;
ShakerSort - Шейкерная сортировка
[Wirth, 2.5]
PROCEDURE ShakerSort;
VAR j, k, L, R: index; x: item;
BEGIN
L:=2; R:=n; k:=n;
REPEAT
FOR j:=R TO L BY -1 DO
IF a[j-1]>a[j] THEN
x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j;
END
END;
L:=L+1;
FOR j:=L TO R BY +1 DO
IF a[j-1]>a[j] THEN
x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j;
END
END
R:=k-1
UNTIL L>R;
END ShakerSort;
ShellSort - Сортировка Шелла
[Wirth, 2.6]
PROCEDURE ShellSort;
CONST t=4; (* расстояние *)
VAR i, j, k, s: index;
x: item;
m: 1..t;
h: ARRAY[1..t] OF INTEGER;
BEGIN
h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=1;
FOR m:=1 TO t DO
k:=h[m]; s:=-k; (* место барьера *)
FOR i:=k+1 TO n DO
x:=a[i]; j:=i-k;
IF s=0 THEN s:=-k END;
s:=s+1; a[s]:=x;
WHILE x<a[j] DO a[j+k]:=a[j]; j:=j-k END;
a[j+k]:=x
END
END
END ShellSort;
HeapSort - Сортировка с помощью дерева
[Wirth, 2.8]
(См. также Кучи)
PROCEDURE HeapSort;
VAR L,R: index; x: item;
PROCEDURE sift(L, R: index);
VAR i, j: index; x: item;
BEGIN
i:=L; j:=2*L; x:=a[L];
IF (j<R)&(a[j]<a[j+1] THEN j:=j+1 END;
WHILE (j<=R)&(x<a[j]) DO
a[i]:=a[j]; i:=j; j:=2*j;
IF (j<R)&(a[j]<a[j+1]) THEN j:=j+1 END
END
END sift;
BEGIN
L:=(n DIV 2)+1; R:=n;
WHILE L>1 DO L:=L-1; sift(L,R) END;
WHILE R>1 DO
x:=a[1]; a[1]:=a[R]; a[R]:=x;
R:=R-1;
sift(L,R);
END
END HeapSort;
QuickSort - Быстрая сортировка Хоара
[Wirth, 2.10]
PROCEDURE QuickSort;
PROCEDURE sort(L, R: index);
VAR i, j: index; w, x: item;
BEGIN
i:=L; j:=R;
x:=a[(L+R) DIV 2];
REPEAT
WHILE a[i]<x DO i:=i+1 END;
WHILE x<a[j] DO j:=j-1 END;
IF i<=j THEN
w:=a[i]; a[i]:=a[j]; a[j]:=w;
i:=i+1; j:=j-1
END
UNTIL i>j;
IF L<j THEN sort(L,j) END;
IF i<R THEN sort(i,R) END;
END sort;
BEGIN sort(1,n);
END QuickSort;
[Bentley 11.2-3]
Набросок
void qsort(l, u)
if l >= u
/* не более одного элемента - ничего не делаем */
return
/* цель: разбить массив относительно какого-либо
элемента, который оказывается на правильном месте */
qsort(l, p-1)
qsort(p+1, u)
Версия 1
void qsort(l, u)
if (l >= u)
return
m = 1
for i = [l+1, u]
/* инвариант: x[l+1..m] < x[l] &&
* x[m+1..i-1] >= x[l] */
if (x[i] < x[l])
swap(++m, i)
swap(l, m)
/* x[l..m-1] < x[m] <= x[m+1, u] */
qsort(l, m-1)
qsort(m+1, u)
Версия 3
void qsort(l, u)
if l >= u
return
t = x[l]; i = l; j = u+1
loop
do i++ while i <= u && x[i] < t
do j-- while x[j] > t
if i > j
break
swap(i, j)
swap(l, j)
qsort(l, j-1)
qsort(j+1, u)
Рекомендации по выбору алгоритмов сортировки
[Wirth]
- Для достаточно малых n прямые методы оказываются быстрее, хотя при больших n ими пользоваться не стоит.
- Прямой выбор предпочтительнее строгого включения. Однако, если ключи вначале упорядочены, то прямое включение будет оставаться несколько более быстрым.
- Шейкерная сортировка с успехом используется в случаях, когда элементы почти упорядочены.
- HeapSort: чем больше n, тем лучше она работает. Она даже становится сравнимой с сортировкой Шелла.
- Пузырьковая сортировка - наихудшая из всех метолов, но ее улучшение приводит к самому лучшему из известных методов сортировки - QuickSort.
- QuickSort - чем неупорядоченее, тем лучше.
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Основные операциии с линейными списками
[Wirth, гл. 4.3]
Представление списка
TYPE Ptr = POINTER TO Node;
TYPE Node = RECORD
key: INTEGER;
next: Ptr;
data: ...;
END;
VAR p, q: Ptr;
Включение нового элемента в начало списка
Allocate(q,SIZE(Node)); q^.next:=p; p:=q;
Формирование списка из n элементов
p:=NIL; (* в начале список пуст *)
WHILE n>0 DO
Allocate(q,SIZE(Node)); q^.next:=p; p:=q;
q^.key:=n; n:=n-1
END;
Включение элемента в список после элемента, на который указывает p
q^.next:=p^.next; p^.next:=q;
Проход по списку
Проход по списку с выполнением над каждым его элементом
операции P(x)
WHILE p#NIL DO
P(p^);
p:=p^.next;
END;
Поиск элемента в списке
WHILE (p#NIL)&(p^.key#x) DO
p:=p^.next;
END
Последовательное распределение
[Knuth, 2.2.2]
Наиболее простой и естественный способ хранения линейного списка в памяти компьютера заключается в расположении элементов в последовательных ячейках, при котором один узел списка следует сразу же за другим. Тогда
LOC(X[j+1])=LOC(X[j])+c,
где c - размер одного узла.
LOC(X[j])=L[0] +cj,
где L[0] - константа, которая называется базовым адресом (base address), т. е. является адресом некоего узла X[0]. стр. 286
КУЧИ
[Bentley 14]
Куча представляет собой структуру данных, используемую для представления множеств элементов.
12
___/ \___
/ \
/ \
20 15
/ \ / \
/ \ / \
29 23 17 22
/\ /\ /
/ \ / \ /
35 40 26 51 19
Это двоичное дерево является кучей благодаря двум свойствам.
Первое свойство мы назовем “порядком”: значение любого узла не превышает значения любого из его дочерних узлов. Отсюда следует, что наименьший элемент набора находится на вершине дерева. Однако о соотношении левого и правого дочерних узлов ничего не говорится.
Второе свойство кучи называется “формой”. Идея формы лучше всего передается следующим рисунком:
/\
/ \
/ \
/ \
/ ___\
/_____|
Другими словами, двоичное дерево, обладающее свойством “формы”, заканчивается не более чем на двух уровнях (то есть заключительные узлы расположены не более чем на двух уровнях), причем находящиеся на нижнем уровне узлы сгруппированы слева. В дереве не должно быть незанятых узлов. Если в нем содержится n узлов, ни один из них не может отстоять более чем на log2(n).
Представление кучи в виде массива
x[1]
/ \
x[2] x[3]
/ \ / \
x[4] x[5] x[6] x[7]
/ \ / \ /
x[8] x[9] x[10] x[11] x[12]
Обратите внимание, что для представления куч массивы нумеруются с единицы. Типичные функции для такого дерева определяются следующим образом:
root = 1
value(i) = x[i]
leftchild(i) = 2*i
rightchild(i) = 2*i + 1
parent(i) = i/2
null(i) = (i < 1) or (i > n)
Неявное дерево из n элементов обязательно будет обладать свойством формы: отсутствие элементов в нем просто не предусмотрено.
Вышеприведенная куча из 12 элементов может быть представлена в виде следующего массива:
| 12 20 15 29 23 17 22 35 40 26 51 19 |
-------------------------------------
1 12
Второе свойство: массив x[1..n] обладает свойством кучи, если
A: 2<=i<=n: x[i/2] <= x[i]
Добавление нового элемента
Добавление произвольного элемента в поле x[n] при условии, что x[1..n-1] является кучей, не обязательно даст кучу. Восстановление свойства кучи обеспечивается функцией siftup. Имя функции описывает стратегию, лежащую в ее основе: новый элемент просеивается и всплывает вверх до полагающегося ему места, обмениваясь позициями с вышестоящими элементами:
void siftup(n)
/* предусловие: n > 0 && heap(1, n-1)
* постусловие: heap(1, n) */
loop
/* инвариант: heap(1, n) за исключением, быть
* может, элемента i и его родителя */
if i == 1
break
p = i/2
if x[p] <= x[i]
break
swap(p, i)
i = p
Если x[1..n] — куча, а мы присваиваем элементу x1 новое значение, то в любом случае остается верным утверждение heap(2, n). Функция siftdown предназначена для расширения этого утверждения до heap(1, n). Это осуществляется путем просеивания элемента x1 вниз по массиву, до тех пор, пока у него не закончатся дочерние элементы или пока элемент не окажется не превышающим значени всех его дочерних элементов.
void siftdown(n)
/* предусловие: heap(2, n) && n >= 0
* постусловие: heap(1, n) */
i = 1
loop
/* инвариант: heap(1, n) верно, за
* исключением, быть может, i и его дочерних
* элементов (0, 1 или 2) */
c = 2*i
if c > n
break
/* c - левый дочерний эл-т i */
if c+1 <= n
/* c+1 - правый дочерний эл-т i */
if x[c+1] < x[c]
c++
/* c - наименьший из дочерних эл-тов */
if x[i] <= x[c]
break
swap(c, i)
i = c
Сортировка с помощью кучи (heapsort)
[Bentley 14.4]
(См. также HeapSort - Сортировка с помощью дерева)
for i = [2, n]
siftup(i)
for (i=n; i >= 2; i--)
swap(1, i)
siftdown(i-1)
ПЕРЕСТАНОВКИ
Перемножение перестановок, представленных в виде циклов
[Knuth, 1.3.3]
Произведение перестановок можно выполнять непосредственно с помощью циклической записи. Например, вычислив произведение перестановок
(a c f g)(b c d)(a e d)(d a d e)(b g f a e),
находим (двигаясь слева направо), что «a переходит в c, c переходит в d, d переходит в a, a переходит в d и d остается без изменений». Таким образом, конечным результатом является то, что a переходит в d, и мы запишем «(a d)» в качестве частичного ответа. Теперь выясним, что происходит с d: «d переходит в b, которое затем переходит в g»; следовательно, имеем частичный результат «(a d g)». Рассмотрев, что происходит с g, находим, что «g переходит в a, затем в e, в f и в a»; таким образом, первый цикл замыкается: «(a d g)». Теперь выберем новый элемент, который еще не встречался, напимер, c. Находим, что c переходит в e… Окончательным ответом будет «(a d g)(c e b)».
Алгоритм A
[Knuth 1.3.3 A]
Этот алгоритм берет произведение циклов вида
(a c f g)(b c d)(a e d)(d a d e)(b g f a e)
и вычисляет получающуюся в результате перестановку в виде произведения непересекающихся циклов. Для простоты здесь не приводится описание процедуры удаления единичных циклов; это было бы лишь незначительным обобщением алгоритма. По мере выполнения алгоритма последовательно «помечаем» элементы исходной формулы, т.е. те символы, которые уже «обработаны».
- [Первый проход] Отметить все левые скобки и заменить все правые скобки помеченной копией входного символа, который следует за соответствующей левой скобкой.
- [Раскрытие скобок] Выполнив поиск слева направо, найти первый непомеченный элемент входной формулы. (Если все элементы помечены, то работа алгоритма заканчивается.) Установить START равным этому элементу; вывести левую скобку; вывести элемент и пометить его.
- [Установка CURRENT] Установить CURRENT равным следующему элементу формулы.
- [Просмотр формулы] Продвигаться вправо, пока не будет либо достигнут конец формулы, либо найден элемент, равный CURRENT; в последнем случае пометить его и вернуться к шагу 3.
- [CURRENT = START?] Если CURRENT <> START, вывести CURRENT и вернуться к шагу 4, снова начав с левого края формулы (продолжая тем самым вывод искомого цикла).
- [Закрытие] (Полный искомый цикл выведен.) Вывести правую скобку и вернуться к шагу 2.
Алгоритм B
[Knuth 1.3.3 B]
Этот алгоритм дает, в сущности, тот же результат, что и алгоритм A. Предположим, что переставляемыми элементами являются x1 , x2 , …, x[n] . Будем использовать вспомогательную таблицу T1, T2, …, T[n]; по окончании работы алгоритма x[i] переходит в x[j] в перестановке тогда и только тогда, когда T[i] = j.
- [Инициализация] Присвоить
T[k] <- k, где 1 <= k <= n. Подготовиться также к просмотру справа налево. - [Следующий элемент] Рассмотреть следующий элемент ввода (справа налево). Если ввод исчерпан, то работа алгоритма заканчивается. Если рассматривается элемент <<)>>, то присвоить Z <- 0 и повторить шаг 2; если это элемент <<(>>, то перейти к шагу 4. В противном случае рассматривается элемент x[i] для некоторого i; тогда перейти к шагу 3.
- [Замена T[i]] Выполнить взаимный обмен Z<->T[i]. Если в результате получится T[i] = 0, то присвоить j <- i. Вернуться к шагу 2.
- [Замена T[j]] Присвоить T[j] <- Z. (Здесь j - это строка, определяющая элемент <<)>>, т.е. правую скобку, которая соответствует только что просмотренной левой скобке.) Вернуться к шагу 2.
Обратная перестановка на месте
Алгоритм I
[Knuth 1.3.3 I]
Заменить X1X2… X[n], которая является перестановкой чисел {1,2,… n}. Этот алгоритм был предложен Бин-Чао Хуан (Bing-Chao Huang).
- [Инициализация] Присвоить m <- n, j <- -1.
- [Следующий элемент] Присвоить i <- X[m]. Если i < 0, перейти к шагу 5 (этот элемент уже был обработан).
- [Обратить один элемент] (В этот момент j < 0 и i=X[m]. Если m не является наибольшим элементом своего цикла, то первоначальная перестановка давала X[-j]=m.) Присвоить X[m] <- j, j <- -m, m <- i, i <- X[m].
- [Конец цикла?] Если i > 0, перейти к шагу 3 (этот цикл не закончен); иначе - присвоить i <- j. (В последнем случае первоначальная перестановка давала X[-j]=m, где m - наибольший элемент в цикле.)
- [Сохранить окончательное значение] Присвоить X[m] <- -i. (Первоначально X[-i] было равно m.)
- [Цикл по m] Уменьшить m на 1. Если m > 0, перейти к шагу 2; в противном случае работа алгоритма заканчивается.
Алгоритм J
[Knuth 1.3.3 J]
Следующий остроумный алгоритм был предложен Дж. Бутройдом (J. Boothroyd). Этот алгоритм дает такой же результат, как и алгоритм I, но на основании другого метода.
- [Сделать все величины отрицательными] Присвоить X[k] <- -X[k] для 1 <= k <= n. Присвоить также m <- n.
- [Инициализация j] Присвоить j <- m.
- [Нахождение отрицательного элемента] Присвоить i <- X[j]. Если i > 0, присвоить j <- i и повторить этот шаг.
- [Обращение] Присвоить X[j] <- X[-i], X[-i] <- m.
- [Цикл по m] Уменьшить m на 1; если m > 0, вернуться к шагу 2. В противном случае работа алгоритма заканчивается.
РАЗНОЕ
Ввод/вывод чисел (без знака)
[Wirth, 1.11.3]
x: WORD;
i: CARDINAL;
ch: CHAR;
d: ARRAY[0..N] OF WORD;
(* ввод и преобразование *)
x:=0; Read(ch);
WHILE ("0"<=ch)&(ch<="9") DO
x:=10*x+(ORD(ch)-ORD("0"));
Read(ch)
END;
(* преобразование и вывод *)
i:=0;
REPEAT d[i]:=x MOD 10; x:=x DIV 10; i:=i+1;
UNTIL x=0;
REPEAT i:=i-1; Write(CHR(d[i]+ORD("0")))
UNTIL i=0;
Простейший кольцевой буфер
[Wirth, 1.11.2]
для использования одной программой
MODULE Buffer;
EXPORT deposit, fetch;
CONST N=1024; (* размер *)
VAR n, in, out: CARDINAL;
buf: ARRAY[0..N-1] OF WORD;
PROCEDURE deposit(x: WORD);
BEGIN
IF n=N THEN HALT END;
n:=n+1; buf[in]:=x; in:=(in+1) MOD N
END deposit;
PROCEDURE fetch(VAR x: WORD);
BEGIN
IF n=0 THEN HALT END;
n:=n-1; x:=buf[out]; out:=(out+1) MOD N
END fetch;
BEGIN n:=0; in:=0; out:=0
END Buffer.
Алгоритм Евклида
[Knuth, 1.1 E]
Даны два целых положительных числа m и n. Требуется найти их наибольший общий делитель.
- [Нахождение остатка] Разделим m на n, и пусть остаток от деления будет равен r (где 0 <= r < n).
- [Сравнение с нулем] Если r=0, то выполнение алгоритма прекращается; n - искомое значение.
- [Замещение] Присвоить m <- n, n <- r и вернуться к шагу 1.
Обобщенный алгоритм Евклида
[Knuth, 1.2.1 E]
Даны два целых положительных числа m и n. Требуется найти их наибольший общий делитель (gcd - greatest common divisor) d и два целых числа a и b, таких, что am+bn=d.
- [Инициализация] Присвоить a’ <- b <- 1, a <- b’ <- c <- m, d <- n.
- [Деление] Пусть q и r - это частное и остаток от деления c на d соответственно. (Тогда c=qd+r, где 0 <= r < d.)
- [Остаток - нуль?] Если r=0, то выполнение алгоритма прекращается; в этом случае имеем am+bn=d, как и требовалось.
- [Повторение цикла] Присвоить c <- d, d <- r, t <- a’, a’ <- a, a <- t-qa, t <- b’,b’ <- b, b <- t-qb и вернуться к шагу 2.
Циклический сдвиг массива
[Bentley 2.3]
Циклический сдвиг массива x из n элементов влево на i позиций за время, пропорциональное n, причем доступно лишь несколько десятков байт оперативной памяти.
Циклический сдвиг массива x сводится фактически к замене ab на ba, где a — первые i элементов, а b — оставшиеся элементы.
Итак, нужно преобразовать массив ab в ba. Предположим, что у нас есть функция reverse, переставляющая элементы некоторой части массива в противоположном порядке. В исходном состоянии массив имеет вид ab. Вызвав эту функцию для первой части, получим a’b. Затем вызовем ее для второй части: получим a’b’. Затем вызовем функцию для всего массива, что даст (a’b')’, а это в точности соответствует ba. Посмотрим, как будет такая функция действовать на массив abcdefgh, который нужно сдвинуть влево на три элемента:
reverse(0, i-1) /* cbadefgh */
reverse(i, n-1) /* cbahgfed */
reverse(0, n-1) /* defghabc */
Дуг Макилрой (Doug McIlroy) предложил наглядную иллюстрацию циклического сдвига массива из десяти элементов вверх на пять позиций; начальное положение: обе руки ладонями к себе, левая над правой.
--== 1 | --=== 5 | --=== 5 | 6 ==--
==== 2 | ==== 4 | ==== 4 | 7 ====
===== 3 X ===== 3 | ===== 3 | 8 =====
==== 4 | ==== 2 | ==== 2 | 9 ====
--=== 5 | --== 1 | --== 1 | 10 ===--
| | X
6 ==-- | 6 ==-- | 10 ===-- | --== 1
7 ==== | 7 ==== | 9 ==== | ==== 2
8 ===== | 8 ===== X 8 ===== | ===== 3
9 ==== | 9 ==== | 7 ==== | ==== 4
10 ===-- | 10 ===-- | 6 ==-- | --=== 5
| | |
повернуть повернуть повернуть
левую руку правую руку обе (как целое)
Поиск максимальной подпоследовательности
[Bentley 8.1]
На входе имеется массив x из n вещественных чисел, на выходе должна быть получена максимальная сумма любой непрерывной последовательности элементов массива.
Вариант 1
Перебор всех пар целых i и j, где 0<=i<=j<n; для каждой пары чисел вычисляется сумма x[i..j], после чего проверяется, преверяется, превосходит ли она предыдущее найденное максимальное значение.
maxsofar = 0
for i = [0, n)
for j = [i, n)
sum = 0
for k = [i, j]
sum += x[k]
/* sum - сумма элементов x[i..j] */
maxsofar = max(mazsofar, sum)
Вариант 2a
Данный алгоритм позволяет быстро вычислить сумму благодаря тому, что сумма x[i..j] легко получается из предыдущей: x[i..j-1].
maxsofar = 0
for i = [0, n)
sum = 0
for j = [i, n)
sum += x[j]
/* sum - сумма x[i..j] */
maxsofar = max(maxsofar, sum)
Вариант 2b
Алгоритм вычисляет сумму во внутреннем цикле, обращаясь к структуре данных, которая строится отдельно, до начала первого цикла. Создается массив cumarr, i-й элемент которого содержит кумулятивную сумму значений x[0..i], поэтому сумму x[i..j] можно получить как разность cumarr[j] - cumarr[i-1].
cumarr[-1] = 0
for i = [0, n)
cumarr[i] = cumarr[i-1] + x[i]
maxsofar = 0
for i = [0, n)
for j = [i, n)
sum = cumarr[j] - cumarr[i-1]
/* sum - сумма x[i..j] */
maxsofar = max(maxsofar, sum)
Вариант 3 “Разделяй и властвуй”
Алгоритм основан на правиле:
Если нужно решить задачу размера n, следует рекурсивно решить две подзадачи размера приблизительно n/2, а затем оббъединить их решения в одно целое.
float maxsum3(l, u)
if (l > u) /* пустой массив */
return 0
if (l == u) /* один элемент */
return max(0, x[l])
m = (1 + u) / 2
/* m: поиск макс. посл. слева от границы */
lmax = sum = 0
for (i = m; i >= l; i--)
sum += x[i]
lmax = max(lmax, sum)
/* m: поиск макс. посл. справа от границы */
rmax = sum = 0
for i = (m, u]
sum += x[i]
rmax = max(rmax, sum)
return max(lmax+rmax, maxsum3(l, m), maxsum3(m+1, u))
Алгоритм запускается вызовом
answer = maxsum3(0, n-1)
Вариант 4 Сканирующий алгоритм
maxsofar = 0
maxendinghere = 0
for i = [0, n)
/* инвариант: значения maxendinghere и maxsofar
точны для x[0..i-1] */
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
Функция comlen - вычисление длины общей части двух строк
[Bentley 15.2]
int comlen(char *p, char *q)
i = 0
while *p && (*p++ == *q++)
i++
return i
Установка, проверка и сброс отдельных битов
[Bentley p.239]
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1+N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i) { return a[i>>SHIFT] & (1<<(i & MASK)); }
RSS