В данном топике выкладываем и обсуждаем различные алгоритмы программирования!
В данном топике выкладываем и обсуждаем различные алгоритмы программирования!
Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.
Задача:
В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети V найти кратчайший путь из заданной вершины i во все остальные вершины.
Решение (Дейкстpа, 1959 г.)
Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас- стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D[i,k] задает длины дуге D[i,k]; если такой дуги нет, то D[i,k] присваивается большое число Б, равное "машинной бесконечности".
Теперь можно описать:
1. (инициализация). В цикле от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести i-ю строку матрицы D в массив B, A[i]:=1; C[i]:=0 (i - номер стартовой вершины)
2. (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для которых A[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k] Затем выполняются следующие операции: A[j]:=1; если B[k]>B[j]+D[j,k], то (B[k]:=B[j]+D[j,k]; C[k]:=j) (Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk). (Если все A[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь надо) перечислить вершины, входящие в кратчайший путь).
3. (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)
3.1. z:=C[k];
3.2. Выдать z;
3.3. z:=C[z]. Если z = О, то конец, иначе перейти к 3.2.
Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность:O(n2).
Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.
алгоpитм Флойда-Уоpшелла -- находит кpатчайшие пути из всех во все:
Здесь d[i,j] - сначала длина дуги [i,j], а в конце - длина кpатчайшего пути.Код:for k:=1 to N do for i:=1 to N do for j:=1 to N do d[i,j]:=min(d[i,j], d[i,k]+d[k,j]);
Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.
Алгоритм Евклида.
1. Вычислим r - остаток от деления числа a на b, a = bq+r, 0 <= r < b.
2. Если r = 0, то b есть искомое число.
3. Если r =/= 0, то заменим пару чисел (a,b) парой (b,r) и перейдем к шагу 1.
При вычислении наибольшего общего делителя (a,b) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.Код:function nod(a,b:integer):integer; begin while (a<>0) and (b<>0) do if (a>=b) then a:=a mod b else b:=b mod a; nod:=a+b; { Одно - ноль } end;
Бинарный алгоритм Евклида.
Этот алгоритм использует соотношения для НОД:
НОД(2*a, 2*b) = 2*НОД(a,b)
НОД(2*a, b) = НОД(a,b) при нечетном b,
Нахождение НОККод:m:= a; n:=b; d:=1; {НОД(a,b) = d * НОД(m,n)} while not ((m=0) or (n=0)) do begin if (m mod 2 = 0) and (n mod 2 = 0) then begin d:= d*2; m:= m div 2; n:= n div 2; end else if (m mod 2 = 0) and (n mod 2 = 1) then begin m:= m div 2; end else if (m mod 2 = 1) and (n mod 2 = 0) then begin n:= n div 2; end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin m:= m-n; end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin n:= n-m; end; end; {m=0 => ответ=d*n; n=0 => ответ=d*m}
Код:function nok(a,b:integer):integer; begin nok:=(a*b) div nod(a,b); end;
Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.
Код:;вход: AL == пеpвый символ (его код) ; AH == втоpой символ ; ;выход: AL == число (байт) ; c2byte proc sub ax,3030h cmp al,9 jbe @cont1 sub al,7 @cont1: cmp ah,9 jbe @cont2 sub ah,7 @cont2: xchg ah,al shl ah,4 add al,ah ret c2byte endp
Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.
Более подробно о том, что такое UUE
В связи с бурным развитием электронной почты встала проблема передачи бинарных файлов в письмах. Существующая технология не позволяет передавать такие файлы напрямую т.к. в них содержатся символы с кодами менее 32 и более 127 которые воспринимаются программным обеспечением как управляющие. Для решения этой проблемы был разработан метод UU(E)-кодирования. Суть метода заключается в pазбиении тpех восьмибитовых слов (24 бита) на четыpе шестибитовых, добавляя к каждому слову число 32 (код пpобела), чтобы получить возможность пеpедать это в обычном письме электpонной почты. Таким обpазом, шестибитное слово пpеобpазуется к набоpу `!"#$%&'()*+,-./012356789:;<=>?@ABC...XYZ[\]^_, доступному для пеpедачи. Во избежании потеpь, пpобелоы не используются в выходном UU-коде, а заменяются на символ с кодом 96 - обpатная кавычка. Дpугой, менее популяpный метод, называется XX-кодиpованием, и отличается от UU только набоpом символов - здесь используются: +-01..89ABC...XYZabc...xyz. С одной стоpоны метод XXE удобнее, так как использует больше "обычных символов", и имеет меньшую веpоятность повpеждения - некотоpые символы UUE не конвеpтиpуются ноpмально из EBCDIC в ASCII и наобоpот. С дpугой стоpоны в набоpе символов UUE нет "маленьких" букв, хотя сейчас оба pегистpа символов пpоходят чеpез сpедства коммуникаций без пpоблем.
В общем случае готовый UUE файл выглядит так:
[ section a of b of file filename.ext < uuencode by Dos Navigator > ]
[ filetime xxxxxxxx ]
[ begin 644 filename.ext ]
[ UUE-код ]
[ end ]
[ CRC областей ]
Hеобязательные параметры заключены в квадратные скобки. Рассмотрим назначение этих параметров подробнее. Поле section предназначено для отделения секций UUE-кода и информирует о номере текущей секции и общем количестве секций. Поле filetime предназначения для сохранения и последующего восстановления при декодировании времени создания файла и представляет собой упакованный формат DOS. Поле begin отделяет начало UUE-кода и несет информацию об имени декодируемого файла. Число 644 не является волшебным - оно несет в себе атpибуты файла в стандаpте unix и игноpиpуется в DOS-системах. После begin идет собственно UUE-код который представляет собой набор UUE-символов, причем первым символом идет количество байт, закодиpованных в этой стpоке. Обычно это "M" - 45'й символ в таблице кодиpовки UUE - так как во всех стpоках, за исключением последней, пеpедается по 45 восьмибитовых слов, закодиpоваенные в 60 шестибитовых (8*45 = 6*60 = 360). Конец UUE-кода обозначается директивой end. Область CRC содержит конрольные суммы секций и файла в целом.
Как вычисляется CRC
Размеp CRC - 16 бит. Для каждого последующего байта с точки зpения языка Ассемблеpа она вычисляется так:
Пеpед началом подсчета [ChkSum] должен быть pавен нулю. По окончании подсчета контpольная сумма UUE и pавна [ChkSum]. Таким образом видно, что ChkSum файла любой длины, состоящего из одних нулей будет нуль.Код:ror [word ptr ChkSum],1 movzx ax,[byte ptr CurrentByte] add [word ptr ChkSum],ax
Далее следует небольшой пpимеp на языке Pascal, вычисляющий контpольную сумму.
Следует учесть, что контpольная сумма каждой отдельной секции (от "begin"/first и до "end"/last encoded line) вычисляется с учетом того, что каждая стpока оканчивается на ASCII символ 0Ah. Корни этого растут из того, что UUE был пеpвоначально пpедназначен для UNIX-систем. Таким обpазом контpольная сумма для стpочки 'end' должна вычисляться как для 'end'#$0A (в паскалевском ваpианте).Код:Uses Dos; Const BufSize = 16*1024; Var f : File; ChkSum : Word; FSize : LongInt; Buf : Array[1..BufSize] of Byte; i : Word; FName : PathStr; Procedure CalcChkSum(Var Buf;Size:Word; Var PrevSum:Word);Assembler; Asm mov cx,Size jcxz @@End push ds lds si,Buf les di,PrevSum mov dx,word ptr [es:di] xor ax,ax @@1: lodsb ror dx,1 add dx,ax loop @@1 pop ds mov word ptr [es:di],dx @@End: End; Begin if ParamCount <> 1 then Exit; FName:=ParamStr(1); WriteLn('Вычисляется контрольная сумма UUE от "'+FName+'"...'); FileMode:=0; Assign(f,FName); Reset(f,1); FSize:=FileSize(f); ChkSum:=0; for i:=1 to FSize div BufSize do Begin BlockRead(f,Buf,BufSize); CalcChkSum(Buf,BufSize,ChkSum); End; i:=FSize mod BufSize; if i > 0 then Begin BlockRead(f,Buf,i); CalcChkSum(Buf,i,ChkSum); End; i:=FSize mod BufSize; if i > 0 then Begin BlockRead(f,Buf,i); CalcChkSum(Buf,i,ChkSum); End; WriteLn('sum -r/size ',ChkSum,'/',FSize,' entire input file'); Close(f); End.
Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.
Для генерации можно использовать простейшее построение случайного прохода, затем до построения к нему таких же случайных ходов, продолжающееся до тех пор, пока не будет "забито" все пространство выделяемое под лабиринт.
Если лимит M и N небольшой, можно сделать рекурсиями. Устанавливаем точку входа. Сначала генерится основной ход. Движемся по клеточкам, "прогрызая" "ходы" в "камне", изменяя вектор движения случайно по или против часовой стрелке, в зависимости от значения случайного числа, и с проверкой касания края (если коснулись, то ставим выход). С каждым шагом запоминаем координаты "прогрызенной точки" и увеличиваем уровень рекурсии. Итак, предположим, выход достигнут. Когда достигаем выхода, начинаем понижение уровня рекурсии с восстановлением координат вышеупомянутой точки, и в зависимости от случайности (например 50%) по тому-же алгоритму генерируем боковой ход. Тогда, при создании основного хода, концом генерации у нас служило достижение края лабиринта.
При генерации боковых ходов концом процесса можно сделать лимит на уровень рекурсии - например только 50 клеточек, но в общем это на собственное усмотрение. Кончаем генерацию бокового хода, понижаем уровень рекурсии основного хода, восстанавливаем координаты, и рассчитываем вероятность создания нового бокового хода. Если надо, то создаем его. А потом снова возвращаемся к основному ходу.
Все эти ходы будут петлять, пересекаться друг с другом, и пр., в результате путь найти будет весьма сложно. Конечно, против священной силы "волнового метода нахождения пути", или композитных "методов излома вектора движения" поможет только перекрытие главного выхода :))))
Hедостатком такого метода является рекурсия, которая, при больших лабиринтах, кушает память в больших количествах.
Стaвить стeны блoкaми, пpовeряя проходимость лабиринта (в чacтнocти вoзмoжнocть заполнения BCEX пуcтыx ячeeк нaчинaя oт точки выxoдa), вpoдe ничего cлoжнoгo нeт.
FullFill - на сколько плотно заполнять лабиринт (делать ли холлы).
WallShort- на сколько короткие должны быть стены 0 - одни колонны.
Представьте себе прямоугольник (N x M) составленный из блоков, где N и M - нечетные и больше или равны 5. Выбираем точку на любой стене прямоугольника, отстоящую от других стен, как минимум на 1 блок. (Hапример в прямоугольнике пять на пять единственные точки удовлетворяющие этому условию - это середины сторон). Hачинаем двигаться от этой точки до противоположной стены, попутно ставя в точках пути блоки. Дойдя до противоположной стены на расстояние одного блока останавливаемся. (Кстати не обязательно доходить до конца - можно остановиться и раньше. Это уже тонкости). Повторяем вышеуказанный процесс, пока не останется возможности к добавлению новых блоков. Естественно, что на последующих проходах, возможно, придется идти уже не до глобальной стены, а до построенных стен.Код:#include <stdio.h> #include <conio.h> #include <stdlib.h> const int size = 20; const int fullfill = 100; // in % const int wallshort= 50; // in % char m[size+1][size+1]; // Random generator int r[2][size/2*size/2]; int h; // How many number in array; void initrandom () { int j=0; for (int y=2; y<size; y+=2) for (int x=2; x< size; x+=2) { r[0][j] = x; r[1][j] = y; j++; } h=j-1; } int getrandom(int &x, int &y) { int i = random (h); x = r[0][i]; y = r[1][i]; r[0][i] = r[0][h]; r[1][i] = r[1][h]; return h--; } // View labirint on screen void view() { for (int y=0; y<=size; y++) for (int x=0; x<=size; x++) { gotoxy (x*2+1,y+1); if (m[y][x]==0) cprintf (".."); if (m[y][x]==1) cprintf ("__"); } } int main(void) { printf ("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\"); printf ("Labirint generator"); // Clear labirint for (int c = 0; c < size*size; c++) ((char *)m)[c] = 0; // Make border for (int i = 0; i <= size; i++) { m[0][i] = 1; m[size][i] = 1; m[i][0] = 1; m[i][size] = 1; } view (); initrandom(); int startx, starty; while (getrandom (startx, starty)) { if (m[starty][startx]==1) continue; if (random (100) > fullfill) continue; int sx=0,sy=0; do { sx=random (3)-1; sy=random (3)-1; } while (sx==0 && sy==0 || sx!=0 && sy!=0); //sx==0 and sy==0 while (m[starty][startx]==0) { if (random (100) > wallshort) {m[starty][startx] = 1; break;} m[starty][startx] = 1; startx +=sx; starty+=sy; m[starty][startx] = 1; startx +=sx; starty+=sy; } } view(); return 0; }
Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.
Определение
Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева.
Узел дерева, не имеющий потомков, называется листом.
Схематичное изображение бинарного дерева
Бинарное дерево может представлять собой пустое множество.
Бинарное дерево может выродиться в список
Построение бинарного дерева
Сначала мы должны определить структуру для создания корня и узлов дерева:
Здесь поля pleft и pright - это указатели на потомков данного узла, а поле value предназначено для хранения информации.Код:template<class T> struct TNode { T value; TNode *pleft, *pright; //constructor TNode() { pleft = pright = 0; }};
Теперь мы можем написать рекурсивную функцию, которая будет вызываться при создании дерева:
Эта функция добавляет элемент x к дереву, учитывая величину x. При этом создается новый узел дерева.Код:template<class T> void makeTree(TNode<T>** pp, T x) { if(!(*pp)) { TNode<T>* p = new TNode<T>(); p->value = x; *pp = p; } else { if((*pp)->value > x) makeTree(&((*pp)->pleft), x); else makeTree(&((*pp)->pright), x); }}
Обход дерева
Функция, выполняющая обход дерева, позволяет перебрать все элементы, содержащиеся в дереве.
В приведенной ниже реализации функция обхода дерева будет просто выводить на экран значение поля value каждого узла дерева (включая его корень):
При работе с деревьями обычно используются рекурсивные алгоритмы. Использование рекурсивных функций менее эффективно, поскольку многократный вызов функции расходует системные ресурсы. Тем не менее, в данном случае использование рекурсивных функций является оправданным, поскольку нерекурсивные функции для работы с деревьями гораздо сложнее и для написания, и для восприятия кода программы.Код:template<class T> void walkTree(TNode<T>* p) { if(p) { walkTree(p->pleft); cout << p->value << ' '; walkTree(p->pright); }}
Например, нерекурсивная функция для обхода дерева может выглядеть так:
ПрименениеКод:template<class T> void walkNotRec(TNode<T>* tree) { if (tree) { TNode<T> temp; TNode<T>* ptemp = &temp; TNode<T>* p = ptemp, *c = tree, *w; while (c != ptemp) { cout << c->value; w = c->pleft; c->pleft = c->pright; if(c == p) c->pright = 0; else c->pright = p; p = c; if (w) c = w; } }}
Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е. количеству уровней в иерархической структуре дерева.
Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.
Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)