Методические аспекты преподавания основ рекурсии

    else System_fib := '1' + System_fib (n - Fib (index), index-1)

End;

•   Построение центра тяжести выпуклого многоугольника

Моделирование задачи о нахождении центра тяжести выпуклого многоугольника требует от учащихся достаточно высокой математической подготовки. Привлечение геометрического материала подчеркивает многообразие моделей и методов работы с ними [4].

В процессе параметризации задачи целесообразно опираться на знания учащихся о центре тяжести отрезка (точка деления отрезка в отношении 1:1), треугольника (точка деления медиан в отношении 2:1, считая от вершины), а также на формулу вычисления координат точки, делящей отрезок в данном отношении. Для выпуклого n-угольника следует свести задачу к подзадаче о треугольнике, которую, в свою очередь, к подзадаче об отрезке. При этом формулируется база рекурсии:

а) центром тяжести отрезка является его середина.

Декомпозиция описывает построение центра тяжести выпуклого многоугольника с числом вершин не меньшим трех (пусть для определенности вершины последовательно пронумерованы 1, 2,..., n):

б) центр тяжести выпуклого n-угольника - это точка, делящая в отношении (n-1):1, считая от вершины, отрезок, соединяющий центр тяжести выпуклого (n-1)-угольника и вершину с номером n.

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

Const min = 1;

             max = 10;

Type dim = array [min..max] of real;

Var xx,yy: dim;

Генерация массивов здесь не рассматривается.

Procedure Oenter_n (x,y: dim; mi, ma: integer; var cx,cy : real);

Begin

if ma - mi = 1 then begin

      cx := (x[mi]+x[ma])/2;

      cy := (y[mi]+y[ma])/2;

     end

else

   begin

        Center_n (x,y, mi, ma - 1, cx, cy);

       cx := (x[ma] + (ma-1)*cx)/ma;

        cy := (y[ma] + (ma-1)*cy)/ma;

    end;

End;

Рекурсивные методы позволяют разрабатывать алгоритмы и решать такие задачи, как вычисление сложного процента, реализация схемы Горнера, алгоритмов интегрирования, быстрой сортировки массивов, обхода графа, расстановки фигур на шахматной доске и т.д. Высокий уровень математической культуры учащихся позволяет провести анализ, моделирование и формализацию задачи математическими методами, что способствует нахождению рационального алгоритма решения, в частности, разработке рекурсивной триады.

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

 

 

 

2.2. Методические разработки  уроков по изучению основ рекурсии

Урок  «Рекурсия»

Цель: дать учащимся представление о рекурсии и возможностях ее использования.

Задачи:

образовательная: сформировать понятия рекурсивного объекта и рекурсивного определения, познакомить учащихся с рекурсивными алгоритмами, научить ребят составлять программы с использованием рекурсивных функций; выражений на алгоритмический язык;

развивающая: развивать логическое мышление;

воспитательная: воспитывать интерес к предмету

Структура урока

I. Организационный момент

II. Актуализация знаний.

III. Изучение нового материала.

IV. Итог урока. Домашнее задание.

Ход урока

I. Организационный момент

II. Актуализация знаний

1. Как описывается функция?
2. Каковы отличия функции от процедуры?
3. Чем отличаются друг от друга формальные и фактические параметры?
4. Что такое область действия переменной?
5. Чем отличаются друг от друга глобальные и локальные параметры?

III. Изучение нового материала.

Подпрограммы в Turbo Pascal и могут обращаться к самим себе. Такое обращение называется рекурсией. Объект, который частично определяется через самого себя, называется - рекурсивным. Рекурсивные определения как мощный аналитический аппарат используются во многих областях науки, особенно в математике. Для того, чтобы не было бесконечного обращения подпрограммы к самой себе, требуется наличие некоторого условия (условного оператора) в тексте программы, по достижении которого дальнейшее обращение не происходит. Таким образом, рекурсивное программирование может включаться только в одну из ветвей условного оператора, присутствующего в подпрограмме.

Описание процессов  осуществляется с помощью алгоритмов.

2 этапа выполнения  рекурсивных алгоритмов:

