Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Вычисление факториала.

Читайте также:
  1. Вычисление величин деформации элементов РП при торможении вагона.
  2. Вычисление величины деформации элементов рычажной передачи при торможение вагона
  3. Вычисление главных компонент.
  4. Вычисление горизонтов прибора станций
  5. Вычисление действительные нажатия композиционных тормозных колодок.
  6. Вычисление диаметра ТЦ по расчетной величине усилия на штоке и выбор необходимого тормозного цилиндра.
  7. Вычисление длин дуг плоских кривых.

Факториал числа n! определяет количество способов размещения n предметов в некотором ряду. Так, при n=3 имеется три способа для размещения первого предмета. Если он уже зафиксирован, то существует два способа установки второго предмета и один для третьего. Таким образом, 3!=3*2*1=6. Приведем таблицу для нескольких первых значений факториала:

4!=24

5!=120

6!=720

7!=5040

8!=40320

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

 

.

Некоторые важные свойства факториала можно найти в справочной литературе, а мы подробнее остановимся на рекурсивном алгоритме его вычисления. Запишем факториал в виде

n! = n (n-1)! (1)

 

В такой записи задача вычисления факториала сводится к ней самой же, путем изменения исходных данных, т.е. «новое» значение n! выражено через «старое» (n-1)!. Кроме того, условие 0! =1 позволяет завершить вычислительный процесс. Составим рекурсивную функцию:

 

function Factorial(n:integer):real;

begin

if n=0

then Factorial:=1

else Factorial:=n* Factorial(n-1)

end;

 

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

 

function Factorial(n:integer):real;

var i, y:longint;

begin

y:=1;

if n=0

then Factorial:=1

else begin

for i:=2 to n do y:=y*i;

Factorial:=y

end

end;

 

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

Принцип работы рекурсивных подпрограмм подобен работе стека. Прямой ход рекурсии – операция засылки информации в стек (операция Push): Обратный ход рекурсии – последовательное извлечение данных из стека (операция Pop):

В прямом ходе, при очередном вызове подпрограммы-функции все ее локальные переменные, а также параметры, заносятся в специальную область памяти (сегмент стека), причем копии всех обращений временно сохраняются. Число копий, находящихся в памяти, т.е. число рекурсивных вызовов подпрограммы без возврата, называется глубиной рекурсии. В прямом ходе рекурсии это число возрастает. Следует помнить, что размеры стека не бесконечны (по умолчанию, объем стека равен 16 Кбайт), и существует реальная опасность его переполнения. Кроме того, в рекурсивном алгоритме обязательно должно быть условие, гарантирующее завершение цепочки обращений к функции.

При обратном ходе оперативная память, занятая под локальные переменные и параметры функции освобождается, а полученный результат передается в точку возврата – оператор присваивания значений вычисляемой функции.

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

 


Дата добавления: 2015-07-26; просмотров: 162 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
II. Экспериментальный раздел работы.| Рекурсия и рекуррентность.

mybiblioteka.su - 2015-2024 год. (0.006 сек.)