Библиотека алгоритмов

для просмотра *.bls файлов (блок-схем алгоритмов) используйте BLS Editor

Выпуклые множества

Геометрия

Графика

Диофантовы уравнения

Интегралы

Интегральные уравнения

Интерполяция функций

Комбинаторика

Комплексный анализ

Криптография

Наборы псевдослучайных чисел

Нахождение собственных значений и собственных векторов матрицы

Неразобранные алгоритмы

Обыкновенные дифференциальные уравнения

Операции над полиномами и степенными рядами

Операции над полиномами

Ортогональные полиномы

Поиск

Полиномиальные и трансцендентные уравнения

Простейшие операции над матрицами

Работа с датами

Работа с разреженными матрицами

Работа с формулами

Решение систем линейных алгебраических уравнений

Сортировка

Суммирование рядов

Теория графов

Теория чисел

Экстремумы функций

для просмотра *.bls файлов (блок-схем алгоритмов) используйте BLS Editor

Библиотека алгоритмов


Библиотекa алгоритмов по программированию. Выпуклые множества.
  • Проверка является ли многоугольник выпуклым. Скачать
  • Проверка является ли многоугольник выпуклым (используя векторные произведения). Скачать
  • Построение выпуклой оболочки множества точек на плоскости.(мой метод) Скачать
  • Построение выпуклой оболочки множества точек на плоскости.(метод Грехема) Скачать
  • Поиск пересечения двух выпуклых многоугольников. Скачать

Проверка является ли многоугольник выпуклым. Скачать

Функция проверяет является ли многоугольник заданный координатами вершин (xi,yi), i=1..n выпуклым или нет. При проверке используется определение выпуклого многоугольника, а именно: многоугольник является выпуклым, если любые две его вершины лежат по одну сторону от прямой продолжения любой из его стороны.

Функция использует описанную ранее функцию для определения лежат ли две точки по одну сторону от прямой. Так же надо заметить, что внутри функции используются элементы X[0],Y[0] для "замыкания" многоугольника, т.е. X[0]=X[n] и Y[0]=Y[n].

Наверх

Проверка является ли многоугольник выпуклым(используя векторные произведения). Скачать

Функция проверяет является ли многоугольник заданный координатами вершин (xi,yi), i=1..n выпуклым или нет. В отличии от предыдущего алгоритма, проверка осуществляется следующим образом: для каждой пары смежных сторон вычисляется векторное произведение. В случае, если для всех пар векторные произведения равны нулю, многоугольник вырожденный (отрезок), если все произведения одного знака - многоугольник выпуклый (при этом если все произведения положительные, то вершины обходятся против часовой стрелки, если все произведения отрицательны, то против часовой), если имеются произведения разных знаков, то многоугольник не является выпуклым.

Внутри функции используются элементы X[0],Y[0] для "замыкания" многоугольника, т.е. X[0]=X[n] и Y[0]=Y[n]. В результате получаем логическую переменную Result, которая истина, если многоугольник выпуклый, и ложь, если многоугольник не выпуклый или вырожденный.

Наверх

Построение выпуклой оболочки множества точек на плоскости.(мой метод) Скачать

Процедура строит выпуклую оболочку множества точек на плоскости, т.е. из множества точек, заданных координатами (xi,yi) выбираются те которые образуют выпуклый многоугольник, содержащий все множество точек.

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

На вход процедуры подаются массивы координат точек входящих в множество, на выходе получаем преобразованный массив координат (из них удаляются дублирующиеся точки) и массив Conv содержащий номера точек, которые являются вершинами искомого выпуклого многоугольника (естественно порядок следования точек важен!)

При работе процедуры вначале из набора удаляются дублирующиеся точки. На следующем шаге строится матрица A элементы которой ai j принимают значения 0 или 1, при этом ai j=1, если все точки исходного множества кроме точек с номерами i,j лежат по одну сторону от прямой, проходящей через точки с номерами i,j и ai j=0 в противном случае. Не трудно показать, что: Во-первых матрица A симметрична, и во-вторых любая строка (столбец) матрицы A содержит 0 либо 2 элемента отличных от нуля. Построив матрицу A переходим к непосредственному заполнению массива Conv, проследить этот процесс несложно рассмотрев блок-схему.

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

Наверх

Построение выпуклой оболочки множества точек на плоскости.(метод Грехема) Скачать

Процедура строит выпуклую оболочку множества точек на плоскости, т.е. из множества точек, заданных координатами (xi,yi) выбираются те которые образуют выпуклый многоугольник, содержащий все множество точек.

Письма с описанием этого алгоритма прислали мне сразу два человека Marsel и Нурий Т. Карачурин за что им большое спасибо.

Работа алгоритма начинается с выбора центра масс множества, т.е. точки с координатами:

    xs=(x1+ . . .+xn)/n
    ys=(y1+ . . .+yn)/n
а также точки заведомо принадлежащей оболочки, например точки с наименьшей координатой x (пусть ее номер l). Далее, каждой точке ставим в соответствие угол отмеренный от прямой проходящей через точки (xs,ys) и (xl,yl), и сортируем точки по величине этого угла.

Проходим все точки в порядке сортировки. Определяем лежит ли i+1 точка и центр масс по одну сторону от прямой проходящей через i и i+2 точки, если да то i+1 точка не содержится в наборе образующем выпуклую оболочку, и ее надо исключить из рассмотрения. Действуем так до тех пор пока не рассмотрим все последовательные тройки.

Несколько замечаний к алгоритму.

Алгоритм быстрее чем предыдущий метод получения выпуклой оболочки, но при этом не всегда корректно работает при малом колличестве исходных точек.

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

Также в алгоритме используется функция проверки лежат ли две точки по одну сторону от прямой., так что желательно скачать и ее тоже для рассмотрения алгоритма.

Как обычно для более подробного рассмотрения алгоритма отсылаю Вас к блок-схеме.

Наверх

Поиск пересечения двух выпуклых многоугольников. Скачать

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

Координаты вершин исходных многоугольников задаются в массивах ax,ay для первого и bx,by для второго результат помещается в массивы cx,cy при этом дополнительно на выходе получаем количество вершин результирующего многоугольника (переменная n), а так же номера "новых" вершин не входящих ни в один из исходных многоугольников (переменные k1,k2).

Вначале ищутся вершины первого многоугольника лежащие внутри второго многоугольника и наоборот вершины второго многоугольника лежащие внутри первого многоугольника. Надо заметить, что в силу выпуклости исходных фигур и в первом и во втором случаи вершины будут идти подряд поэтому достаточно найти номера первой и последней вершины обладающих указанными свойствами. Затем основываясь на результатах поиска заполняется массив вершин искомого многоугольника, на этом же этапе определяется существование дополнительных вершин и их номера. За подробностями отсылаю Вас к блок-схеме.

Процедура использует функции: проверки принадлежит ли точка многоугольнику и поиска пересечения отрезков.

Наверх


Библиотекa алгоритмов по программированию. Геометрия.
  • Проверка принадлежит ли точка прямой. Скачать
  • Проверка принадлежит ли точка плоскости. Скачать
  • Проверка лежат ли две точки по одну сторону от прямой. Скачать
  • Пересечение отрезков. Скачать
  • Положение точки относительно многоугольника. Скачать
  • Положение точки относительно выпуклого многоугольника. Скачать
  • Площадь многоугольника. Скачать
  • Триангуляция области на основе заданного набора точек. Скачать
  • Разбиение многоугольника на треугольники. Скачать

Проверка принадлежит ли точка прямой. Скачать

Функция проверяет принадлежит ли точка с координатами (x,y,z) прямой заданной точками (xli,yli,zli) i=1,2.. В данном случае прямую в пространстве можно задать параметрически при помощи следующей системы:

    x=xl1+t(xl2-xl1)
    y=yl1+t(yl2-yl1)
    z=zl1+t(zl2-zl1)
И точка принадлежит прямой, если система имеет непротиворечивое решение t. Проверкой этого и занимается функция.

Если одновременно выполнены следующие три условия

    xl1=xl2
    yl1=yl2
    zl1=zl2
то прямая вырождается в точку и работа функции не имеет смысла.
Наверх

Проверка принадлежит ли точка плоскости. Скачать

Функция проверяет принадлежит ли точка с координатами (x,y,z) плоскости заданной точками (xpi,ypi,zpi) i=1,2,3.. При этом три точки в пространcтве задают плоскость, если они попарно различны, и не лежат на одной прямой, для проверки последнего условия используется алгоритм из предыдущей задачи. Далее находим параметры a,b,c,d для задания плоскости уравнением:

    ax+by+cz=d, где
    a=(yp2-yp1)(zp3-zp1)-(yp3-yp1)(zp2-zp1);
    b=-(xp2-xp1)(zp3-zp1)+(xp3-xp1)(zp2-zp1);
    c=(xp2-xp1)(yp3-yp1)-(xp3-xp1)(yp2-yp1);
    d=xp1a+yp1b+zp1c
и проверяем удовлетворяет ли точка (x,y,z) полученому уравнению.
Наверх

Проверка лежат ли две точки по одну сторону от прямой. Скачать

Функция проверяет лежат ли точки с координатами (x1,y1) и (x2,y2) по одну сторону от прямой заданной точками (xl1,yl1) и (xl2,yl2) или нет. Да же нечего написать по этому поводу все и так ясно.

Наверх

Пересечение отрезков. Скачать

Процедура ищет пересечение двух отрезков заданных своими конечными точками. Первый отрезок: (x1(1),y1(1));(x2(1),y2(1)). Второй отрезок: (x1(2),y1(2));(x1(2),y1(2)). В результате может получится три варианта пересечения: точка, отрезок, пустое множество.

Прямая содержащая i-й отрезок задается при помощи уравнений:

    x=x1(i)+t(i)(x2(i)-x1(i))
    y=y1(i)+t(i)(y2(i)-y1(i))
при этом точка на прямой принадлежит отрезку, если t лежит внутри отрезка [0,1]. Следовательно, пересечением отрезков будет точка если существует решение (t(1),t(2)) системы:
    t(1)(x2(1)-x1(1))+t(2)(x1(2)-x2(2))=x1(2)-x1(1)
    t(1)(y2(1)-y1(1))+t(2)(y1(2)-y2(2))=y1(2)-y1(1)
и при этом и t(1) и t(2) лежат в отрезке [0,1]. Если хотя бы одно из t(i) не удовлетворяет этому условию, то пересечением отрезков будет пустое множество.

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

В результате работы процедуры, вид пересечения можно определить рассматривая переменную s, а именно: Если s=0, то пересечение является пустым множеством. Если s=1, то пересечение - точка и ее координаты находятся в переменных x,y. Если s=2, то пересечение отрезок и координаты его концов возращаются в переменных x11,y11;x12,y12.

Наверх

Положение точки относительно многоугольника. Скачать

Функция проверяет, лежит ли точка с координатами (x,y) внутри n-угольника (точнее, n-вершинника), заданного координатами вершин (xi,yi), i=1..n.

Опять надо заметить, что внутри функции используются элементы X[0],Y[0] для "замыкания" многоугольника, т.е. X[0]=X[n] и Y[0]=Y[n].

Наверх

Положение точки относительно выпуклого многоугольника. Скачать

Функция проверяет, лежит ли точка P с координатами (x,y) внутри выпуклого n-угольника, заданного координатами вершин Pi(xi,yi), i=1..n.

Принцип простой, если точка внутри выпуклого многоугольника, то sin углов Pi,P,Pi+1(с учетом порядка обхода) имеют один знак для всех i=1..n, если sin равен нулю, то точка лежит на стороне Pi,Pi+1.

Наверх

Площадь многоугольника. Скачать

Если координаты вершин n-угольника равны (xi,yi), i=1..n, то площадь многоугольника может быть вычислена по формуле
где (x0,y0)=(xn,yn).

Отметим, что площадь фигуры заданной вершинами существенно зависит от порядка, в котором заданы вершины.

Наверх

Триангуляция области на основе заданного набора точек. Скачать

Пусть на плоскости задан набор из n точек своими координатами (x[i],y[i]), i=1,...,n. Процедура осуществляет разбиение области на треугольники, при этом разбиение области удовлетворяет двум условиям: 1) область полностью покрыта непересекающимися треугольниками с вершинами в узловых точках; 2) любой выпуклый четырехугольник разбивается по кратчайшей диагонали.

Выполенение этих двух условий позволяет провести "хорошую" интерполяцию функцию, которая заданна значениями в узловых точках.

Алгоритм мне прислал Michael V. Pakki. Я привожу его практически без изменений, единственное усовершенствование, которое я себе позволил, это избавился от рекурсии, итак:
ШАГ 1 Находим такие две точки P1 и P2, чтобы все остальные точки лежали по одну сторону от прямой P1P2;
ШАГ 2 Вводим фиктивную точку P0, лежащую по другую сторону от прямой P1P2;
ШАГ 3 Помещаем на стек номера точек P1,P2,P0.
ШАГ 4 Снимаем со стека точки P1,P2,P3. Ищем такую точку M, разделенную от точки P3 прямой P1P2, чтобы угол P1_M_P2 был максимальный; если такой точки нет, то переход на ШАГ 6;
ШАГ 5 Сравниваем треугольник P1MP2 с найденными ранее; если совпадения не обнаружено, то запоминаем треугольник P1MP2 и помещаем на стек номера точек P1,M,P2 и P2,M,P1;
ШАГ 6 Если стек не пуст возвращаемся к ШАГУ 4;

Отметим несколько обстоятельств. Первое: на стек помещаются упорядоченные тройки точек. Второе: процедура использует, описанный ранее алгоритм проверки лежат ли точки по разные стороны от прямой(в процедуре он для краткости вызывается как IOS).

На выходе получаем в переменной nt количество треугольников, сами треугольники (заданные номерами вершин в исходном массиве) содержаться в массиве tr.

Наверх

Разбиение многоугольника на треугольники. Скачать

Алгоритм производит разбиение произвольного(в смысле выпуклости) многоугольника на треугольники.

Пусть некоторый многоугольник задан набором координат своих вершин P0=(x0,y0);P1=(x1,y1);...;Pn=(xn,yn) при этом будем полагать, что вершины занумерованы по часовой стрелке. В случае если многоугольник выпуклый, задача нахождения разбиения тривиальна, можно взять набор диагоналей выходящих из какой-либо вершины.

В случае невыпуклого многоугольника задача существенно усложняется. Будем действовать следующим образом, на каждом шаге алгоритма будем отсекать один треугольник Pi-1,Pi,Pi+1 и исключать вершину Pi из дальнейшего рассмотрения. Чтобы определить можно ли использовать диагональ Pi-1Pi+1 для отсечения треугольника, будем вначале проверять знак sin угла Pi-1,Pi,Pi+1 учитывая при этом последовательность обхода вершин, так для многоугольника изображенного на рисунке при i=0,1,2,3,4,7 sin будет отрицателен, а при i=5,6 положителен.

Далее найдя i для которой sin отрицателен, проверем не входят ли в треугольник Pi-1,Pi,Pi+1, какие-либо точки из многоугольника (естественно кроме i-1,i,i+1), если нет значит отсечем этот треугольник, иначе ищем следующую вершину с отрицательным sin и проверяем ее. Проверку принадлежности точки треугольнику можно осуществить одним из алгоритмов рассмотренных на этой странице переписав его для частного случае треугольника.

Алгоритм можно оптимизировать по скорости введя, например массив, содержащий знаки sin, и перевычисляя на каждом шаге только i - й знак. Возможны и другие усовершенствования.

Теперь немного о блок-схеме реализующей алгоритм. Номер последней вершины передается в переменной n (всего будет соответственно n+1 вершина), координаты в массивах x и y, полученое разбиение помещается в массив tr, tr[1..3][i] содержит номера вершин исходного многоугольника, составляющие i-ый треугольник. Внутри блок-схемы дополнительно используются массив t для хранения вершин промежуточных многоугольников.


Библиотекa алгоритмов по программированию. Графика.
  • Алгоритм Брезенхема генерации 4-х связной развертки отрезка. Скачать
  • Алгоритм Брезенхема генерации 8-ми связной развертки отрезка. Скачать
  • Алгоритм генерации развертки выпуклого многоугольника (метод построчного сканирования). Скачать
  • Алгоритм заполнения произвольной области с затравкой. Скачать
  • Алгоритм Брезенхема генерации развертки окружности. Скачать
  • Алгоритм Сазерленда-Кохена, отсечение отрезка прямоугольным окном. Скачать
  • Алгоритм Лианга-Барски, отсечение отрезка прямоугольным окном. Скачать

Алгоритм Брезенхема генерации 4-х связной развертки отрезка. Скачать

Алгоритм генерирует 4-х связную развертку отрезка, заданного координатами концов (x1,y1),(x2,y2). В качестве выходного устройства используется массив Screen: array [0.. ScW-1,0..ScH-1] of TColor, в случае реализации для конкретного устройства, присвоение цвета Color элементу массива Screen[i,j] следует заменить соответствующей процедурой "закраски" точки с координатами (i,j) устройства.

Свойство 4-х связности представления, допускает изменения только одной координаты (вертикальной или горизонтальной) текущей точки и не более чем на единицу. "Закраска" точек растрового представления отрезка происходит в цикле.

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

Наверх

Алгоритм Брезенхема генерации 8-ми связной развертки отрезка. Скачать

Алгоритм генерирует 4-х связную развертку отрезка, заданного координатами концов (x1,y1),(x2,y2). В качестве выходного устройства используется массив Screen: array [0.. ScW-1,0..ScH-1] of TColor, в случае реализации для конкретного устройства, присвоение цвета Color элементу массива Screen[i,j] следует заменить соответствующей процедурой "закраски" точки с координатами (i,j) устройства.

Свойство 8-ми связности представления, допускает изменения сразу обеих координат (и вертикальной, и горизонтальной) текущей точки но не более чем на единицу. "Закраска" точек растрового представления отрезка происходит в цикле.

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

Наверх

Алгоритм генерации развертки выпуклого многоугольника (метод построчного сканирования). Скачать

Алгоритм генерации растрового представления выпуклого многоугольника заданного набором вершин (xi,yi),i=0..n-1. Многоугольник закрашивается цветом Color.В качестве выходного устройства используется массив Screen:array[0..ScW-1,0..ScH-1] of TColor.

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

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

Наверх

Алгоритм заполнения произвольной области с затравкой. Скачать

Алгоритм закрашивает цветом IC область на экране (в нашем случае в качестве выходного устройства используется массив Screen:array[0..ScW-1,0..ScH-1] of TColor.). Область должна быть ограничена, некоторой линией цвет которой храниться в переменной BC. В качестве затравочной точки, в алгоритм передаются координаты некоторой внутренней точки области (x0,y0).

Алгоритм использует идею, примененную нами в алгоритме построчного сканирования. Заметим, что на каждой строке множество точек подлежащих закраске, состоит из интервалов, принадлежащих внутренности области. Эти интервалы отделены друг от друга интервалами из точек, принадлежащих границе или внешности области. Кроме того, если набор точек образует связный интервал, принадлежащий внутренней части области, то точки над и под этим интервалом либо являются граничными, либо принадлежат внутренней части области. Последние могут служить затравочными для строк лежащих выше и ниже рассматриваемой строки. Суммируя все это, получаем такой алгоритм:

  1. Поместим затравочную точку на стек.
  2. Извлекаем координаты точки с вершины стека в переменные (x,y)
  3. Заполняем максимально возможный интервал, в котором находится точка, вправо и влево вплоть до достижения граничных точек.
  4. Запоминаем крайнюю левую xl и крайнюю правую xr абсциссы заполненного интервала.
  5. В соседних строках над и под интервалом (xl,xr) находим незаполненные к настоящему моменту внутренние точки области, которые объединены в интервалы, а в правый конец каждого такого интервала помещаем на стек.
  6. Если стек не пуст, то переходим к пункту 3.

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

