Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Теоретические вопросы _ нужно понять функцию

Автор: Jenkins 22.03.2007 5:32


FUNCTION F(X:integer):integer;
BEGIN
     IF X<=1 THEN F:=X
     ELSE IF ODD(X) THEN F:=F(5*X+1)+1
     ELSE F:=F(X div 6)+1;
END

значение функции при х=46 будет 5
(нужно объяснить почему ,как работает функция)

заранее спасибо

Автор: hiv 22.03.2007 15:06

Это рекурсия - когда функция вызывает саму себя. Показать как это работает нетривиально, но можно... Посмотри как это будет вычисляться:

Код
   X   F    CODE
  46        X div 6
   7        5*X+1
  36        X div 6
   6        X div 6
   1        X
   1   1    F:=X
   6   2    F:=F(X div 6)+1
  36   3    F:=F(X div 6)+1
   7   4    F:=F(5*X+1)+1
  46   5    F:=F(X div 6)+1

Автор: Jenkins 23.03.2007 5:17

то , что надо good.gif , а то я вотчи включал

Автор: Jenkins 24.03.2007 1:32

т.е. ,насколько я понял ,если рекурсивная ф-я имеет вид

if x <= Y then f(x):=A
else
f(x):=g(f(x));


,где "A" может быть числом или выражением ,а Y - числом ,то :



1:находим кол-во шагов (k), т.е.

				 k раз
			   ____^___
			 /		\  
считаем ,когда  значение f[f(...f(f(x)] станет меньше или равно Y


2: вычисляем :

			k раз
		 _____^___
		/		 \
результат  =	g[g(...g(g(A)]


ПО_ДРУГОМУ :

вычисляются все члены последовательности
{a1 ,a2 ,a3 ,... ,a(n-1) ,an } (n=k+1)

в которой
a(n-1)=f(an) если n>3

НО в этой последовательности f(a2) <= Y
a1 = A (при условия что f(a2) <=Y)

затем составляется другая последовательность ,состоящая из n элементов :
{b1 ,b2 ,... ,bn } ,в которой
b1=a1=A , b2=g(b1) ,bn=g(b(n-1)) ,

и ,в конце концов f(x) принимает значение bn .


если в условии будет стоять "больше" , то нужно менять f на обратную ей ф-цию (и g тоже на обратную ,НАПРИМЕР ,если g(f(x))=2*f(x) ,то ф-я ,обратная g ,будет "1/2(f(x))" ).

???????????????????????????????????????????????????????????????????????????????????????????????????????????

Автор: hiv 26.03.2007 14:59

Цитата(Jenkins @ 23.03.2007 21:32) *
т.е. ,насколько я понял ,если рекурсивная ф-я имеет вид
Немного поправлю smile.gif
Рекурсивная функция имеет вид: 
function F(X)
begin
  if условие then F:=A(X) {здесь нет рекурсивного вызова ф-ции F(X) в правой части присваивания}
  else F:=H(F(G(X)));  {здесь есть рекурсивный вызов}
end;
Когда условие выполняется рекурсия "заканчивается", т.е. более функция F(X) не вызывается и стековая память под ее аргументы не выделяется. При этом она начинает "обратный ход", т.е. как бы схлопываться с высвобождением памяти, выделенной под вызовы функции F(X).
Итак! В начале идет итерация по аргументам функции X=G(X) до тех пор, пока не выполнится "условие". Т.е. получаем итерационный ряд: X1, X2, X3, ... , Xi=G(Xi-1), ... , Xn.
При Xn вычисляется первое найденное значение F=A(Xn). Назовем его Fn.
Вторым вычислится Fn-1=H(Fn). Т.е. такая же итерация по значениям функции (не путать итерацию с рекурсией!!!).
Итак обратный ход: Fn, Fn-1, ... , Fi=H(Fi+1), F3, F2, F1.
Итоговым значением рекурсивного вызова функции F(X) станет значение F1.

Запомни главными для рекурсивной функции являются два факта:
1) вызов самой себя внутри собственного тела;
2) условие выхода из рекурсии, т.е. такое условие, при котором она перестает сама себя вызывать.
Без второго факта рекурсия просто бред!

Автор: Jenkins 27.03.2007 0:29

теперь тема закрыта