作者pgcci7339 (= =)
站內Math
標題Re: [中學] 遞迴2題
時間Sun Jul 22 11:42:55 2012
※ 引述《stu2005131 (自由幻夢)》之銘言:
: 1.
: 若f[(x+2)/x]=(1/x)f(x+1)+3,則f(5)=?
: 2.
: 若函數f:R^2-->R
: 且滿足
: f(0,y)=y+1 ---------------------------->(1)
: f(x+1,0)=f(x,1)------------------------>(2)
: f(x+1,y+1)=f(x,f(x+1,y))--------------->(3)
: 求f(5,0)=?
1. x=4 => f(3/2)=(1/4)f(5)+3
x=1/2 => f(5)=2f(3/2)+3
∴ f(5)=2[1/4f(5)+3]+3 = 1/2f(5)+9
=> f(5)=18
2. 先證明下列幾個式子:
一、f(1,y)=y+2,利用 (1)、(2)、(3)式 推得。
二、f(2,y)=2y+3
由 (3)和 一 式
f(2,y)=f(1,f(2,y-1))=f(2,y-1)+2
再利用累加的方法可得證。
三、f(3,y)=2^(y+3)-3
由 (3) 和 二 式
f(3,y)=f(2,f(3,y-1))=2f(3,y-1)+3
再利用累乘的方法可得證。
因此,
f(5,0)=f(4,1)=f(3,f(4,0)) ----> by (2) and (3)
f(4,0)=f(3,1)=f(2,f(3,0))
f(3,0)=f(2,1)=(1,f(2,0))
f(2,0)=f(1,1)=3
∴f(3,0)=f(1,3)=5 -----> by 一
f(4,0)=f(2,f(3,0))
=f(2,5)=13 ---> by 二
f(5,0)=f(3,13)=2^16-3 ---> by 三
結束!
PS:其實一開始根本沒有想到上面那三個式子= =
也是一直重覆利用(1)、(2)、(3)式的過程中覺得實在太過複雜,
才想說有沒有更方便的規則,還好有找到了XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.189.16
推 stu2005131 :第一題答案是-(4/25)的說>~< 07/22 11:56
推 stu2005131 :是我打錯了 原題f(x/x+2)=才對 07/22 12:02
推 justinj :核心是f(5)時x為多少...amem 07/22 12:39
推 LPH66 :等等這第二題不就是傳說中的 Ackermann 函數嗎 (驚 07/22 13:02