Разделы презентаций


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

Содержание

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

Слайды и текст этой презентации

Слайд 1Рекурсия в Паскале
Учитель :
Тлехурай Ю.В.
МОУ «Лицей №8»

Рекурсия в ПаскалеУчитель :Тлехурай Ю.В.МОУ «Лицей №8»

Слайд 2Что вы видите на картинах?

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

Слайд 3Это явление в искусстве называется рекурсией
«Чтобы понять рекурсию, нужно сначала

понять рекурсию.»
рекурсия — частичное определение объекта через себя, определение объекта

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

Это явление в искусстве называется рекурсией «Чтобы понять рекурсию, нужно сначала понять рекурсию.»рекурсия — частичное определение объекта

Слайд 4Питер Дойч
Итерация от человека.
Рекурсия – от Бога.

Питер ДойчИтерация от человека.Рекурсия – от Бога.

Слайд 5Рекурсия в физике Рекурсия в языке и литературе
Классическим примером бесконечной рекурсии

являются два поставленные друг напротив друга зеркала: в них образуются

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




Пример рекурсивной словарной статьи:
«У попа была собака…» - типичная рекурсия

Несколько рассказов Станислава Лема посвящены казусам при бесконечной рекурсии:
Рассказ о сепульках («Звёздные дневники Йона Тихого»), в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».
Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).

Рекурсия в физике  Рекурсия в языке и литературе Классическим примером бесконечной рекурсии являются два поставленные друг

Слайд 6Рекурсия в программировании -
это такой способ организации вычислительного процесса, при

котором процедура или функция в ходе выполнения составляющих ее операторов

обращается сама к себе.

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

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

Слайд 7Пример. Вычисление факториала натурального числа
Составить рекурсивную функцию, вычисляющую факториал числа

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.
Пример. Вычисление факториала натурального числаСоставить рекурсивную функцию, вычисляющую факториал числа n следующим образом: function f ( n

Слайд 8Леонардо Пиза́нский Фибоначчи
Числа Фибоначчи – это элементы числовой последовательности
0, 1,

1, 2, 3, 5, 8, 13, 21, 34, 55, 89,

144, …, в которой каждое последующее число равно сумме двух предыдущих.
Леонардо Пиза́нский ФибоначчиЧисла Фибоначчи – это элементы числовой последовательности0, 1, 1, 2, 3, 5, 8, 13, 21,

Слайд 9
Описание переменных:
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.

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

Описание переменных: n – количество элементов ряда;a, b – значения двух последних элементов ряда;c – буферная («запасная»)

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




Это

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

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.


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

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

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

и рекурсию
Даны два натуральных числа а и 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.







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

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

Слайд 12Задача о Ханойских башнях.
При этом неукоснительно должны соблюдаться следующие правила:

за один раз можно перемещать только один диск;
больший диск нельзя

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

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

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

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

задачу о Ханойских башнях при количестве дисков, равном 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}.

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

Слайд 14Program 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.

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

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

Слайд 15Домашнее задание
Написать программу вычисления степени с натуральным показателем

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

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

Если к=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.

Домашнее заданиеНаписать программу вычисления степени с натуральным показателемДано: основание степени хПоказатель степени кЕсли к=0, тогда степень(к,х)=1, Иначе

Слайд 16Самостоятельная работа
Найти сумму цифр числа
Определить, является ли заданное натуральное число

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

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


Самостоятельная работаНайти сумму цифр числаОпределить, является ли заданное натуральное число простымНайти первую цифру числаПеревести натуральное число из

Слайд 17Ответы самостоятельной работы
№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.

Ответы самостоятельной работы№2Program prostoe;var	n, m, s: integer;function prost(m, n:integer): boolean; begin  If n = m Then		prost

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика