Презентация на тему "Рекурсия"

• выработать умения реализовывать построенные алгоритмы в виде программ на языке программирования Visual Basic 6.0;
• сформировать знания базовых конструкций языка программирования Visual Basic 6.0
• сформировать знания принципов объектно-ориентированного программирования.

Тип урока:
– итоговое занятие по циклическим структурам.
– углубленное знания по циклическим алгоритмам.

Оборудование:

• компьютерный класс, интерактивная доска;
• презентация с опорным материалом для объяснения нового материала (Приложение 1);
• учебник Есипов А.С.. Информатика и информационные технологии для учащихся школ и колледжей;
• Волченков Н.Г. Программирование на Visual Basic 6.0.
• программное обеспечение: приложение Power Point, среда программирования Visual Basic 6.0.

1. Повторение пройденного материала.

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

Циклические алгоритмы делятся на алгоритмы с известным и неизвестным заранее числом повторений. Их условно называют соответственно алгоритмы с циклом типа “для” и алгоритмы с циклом типа “пока”. В обоих случаях окончание циклического процесса определяется поставленным заранее условием.

В циклических алгоритмах типа “для” этим условием служит явно заданное количество повторений. Блок-схемы данных циклических структур показаны на рис. Определить какой алгоритмической структуре они относятся?

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

Слайд 1. Слово “рекурсия” происходит от латинского слова “recursio” – возвращение. Практически все программисты применяют эту структуру для решения интересных задач. Если программа (или функция) обращается сама к себе как к подпрограмме (или функции) непосредственно или через цепочку подпрограмм, то это называется рекурсией. При применении этих структур возникает опасность зацикливания программ, вот почему необходимо усвоить очень важное правило: “В первую очередь, необходимо оформить выход из рекурсии”.

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

Слайд 2. Рекурсия бывает числовая, графическая и символьная.

Слайд 3, 4. Чтобы понять, что такое рекурсия, надо понять, что такое рекурсия.

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

Слайд 5. Рассмотрим задачу. Является ли пять коров стадом, если известно что...

1. 3 коровы – это стадо;
2. стадо из n>3 коров – это стадо из n-1 коровы и еще одна корова.

Слайд 6. Рассмотрим решение этой задачи. Нам не известно является ли стадом 5 коров, но мы можем представить 5 коров как сумму 4 коровы + 1 корова. Является ли стадом 4 коровы, но мы можем представить 4 коровы как сумму 3 коров + 1 корова. Нам известно, что 3 коровы – стадо по условию и 3 + 1 корова тоже стадо по условию. Тогда 4 + 1 – стадо по условию. Вывод 5 коров – это стадо.

Слайд 7. Представьте – ствол дерева пускает новую ветвь, на следующий год он “отдыхает” и только через год пускает еще одну ветвь – точно так же ведет себя каждая ветка. Поэтому сначала имеется только главный ствол, на следующий год – две ветви, еще год спустя – три, потом 5, 8, 13. Полученная последовательность чисел известна как ряд Фибоначчи и занимает важное место в математике. Строгое определение этого ряда чисел звучит так: каждое число ряда, начиная со второго, равно сумме двух предыдущих.

Эдуард Люка назвал именем Фибоначчи числовую последовательность, возникающую в одной довольно тривиальной задаче из “Книги об абаке”, написанной Леонардо в 1202 году. Вот эта задача в том виде, как формулирует ее сам Фибоначчи.

“Пара кроликов через месяц производит на свет другую пару, а потомство они дают со второго месяца после своего рождения. Итак, через месяц будет две пары, через два месяца – три пары, а через четыре месяца – пять, так как к паре, рожденной первой парой, добавятся первые дети от второй пары…”. Продолжая процесс, мы и получим количество пар кроликов по месяцам: 1, 1, 2, 3, 5, 8, 13, 21, 35, 56…

При вычислении значения Fib(6) будут вызваны процедуры вычисления Fib(5) и Fib(4). В свою очередь, для вычисления последних потребуется вычисление двух пар Fib(4), Fib(3) и Fib(3), Fib(2). Можно нарисовать «дерево рекурсивных вызовов».

Можно заметить, что Fib(3) вычисляется три раза. Если рассмотреть вычисление Fib(n) при больших n, то повторных вычислений будет очень много. Это и есть основной недостаток рекурсии – повторные вычисления одних и тех же значений. Кроме того, с рекурсивными функциями связана одна серьезная ошибка: дерево рекурсивных вызовов может оказаться бесконечным и компьютер «зависнет». Важно, чтобы процесс сведения задачи к более простым когда-нибудь заканчивался.

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

Слайд 9.

В графике рекурсия применяется для построения фракталов.

