Что такое алгоритм: различия между версиями

Запись алгоритма на формальном языке называется [[w:программа|программой]]. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» — почти синонимы. Небольшое различие заключается в том, что под алгоритмом, как правило, понимают основную идею его построения. Программа же всегда связана с записью алгоритма на конкретном [[w:формальный язык|формальном языке]].

 

 

Приведём для примера простой алгоритм действия пешехода, который

{{Акмар}}

 

 

Конечный набор элементарных объектов может принимать лишь конечное число значений. Так, например, упорядоченный набор 8 бит (один [[w:байт|байт]]}) имеет 255 возможных значений. Из этого простого факта следует очень важное утверждение: среди команд исполнителя не может быть команд сложения или умножения ''произвольных'' натуральных (действительных) чисел.

Она означает следующее: «Запустить процесс вычисления <code>Fibo(n - 1)</code>, затем запустить процесс вычисления <code>Fibo(n - 2)</code>, результаты вычислений сложить и вернуть в качестве результата». Можно считать что в этой строчке исполнитель нашего алгоритма просит другого исполнителя вычислить <code>Fibo(n - 1)</code>, а сам ждёт, когда тот закончит вычисления. Узнаёт у него результат, просит вычислить <code>Fibo(n - 2)</code> и снова ждёт результата. Два полученных результата складывает, возвращает значение суммы как результат и заканчивает работу. Интерес заключается в том, что этот дополнительный исполнитель действует по такому же алгоритму — если его аргумент больше 1, он также вызывает очередного исполнителя для вычисления нужных ему значений. Получается серия вызовов, которые выстраиваются в ''дерево рекурсивных вызовов''.

 

Рис. 1. Дерево рекурсивных вызовов для <math>F_6</math>.

 

Рассмотрим ещё один классический пример на рекурсивные алгоритмы — игру «Ханойские башни», придуманную ещё в 1883 году Эдуардом Люка. Есть три стержня и 64 кольца́, нанизанных на них. В начале все ко́льца находятся на первом стержне, причём все ко́льца разного диаметра, и меньшие ко́льца лежат на бо́льших. За ход разрешается взять верхнее кольцо с любого стержня и положить на другой стержень сверху, при этом запрещается класть большее кольцо на меньшее. Цель игры состоит в том, чтобы переместить всю пирамиду с первого стержня на второй.

 

 

Заметим, что для того, чтобы переместить пирамиду, нам надо будет переместить и самое нижнее большое кольцо. Для этого нам нужно будет, чтобы все остальные ко́льца были на третьем штыре. Значит, чтобы переместить <math>N</math> колец, нам сначала нужно переместить столбик из верхних <math>N-1</math> колец на третий стержень, затем переместить самое большое кольцо с первого на второй и, наконец, переместить столбик из <math>N-1</math> колец с третьего стержня на второй.

 

[[Категория:Журнал «Потенциал»]]

[[Категория:Алгоритмы| ]]