Файл: А. Б. Шнейвайс основы программирования.pdf

Скачать файл (1,48Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 06.12.2023

Просмотров: 319

Скачиваний: 6

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

2.1.2
Нерекурсивная и рекурсивная ФОРТРАН-функции расчета n!
program tstfactor; implicit none
!
Файл tstfactor.for interface function factorn(n) result(w); real(8) w; integer n end function factorn recursive function factorr(n) result(w); real(8) w; integer n;
end function factorr function factornB(n); real(8) factornB; integer n end function factornB
end interface integer n; real(8) rn, rr, rb write(*,*) ’введи n:’; read (*,*) n; write(*,*) ’ n=’,n rn=factorn(n); rr=factorr(n); rb=factornB(n); write(*,1000) rn, rr, rb rn=factorn(n); rr=factorr(n); rb=factornB(n); write(*,1000) rn, rr, rb
1000 format(1x,’ rn=’,g15.7,’
rr=’,g15.7,’
rb=’,g15.7)
end program tstfactor function factorn(n) result(w); implicit none
! factorn - нерекурсивная real(8) w; integer n, i
!
функция расчета n!
w=1; do i=1,n; w=w*i; enddo end function factorn recursive real(8) function factorr(n) result(w); ! factorr1 - рекурсивная.
implicit none; integer n data w /1.0d0/
if (n.eq.0) then;
w=1; else;
w=n*factorr(n-1); endif end function factorr function factornB(n); implicit none
! factornB - нерекурсивная real(8) w,
factornB; integer n, i
!
функция расчета n!
data w /1.0d0/
!
ОПАСНЫЙ вариант !!!
do i=1,n; w=w*i; enddo factornB=w end function factornB
введи n:
n=
5
rn=
120.0000
rr=
120.0000
rb=
120.0000
rn=
120.0000
rr=
120.0000
rb=
14400.00
Внимание! В ФОРТРАН-учебниках можно встретить фразу, что опе- ратор data предназначен для задания начальных значений. Иногда его применяют для задания начального значения какой-нибудь локальной переменной той или иной процедуры (например, расчёта факториала:
data w /1.0d0/), что при повторном вызове процедуры может привести к неожиданным результатам (см., результат второго вызова процедуры factornB(5), который оказался равен 1440).
59

Дело в том, что присваивание data w /1.0/ выполняется компи- лятором, а не при работе программы. Поэтому после первого вызова factornB в w окажется не единица, а 120, а после второго — 1440.
На примере factornB видно, что описание result(w), имеющееся в factorn и factorr, принципиально важно, так как в этом случае компи- лятор на наличие в тексте процедуры оператора data w /1.0/, сообщит:
data w /1.0d0/
1
ошибка: DATA attribute conflicts with RESULT attribute in ’w’ at (1)
Нельзя значение переменной задавать оператором data, если она пред- назначена для возврата результата.
2.1.3
Схема вызовов при расчете f actorr1(3)
fr1:=factorr1(3)
:=-->3* factorr1(2)
:=-->2*factorr1(1)
:=-->1*factr(0)
1 * 1
найден factr(0);
2 *
1 <----------------- найден factr(1);
3 *
2
<----------------------------- найден factr(2);
6
<-------------------------------------------- найден factr(3),
fr:=
6
это значение и возвращается в главную программу.
Замечание: Часто спрашивают: “Почему 0!=1 и 1!=1 ?”
Факториал представляет собой частный случай широко использую- щейся в математике Гамма-функции (интеграл Эйлера):
Γ(x) =
Z
∞
0
e
−t t
x−1
dt
,
значение которой при натуральном x равно соответствующему фактори- алу, именно
Γ(x + 1) = x! .
В частности,
0! = Γ(1) =
Z
∞
0
e
−t dt = 1
,
1! = Γ(2) =
Z
∞
0
e
−t
· tdt = 1 .
60

2.1.4
Достоинства и недостатки рекурсивного описания.
1. Рекурсивное описание функции можно заменить нерекурсивным.
2. Рекурсивность – это не свойство функции, а свойство ее описания.
3. “Какой способ описания выгоднее?” – решать программисту!
Достоинства
Недостатки определяет сколь-угодно как правило, работает медленнее много объектов через нерекурсивного из–за временных конечное высказывание;
затрат на повторные обращения;
записывается фактически не всегда переход на нерекурсивное прямо по описанию описание так же прост, как при алгоритма;
описании f actorn(n);
текст легче воспринимается отладка может оказаться непростой,
пользователем особенно при сложной рекурсии
61

2.2
Понятие глубины рекурсии. Алгоритм Евклида.
Глубина рекурсии – это количество промежуточных вызовов функции в процессе ее вычисления для данного аргумента.
Например, factorr1(3) помимо начального вызова активирует еще три рекурсивных: factorr1(2), factorr1(1), factorr1(0), т.е. рекурсия имеет глубину в три уровня. Для функции n! глубина рекурсии при любом n очевидна. К сожалению, это – исключение. Даже в простом алгоритме
Евклида поиска наибольшего общего делителя двух натуральных чисел a и b глубина рекурсии не очевидна.
2.2.1
Нерекурсивная и рекурсивная СИ-функции поиска НОД.
В соответствие с определением 4 из введения к этой главе имеем:
#include
using namespace std;
int nodn(int,int); int nodr(int,int);
int main()
{int a, b, nn, nr;
cout<<"введите a, b:"<cin>>a>>b;
cout<<" a="<b="<nn=nodn(a,b);
nr=nodr(a,b);
cout<<" nodn="<nodr="<return 0;
}
int nodn(int a, int b)
// Нерекурсивная функция
{int r;
// расчета НОД(a,b).
while (b)
{ r=a%b; a=b; b=r; }
return a;
}
int nodr(int a, int b)
// Рекурсивная функция
{ if (a// расчета НОД(a,b).
else
{ if (b) return nodr(b,a%b);
else return a;
}
}
введите a, b:
// Результат C++ тестирования nodn и nodr:
85 51
a=85
b=51
nodn=17
nodr=17 62