World-Python.org

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

К недостатка можно отнести то что поиск ведется равномерно по всем направлениям, а не только в направлении цели(это сильно сказывается на производительности), и что не все шаги равны, по крайней мере, шаги по диагонали должны быть длиннее ортогональных. Так же минусом можно считать что в нем не учитывается \»проходимость\» той или иной поверхности: либо можно пройти, либо нет.
Алгоритм поиска в ширину находит кройчаший возможный путь, если он существует.

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

Read more …

Описание алгоритма
   1. Найти наименьшее значение в исходном множестве.
   2. Записать его в начало множества, а первый элемент — на место наименьшего.
   3. Снова найти наименьший элемент в оставшемся множестве и переместить его на второе место. Второй элемент при этом перемещается на освободившееся место.
   4. Продолжать выполнять поиcк и обмен, пока не будет достигнут конец множества. Read more …

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД. Read more …

Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13 и т.д.
Формула:
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2
Пример вычисления:
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F5 = F4 + F3 = 3 + 2 = 5
F6 = F5 + F4 = 5 + 3 = 8
и т.д. Read more …

Факториалом числа называют произведение всех натуральных чисел до него включительно. Например, факториал числа 5 равен произведению 1*2*3*4*5 = 120. Формулу нахождения факториала можно записать следующим образом: n! = 1 * 2 * … * n, где n – это число, а n! – факториал этого числа.
Можно записать немного по-другому: n! = 1 * … * (n-2) * (n-1) * n, т.е. каждое предыдущее число меньше на единицу, чем последующее. Нахождение факториала числа по первой формуле можно реализовать с помощью цикла while, а по второй формуле – с помощью рекурсии. Read more …

1. Проход по неупорядоченному множеству (например, списку). При этом, если последующий элемент меньше предыдущего, то они меняются местами. В итоге, самый «тяжелый» элемент оказывается в конце множества. Пример: дано: 4, 7, 3, 6, 1 меняем: 7 и 3, затем 7 и 6, затем 7 и 1 результат: 4, 3, 6, 1, 7
2. Проход по множеству, исключая последний элемент, т.к. он уже отсортирован. При проходе обмен меньшего последующего на больший предыдущий.
3. Количество проходов по множеству равно количеству элементов минус 1. Последний проход не нужен, т.к. остается один элемент, и его значение меньше остальных. Он «всплыл» в результате предыдущих проходов. Read more …

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

Часто требуется проанализировать какой-то ряд значений и определить количество значений, попавших в каждый определенный диапазон. Например, дан список, содержащий 1000 значений натуральных чисел в диапазоне от 1 до 100. Требуется подсчитать, сколько значений попало в диапазоны от 1 до 20, от 21 до 30, от 31 до 40 и т.д. Полученный таким образом результат можно использовать для построения графиков и диаграмм частот встречаемости значений. Read more …

Решето Эратосфена – это алгоритм нахождения простых чисел до заданного числа n. В процессе выполнения данного алгоритма постепенно отсеиваются составные числа, кратные простым, начиная с 2. Read more …

Перебор делителей – это алгоритм, предназначенный для определения, какое число перед нами: простое или составное.
Алгоритм прост и заключается в последовательном делении заданного натурального числа на все целые числа, начиная с двойки и заканчивая значением меньшим или равным квадратному корню тестируемого числа. Если хотя бы один делитель делит тестируемое число без остатка, то оно является составным. Если у тестируемого числа нет ни одного делителя, делящего его без остатка, то такое число является простым. Read more …