Образовательный портал

Электронный журнал Экстернат.РФ, cоциальная сеть для учителей, путеводитель по образовательным учреждениям, новости образования

  • Increase font size
  • Default font size
  • Decrease font size
Звезда не активнаЗвезда не активнаЗвезда не активнаЗвезда не активнаЗвезда не активна
 
Методическая разработка

Алгоритмы с возвратом. Задача о 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 с.


 


You have no rights to post comments

 

Экспресс-курс "ОСНОВЫ ХИМИИ"

chemistry8

Для обучающихся 8 классов, педагогов, репетиторов. Подробнее...

 

Авторизация

Перевод сайта


СВИДЕТЕЛЬСТВО
о регистрации СМИ

Федеральной службы
по надзору в сфере связи,
информационных технологий
и массовых коммуникаций
(Роскомнадзор)
Эл. № ФС 77-44758
от 25 апреля 2011 г.


 

Учредитель и издатель:
АНОО «Центр дополнительного
профессионального
образования «АНЭКС»

Адрес:
191119, Санкт-Петербург, ул. Звенигородская, д. 28 лит. А

Главный редактор:
Ольга Дмитриевна Владимирская, к.п.н.,
директор АНОО «Центр ДПО «АНЭКС»