Презентация "Рекурсия в Паскале" 9 класс скачать бесплатно


Презентация "Рекурсия в Паскале" 9 класс


Подписи к слайдам:
Рекурсия в Паскале

Рекурсия в Паскале

Учитель :

Тлехурай Ю.В.

МОУ «Лицей №8»

Что вы видите на картинах?

Это явление в искусстве называется рекурсией

«Чтобы понять рекурсию, нужно сначала понять рекурсию.»

рекурсия — частичное определение объекта через себя, определение объекта с использованием ранее определённых.

Научно выражаясь:

Рекурсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса.

Питер Дойч

Питер Дойч

Итерация от человека.

Рекурсия – от Бога.

Рекурсия в физике Рекурсия в языке и литературе

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

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

Пример рекурсивной словарной статьи:

«У попа была собака…» - типичная рекурсия

Несколько рассказов Станислава Лема посвящены казусам при бесконечной рекурсии:

Рассказ о сепульках («Звёздные дневники Йона Тихого»), в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».

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

Рекурсия в программировании -

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

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

Пример. Вычисление факториала натурального числа

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

function f ( n : integer): longint;

begin

if n = 1 then f := 1

else f:= n * f( n -1 );

{ функция fвызывает саму себя}

end

Программа на Паскале используя рекурсию:

Var n: integer;

a: longint;

function factorial ( n : integer): longint;

begin

if n = 1 then factorial := 1 else factorial := n * factorial ( n -1 );

End;

Begin

Write(‘n=’);

Readln(n);

A:= factorial ( n );

Write (‘n!=’,a );

Readln;

end.

Леонардо Пиза́нский Фибоначчи

Числа Фибоначчи – это элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …, в которой каждое последующее число равно сумме двух предыдущих.

Задача: Вывести на экран ряд чисел Фибоначчи, состоящий из n элементов.  

Описание переменных:

n – количество элементов ряда;

a, b – значения двух последних элементов ряда;

c – буферная («запасная») переменная;

i – счетчик.

Алгоритм решения задачи:

1. Получить значение n.

2. Присвоить a и b значения 0 и 1 соответственно (это первые числа ряда Фибоначчи). Вывести их на экран.

3. Начиная с 3-го элемента по n:

a) выводить на экран сумму a и b,

b) сохранить значение переменной b в c,

c) записать в b сумму a и b,

d) присвоить a значение с.

Программа на языке Паскаль используя итерацию:

program Fibonacci;

var

a,b,c,i,n: integer;

begin

write('n = ');

readln(n);

a := 0;

write(a,' ');

b := 1;

write(b,' ');

for i:=3 to n do begin

write(a+b,' ');

c := b;

b := a + b;

a := c;

end;

readln;

end.

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

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

Это определение чисел Фибоначчи легко преобразовать в рекурсивную функцию:

function f(n: Integer) : longint;

begin

If n <= 1 Then

f := n

else

f := f(n– 1) + f(n - 2);

end;

Program chislaFibonacci;

var n,i: integer;

a: longint;

function fib ( n : integer): longint;

begin

If n <= 1 Then

fib := n

else

fib:= fib(n– 1) + fib(n - 2);

End;

begin

write(‘n=’);

readln(n);

for i:=0 to n do begin

A:= fib ( n );

write (‘ ’,a );

end;

readln;

end.

Домашнее задание

Написать программу нахождения НОД двух натуральных чисел, используя алгоритм Евклида и рекурсию

Даны два натуральных числа а и b.

Если а = b, то нод (а ,b)=а.

Если а >b, то нод (а ,b)= нод (а -b ,b).

Если а < b, то нод (а ,b)= нод (а ,b-а).

Program noddvyxchisel;

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

write(‘a=’);

readln(a);

write(‘b=’);

readln(b);

A:= nod(a,b);

write(‘nod=’,a);

readln;

end.

Задача о Ханойских башнях.