Наверх

Алгоритм Брезенхема генерации развертки окружности. Скачать

Алгоритм генерирует растровую развертку окружности заданной координатами центра (xc,yc) и радиусом r. Его работа достаточно подробно описана в статье алгоритма растровой графики (часть вторая), поэтому здесь останавливаться на этом не буду, отмечу только, что алгоритм использует только целочисленную арифметику, за счет чего удается получить высокую скорость работы.

Наверх

Алгоритм Сазерленда-Кохена, отсечение отрезка прямоугольным окном. Скачать

Часто возникает необходимость отсечь выводимое изображение по границе области, область обычно имеет вид прямоугольника. Данный алгоритм позволяет для некоторого отрезка заданного координатами начала и конца((x1,y1),(x2,y2)), и некоторой прямоугольной области, определить координаты начала и конца части отрезка лежащей внутри области.

Алгоритм разделяет плоскость на 9 частей, и каждой из них ставит в соответствие 4-х битный код следующим образом: включенный бит 0 означает, что точка лежит левее прямоугольника, включенный бит 1 означает, что точка лежит правее прямоугольника, включенный бит 2 означает, что точка лежит выше прямоугольника, включенный бит 3 означает, что точка лежит ниже прямоугольника, Таким образом получаем:

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

Наверх

Алгоритм Лианга-Барски, отсечение отрезка прямоугольным окном. Скачать

Данный алгоритм решает ту же задачу, что и предыдущий, но используя другую идею. Сравнение по скорости я не проводил, если кто-то займется буду рад опубликовать результаты. Я взял алгоритм из книги "Основные алгоритмы компьютерной графики", автор П.В.Вельтмандер, книжка есть в электронном виде - http://ermak.cs.nstu.ru/kg_rivs/kg01.htm, но поскольку она то появляется, то исчезает, хочу сразу предупредить, что если Вы не смогли ничего найти по указанной ссылке, ко мне не обращайтеся, я ничем не смогу помочь.

Итак вначале об обозначениях (x0,y0);(x1,y1) - координаты соответственно начала и конца отрезка. (XS1,YS1);(XS2,YS2) - координаты соответственно левого-верхнего и правого-нижнего углов "экрана"(- области по которой производим отсечения).

Итак идея алгоритма. Так как область отсечения является прямоугольником, то ее можно представить в виде неравенств.

    XS1 ≤ x ≤ XS2,
    YS1 ≤ y ≤ YS2
Представим наш исходный отрезок в параметрическом виде.
    x=x0+dx t,
    y=y0+dy t, 0 ≤ t ≤ 1
здесь dx=x1-x0 , dy=y1-y0, при этом в случае когда t изменяется вне отрезка (0,1), получаем координаты точки лежащей на прямой содержащей исходный отрезок, но вне самого отрезка. Подставим это представление в неравенства, определющие область отсечения. Получаем
    -dx·t ≤ x0 - XS1 ,
    dx·t ≤ XS2 - x0 ,
    -dy·t ≤ y0 - YS1 ,
    dy·t ≤ YS2 - y0 .
эти неравенства задают значения параметра t, для которых точки прямой содержащей отрезок лежат внутри области отсечения. Каждое из неравенств задает ограничение одной из границ экрана продолженной до бесконечности. Нетрудно заметить общий вид неравенств.
    Pit ≤ Qi , i=1,2,3,4.
при этом
    P1=-dx; Q1=x0 -XS1
    P2=dx; Q2=XS2-x0
    P3=-dy; Q3=y0 -YS1
    P4=dy; Q4=YS2-y0

Решение неравенства зависит от знака Pi, а именно: если Pi < 0, то получаем ограничение на параметр t снизу. если Pi > 0, то получаем ограничение на параметр t сверху. если Pi = 0, то все зависит от знака Qi: если Qi < 0, то решений нет и делаем вывод, что отрезок не видим, если Qi ≥ 0, то любое t является решением и данное неравенство можно не рассматривать.

Таким образом решив систему получим ограничения на t. Следует учесть, что для отрезка диапозон изменения параметра ограничен, а именно 0 ≤ t ≤ 1. И наконец если нашли решение системы с учетом пары ограничений для отрезка можем используя параметрическое представление получить координаты концов точек отсеченного отрезка.

Непосредственно алгоритм будет выглядеть следующим образом: Зададимся величинами t0=0,t1=1 Для i=1,2,3,4 изменим в соответствии со знаком Pi нижнее (t0) или верхнее (t1) ограничение на параметр, или в случае если Pi=0 и Qi < 0, то отрезок не видим и выйдем из цикла. Если отрезок видим вычислим координаты начала и конца видимой части отрезка, используя параметрическое задание.

Алгоритм можно посмотреть по блок-схеме.


Библиотекa алгоритмов по программированию. Диофантовы уравнения.
  • Введение.
  • Диофантово уравнение ax+by=c. Скачать
  • Диофантово уравнение x2+y2=d2. Скачать

Введение.

Эта страница появилась благодаря Казакову Ю.В., который интересуется именно этой тематекой, и я надеюсь пришлет еще не мало интересных алгоритмов. В качестве некоторой вводной, публикую его статью Диофантова задача о «рациональном кубоиде». Надеюсь, что она Вас заинтересует, если да пишите Юрию Казакову, а я буду рад, если пришлете мне алгоритмы, которые появяться в результате Ваших работ.

Наверх

Диофантово уравнение ax+by=c. Скачать

Пусть задано диофантово уравнение:

    ax+by=c, где a,b,c- целые

Его частное решение можно найти следующим образом: Находим наибольший общий делитель чисел a и b - НОД(a,b) и запомним частные qi (см. НОД) деления чисел |a| и |b| по алгоритму Евклида. Если НОД(a,b)=c=0, то уравнению удовлетворяют любые целые x и y. Если НОД(a,b) не равен 0 и c на НОД(a,b) не делится, то уравнение не имеет решения. Иначе производим сокращение коэффициентов a,b,c и получаем уравнение того же вида со взаимно простыми a,b,c. Далее находим u и v, такие, что |a|u+|b|v=1 умножив u и v на csgn(a) и csgn(b) соответственно, находим частное решение уравнения x0,y0. Общее решение тогда имеет вид x=x0+kb, y=y0-ka.

Процедура имеет 3 выходных параметра это s типа string для описания ситуации с решением (есть, нет, все целые и т.п.), и частные решения x0,y0 типа integer.

Наверх

Диофантово уравнение x2+y2=d2. Скачать

Алгоритм прислан Казаковым Ю.В..

Необходимо найти все разложения числа d2 на сумму двух квадратов x2 и y2. x и y - положительные целые числа больше 0. ( Альтернативная формулировка. Найти все прямоугольные треугольники, имеющие целочисленные стороны и длину гипотенузы равную d).

Условие существования разложения d2 на сумму двух целых квадратов требует, чтобы в разложении числа d на множители присутствовало, хотя бы одно простое число вида (4*t+1). То есть должно иметь место представление:
где множитель s не содержит простых сомножителей вида (4*t+1). Количество решений уравнения будет зависить от ki, но не будет зависить от числа s, так как если существует набор пар при s=1, то естественно будет существовать набор и для любого другого s, только каждый элемент пары разложения будут умножен на s. Заметим, что для существования разложения необходимо найти три числа (w,r,q), такие что
    d=w(r2+q2)
тогда
    x=w(r2-q2), y=2wrq.

Таким образом находяться все пары (x,y). Заметим что для пары (x,y) симметричная ей пара (y,x) так же удовлетворяет уравнению, но мы ее в алгоритме на выход не доставляем.

Алгоритм использует выражение вида trunc(a)=a для определения является ли число a целым.


Библиотекa алгоритмов по программированию. Интегралы.
  • Интегрирование методом прямоугольников с оценкой точности. Скачать
  • Интегрирование методом трапеций с оценкой точности. Скачать
  • Интегрирование методом Симпсона с оценкой точности. Скачать
  • Вычисление интеграла методом Симпсона от функции, заданой таблично. Скачать
  • Вычисление интеграла методом Ромберга. Скачать
  • Вычисление криволинейного интеграла в комплексной области. Скачать
  • Вычисление интеграла по двумерной области методом Монте-Карло. Скачать

Интегрирование методом прямоугольников с оценкой точности. Скачать

Собственное значение определенного интеграла
находится методом прямоугольников. Отрезок [a,b] разбивается на n частей x0=a,x1=a+h, . . . ,xn=b с шагом h=(b-a)/n.

На каждом отрезке [xi,xi+1] вычисляется значения интеграла по формуле прямоугольников, таким образом:

Затем количество точек разбиения удваивается и производится оценка точности вычислений:

    Rn=|S2n-Sn|

Если Rn > e, то колличество точек разбиения удваивается.

Наверх

Интегрирование методом трапеций с оценкой точности. Скачать

Собственное значение определенного интеграла
находится методом трапеций. Отрезок [a,b] разбивается на n частей x0=a,x1=a+h, . . . ,xn=b с шагом h=(b-a)/n.

На каждом отрезке [xi,xi+1] вычисляется значения интеграла по формуле трапеций, таким образом:

Затем количество точек разбиения удваивается и производится оценка точности вычислений:

    Rn=|S2n-Sn|/3

Если Rn > e, то колличество точек разбиения удваивается. Для уменьшения времени, затрачиваемого на вычисления в алгоритме при получении S2n используется формула:
Наверх

Интегрирование методом Симпсона с оценкой точности. Скачать

Собственное значение определенного интеграла
находится методом Симпсона (парабол). Отрезок [a,b] разбивается на n=2m частей x0=a,x1=a+h, . . . ,xn=b с шагом h=(b-a)/n.

Вычисляются значения yi=F(xi) функции в точках xi и находится значение интеграла по формуле Симпсона:

    S=Sn+Rn,
где

Затем количество точек разбиения удваивается и производится оценка точности вычислений:

    Rn=|S2n-Sn|/15

Если Rn > e, то колличество точек разбиения удваивается. Значение суммы 2(y1+y2+. . . +y2m-1) сохраняются, поэтому для вычисления интеграла при удвоенния количества точек разбиения требуется вычислять значения yi лишь в новых точках разбиения.

Наверх

Вычисление интеграла методом Симпсона от функции, заданой таблично. Скачать

Если заданы значения функции F(x) на интервале [a,b] y0,y1, . . ., yn в равностоящих точках и n четно, то приближенное значение интеграла вычисляется по формуле:

       =
Наверх

Вычисление интеграла методом Ромберга. Скачать

Задается значение n (на первом шаге n=2) и вычисляется приближенное значение интеграла по формуле трапеций (деленное на (b-a)):

Затем число n удваивается (k раз). Каждый раз значение S(1)n запоминается в массиве T[i].

Погрешность метода имеет порядок 2n+1 (e=1E-(2n+1))

Наверх

Вычисление криволинейного интеграла в комплексной области. Скачать

Процедура вычисляет значение криволинейного интеграла для комплексной переменной z.
с помощью конечной суммы Римана-Стильтьеса.

Процедура использует функции F1(x,y) и F2(x,y) как действительную и мнимую часть функции F(x), где x,y - действительная и мнимая часть аргумента, а функции Z1(x,y) и Z2(x,y) как действительную и мнимую часть функции z(t) определяющую контур по которому происходит интегрирование. И на выходе получаем значения s1,s2 - действительную и мнимую часть значения интеграла.

Наверх

Вычисление интеграла по двумерной области методом Монте-Карло. Скачать

Алгоритм мне прислал Nick Maslov. Функция вычисляет интеграл вида:
Мы будем считать, что область D вписана в квадрат [ax,bx]*[ay,by], тогда полагаем:
и используем для приближенного вычисления интеграла формулу
где (xi,yi) пара независимых равномерно распределенных случайных величин.

На вход функции подается параметры ax,ay,bx,by, которые определяют квадрат [ax,bx]*[ay,by], на плоскости в который вписана область D. В блок-схеме предполагается, что определена функция F(x,y) интеграл от которой необходимо вычислить, а так же функция D(x,y), которая принимает значение истина в случае, когда точка (x,y) принадлежит области интегрирования D и ложь в противном случае.

Параметр n опеределяет кол-во рассматриваемых точек и соответственно влияет на точность вычисления интеграла, но не следует брать его слишком большим иначе придется изменить алгоритм, так как может произойти переполнение при суммировании. Алгоритм нетрудно обобщить для вычисления интегралов от многомерных функций.

Алгоритмы получение случайных величин можно посмотреть здесь. В блок-схеме используется вызов функции Random для получения независимой равномерно распределенной случайной велечины из отрезка [0,1].


Библиотекa алгоритмов по программированию. Интегральные уравнения.
  • Введение.
  • Линейное уравнение Вольтерра второго рода. Скачать
  • Уравнение Вольтерра первого рода. Скачать
  • Уравнение Фредгольма второго рода. Скачать

Введение.

Интегральными уравнениями называются функциональные уравнения, содержащие интегральные преобразования над неизвестной функцией y(x). Интегральное уравнение называется однородным, если ay(x) есть решение уравнения для произвольного a. Линейное интегральное уравнение в общем виде может быть представлено:
где k(x,s)- ядро интегрального преобразования, правая часть f(x) и g(x) являются заданными функциями, a - параметр уравнения. Область интегрирования V может быть фиксированной (интегральные уравнения типа фредгольмовых) или переменной (интегралные уравнения типа вольтерровых).

Линейное интегральное уравнение первого рода получается при g(x)=0, a=-1 и имеет вид:

Однородное линейное интегральное уравнение второго рода получается при f(x)=0,g(x)=1 и имеет вид:

Неоднородное интегральное уравнение второго рода получается при g(x)=1 и имеет вид

Уравнения вида
являются неоднородными.
Наверх

Линейное уравнение Вольтерра второго рода. Скачать

Линейное интегральное уравнение Вольтера второго рода имеет вид:

Причем независимые переменные x,s изменяются на промежутке [a,b], ядро k(x,s) непрерывно внутри и на сторонах треугольника, ограниченного прямыми s=a,x=b,x=s. Функция f(x) на [a,b] непрерывна.

Уравнение данного типа решается с помощью метода квадратурных формул, суть которого состоит в замене интегрального уравнения апроксимирующей системой алгебраических уравнений относительно дискретных значений искомой функции и решении этой системы. В основе такой замены лежит приблежение интеграла квадратурными формулами. Применение формулы трапеций с постоянным шагои h приводит к рекурентной формуле:
где i=2,3,...,1+(b-a)/h, xi=a+(i-1)/h, Aj=1 при j > 1 и Aj=0.5 при j=1.
Наверх

Уравнение Вольтерра первого рода. Скачать

Линейное интегральное уравнение Вольтерра первого рода имеет вид:

Если k(a,a) не равно 0, f(a)=0 и если функции f(x),k(x,s) имеют производные f'(x),k'x(x,s), непрерывные в интервале (a,b), заключенном в интервале интегрирования, внутри которого k(x,s) не обращается в нуль, то уравнение Вольтерра первого рода допускает в интервале (a,b) непрерывное и единственное решение.

Представленная процедура решает уравнение методом квадратурных формул. Вычисление интеграла производится по формуле трапеций с постоянным шагом h:
где xi=a+(i-1)h, i=2,3,..., Aj=1 при j > 1 и Aj=0.5 при j=1.
Наверх

Уравнение Фредгольма второго рода. Скачать

Линейное интегральное неоднородное уравнение Фредгольма второго рода имеет вид:
где ядро определено в квадрате V=[a,b]*[a,b]. Кроме того, полагается, что ядро непрерывно в V. При [image] =1, используя квадратурную формулу трапеций с постоянным шагом h, получим:
где n=(b-a)/h+1 - целое, Aj=1 при j не равном 1 или n и Aj=0.5 при j=1 или n.

В процедуре используется переменная S. S=0, если полученная система алгебраических уравнений не определена и численное решение уравнения не найдено. S=1, тогда численное решение содержится в массиве y.


Библиотекa алгоритмов по программированию. Интерполяция функций.
  • Полином Лагранжа по Эйтекену. Скачать
  • Рациональная интерполяция с помощью непрерывных дробей. Скачать
  • Интерполяция по Ньютону. Скачать
  • Коэффициенты тригонометрического полинома. Скачать
  • Интерполяция функции кубическими сплайнами. Скачать

Полином Лагранжа по Эйтекену. Скачать

Пусть на отрезке [a,b] дано n+1 значение функции Fi=F(xi) в n+1 различных точках: x0,x1, . . . , xn. Тогда полином степени не выше n, имеющий в заданных узлах значение Fi, есть полином Лагранжа:

Вычисление значений Ln(x) по данной формуле осуществляется по итерационной формуле Эйтекена. Начальные значения Fi теряются. Интервалы [xi,xi+1] могут быть неравными.

Наверх

Рациональная интерполяция с помощью непрерывных дробей. Скачать

Если задано m значений функции Fi=F(xi) в m точках x1,x2, . . . , xm, то F(x) может быть определено по формуле:

Эта непрерывная дробь может быть представлена в виде рациональной функции:
где l не превосходит m1=trunc(m/2).
Наверх

Интерполяция по Ньютону. Скачать

Пусть на отрезке [a,b] задано n+1 значение аргумента:x0=a,x1, . . . , xn=b и n+1 значение функции yi=y(xi). Тогда интерполяционный многочлен степени n в форме Ньютона может быть построен по следующим формулам:
где
    N0(x)=1,
    Ni(x)=(x-x0)(x-x1). . .(x-xi-1)(i=1,..,n),
    Ci=[x0,x1,. . .,xi],
    [xi]=yi(i=0,n),
    [x0,x1,. . .,xi]=([x1,. . .,xi]-[x0,. . .,xi-1])/(xi-x0).
Выражение [x0,x1,. . .,xi] называется разделенной разностью.
Наверх

Коэффициенты тригонометрического полинома. Скачать

Пусть на промежутке [image] задано k значений Fi некоторой функции F(x) в равноотстоящих точках [image], где i=0,1,. . . ,k. В этом случае функцию F(x) целесообразно интерполировать тригонометрическим полиномом:
причем Qn(xi)=Fi=F(xi).

Процедура вычисляет коэфициенты ai , bi i=1,..,k. В дальнейшем для вычисления значения полученного полинома в точке x можно воспользоваться алгоритмом Сумма ряда Фурье.

Наверх

Интерполяция функции кубическими сплайнами. Скачать

Пусть заданы точки x1,x2,...,xn и соответствующие им значения y1,y2,...,yn функции f(x). На каждом из отрезков [xi,xi+1], i=1,2,...,n-1 функцию приближаем при помощи полинома степени 3, вида:

    S(x)=yi+c1 i(x-xi)+c2 i(x-xi)2+c3 i(x-xi)3, xi< x <xi+1

Для вычисления коэффициентов c1 i , c2 i , c3 i , i=1,2,...,n-1 решается система линейных уравнений, построенная из условия непрерывности производной S'(x) в узлах сетки и дополнительных краевых условий на вторую производную, которые имеют вид:

    2 * S''1 + b1 * S''2 = b2
    b3 * S''N - 1 + 2 * S''N = b4