1) "погружение" алгоритма  в себя, т. е. применение определения "в обратную сторону", пока не будет найдено начальное определение, не являющееся рекурсивным;

2) последовательное построение  от начального определения до  определения с введенным в  алгоритм значением. 

Некоторые задачи являются рекурсивными по своему определению, поэтому рекурсивные алгоритмы - это точные копии с соответствующего определения.

Пример 1.

Классический пример, без которого не обходятся ни в  одном рассказе о рекурсии, —  определение факториала. С одной  стороны, факториал определяется так: n!=1·2·3·...·n. С другой стороны, Граничным условием в данном случае является n<=1.

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

Function factorial (n: integer): longin t;

begin

if n=l then factorial: =1

else factorial: =n·factorial (n-l);

end.

Найдем 3!. Как же будет  вычисляться факториал этого  числа? Первый вызов этой функции  будет из основной программы (Например, а:= factorial(3)), где переменной а присваиваем значение 3!). Надо заметить, что при каждом обращении к функции будет появляться свой набор локальных переменных со своими значениями, в данном случае - переменная n, для которых выделяется память. А после завершения работы эта часть памяти освобождается и переменные удаляются.

Так как N<>1, то пойдем по ветке Else и функции Factorial присваиваем значение n*Factorial(n-l), то есть надо умножить 3 на значение функции Factorial(2). Поэтому обращаемся второй раз к этой же функции, но передаем ее новое значение параметра -2. Так делаем до тех пор, пока не передадим значение, равное 1. Тогда N=1, а поэтому значение функции Factorials 1. Таким образом, N=1 - это условие, по которому процесс входа в следующую рекурсию заканчивается. Идет возвращение в точку вызова и подстановка в оператор присвоения значения вычисленной функции. То есть возвращаемся в предыдущую функцию для N=2: Factorial:=n·Factorial(n-l), значит, Factorial:=2·l, следовательно, Factorial(2)=2. И возвращаемся дальше n=3: Factorials n·Factorial(n-l), значит, Factorial – 3·2·1, следовательно, Factorial(3)=6.. Таким образом, получаем значение Factorial(3)=6, это значение и присвоим переменной а.

uses crt;

var п: integer; a.longint;

function factorial (n: integer): longint;

begin

if n=l then factorial :=1