При этом неукоснительно должны соблюдаться следующие правила:

  • за один раз можно перемещать только один диск;
  • больший диск нельзя располагать на меньшем диске;
  • снятый диск необходимо надеть на какой-либо шпиль перед тем, как будет снят другой диск.
  • Трудолюбивые буддийские монахи день и ночь переносят диски со шпиля на шпиль. Легенда утверждает, что когда монахи закончат свою работу, наступит конец света. Можно было бы подсчитать, что для решения задачи с 64 дисками потребуется264– 1 перемещений. Поэтому что касается конца света, то он произойдет по истечении пяти миллиардов веков, если считать, что один диск перемещается за одну секунду. Впрочем, и задачу, и легенду для неё придумал в 1883 году математик Эдуард Люка из колледжа Сен-Луи .

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

Задача . Составить рекурсивную программу, которая бы решала поставленную выше задачу о Ханойских башнях при количестве дисков, равном n (n = 1, 2, …).

Решение.

Введем имена для шпилей: a, b, c. Пусть hanoi(n,a,b,c) - искомая функция, возвращающая последовательность перемещений дисков с a на b c использованием c по вышеописанным правилам. При n=1 решать задачу мы умеем. Необходимо просто произвести операцию “переместить a на b”. Предположим, что мы умеем решать эту задачу для n – 1 диска. Переместим n–1 диск с a на с. Далее, переместим один оставшийся диск с a на b и, наконец, переместим n–1 диск с c на b.

Входные данные: количество дисков, находящихся на колышке a;

Выходные данные: последовательность действий;

Шаг0:{определение типа переменных};

Шаг1:{описание процедуры hanoi, которая выводит последовательность действий};

Шаг1.1:{переместить (n-1) дисков с колышка a на колышек b};

Шаг1.2:{переместить n-ый диск с a на c};

Шаг1.3:{переместить (n-1) диск с b на c};

(шаги 1.2-1.3 выполняются рекурсивно);

Шаг2:{основная программа};

Шаг2.1:{ввод количества дисков};

Шаг2.2:{вызов процедуры hanoi}.

Решение задачи в Паскале

Program bahnya;

var n: integer;

a,b,c: char;

procedure hanoi(n: integer;a,b,c: char);

begin

if n>0 then

begin

hanoi(n-1,a,c,b);

writeln ('Peremestit disk so sterzhnya ',a,' na sterzhen" ',b);

hanoi(n-1,c,b,a);

end;

end;

Begin

write ('Vvedite naturalnoe chislo n');

readln (n);

a:='a'; b:='b'; c:='c';

hanoi (n,a,c,b);

readln;

end.

Домашнее задание

Написать программу вычисления степени с натуральным показателем

Дано: основание степени х

Показатель степени к

Если к=0, тогда степень(к,х)=1,

Иначе

степень (к,х)= х· степень (к-1,х)

Program stepen;

var y: real;

n: integer;

function step(k:integer, x:real): real;

begin

If k = 0 Then

step := 1

else step:= x * step(k-1,x)

End;

begin

write(‘vvedite osnovanie stepeni x=’);

readln(y);

write(‘vvedite pokazatel stepeni k=’);

Readln(n);

write(‘x v stepeni k=’,step(n,y));

readln;

end.

Самостоятельная работа

  • Найти сумму цифр числа
  • Определить, является ли заданное натуральное число простым
  • Найти первую цифру числа
  • Перевести натуральное число из десятичной с.с. в двоичную
  • Найти сумму элементов целочисленного массива, состоящего из 20 элементов
  • Поменять местами значения двух целых чисел
  • Упорядочить значения трех переменных а, в, с в порядке их возрастания
  • Найти количество цифр в натуральном числе n
  • Найти наибольшее из трех данных чисел
  • Найти количество положительных чисел среди четырех А, В, С, Д

Ответы самостоятельной работы

№2

Program prostoe;

var n, m, s: integer;

function prost(m, n:integer): boolean;

begin

If n = m Then

prost := true

else prost:= (n mod m <> 0) and prost (m+1, n);

End;

begin

write(‘n=’);

Readln(n);

M:=2;

If prost(m,n) then write (n,’prostoechislo’)

Else write (n,’sostavnoe’);

readln;

end.

№4

program perevod;

var n: longint;

procedure dvd(n:longint);

begin

If n >1 Then dvd (n div 2);

write (n mod 2);

end;

begin

write(‘n=’);

readln(n);

dvd (n);

readln;

end.