Re: [理工] Ackermann的計算法

[MIKEmike07 (加油!)]

※ 引述《oklp1415 (天生我材)》之銘言：
: 詢問 Ackermann 計算的問題
: 關於 Ackermann(2,2) 的計算值為何??
: 有人肯指引一下他的計算過程嗎?  沒有完全弄清楚這複雜的定義運算~"~

原則上是這樣

A(m,n) = {
           n+1 when m=0

           A(m-1,1) when n=0

           A(m-1,A(m,n-1))
         }

A(2,2) = A(1,A(2,1)) 看條件A(2,1)，不符合m=0 or n=0所以繼續做
                |
                |__
                    A(1,A(2,0)) 看條件A(2,0)符合n=0，所以做A(m-1,1)
                           |
                           |__
                               A(1,1) 看條件皆不符合，繼續做
                                  |
                                  |__
                                      A(0,A(1,0)) 看條件A(1,0)符合n=0
                                             |
                                             |__
                                                 A(0,1) 看條件符合m=0 得值=2

接著開始往回推，A(0,A(1,0)=2) = 3，所以A(1,1) = 3

A(1,A(2,0)) = A(1,3) (又要繼續算)
                 |
                 |__
                     A(0,A(1,2))
                            |
                            |__
                                A(0,A(1,1)) 這邊已經知道A(1,1)=3所以不用再繼續

所以再往回推，A(1,3) = 5

回到源頭 A(2,2) = A(1,5) (又要繼續算)
                     |
                     |__
                         A(0,A(1,4))
                                |
                                |__
                                    A(0,A(1,3)) 已知A(1,3) = 5

所以再往回推得 A(2,2) = A(1,5) = 7

基本上他不複雜，主要就是看清楚題目慢慢來，一步步算就好囉

從這之中應該可以發現m,n之間的關係吧

只有當n=0，才能讓m減少，要得到值則是要讓m=0才能得到

考試不會出太大拉，不然會算到很累呵呵

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.254.124.139
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1397846778.A.A87.html
推 oklp1415:感謝大大的用心詳解，受益了!!
推 storm654321:ackermann(2,n)的closed form 為3+2n  建議寫程式
→ storm654321:我一開始不懂 後來寫完C之後就 頓悟了XD
→ storm654321:ACKERMANN跟費是數列比較來 的確難理解...
推 beabetterman:常出的值結果背起來就好了 考試沒時間慢慢推