|
§ 2.3. Конструирование алгоритмов
Вспомогательные алгоритмы (окончание)
Рассмотрим несколько примеров рекурсивных алгоритмов.
 Пример 3. Алгоритм вычисления степени с натуральным показателем n для любого вещественного числа а можно представить в виде рекурсивного:
n-я степень числа а есть не что иное, как произведение аn-1 • а; в свою очередь, аn-1 = аn-2 • а и т. д.
Пример 4. Рекурсивный алгоритм положен в основу эффективно го решения головоломки «Ханойская башня».
 Интерактивная игра «Ханойские башни» (195747) поможет вам вспомнить условие и алгоритм решения головоломки (http://sc.edu.ru/).
Пример 5. Рассмотрим алгоритм построения геометрической фигуры, которая называется снежинкой Коха. Шаг процедуры построения состоит в замене средней трети каждого из имеющихся отрезков двумя новыми такой же длины, как показано на рисунке:
С каждым шагом фигура становится всё причудливее. Граница снежинки Коха — положение кривой после выполнения бесконечного числа шагов.
 Попробуйте подсчитать, сколько рёбер в границе снежинки Коха после четвёртого шага; после пятого шага.
| САМОЕ ГЛАВНОЕ
Один из основных методов конструирования алгоритмов — метод последовательного построения алгоритма. Его суть состоит в том, что: исходная задача разбивается на несколько частей, каждая из которых проще всей задачи, и решение каждой части формулируется в отдельной команде; если получаются команды, выходящие за пределы возможностей исполнителя, то они представляются в виде совокупности ещё более простых предписаний. Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.
Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.
Алгоритм, в котором прямо или косвенно содержится ссылка на него же как на вспомогательный алгоритм, называют рекурсивным.
|
<<< К началу
| 
