Теоретический материал (Ханойские башни)

1. Ханойские башни

Начнем обсуждение этой темы с задачи о Ханойских башнях. Головоломка “Ханойские башни” состоит из трёх стержней, на один из которых нанизано несколько колец. Все кольца имеют разный диаметр и расположены снизу вверх по убыванию диаметра.

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

 

Вот один из возможных алгоритмов. Пронумеруем кольца сверху вниз числами от 1 до n. Пусть нам нужно переложить n колец с первого стержня на третий. Будем рассуждать по индукции.

Если n=1, то решение задачи очевидно.

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

1.       Перекладываем верхние n-1 колец с первого стержня на второй.

2.       Перекладываем последнее (самое большое) кольцо с первого стержня на третий.

3.       Перекладываем n-1 колец со второго стержня на третий.

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

 

procedure Hanoi (n, i, j, k : integer);      {переложить n колец

с i-го стержня на j-й, использую k-й стержень в качестве вспомогательного}

begin

  if n=1 then writeln (i,’->’,j)

  else begin

    Hanoi(n-1,i,k,j);      {Перекладываем n-1 колец

 с i-го стержня на k-й}

    writeln (i,’->’,j);      {Перекладываем оставшееся кольцо

 с i-го стержня на j-й}

    Hanoi(n-1,k,j,i);      {Перекладываем n-1 колец

 с k-го стержня на j-й}

  end;

end;

 

Обратите внимание: наша процедура вызывает сама себя (но с другими параметрами). Так, Hanoi(2, 1,2,3) вызывает Hanoi(1, 1,3,2) и Hanoi(1, 3,2,1).

 

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

 

Для того, чтобы программа не зацикливалась, рекурсивная процедура должна содержать терминальное условие – условие, при котором новых вызовов функции не происходит. В нашем случае таким условием служит условие n = 1. Уже при n = 3 последовательность вызовов функций будет довольно сложной, но мы пока не будем углубляться в механизмы работы рекурсии, а перейдем к следующей задаче.

2. Наибольший общий делитель

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

 

НОД(a,b)=НОД(a-b,b) при a≥b.

 

Это свойство несложно доказать. Если d – делитель чисел a и b, то на d делится и разность чисел a и b. Обратно, если d является делителем чисел a-b и b, то и их сумма (a-b)+b=a делится на d. Таким образом, всякий общий делитель чисел a и b является общим делителем чисел a-b и b, и наоборот. Поэтому и наибольшие делители у этих пар чисел совпадают.

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

 

function NOD (a,b : integer) : integer;

begin

  if a<b then swap(a,b);      {переставляем большее число

на первое место} 

  if  b=0 then NOD:=a         {терминальное условие: НОД(a,0)=a}

  else NOD:=NOD(a-b,b);

end;

 

Работу алгоритам можно еще ускорить, если воспользоваться формулой

 

НОД(a,b)=НОД(a mod b,b).

 

Алгоритм вычисления НОД по этой формуле называют алгоритмом Евклида.

Заметим, что эта формула верна для всех a и b, но если a<b, то a mod b = a и формула вырождается в тривиальную. Чтобы обойтись без процедуры swap, можно пользоваться формулой НОД(a,b)=НОД(b, a mod b).

function NOD (a,b : integer) : integer;

begin

  if  b=0 then NOD:=a         {терминальное условие: НОД(a,0)=a}

  else NOD:=NOD(b, a mod b);

end;

3. Возведение в степень

Формулировка задачи очень проста: требуется возвести число a в степень n. Проще всего, конечно, умножить число a на себя нужное число раз. Этот алгоритм потребует n-1 умножений. Можно ли существенно ускорить, этот алгоритм? Оказывается, да. Заметим, что если мы хотим вычислить, например, a¹⁰, то, вычислив на некотором шаге a⁵, можно умножить его на себя и, тем самым, сэкономить несколько умножений. Такой трюк можно использовать для любой четной степени, что позволяет написать формулы, аналогичные формуле из предыдущей задачи:

 

Эта формула позволяет написать рекурсивную функцию вычисления степени (не забывая о терминальном условии n=1).

 

 

 

 

Итак, подведём некоторые итоги.

·         Рекурсия – это прием программирования, при котором функция (процедура) вызывает сама себя.

·         Для того, чтобы этот процесс вызовов не зацикливался, в функции обязательно должно быть терминальное условие – при выполнении такого условия процесс рекурсивных вызовов прерывается.

·         Любой рекурсивный алгоритм можно реализовать и не прибегая к рекурсии, но рекурсия позволяет записывать многие алгоритмы в более простой форме. При этом рекурсивные алгоритмы обычно более требовательны к ресурсам (памяти), чем нерекурсивные.