здесь возможны два случая. Случай первый, когда известны значения первой производной в краевых точках (y'1=y'(x1), y'n=y'(xn)), тогда следует положить:
    b1=1,	b2=(6/(x2-x1))*((y2- y1)/(x2-x1)-y'1),
    b3=1,	b4=(6/(xn-xn-1))*(y'n-(yn-yn-1)/(xn-xn-1))
Случай второй, когда известны значения второй производной (y''1=y''(x1), y''n=y''(xn)), тогда полагаем:
    b1=0,	b2=2*y''1
    b3=0,	b4=2*y''N

Отметим, что точки xi должны быть отсортированы по возрастанию.

На вход алгоритма подаются массивы x, y на выходе получаем матрицу c:array[1..3,1..n]. Чтобы получить значение интерполируемой функции f в точке x необходимо в начале определить какому из отрезков разбиения она принадлежит (т.е. найти такое i, что xi< x <xi+1) и затем воспользоваться формулой S(x) с сответствующими c1 i , c2 i , c3 i, yi.

Алгоритм взят с сайта численного анализа, который я еще раз рекомендую всем кто сталкивается с задачами численного анализа. Так же не плохая глава по сплайнам есть в книге Каханер Д., Моулер К., Нэш С. "Численные методы и программное обеспечение".


Библиотекa алгоритмов по программированию. Комбинаторика.
  • Вычисление факториала. Скачать
  • Нахождение числа сочетаний [image]. Скачать
  • Перестановки. Скачать
  • Задача о коммивояжере(методом комбинаторики). Скачать
  • Выборки из n элементов по m. Скачать
  • Выборки из n элементов по m (2-й способ). Скачать
  • Решение задачи о рюкзаке. Скачать

Вычисление факториала. Скачать

Этот алгоритм я сделал одним из первых когда пробовал "Редактор блок-схем" поэтому и сюда его добавил. Хотя особой необходимости в нем нет.

Наверх

Нахождение числа сочетаний . Скачать

Функция находит число сочетаний из n элементов по m:

Вычисления проводятся по рекурентной формуле:
Наверх

Перестановки. Скачать

Процедура находит перестановку следующую за данной в лексикографическом порядке. Начальная перестановка задается в массиве X туда же после работы процедуры помещается найденная перестановка. Переменная END равна истине, если на вход подана перестановка являющаяся последней при лексикографическом упорядочивании. Таким образом чтобы получить все перестановки n - чисел надо инициализировать массив X значениями 1,2,. . ., n и последовательно вызывать процедуру до тех пор пока значение переменной END не окажется равным истине.

Заметим, что количество перестановок из n чисел будет равно факториалу числа n.

Наверх

Задача о коммивояжере (методом комбинаторики). Скачать

Процедура находит решение задачи о коммивояжере, используя предыдущий алгоритм для получения всех возможных путей. На вход процедуры подается матрица цен на билеты W при этом, если нет пути из одного города в другой, то соответствующий элемент матрицы равен 10Е6. Матрица не обязательно симметричная. В переменной f находится номер города из которого коммивояжер начинает путешествие. Затем используя алгоритм получения перестановок перебираются все возможные пути (с началом в городе f) и вычисляется их цена и таким образом находится путь минимальный по затратам, который помещается в массив x.

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

Наверх

Выборки из n элементов по m. Скачать

Процедура находит выборку следующую за данной в лексикографическом порядке. Начальная выборка задается в массиве X туда же после работы процедуры помещается найденная выборка. Переменная END равна истине, если на вход подана выборка являющаяся последней при лексикографическом упорядочивании. Таким образом чтобы получить все выборки - надо инициализировать массив X значениями 1,2,. . ., m и последовательно вызывать процедуру до тех пор пока значение переменной END не окажется равным истине. Числа внутри выборки, поданной на вход процедуры, должны быть упорядочены по возрастанию.

Заметим, что количество выборок m из n равно числу сочетаний m из n и вычисляется с помощью этого алгоритма.

Наверх

Выборки из n элементов по m (2-й способ). Скачать

Процедура находит все выборки из n элементов по m. Этот алгоритм мне прислал Александр, и он основан на подходе отличном от того что применялся в предыдущем алгоритме.

Все полученные выборки будут помещаться в массив X: array [1..m,1..CMN] of integer. Размер СMN соответствует количеству выборок m из n и равно числу сочетаний m из n, которое вычисляется с помощью этого алгоритма.

Суть алгоритма в следующем. Выборку можно представить в виде набора длины n 0 и 1, при этом если элемент с номером k участвует в выборке, то в наборе ему соответствует 1, если не участвует, то 0. Такой набор представляет некоторое целое число a ≤ 2n-1в двоичной системе. Мы будем перебирать целые числа в возрастающем порядке и если у них в двоичном представлении ровно m единиц помещать соответствующую выборку в массив X. Осталось определиться с пределами внутри которых надо перебирать целые числа, но это достаточно очевидно. Начать надо с числа в двоичном представлении которого первые m мест занимают единицы 1...10...02=2m-1, а закончить числом 0...01...12=2n-2n-m.

В блок-схеме используется оператор a shr b для обозначения сдвига вправо битового представления числа a на b бит. И соответственно оператор a shl b для сдвига в влево.

Очевидны, некоторые проблемы связанные с данным алгоритмом, во-первых, n ограничено разрядностью представления целых чисел в компьютере, во-вторых, придется перебирать слишком много явно лишних вариантов, что скажется на скоросте работы. Но с другой стороны, прозрачность принципа работы алгоритма возможно компенсирует эти недостатки.

Наверх

Решение задачи о рюкзаке. Скачать

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

В результате работы алгоритма получаем переменную L равную количеству найденых последовательностей. Сами последовательности помещаются в масcив строк Results, каждая строка представляет номера элементов массива A, разделенные запятыми.


Библиотекa алгоритмов по программированию. Комплексный анализ.
  • Умножение комплексных чисел.
  • Деление комплексных чисел. Скачать
  • Корни n-ой степени комплексного числа. Скачать
  • Действительная степень комплексного числа. Скачать
  • Комплексная степень комплексного числа. Скачать

Умножение комплексных чисел.

Произведение двух комплексных чисел вычисляется по формуле:

    e+if=(a+ib)(c+id)=(ac-bd)+i(ad+bc)

При всем моем желании привести библиотеку к некой единой структуре и каждому алгоритму предоопределять блок-схему, для данной позиции рисование блок-схемы кажется мне просто издевательством.

Наверх

Деление комплексных чисел. Скачать

Процедура находит частное от деления двух комплексных чисел:

Вычисления проводятся по формулам:
.
Наверх

Корни n-ой степени комплексного числа. Скачать

Процедура вычисляет все n корней комплексного числа z=r+iu:

Вычисления производятся по формулам:
Наверх

Действительная степень комплексного числа. Скачать

Действительная степень комплексного числа определяется соотношением:

    zw=(x+iy)w=rw(cos(wa)+i sin(wa))
где
a - главное значение аргумента z.

Если w=1/n, то процедура вычисляет главное значение корня n -ой степени из z.

Наверх

Комплексная степень комплексного числа. Скачать

Пусть заданы комплексные числа w и z:
- главное значение аргумента числа z, n- колличество оборотов.

Тогда

Процедура производит вычисления по данной формуле.


Библиотекa алгоритмов по программированию. Криптография.
  • Гаммирование. Скачать
  • Алгоритм Blowfish. Скачать
  • Алгоритм дешифрации для архиватора zip. Скачать
  • Алгоритм подсчета CRC32. Скачать

Гаммирование. Скачать

Алгоритм предлагает простейший способ шифрования/дешифрования данных - гаммирование - наложение/снятие на открытые/зашифрованные данные криптографической гаммы, то есть некоторой последовательности элементов данных. Данный алгоритм в качестве гаммы использует ключ задаваемый в массиве Key. Для наложения гаммы при зашифровании и ее снятия при расшифровании должны использоваться взаимно обратные бинарные операции, в данном алгоритме в качестве такой операции используется "Исключающие ИЛИ" (побитовое сложение по модулю 2).

Для шифрования/дешифрования используется один и тот же алгоритм.

Наверх

Алгоритм Blowfish. Скачать

Blowfish это 64-битный шифр разработанный Шнайером в 1993 году. Это шифр Файстела, и каждый проход состоит из зависимой от ключа перестановки и зависимой от ключа с данными замены. Все действия основаны на операциях XOR и прибавлениях к 32-битным словам. Ключ может иметь длину до 72 байт (остальная часть ключа в данной реализации не влияет на работу).

Процедура шифрования(дешифрования) состоит из двух этапов: 1) Инициализация массивов P и S при помощи ключа. 2) Непосредственно шифрование(дешифрование).

Инициализация массивов P и S реализована в блок-схеме initBlowfish.bls. На вход процедуры подается массив Key байтов ключа, размер массива Key передается в переменной n. В процедуре используется массив случайных величин RandomSeed, каждый из элементов которого имеет тип LongInt(= array [0..3] of byte). Следует заметить, что массив RandomSeed должен быть задан заранее и остается неизменным при шифровании(дешифровании). Использование массива RandomSeed не является обязательным, возможна инициализация массивов P и S случайными величинами напрямую.

Непосредственно шифрование осуществляется процедурой реализованной блок-схемой EncryptBlowfish.bls. Шифруются последовательно пары элементов Xl,Xr типа LongInt. При шифровке изменяется также содержание массивов P и S.

Операция дешифровки реализована в блок-схеме DecryptBlowfish.bls. Эта процедура аналогично дешифрует последовательно пары элементов Xl,Xr типа LongInt.

Таким образом, чтобы зашифровать/расшифровать некий массив 32-х битных величин, надо вначале инициализировать массивы (InitBlowfish) P и S, а затем последовательно подавать на вход процедуры шифровки(EncryptBlowfish)/дешифровки(DecryptBlowfish) пары элементов, при этом по ходу работы алгоритма шифрации/дешифрации массивы P и S будут постоянно изменяться.

Если данные блок-схемы напрямую экспортировать в Паскаль, они составят рабочий модуль шифровки/дешифровки на основе алгоритма Blowfish, но естественно не дадут слишком хороший результат по скорости работы. Желательно провести оптимизацию алгоритмов используя тот факт, что работа осуществляется с 32-битными величинами и следовательно можно существенно оптимизировать процедуры для машин c процессорами типа Pentium. Хотя следует заметить, что использование данных процедур напрямую, не вызвало видимой задержки при работе с файлами до 100 кбайт. Оптимизацию я оставляю Вам, свою же задачу я вижу в ознакомлении с данным алгоритмом.

Наверх

Алгоритм дешифрации для архиватора bls. Скачать

Процедура дешифрует файл зашифрованный архиватором zip. Следует заметить, что zip добавляет к каждому зашифрованному файлу заголовок шифровки состоящий из 12 байт, который представляет из себя набор случайных байт. Известно что последние два байта данного заголовка ни что иное как старшее слово контрольной суммы незашифрованного файла.

Структурно процедура состоит из четырех частей. Первая часть, имеет вспомогательное значение, в ней создается CRC-таблица, используемая в дальнейшем для преобразования ключей дешифрации, а так же непосредственно инициализируются три 32-байтных ключа. Во второй части ключи преобразуются, используя пароль. В третий части происходит преобразование ключей с одновременной расшифровкой 12-байтного заголовка файла, на этом этапе можно осуществить проверку пароля, если известна контрольная сумма дешифруемого файла (zip хранит ее в незакодированном виде). И наконец последняя, четвертая часть в которой происходит непосредственно побайтная дешифрация данных, при этом дешифрованный байт замещает соответстующий байт в исходном массиве.

На вход процедуры подаются следующие данные: n - длина пароля, P- массив содержащий пароль, buffer- 12-байтный заголовок, m- длина дешифруемого массива, stream- массив байт, который необходимо расшифровать. На выходе получаем расшифрованные данные в массиве stream при этом размер массива остается тем же m.

Как и при шифровке Blowfish-ем следует понимать, что не смотря на то, что алгоритм можно использовать без каких-либо изменений, скорость его работы может быть существенно оптимизирована при непосредственном кодировании на одном из языков программирования. Но я не ставлю себе такую задачу, и представляю этот алгоритм только в образовательных целях, конкретную же реализацию как и в большинстве случаев оставляя Вам.

Наверх

Алгоритм подсчета CRC32. Скачать

Функция высчитывает CRC(Cyclic Redundancy Codes) для массива Stream длины N. Вначале по заданному параметру MagWord - определяющему полином расчета CRC строиться массив CRCTable, при помощи которого в дальнейшем производится расчет.

Дополнительно функции передается несколько параметров: InitCrc инициализирующие значение CRC, Inv показывает надо ли инвертировать полученное значение CRC перед выдачей результата.

При реализации использовались следующие функции: A shr B сдвиг бит двоичного представления числа A вправо на B разрядов, Xor и And побитовые операции, соответственно, "Исключающие ИЛИ" и "И", Byte(A) взятие младшего байта числа А. Знак доллара ($) перед числом указывает на то, что число представлено в шестнадцатеричной системе счисления.

Для примера известный архиватор Winzip использует для расчета CRC32 следующие параметры:

    MagWord = $EDB88320
    InitCRC = $FFFFFFFF
    Inv = True


Библиотекa алгоритмов по программированию. Наборы псевдослучайных чисел.
  • Генерация массива псевдослучайных чисел, равномерно распределенных в интервале (0,1). Скачать
  • Генерация массива псевдослучайных чисел, нормально распределенных с нулевым средним значением и единичной дисперсией. Скачать
  • Генерация массива псевдослучайных чисел, имеющих экспоненциальное распределение со средним значением XM и дисперсией XM. Скачать

Генерация массива псевдослучайных чисел, равномерно распределенных в интервале (0,1). Скачать

Алгоритм предназначен для генерации набора rj псевдослучайных чисел, которые равномерно распределены на отрезке (0,1). Генерация происходит по следующим формулам:

    rj=kj*2-31, j=1,...n, где kj=kj-1*75 mod (231-1),
    k0=SEED

На вход алгоритма подается SEED - целое из отрезка 0.. 2147483647. n- размер массива, который необходимо получить.

Наверх

Генерация массива псевдослучайных чисел, нормально распределенных с нулевым средним значением и единичной дисперсией. Скачать

Алгоритм предназначен для генерации набора rj псевдослучайных чисел, которые распределены нормально с нулевым средним значением и единичной дисперсией. Генерация происходит по следующему алгоритму:

Вначале генерируется пара независимых равномерно распределенных чисел U,Vиз отрезка (-1,1). Затем, если S = U2+V2 < 1, то паpа чисел
являются независимыми ноpмально pаспpеделенными псевдослучайными числами и помещаются в массив r.

На вход алгоритма подается SEED - целое из отрезка 0.. 2147483647. n- размер массива, который необходимо получить, поскольку случайные велечины генереруются парами, то n должно быть четно, иначе полагается n=n-1.

Наверх

Генерация массива псевдослучайных чисел, имеющих экспоненциальное распределение со средним значением XM и дисперсией XM. Скачать

Алгоритм предназначен для генерации набора rj псевдослучайных чисел, которые распределены экспоненциально со средним значением XM и дисперсией XM. Генерация происходит по вормуле:

R(I)=-XM*ln(U(I))
где U - массив равномернораспределенных псевдослучайных чисел.

На вход алгоритма подается SEED - целое из отрезка 0.. 2147483647. n- размер массива, который необходимо получить и XM - величина среднего значения и дисперсии.


Библиотекa алгоритмов по программированию. Нахождение собственных значений и собственных векторов матрицы.
  • Введение.
  • Нахождение собственных значений матрицы методом А.M. Данилевского. Скачать
  • Нахождение собственных значений матрицы методом Леверрье. Скачать
  • Нахождение собственных значений матрицы методом неопределенных коэффициентов. Скачать

Введение.

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

Основной прием использующийся при отыскании собственных значений матрицы это развертывание определителя в полином n-й степени. Отыскание же корней полученного полинома является отдельной, отнюдь не тривиальной задачей. Здесь могут пригодится методы из раздела Полиномиальные и трансцендентные уравнения..

Следует заметить, что попытка решение задачи развертывания определителя в полином "в лоб", требует значительных вычислений, и весьма трудоемка. Нетрудно показать, что непосредственное вычисление коэффициентов характеристического полинома эквивалентно вычислению 2n-1 определителей различных порядков.

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

Наверх

Нахождение собственных значений матрицы методом А.M. Данилевского. Скачать

Сущность метода Данилевского заключается в приведении векового определителя к так называемому нормальному виду Фробениуса

Если нам удалось записать вековой определитель в такой форме, то, разлагая его по элементам первой строки будем иметь:

Таким образом задача сводится к нахождению матрицы P в форме Фробениуса подобной матрице A, так как собственные числа инвариантны относительно операции подобия.

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

Опишем первое из преобразований, которое приводит n-ую строку исходной матрицы A к необходимому виду. Вначале преобразуем матрицу A в матрицу B по следующим формулам:

    bi j=ai j - ai n-1an i / an n-1   при i=1,..,n; j не равно n-1;
    bi n-1=ai n-1 / an n-1,  при i=1,..,n
Последняя строка построенной матрицы B будет удовлетворять нашим условиям, но не будет подобна матрице A, поэтому проведем еще одно преобразование и получим матрицу С подобную A и сохраняющую последнюю строку:
    сi j=bi j  при i=1,..,n-2
    cn-1 j=an 1b1 j+an 2b2 j+ . . . +an nbn j  при j=1,...,n

Таким образом получили матрицу С подобную A и с последней строкой как в матрице привеленного вида Фробениуса. Продолжая, преобразуем аналогично n-1 строку матрицы С и т.д.

Допустим, что при преобразовании матрицы A в матрицу Фробенниуса P мы пришли к матрице вида:
причем оказалось, что dk k-1=0.

Тогда преобразования методом Данилевского нельзя продолжить. Здесь возможны два случая: 1. Существует элемент dk l отличный от нуля, где l < k-1 , тогда переставляем местами (k-1) и l столбцы и (k-1) и l строки получаем матрицу подобную D для которой возможны дальнейшие преобразования по методу Данилевского. 2. Все элементы k строки равны нулю, тогда полученная матрица имеет вид:
Причем D2 имеет нормальный вид Фробениуса, а матрицу D1 можно привести к нему методом Данилевского. Полином же порождающий собственные значения матрицы А, есть произведение аналогичных полиномов для D1 и D2, при этом коэффициенты полинома для D2 определены.

Процедура на вход получает матрицу A, а на выходе выдает матрицу C подобную A, при этом С имеет нормальный вид Фробениуса. Флаговая переменная S используется для определения случая когда дальнейшее преобразование не возможно, точнее: S=0 когда алгоритм успешно отработал, S > 0 когда на некотором шаге возник случай описанный в пункте 2, при этом S колличество строк в матрице D1.

Наверх

Нахождение собственных значений матрицы методом Леверрье. Скачать

Процедура определяет коэффициенты характерестического полинома
матрицы A. Положим:
тогда справедливы формулы Ньютона:
Отсюда получаем линеиную алгебраическую систему:
Из которой шаг за шагом определяются коэффицитенты p1,...,pn. Следует заметить, что sk равен следу матрицы Ak, которая находятся непосредственным перемножением используя алгоритм умножения матриц.
Наверх

Нахождение собственных значений матрицы методом неопределенных коэффициентов. Скачать

Процедура определяет коэффициенты характеристического полинома
матрицы A. Для этого полагаем в предыдущем равенстве [image] =0,1,...,(n-1), таким образом получим систему из n линейных уравнений относительно p1,...,pn. Корни системы находим используя любой из методов описанных на странице Решение систем линейных алгебраических уравнений. В блок-схеме вызывается метод Гаусса, но можно использовать любой другой метод.


