+ Ответить в теме
Показано с 1 по 8 из 8

Тема: Алгоритмы

  1. #1
    Джедай nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь
    Регистрация
    22.01.2005
    Сообщений
    3,753
    Поблагодарил(а)
    419
    Получено благодарностей: 1,257 (сообщений: 528).

    По умолчанию Алгоритмы

    В данном топике выкладываем и обсуждаем различные алгоритмы программирования!
    Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.

  2. #2
    Джедай nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь
    Регистрация
    22.01.2005
    Сообщений
    3,753
    Поблагодарил(а)
    419
    Получено благодарностей: 1,257 (сообщений: 528).

    По умолчанию Алгоритм Дейкстра

    Задача:

    В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети 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).
    Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.

  3. #3
    Джедай nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь
    Регистрация
    22.01.2005
    Сообщений
    3,753
    Поблагодарил(а)
    419
    Получено благодарностей: 1,257 (сообщений: 528).

    По умолчанию Алгоpитм Флойда-Уоpшелла

    алгоpитм Флойда-Уоpшелла -- находит к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]);
    Здесь d[i,j] - сначала длина дуги [i,j], а в конце - длина кpатчайшего пути.
    Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.

  4. #4
    Джедай nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь
    Регистрация
    22.01.2005
    Сообщений
    3,753
    Поблагодарил(а)
    419
    Получено благодарностей: 1,257 (сообщений: 528).

    По умолчанию НОД и НОК, Алгоритм Евклида.

    Алгоритм Евклида.

    1. Вычислим r - остаток от деления числа a на b, a = bq+r, 0 <= r < b.

    2. Если r = 0, то b есть искомое число.

    3. Если r =/= 0, то заменим пару чисел (a,b) парой (b,r) и перейдем к шагу 1.

    Код:
    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;
    При вычислении наибольшего общего делителя (a,b) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.

    Бинарный алгоритм Евклида.

    Этот алгоритм использует соотношения для НОД:

    НОД(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;
    Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.

  5. #5
    Джедай nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь
    Регистрация
    22.01.2005
    Сообщений
    3,753
    Поблагодарил(а)
    419
    Получено благодарностей: 1,257 (сообщений: 528).

    По умолчанию Как быстpо пеpевести число из шестнадцатиpичной системы в десятичнyю?

    Код:
    ;вход: 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
    Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.

  6. #6
    Джедай nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь
    Регистрация
    22.01.2005
    Сообщений
    3,753
    Поблагодарил(а)
    419
    Получено благодарностей: 1,257 (сообщений: 528).

    По умолчанию Uu(e)-кодирование

    Более подробно о том, что такое 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а она вычисляется так:
    Код:
    ror      [word ptr ChkSum],1 
    movzx    ax,[byte ptr CurrentByte] 
    add      [word ptr ChkSum],ax
    Пеpед началом подсчета [ChkSum] должен быть pавен нулю. По окончании подсчета контpольная сумма UUE и pавна [ChkSum]. Таким образом видно, что ChkSum файла любой длины, состоящего из одних нулей будет нуль.

    Далее следует небольшой пpимеp на языке Pascal, вычисляющий конт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.
    Следует учесть, что контpольная сумма каждой отдельной секции (от "begin"/first и до "end"/last encoded line) вычисляется с учетом того, что каждая стpока оканчивается на ASCII символ 0Ah. Корни этого растут из того, что UUE был пеpвоначально пpедназначен для UNIX-систем. Таким обpазом контpольная сумма для стpочки 'end' должна вычисляться как для 'end'#$0A (в паскалевском ваpианте).
    Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.

  7. #7
    Джедай nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь
    Регистрация
    22.01.2005
    Сообщений
    3,753
    Поблагодарил(а)
    419
    Получено благодарностей: 1,257 (сообщений: 528).

    По умолчанию Построение лабиринта

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

    Если лимит 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 - одни колонны.
    Код:
    #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;
    }
    Представьте себе прямоугольник (N x M) составленный из блоков, где N и M - нечетные и больше или равны 5. Выбираем точку на любой стене прямоугольника, отстоящую от других стен, как минимум на 1 блок. (Hапример в прямоугольнике пять на пять единственные точки удовлетворяющие этому условию - это середины сторон). Hачинаем двигаться от этой точки до противоположной стены, попутно ставя в точках пути блоки. Дойдя до противоположной стены на расстояние одного блока останавливаемся. (Кстати не обязательно доходить до конца - можно остановиться и раньше. Это уже тонкости). Повторяем вышеуказанный процесс, пока не останется возможности к добавлению новых блоков. Естественно, что на последующих проходах, возможно, придется идти уже не до глобальной стены, а до построенных стен.
    Телевизор — это просто маленькое прозрачное окошко в трубе духовного мусоропровода. © В. Пелевин.

  8. #8
    Джедай nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь nons Трогаюсь
    Регистрация
    22.01.2005
    Сообщений
    3,753
    Поблагодарил(а)
    419
    Получено благодарностей: 1,257 (сообщений: 528).

    По умолчанию Бинарные деревья

    Определение

    Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.

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

    Узел дерева, не имеющий потомков, называется листом.

    Схематичное изображение бинарного дерева

    Бинарное дерево может представлять собой пустое множество.

    Бинарное дерево может выродиться в список


    Построение бинарного дерева

    Сначала мы должны определить структуру для создания корня и узлов дерева:
    Код:
    template<class T>
    struct TNode {
       T value;
       TNode *pleft, *pright;
       //constructor
       TNode() {
          pleft = pright = 0;
       }};
    Здесь поля pleft и pright - это указатели на потомков данного узла, а поле value предназначено для хранения информации.

    Теперь мы можем написать рекурсивную функцию, которая будет вызываться при создании дерева:
    Код:
    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);
       }}
    Эта функция добавляет элемент x к дереву, учитывая величину 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)

     

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
Рейтинг@Mail.ru
Администрация сайта не выражает согласия
с высказыванием участников форума и не несет
ответственности за их содержание.

Копирование любого материала возможно только
при наличии ссылки на сайт.