IPB
ЛогинПароль:

> Правила раздела!

1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!

 
 Ответить  Открыть новую тему 
> нужно понять функцию, рекурсивная ф-я
сообщение
Сообщение #1


Manowar
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: CaHek

Репутация: -  0  +



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
(нужно объяснить почему ,как работает функция)

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


--------------------
Into Glory Ride
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 660
Пол: Мужской
Реальное имя: Михаил

Репутация: -  11  +


Это рекурсия - когда функция вызывает саму себя. Показать как это работает нетривиально, но можно... Посмотри как это будет вычисляться:
Код
   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


Сообщение отредактировано: hiv -


--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Manowar
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: CaHek

Репутация: -  0  +


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


--------------------
Into Glory Ride
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Manowar
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: CaHek

Репутация: -  0  +


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

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))" ).

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

Сообщение отредактировано: volvo -


--------------------
Into Glory Ride
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Профи
****

Группа: Пользователи
Сообщений: 660
Пол: Мужской
Реальное имя: Михаил

Репутация: -  11  +


Цитата(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) условие выхода из рекурсии, т.е. такое условие, при котором она перестает сама себя вызывать.
Без второго факта рекурсия просто бред!

Сообщение отредактировано: hiv -


--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Manowar
*

Группа: Пользователи
Сообщений: 14
Пол: Мужской
Реальное имя: CaHek

Репутация: -  0  +


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



--------------------
Into Glory Ride
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 23:38
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name