Библиотекa алгоритмов по программированию. Неразобранные алгоритмы без блок-схем.
  • Алгоритм выделения из системы векторов эквивалетной ей линейно-независимой подсистемы векторов.
    Алгоритм прислал Бочканов Сергей(Grayscale)
  • Алгоритм преобразования системы векторов в эквивалентную ей линейно-независимую систему ортогональных векторов.
    Алгоритм прислал Бочканов Сергей(Grayscale)

Алгоритм выделения из системы векторов эквивалетной ей линейно-независимой подсистемы векторов. Алгоритм прислал Бочканов Сергей(Grayscale)

Вход: система векторов a1..an. Выход: система векторов ai1..air - линейно-независимая подсистема. Линейные оболочки систем равны:
L(a1..an)=L(ai1..air)

Алгоритм:

  1. Запишем систему векторов B={a0}, R={a0}.
  2. Положим s=2.
  3. Найдём вектор t = as - ∑i=1..s-1 λibi,
    bi - i-ый вектор в B, λi=(as,bi) / (bi,bi).
  4. если t ≠ 0, то добавим t в B, as добавим в R.
  5. если s ≠ n, то s=s+1, переходим к пункту 3.
  6. R - результат.
Наверх

Алгоритм преобразования системы векторов в эквивалентную ей линейно-независимую систему ортогональных векторов. Алгоритм прислал Бочканов Сергей(Grayscale)

Вход: система векторов a1..an. Выход: система векторов b1..br - линейно-независимая, ортогональная. Линейные оболочки систем равны:
L(a1..an)=L(b1..br)

Алгоритм:

  1. Запишем систему векторов B={a0}.
  2. Положим s=2.
  3. Найдём вектор t = as - ∑i=1..s-1 λibi,
    bi - i-ый вектор в B, λi=(as,bi) / (bi,bi).
  4. если t ≠ 0, то добавим t в B.
  5. если s ≠ n, то s=s+1, переходим к пункту 3.
  6. B - результат.


Библиотекa алгоритмов по программированию. Обыкновенные дифференциальные уравнения.
  • Модифицированные методы Эйлера решения уравнения первого порядка. Скачать
  • Метод Рунге-Кутта четвертого порядка для решения уравнения первого порядка. Скачать
  • Обыкновенные дифферециальные уравнения высших порядков и системы дифферециальных уравнений. Скачать
  • Метод Рунге-Кутта с автоматическим выбором шага. Скачать

Модиффицированные методы Эйлера решения уравнения первого порядка. Скачать

При численном интегрировании дифференциального уравнения первого порядка

    y'=F(x,y)
с начальным условием y(x0)=y0 (задача Коши) сначала выбираем фиксированное приращение аргумента h=(xf -x0)/n, где xf - конечная точка интервала интегрирования, n- число шагов. Затем, применяя процедуру модифицированного метода Эйлера, вычисляем yk по рекурентной формуле:
    yk=yk-1+h[Fk-1+F(xk ,yk-1+hFk-1)]/2
где Fk=F(xk,yk).

Можно воспользоваться другой рекурентной формулой:

    yk=yk-1+F(xk-1+h/2,yk-1+Fk-1 h/2)
.
Наверх

Метод Рунге-Кутта четвертого порядка для решения уравнения первого порядка. Скачать

Наиболее употребительным методом Рунге-Кутта является метод четвертого порядка, в котором вычисления производятся по формуле:

    yk+1=yk+(k1+2k2+2k3+k4)/6,
где
    k1=Fk h=F(xk,yk)h
    k2=F(xk+h/2,yk+k1/2) h
    k3=F(xk+h/2,yk+k2/2) h
    k4=F(xk+1,yk+k3) h, k=0, . . .,n-1
    h=(xf -x0)/n
Наверх

Обыкновенные дифферециальные уравнения высших порядков и системы дифферециальных уравнений. Скачать

Система обыкновенных диференциальных уравнений высшего порядка путем введения новых функций может быть сведена к системе уравнений первого порядка. Рассмотрим такую систему

    yi'=Fi(x,y)
где i=1,...,n; y=(y1,y2, . . .,yn); y(x0)=y(0)=(y(0)1, . . .,y(0)n).

Систему будем решать методом Рунге-Кутта, вычисляя yik по формуле:

    yi(k+1)=yi(k)+(k1(i)+2k2(i)+2k3(i)+k4(i))/6
где
    k1(i)=Fi(x(k),y(k))h
    k2(i)=Fi(x(k)+h/2,y(k)+k1(i)/2) h
    k3(i)=Fi(x(k)+h/2,y(k)+k2(i)/2) h
    k4(i)=Fi(x(k+1),y(k)+k3(i)) h,
    h=(xf -x0)/m
m - колличество шагов интегрирования.

Процедура использует набор функций F(i,x,y), которые соответствуют функциям F(i,x,y) описанным выше.

Наверх

Метод Рунге-Кутта с автоматическим выбором шага. Скачать

Процедура интегрирует систему дифференциальных уравнений первого порядка

    yi'=Fi(x,y)
с начальным условием y(x0)=y(0)=(y(0)1, . . .,y(0)n) методом Рунге-Кутта с автоматическим выбором шага. Вначале шаг интегрирования выбирается равным: h=(xf -x0)/2. По формулам предыдущего раздела вычисляются значения функций y1 i=yi(x0+2h) (т.е. на шаге интегрирования 2h), затем эти же формулы применяются дважды с шагом h: вначале для нахождения решения y2 i в точках x0+h и по этим значениям для нахождения y3 i=yi(x0+2h). Полученные значения y1 i и y3 i сравниваются. Если абсолютные значения разности мантисс y1 i и y3 i (после выравнивания порядков этих величин и 10 s ) больше e, то происходит уменьшение шага вдвое.

После пятикратного интегрирования с шагом h происходит двухкратное увеличение шага. После вычисления y(x0+2h) за исходную принимается точка x+2h, а за исходное значение функции y(x+2h), затем процесс вычисления повторяется.

Данная процедура также как и предыдущая использует набор функций F(i,x,y), которые соответствуют функциям F(i,x,y) описанным выше.

Процедура вызывает процедуру RK, блок-схема которой находится в том же файле. Если Вы решите экспортировать блок-схемы в паскаль, то необходимо вынести процедуру RK в новый документ и экспортировать отдельно от основной процедуры.


Библиотекa алгоритмов по программированию. Операции над полиномами и степенными рядами.
  • Умножение рядов. Скачать
  • Деление рядов. Скачать
  • Возведение ряда в степень. Скачать
  • Обращение ряда. Скачать

Умножение рядов. Скачать

Процедура находит n+1 коэффициент произведения двух степенных рядов:

    g(x)=g0+g1x+. . . +gnxn+. . .,
    h(x)=h0+h1x+. . . +hnxn+. . .,
    C(x)=g(x)h(x)=C0+C1x+. . . +Cnxn+. . .  .
причем

Процедура по известным значениям gi и hi вычисляет по данной формуле значения Сi.

Наверх

Деление рядов. Скачать

Пусть заданы два ряда:

    h(x)=h0+h1x+. . . +hnxn+. . .,
    g(x)=g0+g1x+. . . +gnxn+. . .  .

Тогда коэффициенты частного от деления этих рядов

    C(x)=g(x)/h(x)=C0+C1x+. . . +Cnxn+. . .  .
могут быть опрeделены из следующих соотношений:
    Ci=[hi - (C0 gi+ . . . +Ci-1 g1)]/g0 , i=0,1,2...

Процедура помещает коэффициенты ряда С в массив h.

Наверх

Возведение ряда в степень. Скачать

Пусть задан ряд:

    f(x)=1+a1x+. . . +anxn+. . .

Коэффициентs p-й степени ряда f(x) можно найти по рекурентному соотношению:
где
    i=1,2,. . .; f p(x)=1+b1x+b2x2+ . . .

Соотношение для коэффициентов bi справедливо для любого вещественного p отличного от 0. Если p=0, то получим коэффициенты ряда ln f(x). Если a0 не равно 1, то необходимо предварительно разделить все ai на a0 и в конце умножить bi на a0p.

Наверх

Обращение ряда. Скачать

Пусть задан степенной ряд

    y=x+a2 x2+ . . . +an xn+ . .

Процедура находит коэффициенты обращенного степенного ряда

    x=y+b2 y 2+ . . . +bn y n+ . .


Библиотекa алгоритмов по программированию. Операции над полиномами.
  • Вычисление значения полинома от заданного аргумента. Скачать
  • Умножение полиномов. Скачать
  • Деление с остатком. Скачать
  • Коэффициенты полинома при линейном преобразовании аргумента. Скачать
  • Коэффициенты полинома по заданным вещественным корням. Скачать
  • Вычисление коэффициентов полинома обратного заданному. Скачать

Вычисление значения полинома от заданного аргумента. Скачать

Функция вычисляет значение полинома P(x)=p0+p1x+. . . +pnxn в точке x0 по схеме Горнера. Т.е. используя формулу:

    P(x)=(..(pnx0+pn-1)x0+. . . +p1)x0+p0
Наверх

Умножение полиномов. Скачать

Процедура находит коэффициенты полинома полученного в результате перемножения двух полиномов:

    Q(x)=q0+q1x+. . . +qmxm,
    P(x)=p0+p1x+. . . +pnxn,
    H(x)=P(x)Q(x)=h0+h1x+. . . +hn+mxn+m

Процедура по известным значениям pi и qi вычисляет значения hi. Надо заметить, что алгоритм усложняется, т.к. не известно можно ли использовать переменные массивов p,q с номерами большими n,m, если же положить их равными 0, то можно использовать алгоритм перемножения рядов положив в нем n=n+m.

Наверх

Деление с остатком. Скачать

Пусть заданы два полинома:

    Q(x)=q0+q1x+. . . +qmxm,Q(x)<>0,
    P(x)=p0+p1x+. . . +pnxn.

Алгоритм осуществляет поиск коэфициентов полиномов

    H(x)=h0+h1x+. . . +hn-mxn-m,
    R(x)=r0+r1x+. . . +rkxk, k < m
удовлетворяющих соотношению:
    P(x)=Q(x)H(x)+R(x)

При этом предполагаем, что pn,qm не равны 0. Переменная k на выходе из процедуры содержит значение степени полинома R(x), если k=-1 значит полином Q(x) делитель полинома P(x).

Наверх

Коэффициенты полинома при линейном преобразовании аргумента. Скачать

Если в полиноме n -й степени

    P(x)=c0+c1x+ . . .+cnxn
аргумент x заменить на x=at+b, то получим полином
    P(at+b)=c0+c1(at+b)+. . .+cn(at+b)n=d0+d1t+. . .+dntn
где

Процедура вычисляет коэффициенты di

Наверх

Коэффициенты полинома по заданным вещественным корням. Скачать

Алгоритм вычисляет коэффициенты полинома по заданным вещественным корням. Работа алгоритма сводиться к последовательному умножению текущего полинома на (x-xk), где xk - k-й корень.

На вход подается массив P[1..n] - корней полинома, на выходе получаем массив A[0..n] - коэффициентов полинома A(x)=a0+a1x+...+anxn

Наверх

Вычисление коэффициентов полинома обратного заданному. Скачать

Алгоритм для полинома A(x)=a0+a1x+...+anxn находит m- первых коэффициентов обратного полинома:

    B(x)=1/A(x)=x-k (b0+b1x+...+bmxm+...)
здесь k - количество первых нулевых коэффициентов полинома A(x).

Коэффициенты bj ищутся по формулам:

    b0=1/a0;
    bj=-b0(a1bj-1+...+ajb0), j=1..n
    bj=-b0(a1bj-1+...+anbj-n), j=n+1,n+2,...

На вход алгоритма подаются переменные n,m соответственно степень полинома A и количество коэффициентов полинома B, которые необходимо вычислить, а так же массив a[0..n] - содержащий коэффициенты исходного полинома. На выходе получаем переменную k, и массив b[0..m] - коэффициенты полинома b.


Библиотекa алгоритмов по программированию. Ортогональные полиномы.
  • Вычисление значения полиномов Чебышева I-го и II-го рода от заданного аргумента. Скачать
  • Вычисление коэффициентов полинома Чебышева I-го рода. Скачать
  • Вычисление суммы ряда по полиномам Чебышева от заданного аргумента(метод Кленшоу). Скачать
  • Восстановление коэффициентов полинома, заданного разложением по полиномам Чебышева. Скачать
  • Вычисление значения полиномов Эрмита от заданного аргумента. Скачать
  • Вычисление коэффициентов полинома Эрмита. Скачать
  • Вычисление суммы ряда по полиномам Эрмита от заданного аргумента(метод Кленшоу). Скачать
  • Вычисление значения полиномов Лежандра от заданного аргумента. Скачать
  • Вычисление коэффициентов полинома Лежандра. Скачать
  • Вычисление суммы ряда по полиномам Лежандра от заданного аргумента(метод Кленшоу). Скачать
  • Вычисление значения полиномов Лагерра от заданного аргумента. Скачать
  • Вычисление коэффициентов полинома Лагерра. Скачать
  • Вычисление суммы ряда по полиномам Лагерра от заданного аргумента(метод Кленшоу). Скачать

Вычисление значения полиномов Чебышева I-го и II-го рода от заданного аргумента. Скачать

Полиномы Чебышева I-го рода Tn(x) и II-го рода Un(x) определяются как,

    Tn(x)=cos(n arccos x)
    Un(x)=sin(n arccos x)
При этом получаем
Функции Tn(x) и Un(x) удовлетворяют рекуррентной формуле:
    Wn+1(x)=2x Wn(x)-Wn-1(x)

Процедура вычисляет значения полиномов Чебышева n-го порядка в заданной точке x. Переменная r определяет род полинома: r=1 - полином I-го рода, r=2 - полином II-го рода. Результат помещается в переменную Result.

Наверх

Вычисление коэффициентов полинома Чебышева I-го рода. Скачать

Процедура производит вычисление коэффициентов полиномов Чебышева I-го рода на основании явного выражения для многочлена Tn(x):
где k= n div 2 и
из последнего выражения следует рекуррентное соотношение для коэффициентов am:
      ,
которое мы используем в нашей процедуре. При чем a0=1 при n=0, и a0=1/2n-1 при n > 0.

Коэффициенты полинома помещаются в массив a. Следует отметить что a[m] - коэффициент при xn-2m, а не при xm.

Наверх

Вычисление суммы ряда по полиномам Чебышева от заданного аргумента(методом Кленшоу). Скачать

Процедура вычисляет значение функции:

    Sn(x)=a0(x)Ф0(x)+...+an(x)Фn(x)
здесь Фn(x) - n-ый полином Чебышева(I-го или II-го рода). При вычислении используется метод Кленшоу, согласно которому
    Sn(x)=(a0-b2(x))Ф0(x)+b1(x)Ф1(x)
а значения bk вычисляются последовательно по формулам:
    bk(x)=2xbk+1(x)-bk+2(x)+ak(x), bn+1(x)=bn+2(x)=0

На вход функции подается массив а коэффициентов в переменной Result получаем значение суммы. Переменная r выступает в роли переключателя: r=1 - сумма по полиномам Чебышева I-го рода, r=2 - II-го рода.

Описание данного метода мне прислал Вячеслав Андреев. Более подробно о методе Кленшоу см. статью

Наверх

Восстановление коэффициентов полинома, заданного разложением по полиномам Чебышева. Скачать

Пусть известны коэффициенты a0,a1, ..., an разложения многочлена Р(x) по полиномам Чебышева {Тk(x)}:

    P(x)=a0T0(x)+...+anTn(x)
Алгоритм вычисляет коэффициенты b0,b1, ..., bn разложения этого многочлена по степеням x:
    P(x)=b0+b1x+...+bnxn

Основой алгоритма служит рекурентная формула для полиномов Чебышева:

    Tn+1(x)=2xTn(x)-Tn-1(x)
    T0(x)=1
    T1(x)=x

В блок-схеме используется массив A для коэффициентов разложения по полиномам Чебышева и массив B для коэффициентов разложения по степеням x.

Наверх

Вычисление значения полиномов Эрмита от заданного аргумента. Скачать

Полиномы Эрмита Hn(x) определяются как,
При этом Hn(x) удовлетворяют рекуррентной формуле:
    Hn+1(x)=2x Hn(x)-2nHn-1(x)
причем H0(x)=1, H1(x)=2x.

Процедура вычисляет значения полиномов Эрмита n-го порядка в заданной точке x, результат помещается в переменную Result.

Наверх

Вычисление коэффициентов полинома Эрмита. Скачать

Процедура производит вычисление коэффициентов полиномов Эрмита на основании формул:
где k= n div 2, а коэффициенты определяются по формулам:
Отсюда следует рекуррентное соотношение для коэффициентов am:
которое мы используем в нашей процедуре.

Коэффициенты полинома помещаются в массив a. Следует отметить что a[m] - коэффициент при xn-2m, а не при xm.

Наверх

Вычисление суммы ряда по полиномам Эрмита от заданного аргумента(метод Кленшоу). Скачать

Процедура вычисляет значение функции:

    Sn(x)=a0(x)H0(x)+...+an(x)Hn(x)
При вычислении используется метод Кленшоу, согласно которому получаем:
    Sn(x)=b0(x)
а значения bk вычисляются последовательно по формулам:
    bk(x)=2xbk+1(x)-(k+1)bk+2(x)+ak(x), bn+1(x)=bn+2(x)=0

На вход функции подается массив а коэффициентов в переменной Result получаем значение суммы.

Описание данного метода мне прислал Вячеслав Андреев. Более подробно о методе Кленшоу см. статью

Наверх

Вычисление значения полиномов Лежандра от заданного аргумента. Скачать

Полиномы Лежандра Un(x) определяются как,
Функции Pn(x) удовлетворяют рекуррентной формуле:
    (n+1)Pn+1(x)=(2n+1)x Pn(x)-nPn-1(x)
при этом P0(x)=1, P1(x)=x

Процедура вычисляет значения полиномов Лежандра n-го порядка в точке x. Результат помещается в переменную Result.

Наверх

Вычисление коэффициентов полинома Лежандра. Скачать

Процедура производит вычисление коэффициентов полиномов Лежандра на основании явного выражения для многочлена Pn(x):
где k= n div 2, а коэффициенты определяются по формулам:
Отсюда следует рекуррентное соотношение для коэффициентов am:
которое мы используем в нашей процедуре.При чем:

Коэффициенты полинома помещаются в массив a. Следует отметить что a[m] - коэффициент при xn-2m, а не при xm.

Наверх

Вычисление суммы ряда по полиномам Лежандра от заданного аргумента (метод Кленшоу). Скачать

Процедура вычисляет значение функции:

    Sn(x)=a0(x)P0(x)+...+an(x)Pn(x)
здесь Pn(x) - n-ый полином Лежандра. При вычислении используется метод Кленшоу, согласно которому
    Sn(x)=b0(x)
а значения bk вычисляются последовательно по формулам:
    bk(x)=(2k+1)xbk+1(x)/(k+1)-(k+1)bk+2(x)/(k+2)+ak(x), bn+1(x)=bn+2(x)=0

На вход функции подается массив а коэффициентов,на выходе в переменной Result получаем значение суммы.

Описание данного метода мне прислал Вячеслав Андреев. Более подробно о методе Кленшоу см. статью

Наверх

Вычисление значения полиномов Лагерра от заданного аргумента. Скачать

Полиномы Лагерра Ln(x) определяются как,
Функции Ln(x) удовлетворяют рекуррентной формуле:
    (n+1)Ln+1(x)=(2n+1-x)Ln(x)-nLn-1(x)
