Конспект урока информатики в 10 классе

Подготовил: учитель информатики Жаренова О.А.

Тема урока: «Рекурсия и рекурсивные алгоритмы в ЯП Паскаль»

Цели и задачи урока:

• образовательная

• сформировать у учащихся единую систему понятий, связанных с понятием рекурсии;

• научить применять рекурсивные алгоритмы при решении задач на ЯП Паскаль;

• показать основные приемы использования рекурсии;

• воспитательная

• воспитать аккуратность, внимание, организованность;

• культура вычислительных навыков;

• развивающая

• развить логическое мышление, алгоритмического мышления учащихся;

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

Оборудование: ПК, проектор, экран, презентация «Рекурсия в ЯП Паскаль»

Тип урока: урок изучения нового материала

Этапы урока:

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

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

3. Изложение нового материала

4. Закрепление изученного

5. Подведение итогов и задание на дом

Ход урока:

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

2. Актуализация знаний - беседа с учащимися

3. Изложение нового материала

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

Пример.

Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок». Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.

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

Пример программы с использованием рекурсии

Program Arsac;

Var first: word;

Procedure posledov (i: word);

Begin

Writeln (i);

If i=1 then exit;

If odd(i) then posledov(3*i+1) else posledov(i div 2);

End;

Begin

Write (' введите первое значение '); readln (first);

Posledov (first);

Readln ;

End.

Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.

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

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

4. Закрепление изученного - беседа с учащимися.

5. Подведение итогов и задание на дом - написать программу возведения числа в квадрат, используя соотношение n²= (n-1)²+2n-1