問題描述
評測題目: 給出如下的遞歸函數(shù)梗夸，求ack(3,3)的值层玲。
int
ack(int m, int n)
{
if (m == 0) return n + 1;
else if (n == 0) return ack(m - 1, 1);
else return ack(m - 1, ack(m, n - 1));
}
編程方法
根據(jù)題目中的c語言程序改寫成python如下：
cost = 0
def ack(m,n):
global cost
cost += 1
if m==0: return n+1
elif n==0: return ack(m-1,1)
else: return ack(m - 1, ack(m, n - 1))
print(ack(3,3))
print(cost)
運(yùn)行得到結(jié)果為：
The answer is: 61
The number of iterations is: 2432
可知正確答案為61号醉，計算機(jī)運(yùn)行該程序時一共調(diào)用了ack()函數(shù)2432次反症。
數(shù)學(xué)方法
作為一道筆試題，想要迭代完成2432次計算是不可能的畔派，因此這里講解求ack(3,3)的數(shù)學(xué)思路铅碍。
-
討論ack(1,0)和ack(2,0)，通過簡單計算可得
-
討論ack(1,n)线椰，可得如下遞歸公式
-
討論ack(2,n)胞谈，可得如下遞歸公式
-
討論ack(3,n)，可得如下遞歸公式整理可得由等比數(shù)列公式可知又故
將n=3代入上式憨愉，可知正確答案為61烦绳。