при этом L0(x)=1,L1(x)=1-x.

Процедура вычисляет значения полиномов Лагерра n-го порядка в точке x. Результат помещается в переменную Result.

Наверх

Вычисление коэффициентов полинома Лагерра. Скачать

Процедура производит вычисление коэффициентов полиномов Лагерра на основании явного выражения для многочлена Ln(x):
где коэффициенты определяются по формулам:
Отсюда следует рекуррентное соотношение для коэффициентов am:
которое мы используем в нашей процедуре.При чем:
    a0=1

Коэффициенты полинома помещаются в массив a.

Наверх

Вычисление суммы ряда по полиномам Лагерра от заданного аргумента (метод Кленшоу). Скачать

Процедура вычисляет значение функции:

    Sn(x)=a0(x)L0(x)+...+an(x)Ln(x)
здесь Ln(x) - n-ый полином Лагерра. При вычислении используется метод Кленшоу, согласно которому
    Sn(x)=b0(x)
а значения bk вычисляются последовательно по формулам:
    bk(x)=(2k+1-x)bk+1(x)/(k+1)-(k+1)bk+2(x)/(k+2)+ak(x), bn+1(x)=bn+2(x)=0

На вход функции подается массив а коэффициентов,на выходе в переменной Result получаем значение суммы.

Описание данного метода мне прислал Вячеслав Андреев. Более подробно о методе Кленшоу см. статью


Библиотекa алгоритмов по программированию. Поиск.
  • Поиск подпоследовательности в массиве (простой). Скачать
  • Поиск подпоследовательности в массиве (алгоритм Бойера - Мура - Хорспула). Скачать
  • Поиск подпоследовательности в массиве (алгоритм Кнута-Морриса-Пратта). Скачать
  • Поиск подпоследовательности в массиве (алгоритм СДВИГ-И). Скачать
  • Поиск подпоследовательности в массиве (алгоритм Бойера - Мура). Скачать

Поиск подпоследовательности в массиве (простой). Скачать

Функция осуществляет поиск первого вхождения массива W в массив T, в результате функция выдает номер первого элемента в массиве T начиная с которого встречается массив W. В случае, если массив W не встречается в массиве T результат функции равен -1.

Поиск осуществляется методом простого перебора, поэтому скорость работы функции не высока, но зато не занимается дополнительной памяти, и алгоритм прост в использовании.

Наверх

Поиск подпоследовательности в массиве (алгоритм Бойера - Мура - Хорспула) . Скачать

Функция осуществляет поиск первого вхождения массива W(размера m) в массив T, в результате функция выдает номер первого элемента в массиве T начиная с которого встречается массив W. В случае, если массив W не встречается в массиве T результат функции равен -1.

Вначале функция создает BMH-таблицу содержимое, которой зависит от искомого массива, а именно если число i не содержится в подмассиве W[1..m-1], то BMHTable[i]=m, если число i содержится в подмассиве W[1..m-1], то берется максимальный номер j, т.ч. W[j]=i и тогда BMHTable[i]=m-j. В дальнейшем таблица используется для "ускорения" прохода массива в котором осуществляется поиск, следующим образом: 1. Положим j=m; 2. Пусть k=m; i=j. Пока W[k]=T[j] и k>0, уменьшаем на единицу k и i; 3. Если k=0, значит массив W входит в массив T начиная с номера i+1 и ВЫХОД. 4. Увеличим значение j на BMHTable[T[j]] (действительно T[j] в массиве W может быть на расстоянии не меньшем, чем BMHTable[T[j]] от конца). 5. Если j ≤ n переходим к шагу 2, иначе ВЫХОД и массив W не содержится в массиве T.

Алгоритм оптимизирован по сравнению с предыдущим для случая длинного искомого массива с не одинаковыми элементами. Интересно, что алгоритм работает намного медленее предыдущего например в случае когда массив T состоит из одних нулей, а массив W имеет следующий вид: 1000000.

Наверх

Поиск подпоследовательности в массиве (алгоритм Кнута-Морриса-Пратта). Скачать

Функция осуществляет поиск первого вхождения массива W(размера m) в массив T, в результате функция выдает номер первого элемента в массиве T начиная с которого встречается массив W. В случае, если массив W не встречается в массиве T результат функции равен -1.

Рассмотрим вначале функцию F которая определена на последовательностях X[1],...,X[k] следующим образом: рассмотрим все начала последовательности X одновременно являющиеся ее концами, и выберем из них самое длинное. (Не считая, конечно, самой последовательности X). Тогда F(X)= длине такой подпоследовательности.

Работа алгоритма заключается в вычислении функции F на последовательности полученной слиянием массивов W и T с использованием разделителя в качестве которого должен выступать элемент не содержащийся ни в первом ни во втором массивах: W[1],...,W[m],@,T[1],...,T[j]; j=1..n. Тогда, если значение F при некотором j равно m (длине последовательности W), то массив W содержится в массиве T, иначе нет.

В первой части алгоритма заполняется массив L, при этом L[i]=F(W[1],...W[i]). На этом стоит остановится подробнее, т.к. методика заполнения массива L является ключевой в данном алгоритме. Итак тривиально L[1]=0 (поскольку F - длина подпоследовательности). Далее, допустим мы заполнили массив L для элементов с первого по i-ый. Теперь необходимо определить значение L[i+1]=F(W[1],...,W[i],W[i+1]). Для этого положим вначале len=L[i]. По построению массива L мы знаем, что W[i-len+1]=W[1] ,..., W[i]=W[len], и если W[i+1]=W[len+1], то L[i+1]=L[i]+1, допустим это не так, т.е. W[i+1]<>W[len+1], значит надо уменьшить длину начального подмассива который мы рассматриваем, положим len_=L[len], тогда получаем W[i-len+1]=W[1]=W[len-len_+1]=W[i-len_+1],...,W[i-len+len_]=W[len_]=W[len]=W[i], или выписав только важные для нас соотношения: W[1]=W[i-len_+1],...,W[len_]=W[i], и осталось снова сравнить W[i+1] и W[len_+1], если они снова не равны положим len=len_; len_=L[len], продолжая этот процесс мы на некотором шаге получим либо len=0 и тогда L[i+1]=0, если W[i+1]<>W[1] и L[i+1]=1, если W[i+1]=W[1], либо равенство W[i+1]=W[len_+1] и значит L[i]=len_+1.

После заполнения массива L осуществляется вычисление функции F на массиве W[1],...,W[m],@,T[1],...,T[j]; j=1..n, воспользовавшись алгоритмом похожим на тот, что использовался в предыдущем абзаце, при этом разделитель как таковой не используется.

Несмотря на кажущуюся сложность (лучше посмотреть блок-схему все станет более понятным), алгоритм хорошо оптимизирован как по скорости поиска, так и по объему используемой памяти.

Наверх

Поиск подпоследовательности в массиве (алгоритм СДВИГ-И). Скачать

Функция осуществляет поиск первого вхождения массива W в массив T, в результате функция выдает номер первого элемента в массиве T начиная с которого встречается массив W. В случае, если массив W не встречается в массиве T результат функции равен -1.

Алгоритм описан в статье В. Максимова в журнале "Монитор", №6 за 1995 год, ссылку на элестронную версию статьи в гостевой книге предложил Valera, мне статья очень понравилась, если Вы интересуетесь алгоритмами поиска советую прочитать. Ссылку на статью повторяю: Алгоритмы поиска, или Как искать неизвестно что.

Теперь подробнее об алгоритме.

Алгоритм поиска СДВИГ-И предложен в 1992 году Уди Манбер (Udi Manber) и Сан Ву (Sun Wu). Помимо того что алгоритм быстро работает и его просто программировать, он обладает уникальной особенностью: его можно легко, если не сказать элементарно, обобщить на случай нечеткого (приблизительного) поиска.

Допустим мы ищем вхождения последовательности vivid в массив vivi&dv&vivid. Будем искать все вхождения пяти шаблонов: v, vi, viv, vivi и vivid. Построим таблицу, которая бы отражала для каждой позиции текста, является ли эта позиция концом каждого из рассматриваемых пяти шаблонов. Для каждой позиции текста получим битовый 5-элементный вектор-массив, в котором k-й бит равен 1, если эта позиция соответствует концу вхождения k-го префикса. В итоге имеем таблицу из m строк и n столбцов:

        vivi&dv&vivid
    v	1010001010100
    i	0101000001010
    v	0010000000100
    i	0001000000010
    d	0000000000001
Будем следить за последней строкой, появление в ней единицы, означает, что найдено вхождение искомой подпоследовательности в массив. Ясно, что основная задача получить алгоритм быстрого построения таблицы.

Мы будем предполагать, что длина массива W не превышает 32, тогда любой столбец таблицы можно представить в виде двойного слова (тип dword или LongInt). Для построения таблицы вначале для каждого символа алфавита построим характеристический вектор (у нас символы соответствуют произвольному целому 0-255), т.е. построим массив CVTab: array [0..255] of dword, при этом элемент CVTab[i] в двоичном представлении имеет единицы в тех позициях, в которых i-ый символ встречается в массиве W, т.е. для нашего примера CVTab для символа v будет иметь единицы в первой и третьей позиции (101), для символа i во второй и четвертой (1010), для тех символов, которые отсутствуют в шаблоне, характеристический вектор будет равен нулю.

Далее на j-ом шаге строим столбец таблицы по следующему алгоритму: вначале осуществляем сдвиг "вниз" предыдущего (j-1) столбца таблицы, заполняя первый бит 1, затем берем логическое И для полученного столбца с характеристическим вектором символа стоящего на j-ой позиции в последовательности T, в которой осуществляем поиск. Так например строя 3-й столбец в нашем примере: вначале осуществляем сдвиг для второго столбца (00010 - 00101), а затем берем логическое "И" с вектором соответствующем символу i (00101 AND 00101 = 00101).

Нетрудно изменить алгоритм для осуществления поиска подпоследовательностей с неопределенным значением некоторых символов, например в нашем примере, если надо найти вхождения любой подпоследовательности из 5 элементов, у которой на 2 и 4 позиции стоят символы i достаточно слегка подкоректировать характеристические вектора для символов алфавита.

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

Наверх

Поиск подпоследовательности в массиве (алгоритм Бойера - Мура). Скачать

Функция осуществляет поиск первого вхождения массива W(размера m) в массив T, в результате функция выдает номер первого элемента в массиве T начиная с которого встречается массив W. В случае, если массив W не встречается в массиве T результат функции равен -1.

Это еще один пример как можно ускорить проход по массиву T, в алгоритме Бойера - Мура - Хорспула мы использовали для этого таблицу BMHTable, которая создавалась на основе массива W, в данном алгоритме кроме нее (BMHTable здесь называется bm_bc) используется еще таблица bm_gs на которой мы остановимся чуть подробнее. Эта таблица имеет размер на 1 больший размера массива W, т.е. m+1, и позволяет при проходе по массиву T использовать частичные совпадения для ускорения прохода. Рассмотрим пример массив T=CATCGCAGAGAGTATACAGTACG, а массив W=GCAGAGAG. Посмотрим на первое сравнение

    C A T C G C A G A G A G T A T A C A G T A C G
              !
    G C A G A G A G

В случае алгоритма БМХ мы бы должны были сдвинуться только на 2 позиции (BMHTable[G]=2), но очевидно что этот сдвиг не достаточен поскольку мы вновь получим C<>G. Используя собранную заранее в таблицу bm_gs информацию о массиве W мы в данном алгоритме будем сдвигаться на 4 позиции тем самым увеличив скорость прохода. Таблица bm_gs для данного примера будет следующей:

    G C A G A G A G
    7 7 7 7 2 7 4 7 1

Получив не совпадение на 6 символе, мы выбираем величину сдвига равной bm_gs[7]=4. bm_gs[1] - используется в случае когда найдено полное совпадение, для сдвига на позицию с которой надо продолжить поиск. Использование двух таблиц для определения величины сдвига (bm_bc и bm_gs) позволяет брать максимум из величин.

Алгоритм построения вспомогательных таблиц проще всего посмотреть по блок-схеме.

Более подробное описание алгоритма есть в разделе "Поиск" на сайте algolist.da.ru, там лежит кусочный перевод статьи "Exact string matching algorithms".


Библиотекa алгоритмов по программированию. Полиномиальные и трансцендентные уравнения.
  • Поиск действительных корней квадратного уравнения вида: ax2+bx+c=0. Скачать
  • Поиск корней кубического уравнения вида: x3+ax2+bx+c=0. Скачать
  • Поиск корней уравнения четвертой степени вида: x4+ax3+bx2+cx+d=0. Скачать
  • Корень уравнения x=F(x). Скачать
  • Корень уравнения x=F(x) - модифицированный метод итераций. Скачать
  • Корень уравнения метод половинного деления. Скачать
  • Решение уравнения методом Ньютона (метод касательных). Скачать
  • Нахождение корней уравнения модифицированным методом Ньютона (метод хорд). Скачать
  • Решение уравнения методом секущих-хорд. Скачать
  • Решение системы уравнений. Скачать
  • Разложение полинома на рациональные линейные множители. Скачать

Поиск действительных корней квадратного уравнения вида: ax2+bx+c=0. Скачать

Вначале ищем детерминант уравнения по формуле D=b2-4ac,а затем, если дискреминант больше либо равен нуля определяем корни по формуле:

При этом переменная HasRoot принимает значение True.

Если D меньше нуля, то уравнение не имеет действительных решений и переменная HasRoot принимает значение False.

Наверх

Поиск корней кубического уравнения вида: x3+ax2+bx+c=0. Скачать

Процедура находит все корни кубического уравнения. Известно, что возможно два варианта: три действительных корня, либо один действительный корень и два комплексно сопряженных. В первом случае корни уравнения помещаются в массив x, во втором случае на выходе из процедуры в переменной x[1] содержится действительный корень, а в переменных x[2] и x[3] соответственно действительная и мнимая части комплексно сопряженных корней. Колличество действительных корней содержится в переменной nr.

Для решения уравнения вначале делаем подстановку y=x-a/3 в результате которой исходное уравнение преобразуется к виду:

    y3+py+q=0, где p=-a2/3+b, q=2(a/3)3-ab/3+c
далее вычисляем:
    Q=(p/3)3+(q/2)2
В случае, если Q - отрицательно (откуда очевидно p - отрицательно), уравнение имеет три действительных корня, которые получаются по формулам:
если Q=0 - уравнение имеет три действительных корня, которые получаются по формулам:
если Q - положительно то корни уравнения получаются по формулам:
Наверх

Поиск корней уравнения четвертой степени вида: x4+ax3+bx2+cx+d=0. Скачать

Процедура находит все корни уравнения четвертой степени. Известно, что возможно три варианта: четыре действительных корня, два действительных корня и два комплексно сопряженных или четыре комплексных попарно сопряженных корня. В первом случае корни уравнения помещаются в массив x, во втором случае на выходе из процедуры в переменных x[1] и x[2] содержатся действительные корни, а в переменных x[3] и x[4] соответственно действительная и мнимая части комплексно сопряженных корней, в третьем случае в переменных x[1] и x[2] содержиться соответственно действительная и мнимая части одной пары комплексно сопряженных корней, а в переменных x[3] и x[4] - другой. Колличество действительных корней находиться в переменной nr.

При решении уравнения используется метод Феррари, вначале находится действительный корень y1 кубического уравнения:

    y3-by2+(ac-4d)y-a2d+4bd-c2
при этом в случае когда три действительных корня берется максимальный. Для решения кубического уравнения используется предыдущий алгоритм.

Затем корни исходного уравнения находяться как корни двух квадратных уравнений:
при этом следует отметить, что подкоренное выражение в правой части является полным квадратом.
Наверх

Корень уравнения x=F(x). Скачать

Функция находит корень уравнения x=F(x) методом простой итерации с относительной погрешностью e. По i-му приближению корня xi находится следующие приближение по формуле

    xi+1=F(xi), i=0,1,2,...

Процесс продолжается до тех пор, пока относительная точность для двух последовательных приближений не станет меньше e:

    |(xi+1-xi)/xi| < e
Процесс итерации сходится на [a,b], если
    |F'(x)| < 1
при всех x на (a,b).

Чтобы избежать зацикливания функция прекращает работу после n итераций. Переменная HasRoot=True если необходимая точность e достигнута менее чем за n итераций, и HasRoot=False, если необходимая точность за n итераций недостигнута.

Наверх

Корень уравнения x=F(x) - модифицированный метод итераций. Скачать

Процедура находит корень уравнения модифицированным методом итерации. Условие сходимости в этом методе отличается от условия в методе простой итерации. Процесс сходится к значению x' при условии, что в некоторый момент

    |F(x)-x'| |F''(x')| < 2|F'(x')-1|

Следующее приближение определяется по формулам:

    x0=a; xi+1=xi+di;
    d0=F(x0)-x0; di=di-1/(hi-1);
    hi=(F(xi-1)-xi-1)/(F(xi)-xi).

Чтобы избежать зацикливания функция прекращает работу после n итераций. Переменная HasRoot=True если необходимая точность e достигнута менее чем за n итераций, параметр m показывает, сколько раз поправка превосходила предыдущую. Если разность F(xi)-xi имела одно и тоже значение дважды подряд, то HasRoot=False. Так же HasRoot=False, если необходимая точность за n итераций недостигнута.

Наверх

Корень уравнения метод половинного деления. Скачать

Процедура находит корень уравнения F(x)=0, где F(x) - непрерывная на отрезке [a,b] функция, удовлетворяющая условию

    F(a)F(b) < 0

Для нахождения корня отрезок [a,b] делится пополам и выбирается тот полуинтервал на концах которого знаки F(x) разные. Затем процесс деления повторяется до тех пор, пока длина интервала не станет меньше e.

Если начальное условие F(a)F(b) < 0 не выполнено, то процедура прекращает работу и переменной HasRoot присваивается значение False. Если корень найден, то HasRoot=True, и корень находится в переменной x.

Наверх

Решение уравнения методом Ньютона (метод касательных). Скачать

Действительный корень x' уравнения F(x)=0 вычисляется методом Ньютона по итерационному уравнению:

    xk+1=xk-F(xk)/F'(xk)

Процесс сходится к точному значению корня, если начальное приближение x1 выбрано так, что

    |F(x1)F''(x1)| < |F'(x1)|2

Оценка погрешности k-го приближения производится по приближенной формуле

    |F(xk)F'(xk)| < e

В процедуре кроме функции F используется также функция DF- производная функции F.

Наверх

Нахождение корней уравнения модифицированным методом Ньютона (метод хорд). Скачать

Если вычисление производной в методе Ньютона затруднено, можно заменить ее вычисление оценкой:

    F'(x)= (F(x+h)-F(x))/h

Кроме ставшей уже обычной в этом разделе точности e, в процедуру так же передается параметр h из предыдущей оценочной формулы для производной.

Наверх

Решение уравнения методом секущих-хорд. Скачать

Если на интервале [a,b] непрерывная функция F(x) удовлетворяет условию F(a)F(b) меньше нуля, то корень уравнения F(x)=0 может быть найден методом секущих:

    xn=xn-1-F(xn-1)(xn-1-xn-2)/(F(xn-1)-F(xn-2)).

Погрешность значения корня оценивается по формуле

    |xn-xn-1| < e
для этого в процедуру передается переменная е.

Если на некотором этапе работы процедуры F(xn)F(xn-1) становится больше 0, то дальнейшие приближения ничего не дадут и процедура завершает поиск корня и выставляет переменную HasRoot=False. Если же HasRoot=True, значит корень найден с заданным приблежением и находится в переменной x.

