Одним из древнейших шифров является шифр Цезаря. Этот шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки со своими генералами. Идея данного шифрования заключается в замене всех букв послания на буквы, находящиеся на n позиций от текущей в алфавите.
Архив рубрики ‘Алгоритмы’
Получение списка фундаментальных циклов графа
Дата: 10th Ноябрь 2010. Автор: Maxsbelt. Рубрика: C#, Алгоритмы, ГрафыМетки: алгоритмы, графы, Дискретная математика
В этой статье мы рассмотрим алгоритм получения списка фундаментальных циклов для неориентированного, связного графа без петель. Кроме того, граф не является мультиграфом. Весь алгоритм можно расписать следующим образом:
Определяем, связан ли граф (Если нет — циклов нет);
Строим матрицу смежности остовного дерева графа;
Устраиваем цикл по хордам;
Выводим список фундаментальных циклов графа.
Приступим к реализации алгоритма
Алгоритм Дейкстры
Дата: 9th Июнь 2010. Автор: KAS. Рубрика: ГрафыМетки: алгоритмы, Дискретная математика, ДМ
Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры.
Алгоритм Форда-Белмана
Дата: 8th Июнь 2010. Автор: KAS. Рубрика: АлгоритмыМетки: алгоритмы, Дискретная математика, ДМ
Алгоритм Форда-Белмана для поиска кратчайшего расстояния в графе. private void algFordaBelmana() { int s=Convert.ToInt32(textBox5.Text) — 1; //произвольная вершина графа, которая послужит началом пути int[] D=new int[n]; initGraph(); initMatrixWeight(); if (s < 0 || s >= n) return; for (int i = 0; i < n; i++) { D[i] = A[s, i]; } [...]
Циклом Гамильтона называется путь проходящий через каждую вершину графа только 1 раз. Псевдокод: procedure ГАМИЛЬТ(k) {генерация всех гамильтоновых циклов, являющихся расширением последовательности X[1], . . ., X[k – 1]: массив X — глобальный } begin for y принадлежит ЗАПИСЬ [X[k – 1]] do if (k = n +1) and (y = v0) then write(X[1], . [...]
Рисуем стрелку
Дата: 30th Май 2010. Автор: KAS. Рубрика: АлгоритмыМетки: source, алгоритмы, исходники
Код для отрисовки стрелочки аля вектор //by Makar double u = Math.Atan((double)(y2 — y1) / (x2 — x1)); if (x2 < x1) { u += Math.PI; } int x = Math.Abs(x2 — x1) / 2 + Math.Min(x1, x2); int y = Math.Abs(y2 — y1) / 2 + Math.Min(y1, y2); if (y1 >= y2) { gr.DrawLine(pen, [...]
Циклы Эйлера
Дата: 19th Апрель 2010. Автор: KAS. Рубрика: АлгоритмыМетки: алгоритмы, Дискретная математика, ДМ
Циклом Эйлера называется путь проходящий только 1 раз через каждое ребро графа. Для существования циклов Эйлера необходимо чтобы граф был связанный и все его вершины имели четную степень (кол-во ребер инцидентных вершине четно).
Алгоритм определения числа связности графа
Дата: 11th Апрель 2010. Автор: KAS. Рубрика: АлгоритмыМетки: алгоритмы, Дискретная математика, ДМ
Компонентом связности называют максимально связанный порожденный подграф. Числом связности графа – кол-во компонент связности.