Методическая разработка
Алгоритмы с возвратом. Задача о 8 ферзях.
Практическая реализация
Юркова Татьяна Анатольевна
Введение. Рекурсивные алгоритмы - интереснейшая область в алгоритмизации и программировании. Рекурсивные задачи требуют определенного воображения, просчета ожидаемых результатов на несколько шагов вперед и удивления от изящности возможного решения. Несмотря на то, что применение рекурсивных алгоритмов не всегда оправданно в связи с требуемой динамической памятью, определенные задачи, где используются алгоритмы, ищущие решения не по заданным правилам вычислений, а путем проб и ошибок, для думающих учеников всегда вызывают большой интерес.
Именно таким алгоритмам - алгоритмам с возвратом посвящена данная методическая разработка.
Предварительно дадим основные определения и несколько простых примеров.
Рекурсивные алгоритмы.
Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя.
Несколько примеров из математики:
Факториал числа
n!=(n-1)!*n 0!=1
Степень числа
an=an-1*a a0=1
Числа ряда Фибоначчи
Fibn=Fibn-2+Fibn-1 Fib0+Fib1=1
Приведем программу вычисления n!, воспользуясь предложенным выше определением.
В программе используем рекурсивную функцию F, которая вызывает сама себя.
program Recurs;
Uses Crt
var
x:integer;
Function F(n:integer):integer;
{рекурсивная функция вычисления n!; вызывает сама себя с параметром на 1 меньше}
{вызов прекращается, когда n=0, в этом случае возвращаемый результат 0!=1, F:=1}
begin
if n>0 then F:=F(n-1)*n
else F:=1;
end; {конец тела функции F}
begin {тело программы}
writeln (‘введите число’);
readln (x);
writeln (‘результат=’,F(x));
readln;
end.
Графическая иллюстрация предложена в файле Рекурсия-1.
Алгоритмы с возвратом. Задача о восьми ферзях
Задача о восьми ферзях - хорошо известный пример использования методов проб и ошибок и алгоритмов с возвратами. в 1850 году эту задачу исследовал К.Ф.Гаусс, однакоон ее так и не решил. Для подобных задач характерно отсутствие аналитического решения. В данной разработке (файл Алгоритмы-с-возвратом). предлагается первое знакомство с задачей и ее практическое решение на конкретном примере, конечно, без аналитических выкладок. Данный материал разработан автором этой статьи и адаптирован для учащихся 9-10 класса.
Используемая литература
Никлаус Вирт. Алгоритмы и структуры данных: Перевод с англ. - 2-е изд., испр. - СПб.: Невский диалект, 2001 - 352 с.
Степень числа
an=an-1*a a0=1
Числа ряда Фибоначчи
Fibn=Fibn-2+Fibn-1 Fib0+Fib1=1
Приведем программу вычисления n!, воспользуясь предложенным выше определением.
В программе используем рекурсивную функцию F, которая вызывает сама себя.
program Recurs;
Uses Crt
var
x:integer;
Function F(n:integer):integer;
{рекурсивная функция вычисления n!; вызывает сама себя с параметром на 1 меньше}
{вызов прекращается, когда n=0, в этом случае возвращаемый результат 0!=1, F:=1}
begin
if n>0 then F:=F(n-1)*n
else F:=1;
end; {конец тела функции F}
begin {тело программы}
writeln (‘введите число’);
readln (x);
writeln (‘результат=’,F(x));
readln;
end.
Графическая иллюстрация предложена в файле Рекурсия-1.
Алгоритмы с возвратом. Задача о восьми ферзях
Задача о восьми ферзях - хорошо известный пример использования методов проб и ошибок и алгоритмов с возвратами. в 1850 году эту задачу исследовал К.Ф.Гаусс, однакоон ее так и не решил. Для подобных задач характерно отсутствие аналитического решения. В данной разработке (файл Алгоритмы-с-возвратом). предлагается первое знакомство с задачей и ее практическое решение на конкретном примере, конечно, без аналитических выкладок. Данный материал разработан автором этой статьи и адаптирован для учащихся 9-10 класса.
Используемая литература
Никлаус Вирт. Алгоритмы и структуры данных: Перевод с англ. - 2-е изд., испр. - СПб.: Невский диалект, 2001 - 352 с.