Наверх

Решение системы уравнений. Скачать

Решение системы трансцендентных уравнений

    x1=F1(x1,x2, . . .,xn),
    x2=F2(x1,x2, . . .,xn),
    . . . .
    xn=Fn(x1,x2, . . .,xn)
Производится по итерационным формулам модифицированного метода Зейделя:
    x1(k+1)=F1(x1(k),x2(k), . . .,xn(k)),
    x2(k+1)=F2(x1(k+1),x2(k), . . .,xn(k)),
    . . . .
    xn(k+1)=Fn(x1(k+1),x2(k+1), . . .,xn-1(k+1),xn(k)).
Оценка точности имеет вид:
    max|xi(k+1)-xi(k)| < e, i=1..n.
Итерационный процесс сходится при условии

В процедуре используются функции F(i,x[1..N]), где i соответствует номеру функции в исходной системе, а вектор x аргумент функции в системе.

Наверх

Разложение полинома на рациональные линейные множители. Скачать

Процедура находит все рациональные линейные множители (Uix+Vi) многочлена

    p(x)=a0xn+a1xn-1+...+an=(U1x+V1)...(Urx+Vr)(d0xn-r+...+dn-r),
где коэффициенты ak - целые, а полином с коэфициентами dk линейных рациональных множетелей не содержит.

В процедуре находятся все делители p и q чисел a0 и an соответственно. Затем при условии, что px-q является множителем многочлена, p(x) делится по алгоритму Евклида на px-q. Получается новый полином, для которого повторяется вся процедура до тех пор, пока не будет получен полином, не имеющий рациональных линейных множителей.

Коэфициенты исходного полинома передаются в процедуру используя массив A, в этот массив на выходе из процедуры помещаются коэфициенты полинома не содержащего линейных рациональных множителей di.


Библиотекa алгоритмов по программированию. Простейшие операции над матрицами.
  • Умножение матриц. Скачать
  • Вероятностная проверка умножения матриц. Скачать
  • Обращение матрицы с помощью расширенной матрицы. Скачать
  • Обращение матрицы методом Гаусса. Скачать
  • Вычисление определителя методом триангуляции. Скачать

Умножение матриц. Скачать

Процедура переножает две матрицы A=(ai j) размера n*m и B=(bi j) размера m*k получая в итоге матрицу C=(ci j) размера n*k. Формула по которой получаем элементы матрицы C следующая:

    сij=ai1b1j+...+aimbmj для i=1..n;j=1..k
Наверх

Вероятностная проверка умножения матриц. Скачать

Алгоритм прислан riiki и мне этот алгоритм очень понравился, надеюсь, что многим он будет полезен.

Допустим нам надо проверить матричное равенство A*B=C, в котором матрицы A,B,C квадратные размера n*n. Для проверки "в лоб" с помощью простого перемножения матриц A,B и затем сравнения полученного результата с матрицей C, потребует выполнение O(n3) операций. Но есть другой вариант - использовать вероятностный алгоритм.

Выберем вектор Y=(y1,...,yn) у которого координаты равны 0 или 1, при этом появление 0 или 1 равновероятно. Сравним A*(B*Y) и C*Y, если равенства нет, то и исходное равенство не выполнено. Если же A*(B*Y)=C*Y, то вероятность того, что A*B < > C меньше 1/2. Таким образом мы можем проверить равенство с необходимой вероятностью.

На вход алгоритм получает матрицы A,B,C и вероятность с которой нам необходимо удостовериться в равенстве, на выходе получаем True или False, соответственно, если равенство выполнено с заданной вероятностью или нет.

Алгоритм использует уже имеющиеся для получения псевдослучайных чисел распределенных равномерно и перемножения матриц. Использование последнего алгоритма обусловлено желанием не перегружать блок-схему, хотя правильние было бы произвести перемножения матрицы на вектор на прямую, подразумевая тот факт, что компоненты вектора принимают значения только 0,1.

Наверх

Обращение матрицы с помощью расширенной матрицы. Скачать

Процедура обращает квадратную матрицу M размером n*n с помощью элементарных операций, которые приводят матрицу M к единичной. Обозначим расширенную матрицу A:

К числу элементарных операций относятся:

  1. Перестановка двух столбцов (строк) матрицы.
  2. Умножение строки (столбца) на k не равное 0.
  3. Сложение двух строк (столбцов).

Поскольку если матрица вырожденна, то у нее не существует обратной в алгоритме вводится дополнительная переменная S, по значению которой можно определить вырождена матрица (S=1) или нет (S=0)

Наверх

Обращение матрицы методом Гаусса. Скачать

Процедура находит, обратную квадратной матрице A размером n*n, по методу Гаусса. Для несобственной матрицы A=(ai j) находится матрица A -1=(xi j) , такая, что

    A A -1=E,
где E- единичная матрица.

Уравнение представляет собой n систем n линейных уравнений для n2 неизвестных xi j. Каждая из систем имеет одну и ту же основную матрицу A и различные свободные члены. Все системы решаются одновременно методом Гаусса (см. метод Гаусса).

В процедуре введена переменная S, если матрица близка к вырожденной, то S=1 и обратная матрица не вычисляется, иначе S=0.

Наверх

Вычисление определителя методом триангуляции. Скачать

Функция вычисляет определитель матрицы det (ai j). Матрица A имеет размер n*n. Триангуляция производится с выбором максимального элемента.

Алгоритм вычисления: а) первом столбце определяется максимальный элемент M1. Если он находится в j-й строке, то первая и j-я строки переставляются. При М1=0 определитель равен нулю; б) затем из элементов ai,j(j>1) вычитаются соответствующие элементы первого столбца, умноженные на a1 j1 1. В результате получим:
где a(1)i j = ai j - ai1 a1 j / a11

К определителю матрицы a(1)i j применяем тот же прием еще (n-2) раза. Окончательно получим:

При перестановке столбцов учитывается изменение знака определителя.


Библиотекa алгоритмов по программированию. Работа с датами.
  • Проверка является ли год високосным.
  • Число лет, месяцев и дней между двумя датами. Скачать
  • Количество дней между двумя датами. Скачать
  • День недели по дате. Скачать
  • Перевод даты в модифицированную юлианскую. Скачать
  • Перевод модифицированной юлианской даты в обычную. Скачать

Проверка является ли год високосным.

Блок-схемы для этой функции не делаю это одно издевательство, но если интересно она входит, как часть, в следующий алгоритм. А при проверке является ли год с номером Year високосным следует помнить, что год считается таковым, если его номер делится нацело на 4, но не делится на 100 или делится нацело на 400, иначе говоря (Year mod 4 = 0) and ((Year mod 100 <> 0) or (Year mod 400 = 0))

Наверх

Число лет, месяцев и дней между двумя датами. Скачать

Этот алгоритм прислан JINX за что ему большое спасибо так ка именно его алгоритм навел меня на мысль создать этот раздел.

Процедура вычисляет число лет, месяцев и дней между двумя датами. Ну вроде, идея понятная и объяснять особенно нечего, реализацию смотрите на блок-схеме. Я не много переделал присланный алгоритм убрав использование встроенных функций и переменных Delphi, а в остальном это тот же алгоритм, который был прислан.

Наверх

Количество дней между двумя датами. Скачать

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

Наверх

День недели по дате. Скачать

Функция вычисляет номер дня недели по дате. При этом Понедельник- имеет номер 1, Вторник - 2, ..., Воскресенье - 7. Структура функции понятна из блок-схемы.

Наверх

Перевод даты в модифицированную юлианскую. Скачать

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

Наверх

Перевод модифицированной юлианской даты в обычную. Скачать

Процедура переводит модифицированную юлианскую дату в привычную нам. Используется совместно с предыдущей функцией.


Библиотекa алгоритмов по программированию. Работа с разреженными матрицами.
  • Конвертация разреженной матрицы из нормальной формы в формат RR(C)O. Скачать
  • Конвертация разреженной матрицы, представленной в формате RR(C)U в нормальную форму. Скачать
  • Транспонирование разреженной матрицы, заданной в формате RR(C)U. Скачать
  • Сложение двух матриц, заданных в формате RR(C)U.(1-й способ) Скачать
  • Сложение двух матриц, заданных в формате RR(C)U.(2-й способ) Скачать
  • Умножение двух матриц, заданных в формате RR(C)U.(1-й способ) Скачать
  • Умножение двух матриц, заданных в формате RR(C)U.(2-й способ) Скачать

Конвертация разреженной матрицы из нормальной формы в формат RR(C)O. Скачать

Процедура конвертирует матрицу содержащуюся в массиве A в формат RR(C)O. Описание формата RR(C)O есть в статье о разреженных матрицах. На выходе получаем: NNZ - число ненулевых элементов матрицы, IA,JA,AN - соответственно массивы используемые в представлении RR(C)O.

Наверх

Конвертация разреженной матрицы, представленной в формате RR(C)U в нормальную форму. Скачать

Описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные N,M - соответственно количество строк и столбцов матрицы, NNZ - число ненулевых элементов матрицы, IA,JA,AN - массивы используемые в представлении RR(C)U. На выходе получаем массив A содержащий искомую матрицу в нормальной форме. В начале работы алгоритм заполняет массив A нулями, в большинстве языков есть специальные команды, чтобы обнулить некоторый кусок памяти, лучше использовать их, так как обнуление массива в двойном цикле скажется на скоросте работы, особенно в случае, если матрица имеет значительные размеры.

Наверх

Транспонирование разреженной матрицы, заданной в формате RR(C)U. Скачать

Описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные N,M - соответственно количество строк и столбцов матрицы, IA,JA,AN - массивы используемые в представлении RR(C)U. На выходе получаем массивы IAT,JAT,ANT содержащий искомую матрицу в форме RR(C)O, количество ненулевых элементов (IA[N]-1 число элементов массивов JA,AN,JAT,ANT) не изменяется, а количество строк исходной матрице равно количеству столбцов транспонированной и наоборот.

Блок-схема является переработкой программы на фортране взятой с сайта библиотеки численного анализа БЧА НИВЦ МГУ.

Наверх

Сложение двух матриц, заданных в формате RR(C)U.(1-й способ) Скачать

Описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные N,M - соответственно количество строк и столбцов матриц, IA,JA,AN - массивы используемые в представлении RR(C)U матрицы A. IB,JB,AB - массивы используемые в представлении RR(C)U матрицы B. На выходе получаем массивы IC,JC,CN содержащий искомую матрицу в форме RR(C)U.

Блок-схема является переработкой программ на фортране взятых с сайта библиотеки численного анализа БЧА НИВЦ МГУ.

Алгоритм вначале формирует портрет матрицы С в массивах IC,JC, а затем заполняет массив CN значениями ненулевых элементов матрицы C. Можно исправить алгоритм сделав так, чтобы формирование портрета матрицы и заполнение массива CN проводилось одновременно, именно так устроен алгоритм, предъявленный ниже.

Есть одна маленькая проблема в работе алгоритма, а именно, если для некоторых i,j выполняется a[i,j]=-b[i,j] < >0, то в представлении результирующей матрицы элемент c[i,j] должен отсутствовать, но данный алгоритм не отслеживает эту ситуацию, поэтому возможно возникновение нулевых элементов в массиве СN.

Возникает вопрос для чего необходимо разбиение алгоритма сложения на два этапа? Все дело в том, что результат получается в формате RR(C)U, т.е. неупорядоченный по столбцам, вне зависимости от того были ли исходные матрицы в формате RR(C)O или нет, но поскольку вначале мы получаем портрет результирующей матрицы, то если после этого привести полученный портрет к формату RR(C)O, например, дважды выполнив алгоритм транспонирования матрицы, учитывая только портрет С, а уже затем заполнять массив CN, то в результате матрица С будет представлена в формате RR(C)O.

Наверх

Сложение двух матриц, заданных в формате RR(C)U.(2-й способ) Скачать

Описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные N,M - соответственно количество строк и столбцов матриц, IA,JA,AN - массивы используемые в представлении RR(C)U матрицы A. IB,JB,AB - массивы используемые в представлении RR(C)U матрицы B. На выходе получаем массивы IC,JC,CN содержащий искомую матрицу в форме RR(C)U.

В отличии от предыдущего, данный алгоритм заполняет массивы IC,JC,NC за один проход, к тому же он проверяет возникновение ситуации, когда a[i,j]=-b[i,j] < >0 и не допускает появления в массиве CN нулевых элементов, правда это скажется на скорости работы.

Результирующая матрица представлена в формате RR(C)U, т.е. неупорядоченная по столбцам.

Наверх

Умножение двух матриц, заданных в формате RR(C)U.(1-й способ) Скачать

Алгоритм перемножает матрицы A размера n*m и B (m*q), заданные в формате RR(C)U и результат помещает в матрицу C, описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные n,m,q - соответствeющие размерности матриц, IA,JA,AN - массивы используемые в представлении RR(C)U матрицы A. IB,JB,AB - массивы используемые в представлении RR(C)U матрицы B. На выходе получаем массивы IC,JC,CN содержащий искомую матрицу в форме RR(C)U.

Блок-схема является переработкой программ на фортране взятых с сайта библиотеки численного анализа БЧА НИВЦ МГУ.

Известно, что элементы матрицы С получаются по формулам:

    сik=ai1b1k+...+aimbmk для i=1..n;k=1..q
Эта формула выражает элемент ci k как скалярное произведение i-й строки матрицы A на k- й столбец матрицы B. Однако поскольку матрица B задана строчным форматом, то к ее столбцам нет непосредственного доступа. Эту трудность можно обойти измененив порядок вычислений попарных произведений. При вычислении cik: при фиксированных i и j элемент ai j умножается на все элементы bjk j -й строки матрицы B; полученные произведения прибавляются к соответствующим компонентам вещественного вспомогательного массива X, начальные значения которых равны нулю. Когда таким образом обработаны все элементы i-й строки матрицы A, массив X содержит полную i-ю строку матрицы C.

Как и в первом способе сложения матриц данный алгоритм вначале вычисляет портрет результирующей матрицы C, а затем заполняет массив CN соответствующими значениями элементов. В связи с этим возможна ситуация (она даже более вероятна чем при сложении), когда в массиве CN появяться нулевые элементы, чтобы исключить такую неприятность используйте второй способ умножения.

Результирующая матрица представлена в формате RR(C)U, т.е. неупорядоченная по столбцам.

Наверх

Умножение двух матриц, заданных в формате RR(C)U.(2-й способ) Скачать

Алгоритм перемножает матрицы A размера n*m и B (m*q), заданные в формате RR(C)U и результат помещает в матрицу C, описание формата RR(C)U есть в статье о разреженных матрицах. На вход подаются переменные n,m,q - соответствeющие размерности матриц, IA,JA,AN - массивы используемые в представлении RR(C)U матрицы A. IB,JB,AB - массивы используемые в представлении RR(C)U матрицы B. На выходе получаем массивы IC,JC,CN содержащий искомую матрицу в форме RR(C)U.

Принципиально алгоритм основан на тех же соображениях, что и предыдущий, однако данный алгоритм заполняет массивы IC,JC,NC за один проход, к тому же он не допускает появления в массиве CN нулевых элементов.

Результирующая матрица представлена в формате RR(C)U, т.е. неупорядоченная по столбцам.


Библиотекa алгоритмов по программированию. Работа с формулами.
  • Введение
  • Преобразование выражения в польскую запись (4 операции). Скачать
  • Преобразование выражения в польскую запись. Скачать
  • Вычисление выражения представленного в польской запись (4 операции). Скачать
  • Преобразование выражения из польской записи в стандартную форму. Скачать

Введение.

На данной странице я постараюсь представить алгоритмы преобразования и вычисления формул, заданных в виде строки символов. Такая проблема возникает достаточно часто, например, в случае если Вам необходимо написать компилятор, Вам не обойтись без вычислителя формул.

Вычислить формулу, заданную в привычном нам виде не так легко, поэтому зачастую вначале необходимо преобразовать ее к виду удобному для вычислений, в связи с этой проблемой на странице представлены два алгоритма, первый преобразует формулы в польскую запись, а второй позволяет вычислять значение формулы в польской записи, при известных значениях переменных входящих в формулу. Алгоритмы несколько облегчены (в них отсутствует обработка функций, обрабатываются только 4 простейших операции), для простоты понимания принципов, но в дальнейшем их можно усовершенствовать.

Кроме непосредственно вычисления формулы (функции) подстановкой в нее значений переменных, возникает задача преобразования формул в символьном виде, например, упростить формулу, разложить в произведение и т.д.

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

Если кто-то знает алгоритмы решения описанных выше задач, и хочет поделиться ими, присылайте буду весьма признателен.

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

Наверх

Преобразование выражения в польскую запись.(4 операции) Скачать

Алгоритм предназначен для преобразования формулы к виду удобному для вычислений, а именно к польской записи. Приведу несколько примеров, для понимания о чем собственно разговор:
Исходная формула | Польская запись
a+b | a b +
a+b*c | a b c * +
(a+b)*c | a b +c *
d*(a+b)*c | d a b + * c *

Алгоритм прислал мне Владимир Кошелев, за что ему большое спасибо, насколько я понимаю, алгоритм обсуждался в конференции RU.ALGORITHMS. Поскольку я не силен в ФИДО (к глубокому своему сожалению), более подробно указать ничего не могу.

Данный алгоритм преобразует формулу помещенную в массив символов Eq длины n, при этом предполагается, что: 1. имена переменных начинаются с символов английского алфавита и содержат только символы и цифры, длина имени переменной произвольна. 2. в формуле используются только 4 арифметические операции: +, -, *, / 3. в формуле допустимо использование скобок вида '(',')'. В случае если алгоритм не может обработать формулу, то в качестве результата выдается "ERROR".

Алгоритм дополнительно использует две функции: 1. function Sym(a:Char):byte; - выдает 0, если аргумент цифра; 1 если аргумент символ английского алфавита; и 2 во всех остальных случаях. 2. function Prior(a:Char):byte; - выдает 0, если аргумент '('; 1 если аргумент ')', '+' или '-'; 2 если аргумент '*' или '/'; и 255 во всех остальных случаях. Так же в алгоритме используется стек, который реализован при помощи массива Stack, а номер элемента на вершине стека задается переменной Top.

Работа алгоритма достаточно тривиальна мы проходим по массиву Eq выделяя пять возможных ситуаций: 1. Символ английского алфавита, значит мы имеем переменную - считываем ее имя и помещаем в результирующую строку. 2. Цифра, значит мы имеем число - считываем его полностью и помещаем в результирующую строку. 3. Открывающаяся скобка '(' - помещаем ее на стек. 4. Закрывающаяся скобка ')' - переносим операции со стека в результирующую строку до момента пока не сняли со стека '(', открывающуюся скобку в результат не помещаем. Если открывающаяся скобка так и не встретилась, значит в исходном выражение неправильно расставлены скобки помещаем в результат "ERROR" и выходим из алгоритма. 5. Операция '+','-','*','/' - переносим в результат операции с вершины стека до тех пор пока стек не пуст и приоритет текущей операции меньше либо равен приритету операции находящейся на вершине стеке. Затем помещаем текущую операцию на стек. После окончания прохода по исходному массиву, переносим операции оставшиеся на стеке в результат. Если на стеке осталась открывающаяся скобка, значит в обрабатываемом выражении содержится ошибка, а следовательно помещаем в результат "ERROR".

Напомню, для тех кто забыл, что принцип хранения информации на стеке "первый пришел последний ушел", т.е. "достаем" элементы из стека в обратном порядке.

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

Наверх

Преобразование выражения в польскую запись. Скачать

