作者chenbojyh (阿志)
看板Grad-ProbAsk
标题Re: [理工] [离散]-中正97-通讯
时间Fri Feb 5 17:45:59 2010
※ 引述《noty1311 (木子)》之铭言：
: A(0,n) = n+1 n>0
: A(m,0) = A(m-1,1) m>0
: A(m,n) = A(m-1,A(m,n-1)) m,n>0
: What is A(4,1)?
: 不知道要怎麽算，我代到一半就放弃了...
以下是我的解答.......
A(0,n) = n+1
A(1,n) = A(0,A(1,n-1))
= A(1,n-1) + 1
= A(1,n-2) + 2
= A(1,0) + n
= A(0,1) + n
= n+2
A(2,n) = A(1,A(2,n-1))
= A(2,n-1) + 2
= A(2,n-2) + 4
= A(2,0) + 2n
= A(1,1) + 2n
= 2n+3
A(3,n) = A(2,A(3,n-1))
= 2A(3,n-1) + 3
= 2( 2A(3,n-2) + 3 ) + 3
= (2^n)A(3,0) + 3*(1-2^n)/(1-2)
= (2^n)A(2,1) + 3*(2^n) - 3
= 5*(2^n) + 3*(2^n) - 3
= 8*(2^n) -3
= 2^(n+3) -3
A(4,1) = A(3,A(4,0))
= A(3,A(3,1))
= A(3,13)
= 2^16 - 3
ANS: A(4,1) = 2^16 - 3
￣￣￣￣￣￣￣￣￣￣￣￣
这个是特殊的递回
好像叫Ackermann function
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.227.134.190
1F：→ noty1311:感谢 02/05 20:30