Фрактал – это геометрический объект дробной размерности. Фракталы нельзя нарисовать или вылепить из пластилина – они являются результатом работы некоторых рекурсивных алгоритмов, если те работают бесконечно долго.

Слайд 10.

Для построения геометрического образа, который приближается к фракталу, используется следующий алгоритм. Берется какое-нибудь исходное изображение, по определенному закону создаются уменьшенные копии исходного изображения, которые так же по определенному закону размещаются на плоскости будущего рисунка. Исходное изображение стирается. То же самое рекурсивно проделывается с каждой копией.

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

Конечная картинка зависит только от законов, по которым строились и размещались копии.

Private Sub Треугольник_Серпиньского(d, x1, y1, x2, y2)
If y2 – y1 > d Then ‘Условие выхода из рекурсии
‘Рисование треугольника
Picture1.Line ((x1 + x2) / 2, y1)-(x1, y2):
Picture1.Line ((x1 + x2) / 2, y1)-(x2, y2)
Picture1.Line (x1, y2)-(x2, y2)
‘Вычисление координат трех новых квадратов: координаты верхнего квадрата
x11 = (x1 * 3 + x2) / 4: y11 = y1: x21 = (x2 * 3 + x1) / 4: y21 = (y1 + y2) / 2
‘Координаты левого нижнего квадрата
x12 = x1: y12 = (y1 + y2) / 2: x22 = (x1 + x2) / 2: y22 = y2
‘Координаты правого нижнего квадрата
x13 = (x1 + x2) / 2: y13 = (y1 + y2) / 2: x23 = x2: y23 = y2
Call Треугольник_Серпиньского (d, x11, y11, x21, y21)
Call Треугольник_Серпиньского (d, x12, y12, x22, y22)
Call Треугольник_Серпиньского (d, x13, y13, x23, y23)
End If
End Sub
Private Sub Command1_Click()
Picture1.Scale (-10, -10)-(266, 266)
Call Треугольник_Серпиньского (10, 0, 0, 256, 256)
End Sub

Private Sub Ковер(x1, y1, r)
Picture1.Circle (x1, y1), r, Цвет
r1 = r / 2
If r > 10 Then 'Условие выполнения (завершения) рекурсии
(глубина рекурсии)
x12 = x1: y12 = y1 – r 'Верхний круг
x13 = x1: y13 = y1 + r ‘Нижний круг
x14 = x1 – r: y14 = y1 'Левый круг
x15 = x1 + r: y15 = y1 'Правый круг
Call Ковер(x12, y12, r1) ‘Вызов процедуры Ковер с новыми
Call Ковер (x14, y14, r1) параметрами
Call Ковер (x15, y15, r1)
End If
End Sub
Private Sub Command1_Click()
Picture1.Scale (0, 0)-(500, 500)
Call Ковер(250, 250, 120)
End Sub

3. Самостоятельная работа учащихся.

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

“10 негритят пошли купаться в море,
10 негритят резвились на просторе,
Один из них пропал – и вот вам результат:

9 негритят пошли купаться в море,
9 негритят резвились на просторе,
Один из них пропал – и вот вам результат:

.
.
.

1 (из) негритят пошли(ел) купаться в море,
1 (из) негритят резвились(ся) на просторе,
Один из них пропал – и вот вам результат:
Нет больше негритят!”

Первые три строчки этого стихотворения повторяются 10 раз с небольшими изменением – число негритят уменьшается с каждым разом на единицу. И только когда число негритят уменьшится до нуля, стихотворение заканчивается единственной строчкой “Нет больше негритят!”.

Листинг программы 3. 10 негритят.

Private Sub Negr(k) ' k – число негритят, параметр процедуры
If k = 0 then ' проверка, что число негритят равно 0
print “Нет больше негритят!”
End sub ' выход из рекурсии
End If
print k; “ негритят пошли купаться в море,”
print k; “ негритят резвились на просторе.”
print “Один из них пропал – и вот вам результат:”
print
Call Negr (k-1)‘Вызов процедуры k на единицу меньше
End sub
Call Negr (10)‘Вызов рекурсивной процедуры в головной программе

Работу данной программы можно иллюстрировать следующим рисунком для k=3

4. Рефлексия урока.

После окончания урока студенты получают три цветных листочка: зеленый, желтый и красный. По окончанию урока они сдают преподавателю только один листочек. Результат усвоения, он узнает после обработки количества этих листочков, их можно клеить на доску липким слоем по окончанию урока:

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

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

Использованная литература:

1. А.С. Есипов Информатика и информационные технологии (для учащихся школ и колледжей).
2. А.С. Есипов, Н.Н. Паньгина, М.И. Громада. Информатика. Задачник.
3. Н.Г. Волченков. Программирование на Visual Basic 6.0.
4. Приложение 1 сентября. Информатика.