Алгоритм является усовершенствованым вариантом предыдущего, отличие заключается в возможности кроме четырех операций (+,-,*,/) обрабатывать дополнительно элементарные функции (я ввел только функции от одной переменной, так как мне сейчас интересен именно этот случай, если кто-то заинтересуется, то без особых затруднений переделает алгоритм на вариант функций многих переменных)

Чтобы определить эту возможность дополнительно введем две функции: 1. function FNToCh(FuncName:string):Char; - функция сопоставляет имени функции некоторый символ. Символы можно выберать произвольно, единственно нельзя использовать: +,-,*,/,^,?, первые пять зарезервированы дл операций сложения, вычетания, умножения, деления и возведения в степень, а последний символ функция выдает в случае когда входному параметру не соответствует ни одна из функций. 2. function ChToFN(a:Char):string; - функция обратная предыдущей.

Для примера я составил табличку определяющую работу функции FNToCh, Вы можете расширить ее введением имен дополнительных функций
FuncName | FNToCh(FuncName)
+ | +
- | -
* | *
/ | /
^ | ^
sin | A
cos | B
tg | C
ctg | D
arcsin | E
arccos | F
ln | G
log | H
exp | I
sqr | J

Так же раширена функция Prior, использовавшаяся в предыдущем алгоритме, все символы отвечающие за вновь введенные функции имеют приритет 3.

Наверх

Вычисление выражения представленного в польской записи (4 операции). Скачать

Алгоритм позволяет вычислить значение выражения представленного в польской записе, при известных значениях входящих в него переменных.

В начале определим, что мы имеем в виду под польской записью, польская запись - постфиксная форма выражения. Четкого определения я нигде не нашел, формулировать самому мне немного лень, но принцип лежащий в основе понятен из примеров:
Исходная формула | Польская запись
a+b | a b +
a+b*c | a b c * +
(a+b)*c | a b +c *
123*(a+b)*c | 123 a b + * c *

Я предполагаю, что элементы (переменные, числа, символы операций) в записе разделены пробелом. Так оно и есть если для перевода в польскую запись использовался предыдущий алгоритм.

Принцип вычисления выражения преобразованного к польской записи, достаточно прост. Проходим все элементы по порядку определяемся если: 1. обрабатываемый элемент переменная, помещаем ее значение на стек. 2. обрабатываемый элемент число, помещаем его на стек. 3. обрабатываемый элемент операция, снимаем со стека два элемента, и выполняем операцию, полученный результат помещаем на стек. В конечном итоге на стеке должен остаться одно число, которое и есть результат вычисления выражения.

В алгоритме используются две функции: 1. function Sym(a:Char):byte; - выдает 0, если аргумент цифра; 1 если аргумент символ английского алфавита; и 2 во всех остальных случаях. 2. function Value(a:string):real; - определяет по имени переменной ее числовое значение.

Я снова привожу несколько упрощенный алгоритм, который допускает в выражении только четыре арифметические операции. Алгоритм допускающий в польской записи функции, несколько сложнее, но мне кажется, что поняв принцип работы Вы без труда его сделаете.

Наверх

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

Алгоритм позволяет преобразовать выражение из польской записи в привычную нам форму. Работа алгоритма практически полностью повторяет работу "вычислителя" для польской записи, поэтому вначале рекомендую прочитать его описание, а затем вернуться сюда. Теперь отличия, во-первых элементы стека теперь не вещественные числа, а строки, во-вторых если раньше мы встретив операцию снимали со стека два числа, выполняли операцию и результат помещали на стек, то теперь мы не выполняем операцию, а создаем строку отражающую действие операции в нормальной форме. Т.е. допустим в исходной строке мы встретили знак '+', мы снимаем со стека два элемента (например 'FirstVar' и 'SecondVar') и помещаем на стек строку 'FirstVar+SecondVar'. Надеюсь все понятно, если не до конца, то посмотрите блок-схему.

Еще одно отличие от "вычислителя" заключается в том, что в данном случае мы допускаем наличие в выражении функций (одной переменной), в случае если мы встречаем имя функции, то действия практически те же, что и для операции, единственно со стека снимается один параметр. В алгоритме используется функция FNToCh описание которой дано в алгоритме преобразования выражения в польскую запись.

И напоследок: в алгоритме используется стек pSt который хранит приоритет операции соответствующий строки со стека Stack (т.е. если например Stack[1]:='23',Stack[2]:='100+x', то pSt[1]:=3, pSt[2]:=2) это необходимо чтобы правильно расставить скобки в выражениях.


Библиотекa алгоритмов по программированию. Решение систем линейных алгебраических уравнений.
  • Решение системы линейных алгебраических уравнений методом Крамера. Скачать
  • Решение системы линейных алгебраических уравнений методом Халецкого. Скачать
  • Решение системы линейных алгебраических уравнений методом Гаусса. Скачать
  • Решение системы линейных алгебраических уравнений методом Гаусса с частичным выбором главного элемента. Скачать
  • Решение системы линейных алгебраических уравнений методом вращений. Скачать
  • Решение системы линейных алгебраических уравнений методом отражений. Скачать

Решение системы линейных алгебраических уравнений методом Крамера. Скачать

Процедура решает неоднородную систему n линейных алгебраических уравнений с n неизвестными:

    a11 x1+a12 x2+ . . .+a1n xn=a1n+1
    a21 x1+a22 x2+ . . .+a2n xn=a2n+1
    .	.	.	.
    an1 x1+an2 x2+ . . .+ann xn=ann+1

Процедура позволяет найти корни, если определитель основной матрицы A=(aij) не равен нулю. Для нахождения i-го корня ищем определитель:
для всех i=1..n. Тогда

В результате получим: если система не имеет решения, то S=0; если система имеет решения S=1, а массив X содержит решения системы. В процедуре вызывается функция вычисления определителя, в качестве которой можно использовать функцию приведенную здесь или другую имеющуюся у Вас.

Наверх

Решение системы линейных алгебраических уравнений методом Халецкого. Скачать

Для удобства рассуждений систему запишем в матричном виде:

    Ax=b
где A=[aij]- квадратная матрица порядка n,
- векторы столбцы. Представим матрицу A в виде произведения нижней треуголной матрицы B=(bij) и верхней треугольной матрицы C=(cij) с единичной диагональю, т.е.
    A=BC
тогда искомый вектор x может быть вычислен из цепи уравнений
    By=b,	Cx=y
так как матрицы В и C - треугольные, то системы легко решаются.

Процедура не проверяет имеет ли система решение.

Наверх

Решение системы линейных алгебраических уравнений методом Гаусса. Скачать

Процедура решает неоднородную систему n линейных алгебраических уравнений с n неизвестными:

    a11 x1+a12 x2+ . . .+a1n xn=a1n+1
    a21 x1+a22 x2+ . . .+a2n xn=a2n+1
    .	.	.	.
    an1 x1+an2 x2+ . . .+ann xn=ann+1

Вначале находим отличный от нуля коэффициент при x1. Соответствующее уравнение переставляем с первым (если это необходимо). Получаем систему с a11 отличным от нуля. Разделив коэффициенты этого уравнения на a11, получим:

    x1+b12 x2+ . . .+b1n xn=b1n+1
При помощи этого уравнения исключаем x1 из исходной системы:
    a(1)22 x2+a(1)23 x3+ . . .+a(1)2n xn=a(1)2n+1
    .	.	.	.
    a(1)n2 x2+a(1)n3 x3+ . . .+a(1)nn xn=a(1)nn+1
где
    a(1)i j=ai j-ai 1b1 j, i,j= 2...n
Полученная система содержит n-1 уравнение. Применяем описанную выше процедуру к этой системе. Операции повторяем требуемое число раз, пока не приведем систему к треугольному виду:
    x1+с12 x2+ . . .+с1n xn=с1n+1
    x2+ . . .+c2n xn=c2n+1
    .	.	.	.
    xn=cnn+1

Теперь легко определить xn,xn-1, . . ., x1.

Если det(A)=0, то исходная система не имеет решений и процедура выдает S=0 иначе S=1 и решения находятся в массиве X.

Наверх

Решение системы линейных алгебраических уравнений методом Гаусса с частичным выбором главного элемента. Скачать

Процедура решает неоднородную систему n линейных алгебраических уравнений с n неизвестными:

    a11 x1+a12 x2+ . . .+a1n xn=a1n+1
    a21 x1+a22 x2+ . . .+a2n xn=a2n+1
    .	.	.	.
    an1 x1+an2 x2+ . . .+ann xn=ann+1

В отличии от предыдущего алгоритма на каждом шаге мы ищем не просто отличный от нуля коэффициент при xk, а максимальный из них по абсолютной величине, в остальном практически таже схема приведения системы к треугольному виду:

    с11x1+с12 x2+ . . .+с1n xn=с1n+1
    с22x2+ . . .+c2n xn=c2n+1
    .	.	.	.
    сnnxn=cnn+1

Если det(A)=0, то исходная система не имеет решений и процедура выдает S=0 иначе S=1 и решения находятся в массиве X. Выбор на каждом шаге максимального по абсолютной величине коэффициента, позволяет получить малые невязки при решении системы.

Наверх

Решение системы линейных алгебраических уравнений методом вращений. Скачать

Вновь решаем систему n линейных уравнений Ax=b. Вначале приведем матрицу A к нижне-треугольному виду преобразованиями вращения:

    A=L*Rn-1 n ... R1 2
здесь L - нижняя треугольная матрица (т.е. элемент li j=0, если j > i), а Ri j - матрица вращения. Матрица вращения это "почти единичная" матрица у которой ri i=rj j=cos(u), и ri j=-rj i=sin(u). Действительно нетрудно проверить, что умножая, например, матрицу 2-го порядка
       | cos(u) sin(u)|
    R= |              |
       |-sin(u) cos(u)|
на некоторый вектор x, мы осуществим поворот этого вектора на угол u относительно начала координат. Заметим, что определитель матрицы врщения равен 1, и Ri j*RTi j=E, т.е. обратная матрица совпадает с транспонированной.

Итак представив исходную матрицу в виде произведения нижней треугольной матрицы на последовательность матриц вращения, мы можем решить вначале систему Ly=b, а затем систему Rn-1 n ... R1 2x=y. Первая система легко решается благодаря простому виду матрицы L, а вторую систему нетрудно разрешить, благодаря свойствам матрицы вращения.

Несколько слов непосредственно о реализации алгоритма. Вначале последовательно для каждого ненулевого элемента расположенного выше главной диагонали матрицы A находится преобразование вращения, которое переводит его в нуль. Для хранения преобразование вращения Ri j достаточно хранить соответствующий угол u, но проще хранить t=tg(2u), тогда

    cos(u)=(1-t2)/(1+t2)
    sin(u)=2t/(1+t2)
В результате последовательности преобразований, в массиве A будет, непосредственно матрица L(a[i,j]=li j, i≥j; li j=0, i< j) и соответствующие преобразование Ri j (a[i,j]=ti j, i<j, здесь ti j - тангес удвоенного угла вращения для преобразования Ri j). Теперь решаем вначале систему Ly=b, а затем из вектора y, получаем решения исходной системы обращая преобразования вращения.
Наверх

Решение системы линейных алгебраических уравнений методом отражений. Скачать

Вновь решаем систему n линейных уравнений Ax=b. Вначале приведем матрицу A к верхне-треугольному виду преобразованиями отражений:

    Qn-1 ... Q2*Q1*A*S = R,
здесь Qi - соответствующие матрицы отражения, S -результирующая матрица перестановок, R - верхняя треугольная матрица.

Теперь решив треугольную систему

    R*Y=Qn-1 ... Q2*Q1*b
нетрудно определить решение исходной системы
    X=S*Y

Чуть подробнее о реализации алгоритма. Вначале находим преобразования отражения, применяя их к матрице A и вектору b. Затем решаем полученную систему, помещая решение в вектор X, и, наконец, переставляем элементы вектора X используя вектор S, который содержит информацию о перестановках в исходной матрице A.


Библиотекa алгоритмов по программированию. Сортировка.
  • Поиск наименьшего элемента массива. Скачать
  • Сортировка массива по возрастанию. Скачать
  • Сортировка массива по возрастанию (метод пузырька). Скачать
  • Сортировка массива по возрастанию (метод простых вставок). Скачать
  • Сортировка массива по возрастанию (метод бинарных вставок). Скачать
  • Сортировка массива методом Шелла. Скачать
  • Сортировка массива по возрастанию (метод Уильяма Флойда, бинарных деревьев). Скачать
  • Сортировка массива по возрастанию (метод фон Неймана, слияний). Скачать
  • Поиск k-го по величине элемента массива. Скачать

Поиск наименьшего элемента массива. Скачать

Ищет наименьший элемент в массиве простым перебором. Если заменить знак "<" на ">", то можно искать наибольший элемент.

Наверх

Сортировка массива по возрастанию. Скачать

Это наиболее естественный алгоритм упорядочивания.

Допустим, что элементы a1,...,ai-1 уже упорядочены, тогда среди оставшихся (ai,...,an) находим минимальный элемент и меняем его местами с i-тым элементом. И т.д. пока массив не будет полностью упорядочен.

Благодарю Alex Maximenko за то, что он прислал мне этот алгоритм.

Наверх

Сортировка массива по возрастанию (метод пузырька). Скачать

Последовательно просматриваем числа a1,...,an находим наименьшее i такое, что a i > ai+1. Поменять ai и ai+1 местами,возобновить просмотр с элемента ai+1 и т.д. Тем самым наибольшее число передвиниться на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра в котором участвовали только первый и второй элементы.

Наверх

Сортировка массива по возрастанию (метод простых вставок). Скачать

Последовательно просматриваем a2,...,an и каждый новый элемент ai вставляем на подходящее место в уже упорядоченную совокупность a1,...,ai-1. Это место определяется последовательным сравнением ai с упорядоченными элементами a1,...,ai-1.

Наверх

Сортировка массива по возрастанию (метод бинарных вставок). Скачать

Этот алгоритм представляет из себя оптимизированную версию предыдущего, отличие заключается в том, что при поиске место, на которое надо вставить элемент ai в уже упорядоченную совокупность a1,...,ai-1, определяется алгоритмом деления пополам (отсюда и название алгоритма "бинарные вставки" здесь понимаем как "вставка делением пополам").

Наверх

Сортировка массива методом Шелла. Скачать

Данный алгоритм прислан мне Широковым А.В за что ему большое спасибо. Присылайте больше и чаще.

Описывать алгоритм не буду, смотрите блок-схему алгоритм простой как все гениальное.

Наверх

Сортировка массива по возрастанию (метод Уильяма Флойда, бинарных деревьев). Скачать

Алгоритм основан на представлении массива в виде бинарного дерева, обладающего особыми свойствами. В памяти компьютера все элементы массива расположены последовательно, структура же дерева определяется следующим образом: будем считать, что i элемент массива ("предок") имеет два элемента потомка с номерами 2i и 2i+1. Дерево имеет нормальную форму, если любой элемент предок больше своих потомков.

Для понимания алгоритма рассмотрите приведенную блок-схему. Из свойств алгоритма стоит заметить, что он дает стабильно хорошую скорость упорядочивания (порядка n log(n)), вне зависимости от того с каким массивом работает, и поэтому используется в случаях когда необходимо гарантировано упорядочить массив за короткое время.

Наверх

Сортировка массива по возрастанию (метод фон Неймана, слияний). Скачать

Алгоритм фон Неймана упорядочивания массива (алгоритм сортировки слияниями) основан на многократных слияниях уже упорядоченных групп элементов массива. Вначале весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждой. Слиянием соседних групп получаем упорядоченные группы, каждая из которых содержит два элемента (кроме, возможно, последней группы которой не нашлось парной). Далее, упорядоченные группы укрупняются тем же способом и т.д.

Алгоритм дает хорошие показатели по скорости работы, даже в сравнении с сортировкой методом бинарных деревьев. Единственный недостаток - необходимость использовать дополнительный массив того же размера.

Реализацию данного алгоритма мне прислал Alex Kochnev.

Наверх

Поиск k-го по величине элемента массива. Скачать

Алгоритм ищет в массиве M, состоящем из n элементов, k-ый по величине элемент. Эту задачу можно решить упорядочив массив и взяв элемент M[k], но упорядочивание имеет скорость не лучше O(n log n), данный же алгоритм, и это можно достаточно строго доказать, имеет скорость работы O(n).

Каждый шаг работы алгоритма состоит из двух этапов и приводит к сокращению числа рассматриваемых элементов n.

Первый этап. Поиск некоторого "среднего" элемента в массиве M, который осуществляется следующим образом: разобьем массив М на части по 5 элементов в каждой и упорядочим подмассивы по неубыванию. Из средних элементов подмассивов (элементов с номером 3) составим новый массив, с которым проделаем то же самое, будем осуществлять этот алгоритм пока не останется один элемент, который мы помещаем в переменную med и переходим ко второму этапу.

Второй этап. Просматривая элементы массива M, перегруппируем их так, чтобы вначале шли элементы меньшие или равные med, а затем большие med. Допустим первая часть массива содержит j элементов (соответственно вторая n-j). Если k < j, то искомый элемент содержиться в первой половине массива, тогда полагаем n=j и возвращаемся к первому этапу. Если k > j, то искомый элемент находится во второй части массива, тогда переносим n-j последних элементов в начало массива, полагаем n=n-j; k=k-j и возращаемся к первому этапу.

Продолжаем до того момента пока n не станет меньше 5, когда это произойдет просто упорядочим оставшиеся элементы (их меньше 5) и элемент с номером k, будет искомым.

Принцип построения алгоритма прислан riiki, но он предлагал использовать рекурсию и два дополнительных массива, надеюсь, что то что я избавился от рекурсии не сократит скорость работы.


Библиотекa алгоритмов по программированию. Суммирование рядов.
  • Сумма ряда Фурье. Скачать
  • Сумма ряда по Эйлеру. Скачать

Сумма ряда Фурье. Скачать

С помощью процедуры суммируется n слагаемых рядов Фурье:

Вычисление значений cos(rw) и sin(rw) производится на основании рекурентных соотношений:

    t0=0; t1=1; tr=sin(rw)/sin(w)=2 cos(wtr-1)- tr-2 (r > 1);
    sin(rw)=tr sin(w); cos(rw)=tr+1 - trcos(w).

Из этих выражений получим
Наверх

Сумма ряда по Эйлеру. Скачать

Функция находит сумму ряда [image] с помощью преобразования Эйлера. Суммирование производится до тех пор, пока t1 раз подряд абсолютные значение слагаемых преобразованного ряда будут меньше чем e, где е - погрешность суммирования.


Библиотекa алгоритмов по программированию. Теория графов.
  • Введение.
  • Путь с минимальным количеством промежуточных вершин.(волновой алгоритм) Скачать
  • Путь минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Дейкстры) Скачать
  • Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин.(алгоритм Флойда) Скачать
  • Нахождение K путей минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Йена) Скачать
  • Построения минимального остовного дерева (Алгоритм Краскала) Скачать

Введение.

На этой странице рассматриваются алгоритмы работы с графами. Граф - пара G=(V,E), где V - множество вершин (вершинами могут быть объекты произвольной природы) и E - множество ребер, ребра - элементы вида e=(vi,vj), где vi,vj принадлежат множеству вершин, т.е. ребро это элемент из декартова произведения множества V на себя. Достаточно подробно терминология теории графов разобрана на странице А.Чернобаева, поэтому за более полной информацией можно обратиться туда, там же можно найти алгоритмы для работы с графами, как те которые представлены здесь, так и многие другие. Нам же для дальнейшей работы понадобится рассмотреть способы задания и структуры для хранения информации о графе.

