【經典算法實現 14】阿克曼函數---手動推導求解、遞歸實現、非遞歸實現

• • 一、阿克曼函數 手動求解
  • 二、阿克曼函數 遞歸實現
  • 三、阿克曼函數 非遞歸實現

該題目來自騰訊實習生的招聘筆試，題目給出如下的遞歸函數，求ack(3,3)的值。

long 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));} }

題目來自:《【騰訊筆試】已知遞歸函數計算ack（3,3）的值》

一、阿克曼函數 手動求解

ack(0, n) = n+1 ack(m, 0) = ack(m-1, 1) ack(m, n) = ack(m-1, ack(m, n-1))由此可見，m 每一行，都是一個等差數列推導公式 =======> 當 m = 1 時 ack(1, 0) = ack(0, 1) = 1 + 1 = 2 ack(1, n) = ack(1, n-1 ) +1 = 2 + N=======> 當 m = 2 時 ack(2, 0) = ack(1, 1) = 2+1 = 3 ack(2, n) = ack(1, ack(2,n-1)) = 2 + ack(2, n-1) = 2 * N + ack(2, 0) = 2*N + 3 可以得到，m = 2時，是等差為2 的等差數列=======> 當 m = 3 時 ack(3, 0) = ack(2, 1) = 2 * 1 + 3 = 5 ack(3, n) = ack(2, ack(3, n-1)) = 2 * (ack(3, n-1)) + 3 計算如下： ack(3, 1) = 2 * (ack(3,0)) + 3 = 2 * 5 + 3 = 13 ack(3, 2) = 2 * (ack(3,1)) + 3 = 2 * 13 + 3 = 29 ack(3, 3) = 2 * 29 + 3 = 61 ack(3, 4) = 2 * 61 + 3 = 125 ack(3, 5) = 2 * 125 + 3 = 253 ack(3, 6) = 2 * 253 + 3 = 509 ack(3, 7) = 2 * 509 + 3 = 1021 ack(3, 8) = 2 * 1021 + 3 = 2045 ack(3, 9) = 2 * 1021 + 3 = 2045 ack(3, 10) = 2 * 2045 + 3 = 4093 ack(3, 11) = 2 * 4093 + 3 = 8189 ack(3, 12) = 2 * 8189 + 3 = 16381 ack(3, 13) = 2 * 16381 + 3 = 32765=======> 當 m = 4 時 ack(4, 0) = ack(3, 1) = 13 ack(4, n) = ack(3, ack(4, n-1)) = 2 * (ack(4, n-1)) + 3 ack(4, 1) = ack(3, ack(4, 0)) = ack(3, ack(3,1)) = ack(3, 13) = 32765 ack(4, 2) = ack(3, ack(4, 1)) = ack(3, 32765)

可以看到，當計算到 ack(4, 2)時，整個數一定特別大了，人工去算基本是不可能的了。

二、阿克曼函數 遞歸實現

#include <stdio.h>long long ack(int m, int n) {if(m == 0){return n+1;}else if(n == 0){return ack(m - 1, 1);}else{printf("m = %d, n = %d\n", m, n);return ack(m - 1, ack(m, n - 1));} }int main(void) {int m=0, n=0;long long val=0;while(1){scanf("%d %d", &m, &n);val = ack(m, n);printf("\nack(%d, %d) = %lld\n",m ,n, val);} }

實際使用計算機計算，由于是遞歸，做了很多重復的操作，整個求解過程也非常慢，
實測計算 m = 3, n = 6 ，我的電腦用了差不多 6 s

更別說，m = 4 的時候了。

三、阿克曼函數 非遞歸實現

網上有個兄弟使用java stack 棧來實現的，有興趣的兄弟可以看下：
《每天刷個算法題20160524：阿克曼函數的遞歸轉非遞歸解法》
《關于阿克曼函數(akermann）非遞歸算法的一點見解 c++》

有關C語言的解法，待更新。。。先吃飯

總結

以上是生活随笔為你收集整理的【经典算法实现 14】阿克曼函数（手动推导求解、递归实现、非递归实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。