else factorial :=n*factorial (n-'l);

end;

begin

clrscr;

writeln('n=');readln(n);

a:=factorial (n);

writeln('a=',a);

readln;

end.

Пример 2.

Нахождение НОД (наибольшего общего делителя) двух натуральных чисел.

Решение.

Есть несколько способов нахождения этого значения. Одним  из них является алгоритм Евклида. Рассмотрим еще один из вариантов его реализации.

Пусть есть два целых  числа а и b.

Если а=b, то НОД(а,b)=а.

Если а>b, то НОД(а,b)=НОД(а-b,b).

Если а<b, то НОД(а,b)=НОД(а,b-а).

Рассмотрим на примере. Найдем наибольший общий делитель чисел 22 и 16.

а	b	Примечание
22	16	так как а>b, то а = а-b
6	16	так как b>а, то b = b-а
6	10	b = b-а
6	4	так как а>b, то а =а-b
2	4	b=b-а
2	2	Так как а = b,то НОД=а

Таким образом, можно  составить следующую функцию и программу:

uses crt;

var a,b:longint;

function nod (a,b:longint):longint;

begin

if a=b then nod: =a else if a>b then nod:=nod(a - b,b)

else nod:=nod(a,b- a)

end;

begin

clrscr;

 writeln('a-b=') ;

readln(a, b);

a:=nod(a,b);

writeln('nod=’, a);

readln;

end.

Пример 3.

Перевод натурального числа из десятичной системы счисления в двоичную.

Для решения этой задачи рассмотрим сначала, как перевести  число из десятичной системы счисления  в двоичную. Пусть есть число 39, которое  и надо представить в двоичной системе. Для этого разделим его на 2, получим целую часть и остаток от деления. Целую часть снова делим на 2 и получаем целую часть и остаток. Так делаем до тех пор, пока целую часть можно делить на 2 (то есть пока она не станет равной 1).

Теперь, начиная с этой единицы, выписываем в обратном порядке все остатки от деления, это и будет запись числа 39 в двоичной системе счисления: 39₁₀=100111₂.

Таким образом можно  переводить любое натуральное число  из десятичной системы счисления  в двоичную, а также и другие системы (например, восьмеричную или шестеричную).

uses crt;

var n.longint;

procedure REC (n:longint);

begin

if n>l then rec(n div 2);

writeln (mod 2);

end;

begin

clrscr;

 writeln('n - ');

readln(n);

rec(n);

 readln;

end.

Результат на экране: 100111.

Первая цифра (1) выводится на экран из последнего вызова, следующая цифра (0) - из предпоследнего и так далее, последняя (1) - из первого. Таким образом, вывод очередной цифры происходит перед тем, как выйти из данной функции.

IV. Домашнее задание;

1. Повторить понятие процедур и функций.
2. Выучить конспект.
3. Написать программу нахождения факториала числа при помощи рекурсивной функции.

 

Урок «Рекурсивные алгоритмы»

Цель: Закрепить  навыки разработки рекурсивных функций (процедур)

Структура урока

I. Организационный момент

II. Актуализация знаний.

III. Решение задач.

IV. Итог урока. Домашнее задание.

Ход урока

I. Организационный момент

II. Актуализация знаний

1. Какое определение называется рекурсивным? Приведите собственные примеры рекурсивных определений.
2. Какой вспомогательный алгоритм (подпрограмма) называются рекурсивными? Приведите собственные примеры содержательных задач, где для решения может быть использован рекурсивный вспомогательный алгоритм.
3. Что такое граничное условие и каково его назначение в рекурсивной подпрограмме?
4. На каком этапе выполнения рекурсивной подпрограммы могут выполняться её операторы?
5. Почему приведённый ниже алгоритм посимвольного формирования строки завершится аварийно?

Function Stroka : String;

Var C : Char;

Begin

     Write('Введите  очередной символ: '); ReadLn(C);

     Stroka:=Stroka+C

End;

На каком этапе выполняются  действия в этом алгоритме?

III. Решение задач

Классическим примером задач с использованием рекурсивных  алгоритмов является задача «Ханойские башни»

В одной из древних  легенд говорится следующее. «В храме  Бенареса находится бронзовая плита  с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разного диаметра из чистого золота так, что наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят диски с одного стержня на другой, следуя законам Брамы:

1. диски можно перемещать с одного стержня на другой только по одному;

2. нельзя класть больший  диск на меньший.

Когда все 64 диска будут  перенесены с одного стержня на другой, и башня, и храмы, и жрецы-брамины  превратятся в прах, и наступит конец света».

Эта древняя легенда породила задачу о Ханойской башне: переместить m дисков с одного из трех стержней на другой, соблюдая «законы Брамы».

Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносе m дисков с  левого стержня на правый.

Задача может быть решена одним перемещением только для одного (m = 1) диска. В общем случае потребуется 2m-1 перемещений.

Построим рекурсивное  решение задачи, состоящее из трех этапов:

a) перенести башню,  состоящую из m – 1 диска, с левого  стержня на средний;

b) перенести один оставшийся  диск с левого стержня на  правый;

c) перенести башню,  состоящую из m – 1 диска, со  среднего стержня на правый.

Таким образом, задача о  перемещении m дисков сводится к задаче о перемещении m – 1 диска. Обращаясь  опять к этому же алгоритму, сведем задачу к перемещению m – 2 дисков. Продолжая этот процесс, получим, в конце концов, задачу о перемещении одного диска. Эта задача решается за один ход. Таким образом, в процессе решения возникают промежуточные задачи: переместить башню из нескольких n дисков с одного стержня на другой.

Обозначим тот стержень, с которого следует снять диски, через s1, на который надеть – через sk, а вспомогательный стержень через sw.

Оформим алгоритм решения  задачи о переносе башни из n дисков с s1 на sk в виде процедуры move с 4-мя параметрами: n, s1, sw, sk; алгоритм для n = 1 выделим в отдельную процедуру step, которая перемещает один диск со стержня s1 на sk.