Первый способ задания графа (невзвешенного) это задать матрицу связности S размера n*n, где n количество вершин графа, т.е. мощность множества V, при этом элемент si j=1, если существует ребро из i-ой в j-ую вершины и si j=0, если такого ребра нет. Нетрудно видеть, что матрица S- симметрична, если граф неориентированный, и может быть не симметричный в противном случае. При этом полагаем, что si i=0, т.е. в графе нет петель. Такой способ задания графа используется например в волновом алгоритме.

Второй способ используется для задания взвешенного графа, т.е. графа каждому ребру которого соответствует некий параметр - вес. Для определения такого графа используется матрица весов W размер которой n*n, где n количество вершин графа. При этом элемент wi j равен весу ребра соединяющего i-ую и j-ую вершины. Если такого ребра нет, то wi j полагаем равным бесконечности (на практике это максимальное число возможное на данном языке программирования). Этот способ задания используется например в алгоритмах поиска пути во взвешенном графе.

Наверх

Путь с минимальным количеством промежуточных вершин.(волновой алгоритм) Скачать

Процедура находит один из минимальных путей (здесь путей проходящих через минимальное количество вершин) в графе G=(V,E) заданном матрицей связности S. Путь ищется из вершины номер u1 к вершине номер u2. Процедура использует волновой алгоритм.

Волновой алгоритм заключается в следующем:

  1. каждой веpшине i пpиписывается два целых числа T[i] - вpеменная метка и P[i] - метка предыдущей вершины пути (начальное значение T[i]=0, P[i]=0 для всех i);
  2. заводятся два списка "фpонта волны" NF и OF, а также пеpеменная T (текyщее вpемя);
  3. OF:={u1}; NF:={}; T:=1;
  4. для каждой из веpшин i, входящих в OF, пpосматpиваются соседние веpшины j, и если T[j] = 0, то T[j]=T, NF=NF + {j}; в переменную P[j] заносится номер i.
  5. если NF = {}, то пyть не сyществyет, переход к шагу 8;
  6. если одна из веpшин совпадает с u2, то найден кpатчайший пyть длины T, переход к шагу 8;
  7. OF:=NF; NF:={}; T:=T+1; возврат к шагу 4.
  8. Восстанавливаем путь проходя массив P.

В качестве OF, NF я использую массивы размера n (количество вершин в графе), некоторые языки (например Pascal) позволяют работать с объектами типа множества, тогда правильнее использовать именно такую структуру для определения OF, NF, но для того чтобы не нарушать общности я все же остановился именно на массивах, которые присутствуют практически во всех языках программирования.

На выходе имеем переменную length, которая определяет длину пути (length=-1 если пути не существует, length=0, если u1=u2) и массив Path содержащий последовательность номеров вершин определяющих путь.

Наверх

Путь минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Дейкстры) Скачать

Процедура находит путь минимального веса в графе G=(V,E) заданном весовой матрицей w у которой элемент wi j равен весу ребра соединяющего i-ую и j-ую вершины. При этом предполагается, что все элементы wi j неотрицательны. Путь ищется из вершины номер u1 к вершине номер u2. Процедура использует алгоритм Дейкстры. Для бесконечности используется число GM его можно задавать в зависимости от конкретной задачи.

Алгоритм по которому происходит поиск заключается в следующем:

  1. всем веpшинам пpиписывается вес - вещественное число, d(i)=GM для всех вершин кроме вершины с номером u1, а d(u1)=0;
  2. всем веpшинам пpиписывается метка m(i)=0;
  3. вершина u1 объявляется текущей - t=u1
  4. для всех вершин у которых m(i)=0, пересчитываем вес по формуле: d(i):=min{d(i), d(t)+W[t,i]}
  5. среди вершин для которых выполнено m(i)=0 ищем ту для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует; ВЫХОД;
  6. иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t)=1)
  7. если t=u2, то найден путь веса d(t),ВЫХОД;
  8. переходим на шаг 4.

На выходе имеем переменную length, которая определяет длину пути (length=-1 если пути не существует, length=0, если u1=u2), переменную Weight -вес пути и массив Path содержащий последовательность номеров вершин определяющих путь. В алгоритме не упомянуто, как же определить сам путь, но это легко выяснить, если посмотреть блок-схему.

Наверх

Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин.(алгоритм Флойда) Скачать

Процедура находит пути минимального веса в графе G=(V,E) заданном весовой матрицей w у которой элемент wi j равен весу ребра соединяющего i-ую и j-ую вершины. При этом полагаем, что W[i,i]=0 для всех i. Путь ищется для всех пар вершин графа. Для бесконечности используется число GM его можно задавать в зависимости от конкретной задачи.

Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее надо заметить, что если граф неориентированный (W[i,j]- симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым)

Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы d[i,j] которой представляют из себя вес минимального пути соединяющего i и j вершины. Рассмотрим преобразования матрицы весов:

    D0=W
    dm+1[i,j]=min{dm[i,j], dm[i,(m+1)] + dm[(m+1),j]}, где i<>j; dm+1[i,i]=0.
преобразование проделывается для m=1..n, где n - мощность множества вершин графа. Если на некотором шаге получим отрицательное dm[i,m]+dm[m,i] для какого-нибудь i, то в графе существует контур отрицательного веса, проходящий через вершину i и задача не разрешима.

На выходе получаем матрицу D минимальных весов и матрицу P при помощи которой можно востановить путь минимального веса следующим образом: значение p[i,j] будет равно номеру предпоследней вершины в пути между i и j (либо p[i,j]=i, если путь не существует). Переменная s на выходе равна 1, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.

Заметим, что если граф неориентированный, то W а также все матрицы получаемые в результате преобразований симметричны и следовательно достаточно вычислять только элементы расположенные выше главной диагонали.

Наверх

Нахождение K путей минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Йена) Скачать

Алгоритм предназначен для нахождения К путей минимальной длины во взвешеном графе соединяющих вершины u1,u2. Ищутся пути, которые не содержат петель. Алгоритм прислал Pavel Mikheyev

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

Работа алгоритма начинается с нахождения кратчайшего пути, для этого будем использовать уже описанный алгоритм Дейкстры. Второй путь ищем перебирая кратчайшие отклонения от первого, третий кратчайшие отклонения от второго и т.д. Более точное пошаговое описание: 1. Найти минимальный путь P1=(v11,...,v1L[1]) .Положить k = 2. Включить P1 в результирующий список. 2. Положить MinW равным бесконечности. Найти отклонение минимального веса, от (k–1)-го кратчайшего пути Pk-1 для всех i=1,2,...,L[k-1], выполняя для каждого i шаги с 3-го по 6-й. 3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Pk-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2,...,k–1). Если да, положить W[vk-1i,vji+1] равным бесконечности в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результат одних и тех же путей). 4. Используя алгоритм нахождения кратчайшего пути, найти пути от vk-1i к u2, исключая из рассмотрения корни (vk-11,...,vk-1i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам входящим в корень. 5. Построить путь, объединяя корень и найденное кратчайшее ответвление, если его вес меньше MinW, то запомнить его. 6. Восстановить исходную матрицу весов W и возвратиться к шагу 3. 7. Поместить путь минимального веса (MinW), найденый в результате выполнения шагов с 3 по 6, в результирующий список.Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.

Алгоритм использует массив p для результирующего списка путей, и массив length для хранения соответствующих длин, при этом если начиная с некоторого i элементы length[i] равны -1, значит существует только i-1 кратчайшех путей без петель.

Наверх

Построения минимального остовного дерева (Алгоритм Краскала) Скачать

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

Вначале опишем алгоритм (возможно не достаточно строго), а затем обсудим какой способ задания графа был бы наилучшим в данном случае, а так же покажем как от тех способов задания, которые мы использовали ранее перейти к способу применимому здесь.

Итак алгоритм Краскала:
1. Сортируем ребра графа по возрастанию весов.
2. Полагаем что каждая вершина относится к своей компоненте связности.
3. Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем:

Если вершины, соединяемые данным ребром лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву.

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

Предположим, что как и ранее граф задается матрицой весов W (см. введение), ясно, что в данном случае работать непосредственно с матрицей весов не удобно, это выявляется уже на этапе упорядочивания ребер по весу, поэтому вначале выделим массив ребер с соответствующими весами. В нашем случае достаточно если ребро будет иметь три свойства: начальная вершина, конечная вершина и вес (вообще работа с графами хорошо реализуется методами ООП, но поскольку мы не используем расширения языков, то будем работать с простыми массивами). Для задания набора ребер используем два массива E: array [1..m,1..2] of integer - здесь m - количество ребер (m<n2-n+1, где n - количество вершин), и массив EW: array [1..m] of real, тогда ребро ei, соединяющее вершины u,v с весом wi будет соответствовать элементам E[i,1]=u,E[i,2]=v,EW[i]=w. Таким образом до начала непосредственно поиска минимального остовного дерева нам необходимо пройти матрицу весов W и заполнить массивы E и EW.

Преобразовав представление графа от весовой матрицы к набору ребер (часто граф изначально задается при помощи списка ребер, и тогда предыдущая часть алгоритма становиться не нужна), мы уже можем легко упорядочить ребра по неубыванию весов, я для этого использую в блок-схеме алгоритм пузырька, чтобы не "замазывать" основной алгоритм, но можно легко перейти и к другим способам упорядочивания. Далее в алгоритме вводиться массив V:array [1..n] of integer элементы, которого характеризуют номер компоненты связности соответствующих вершин (две вершины u1,u2 лежат в одной компоненте связности, если и только если V[u1]=V[u2]). Теперь все структуры используемые в алгоритме описаны, и его работу легко будет понять из блок-схемы.

В заключении еще только одно замечание. В алгоритме используется переменная q, которая инициализируется значением n-1(на единицу меньше числа вершин) и затем, при объединении двух компонент связности на шаге 3, q уменьшается на единицу, таким образом когда (если) q на некотором шаге занулиться, то это будет означать, что все вершины лежат в одной компоненте связности и работа алгоритма завершена.

Найденое дерево будет определено с помощью массива WO - матрицы весов.


Библиотекa алгоритмов по программированию. Теория чисел.
  • Наибольший общий делитель двух целых чисел (алгоритм Евклида). Скачать
  • Наибольший общий делитель двух целых чисел (бинарный алгоритм Евклида). Скачать
  • Наибольший общий делитель двух целых чисел (расширенный алгоритм Евклида). Скачать
  • Наименьшее общие кратное двух целых чисел. Скачать
  • Решето Эратосфена для нахождения простых чисел. Скачать
  • Сложение двух целых чисел в системе с основанием счисления p. Скачать
  • Сравнение двух целых положительных чисел в системе счисления с основанием p. Скачать
  • Разность двух целых положительных чисел в системе счисления с основанием p. Скачать
  • Произведение двух целых положительных чисел в системе счисления с основанием p. Скачать
  • Частное и остаток при делении двух целых положительных чисел в системе счисления с основанием p. Скачать
  • Перевод числа из системы счисления с основанием p в систему счисления с основанием q. Скачать

Наибольший общий делитель двух целых чисел (алгоритм Евклида). Скачать

Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее по модулю число, которое делит эти два числа. По определению НОД(0,0)=0.

Данный алгоритм вычисления НОД двух целых чисел a и b состоит в следующем: если хотя бы одно из чисел равно нулю, то НОД(a,b)=|a+b|, в других случаях последовательно находятся остатки ri от делений:

    a на b-a=bq1+r1,
    b на r1-b=r1q2+r2,
    r1 на r2-r1=r2q3+r3,
    . . . . . .
и т.д., пока rn+1 не станет равно нулю. Тогда НОД(a,b)=НОД(b,r1)=НОД(r1 ,r2)=...=НОД(rn-1 ,rn )=rn.
Наверх

Наибольший общий делитель двух целых чисел (бинарный алгоритм Евклида). Скачать

Данный алгоритм вычисления НОД(a,b) основан на бинарном алгоритме Евклида. Вычисления проводятся на основании следующих свойств НОД:

    НОД(2m,2n)=2 НОД(m,n),
    НОД(2m,2n+1)= НОД(m,2n+1),
    НОД(-m,n)= НОД(m,n).
Наверх

Наибольший общий делитель двух целых чисел (расширенный алгоритм Евклида). Скачать

Алгоритм, кроме поиска НОД двух целых чисел a,b также находит величины x,y, т.ч. ax+by=НОД(a,b). Алгоритм включает в себя алгоритм Евклида и похож на алгоритм решения диофантового уравнения, который рассматривается здесь. Привожу его поскольку часто возникает необходимость отыскать именно x,y удовлетворяющие приведенному выше условию.

Наверх

Наименьшее общие кратное двух целых чисел. Скачать

Наименьшим общим кратным двух целых чисел a и b называется наименьшее положительное число, которое делится на a и b.

Известно, что

    НОК(a,b)=ab/НОД(a,b).

Сначала в функцие вычисляется НОД(a,b), затем НОК по предыдущей формуле. При a=0 или b=0 НОК полагается равным 0.

Наверх

Решето Эратосфена для нахождения простых чисел. Скачать

В последовательности чисел 2,3, ... , n последовательно вычеркиваем каждое второе число после 2. Первое незачеркнутое число простое (3). Далее вычеркиваем каждое третье число после 3. Первое незачеркнутое число простое (5). Затем вычеркиваем каждое пятое число после 5 и т.д. до тех пор, пока не дойдем до числа, большего корня из n (известно, что если целое положительное число n неравное 1 не делится ни на одно положительное простое число, не большее корня из n то оно простое). Все числа, которые остаются, простые. Такой метод нахождения простых чисел называется решетом Эратосфена.

Колличество простых чисел r не превышает:

    trunc(1.6n/ln n+1), если n<=200;
    trunc(n/(lnn-2)+1), если n>200.

Процедура заполняет массив P простыми числами меньшими n, элемент массива является последним, если следующий за ним элемент равен 0.

Наверх

Сложение двух целых положительных чисел в системе с основанием p. Скачать

Алгоритм складывает два целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

    A=anpn+an-1pn-1+...+a0,
    B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Сумма помещается в массив C, а колличество разрядов суммы представленно переменной l.

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

Наверх

Сравнение двух целых положительных чисел в системе с основанием p. Скачать

Алгоритм сравнивает два целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

    A=anpn+an-1pn-1+...+a0,
    B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Результат работы функции -1,0,1 соответствует случаям A < B, A=B, A > B.

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

Наверх

Разность двух целых положительных чисел в системе с основанием p. Скачать

Алгоритм вычисляет разность двух целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

    A=anpn+an-1pn-1+...+a0,
    B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Результат работы помещается в массив С, колличество разрядов разности представленно переменной l, знак разности совпадает с знаком sign.

Всю информацию об алгоритме можно получить из блок-схемы.Используется описанный ранее алгоритм сравнения.

Наверх

Произведение двух целых положительных чисел в системе с основанием p. Скачать

Алгоритм вычисляет произведение двух целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

    A=anpn+an-1pn-1+...+a0,
    B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Результат работы помещается в массив С, колличество разрядов произведения представленно переменной l.

Всю информацию об алгоритме можно получить из блок-схемы.

Наверх

Частное и остаток при делении двух целых положительных чисел в системе счисления с основанием p. Скачать

Алгоритм вычисляет частное и остаток при делении двух целых числа A и B представленных в системе счисления с основанием p. Цифры p-ичного разложения чисел хранятся в массивах a и b при этом число A имеет n разрядов, а число B - m.

    A=anpn+an-1pn-1+...+a0,
    B=bmpm+bm-1pm-1+...+b0.

Элементы массивов - целые в промежутке от 0 до p-1. Частное помещается в массив С, колличество разрядов частного представленно переменной l. Остаток помещается в массив D, колличество разрядов остатка представленно переменной k.

Всю информацию об алгоритме можно получить из блок-схемы. Используются описанные ранее алгоритмы вычитания и сравнения.

Наверх

Перевод числа из системы счисления с основанием p в систему счисления с основанием q. Скачать

Алгоритм переводит число представленное в системе счисления с основанием p в систему счисления с основанием q. Цифры p-ичного разложения числа хранятся в массиве a при этом число в этой системе имеет n разрядов. Полученное представление в системе с основанием q помещается в массив b и имеет m разрядов:

    A=anpn+an-1pn-1+...+a0=bmqm+bm-1qm-1+...+b0.

Элементы массива a - целые в промежутке от 0 до p-1, элементы массива b - целые в промежутке от 0 до q-1. В зависимости от того основание какой системы счисления больше, применяется разные алгоритмы перевода:

1. В случае p > q алгоритм перевода заключается в последовательном делении исходного числа на q (операция осуществляется в системе с основанием p) и заполнения массива b остатками от деления (заполнять начинаем с младшего разряда). Т.е.

    A = A1*q+b0
    A1 = A2*q+b1
    ...
Понятно, что для некоторого k получим Ak=0 и алгоритм завершится.

2. В случае p < q алгоритм перевода заключается в вычислении:

    A=an*pn+an-1*pn-1+a0
при этом операции производим в системе счисления с основанием q.

В принципе в обоих случаях можно использовать алгоритм 2, но если во-втором случае известно представление p в системе с основанием q, то в случае p > q его вначале необходимо получить. Использование алгоритма 1 в случае 2, так же не слишком привлекательно, т.к. если в случае 1, остаток всегда представляется одной цифрой, то в случае 2 такое свойство нарушается.

Полною информацию об алгоритме можно получить из блок-схемы. Используются описанные ранее алгоритмы сложения,сравнения, умножения и деления с остатком.


Библиотекa алгоритмов по программированию. Экстремумы функций.
  • Метод наискорейшего спуска. Скачать
  • Минимизация функции многих переменных методом конфигураций. Скачать

Метод наискорейшего спуска. Скачать

Методом наискорейшего спуска может быть найден минимум функции n переменных F(x1, . . . ,xn) или найдены решения системы уравнений вида:

    Fi(x1,x2, . . .,xn)=0, i=1, . . ,n.

Решение данной системы эквивалентно отысканию равного нулю минимума функции:

Для нахождения минимума F задаем некоторое начальное приближение xi(0) (i=1,...,n) и строим последующие приближения по формуле:
где направления vi(j) и величина шага на j-м шаге соответственно равны:

Все производные вычисляются при xi=xi(j).

Итерационный процесс продолжается до тех пор, пока не будет удовлетворяться условие

    |xi(j+1)-xi(j)| < e (i=1,...,n)
или все производные dF/dxk не станут равны нулю.

В процедуре используются функция F(x:array[1..n] of real):real; - минимизируемая функция; набор функций DF (i:integer;x:array[1..n] of real):real;- производные dF/dxi набор функций DF2 (i,j:integer;x:array[1..n] of real):real;- производные d2F/dxidxj

Наверх

Минимизация функции многих переменных методом конфигураций. Скачать

Пусть задана функция n переменных F(x1,x2, . . ., xn). Поиск минимального значения начинаем с некоторой начальной точки Pi и начального шага S1 i=d. Вычисляем значение функции в точках F(P1,...,Pi-d,...,Pn), F(P1,...,Pi,...,Pn), F(P1,...,Pi+d,...,Pn). Если из этих трех значений функция минимальна в крайней точке, то принимаем ее за начальную, если в средней точке (P1,...,Pi,...,Pn), то она принимается за начальную, а размер шага по xi уменьшается на коэффициент r и становится равным по i-му аргументу S1 i=S1 i r. Вычисления прекращаются, если размер шага по всем аргументам становится меньше d1 или количество вычислений функции F становится больше m2.