uzluga.ru
добавить свой файл
1



Продолжим изучение подпрограмм.

  • Продолжим изучение подпрограмм.

  • Узнаем, что такое рекурсия, как выполняется рекурсивный алгоритм.











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

  • Если поставить два зеркала напротив друг друга и между ними поместить предмет, то получится бесконечное множество отображений, причем каждое из них содержит свое собственное отображение.

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



Берётся сплошной равносторонний треугольник, на первом шаге из центра удаляется внутренность срединного треугольника. На втором шаге удаляется три срединных треугольника из трёх оставшихся треугольников и т. д. После бесконечного повторения этой процедуры, от сплошного треугольника остаётся подмножество — треугольник Серпинского.

  • Берётся сплошной равносторонний треугольник, на первом шаге из центра удаляется внутренность срединного треугольника. На втором шаге удаляется три срединных треугольника из трёх оставшихся треугольников и т. д. После бесконечного повторения этой процедуры, от сплошного треугольника остаётся подмножество — треугольник Серпинского.







У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал:



  • Простота построения;

  • Несхожесть конечного результата с начальными данными;

  • Внутреннее самоподобие.



1) Определение натурального числа.

  • 1) Определение натурального числа.

  • а) 1 - натуральное число;

  • б) число, следующее за натуральным (т.е. больше его на единицу), есть натуральное число.

  • 2) Арифметическая прогрессия:

  • а)а1=а0;

  • б) аn=аn-1+d. При а0=1, d=1 имеем натуральный ряд 1,2,3,...

  • 3) Геометрическая прогрессия:

  • а) а1=а0;

  • б) аn=а n-1*q. При а0=2, q=2 имеем степенной ряд 2,4,8,16,32,...;



4) Факториал an=n! (Fасtоr— сомножитель) n!=1*2*3*4*5*б*...*n.

  • 4) Факториал an=n! (Fасtоr— сомножитель) n!=1*2*3*4*5*б*...*n.

    • а)а1=1; б) аn=n*аn-1.
  • 5) Числа Фибоначчи. Они определяются следующим образом:

  • x[1]=x[2]=1

  • x[n]=x[n-1]+x[n-2] при n > 2  

  • Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, т.е.

  • 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …



В «Книге абака» 1202 г. изложил формулы решения квадратного уравнения по образцу ал-Хорезми, в этой книге впервые встречается правило для нахождения суммы членов произвольной арифметической прогрессии.

  • В «Книге абака» 1202 г. изложил формулы решения квадратного уравнения по образцу ал-Хорезми, в этой книге впервые встречается правило для нахождения суммы членов произвольной арифметической прогрессии.

  • Фибоначчи придумал последовательность натуральных чисел : а) если n<3, то аn=1;

  • б) аn=аn-1+аn-2, каждый элемент последовательности, начиная с трётьего равен сумме двух предшествующих.



Рекурсия — это способ описания функции или процессов через самих себя.

  • Рекурсия — это способ описания функции или процессов через самих себя.

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

  • В таких алгоритмах выделяется два этапа:

  • 1) «погружение» алгоритма в себя, т.е. применениё определения в «обратную сторону», пока не будет найдено начальное определение, не являющееся рекурсивным;

  • 2) последовательное построение от начального определения до определения с введенным в алгоритм значением.



Функция для вычисления факториала:

  • Функция для вычисления факториала:

  • Function F(n: integer): longin;

  • Веgin

  • If n=1 then F:=1

  • else:=n*F(n-1)

  • End;



1 вызов (n=5)

  • 1 вызов (n=5)

  • у:=F(5), так как n≠1, то управление передается на ветку иначе и функция F:=5*F(4).

  • 2 вызов (n=4), так как n ≠ 1, то F:=4*F(3).

  • З вызов (n=З), так как n ≠ 1, то F:=3*F(2).

  • 4 вызов (n=2), так как n ≠ 1, то F:=2*F(1)=2*1=2..



Ответ: 5!=120

  • Ответ: 5!=120

  • Это значение присваивается переменной.

  • 1 вызов (n=5), то F:=5*F(4)=5*24=120.

  • 2 вызов (n=4), то F:=4*F(3)=4*6=24.

  • 3 вызов (n=3), то F:=3*F(2)=З*2=6.





Вычислите 8-е число Фибоначчи

  • Вычислите 8-е число Фибоначчи





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

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