Тема: Итерация и рекурсия

Тема: Итерация и рекурсия.

Цели урока:

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

Ход урока.

Организационный момент.
Актуализация знаний.

Как найти факториал числа?

N!=1*2*…*(N-1)*N

Какими способами можно решить данную задачу, используя компьютер?

Итерация и рекурсия

Какая функция является рекурсивной?

Рекурсивной называется функция которая обращается сама к себе?

Какая алгоритмическая конструкция используется при итерации

Цикл с параметром

В чем преимущество рекурсии?

Она позволяет экономить оперативную память.

Практическая работа.

Создание графического интерфейса проекта на языках Visual Basic .NET, Visual C#, Visual J# и Turbo Delphi

Разместить на форме: текстовое поле TextBox1 для ввода числа;

Список ListBox1 для вывода шагов вычисления факториала в качестве элементов списка;

Надписи для вывода поясняющих текстов;

Для вычисления факториала числа (переменная N) воспользуемся циклом со счетчиком , в котором счетчик цикла (переменная I) будем принимать значения от минимального (1) до максимального значения ( переменной N). В теле цикла будем последовательно в каждом шаге цикла умножать факториал (переменная F) на значение счетчика (переменная I) и выводить из значения в список.

Создание программного кода на языке программирования Visual Basic .NET

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

Dim N, I As Byte, F As Long

Private Sub TextBox1_TextChanged ( ByVal sender As

System.Object, ByVal e As System.EnentArgs)

Handles TextBox1.TextChanged

ListenBox1.Iteams.Clear ()

N = Val (TextBox1.Text)

F = 1

For I = 1 To N

F = F * I

ListenBox1.Items.Add (Str (I) & «! =» & Str (F))

Next I

End Sub

Запуск проекта на языках Visual Basic .NET, Visual C#, Visual J# и Turbo Delphi

Запустить проект на выполнение и ввести в текстовое поле число (например,20).

В списке будут выведены шаги вычисления факториала введенного числа.

Проект «Факториал (рекурсия)». Создать проект, в котором факториал числа вычисляется с использованием рекурсивной функции.

Будем вводить в текстовое поле и выводить шаги вычисления факториала этого числа в список.

Создание графического интерфейса проекта на языках Visual Basic. NET, Visual C#, Visual J# И Turbo Delphi

Разместить на форме:

- текстовое поле Edit1 для ввода числа ;

- список ListBox1 для вывода шагов вычисления факториала в качестве элементов списка;

-надписи для вывода поясняющих текстов.

Формулу для вычисления факториала можно записать следующим образом:

N!=N*(N-1)*(N-2)*…* 2*1=N*(N-1)!

Следовательно, факториал числа N! Равен произведению числа N на факториал числа (N-1)!. В свою очередь, факториал числа (N-1)! -это произведение числа N-1 на факториал числа (N-2)! и.т.д.

Таким образом, если вычисление факториала числа N! Реализовать как функцию, то в теле этой функции должен быть вызов вычисления факториала числа (N-1)!, т.е. получим рекурсивную функцию, так как она вызывает сама себя.

Создание программного кода на языке программирования Turbo Delphi

Для вычисления факториала числа создадим рекурсивную функцию Factorial(N: byte) , аргументом которой является число N. В зависимости от значения числа N с использованием оператора ветвления if…then…else будем вычислять значение функции. Если вызывается с аргументом, равным 1, то она возвращает значение 1, в противном случае она обращается сама к себе и возвращает произведение Factorial(N – 1).

2.Создать рекурсивную функцию, реализующую вычисление факториала:

function Factorial(N: byte): int64

begin

If N = 1

Then Factorial := 1

Else Factorial := Factorial(N -1);

End;

Для вывода шагов вычисления факториала воспользуемся циклом со счётчиком, в котором счетчик чикла( переменная I) будем принимать значения от минимального (1) до максимального ( значение переменной N). В теле цикла будем вызывать рекурсивную функцию, вычисляющую факториал, и выводить значение счётчика цикла и функции в список.

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

Var

I: byte;

N: byte;

Procedure TForm1.Edit1Change (sender: TObject) ;

Begin

N := StrToInt(Edit1.Text);

ListBox1.Item.Clear;

For I := 1 To N Do

Begin

ListBox1/Items/Add(IntToStr(I) + ‘! =’ + IntToStr(Factorial(I)));

End;

Игра «Оптимальная стратегия»

Учащиеся, которые выполнили практическую работу, разбиваются на группы. Каждой группе даю фишки или камешки и предлагаю одну из следующих задач:

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 17 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Два игрока играют в следующую игру. Перед ними лежат три кучки камней, в первой из которых 2, во второй – 3, в третьей – 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет по два камня в каждую из куч. Выигрывает игрок, после хода которого либо в одной из куч становится не менее 15 камней, либо общее число камней во всех трех кучах становится не менее 25. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Даны три кучи камней, содержащих соответственно 2,3 и 4 камня. За один ход разрешается или удвоить количество камней в меньшей куче (если их две – то в каждой из них), или добавить по 1 камню в каждую из всех трех куч. Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.