【經典算法實現 15】阿克曼函數 -- 非遞歸實現

• • 一、阿克曼函數 -- 非遞歸實現

在前面《【經典算法實現 14】阿克曼函數（手動推導求解、遞歸實現、非遞歸實現）》 中，
我們實現了阿克曼函數的手動推導及遞歸實現代碼，
在本文中，我們來研究下它的非遞歸實現。

其遞歸代碼為：

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

一、阿克曼函數 – 非遞歸實現

由于阿克曼函數中，每計算一個數，其都高度依賴前一個數計算的結果，
因此在本非遞歸實現的思路，其實和遞歸差不多，利用棧來實現。

由于在C 語言中，操作棧比較麻煩，我們此處，就用單向循環鏈表來模擬棧。
以鏈表的頭指針作為棧頂， 每次入棧就是向鏈表頭部插入一個元素，出棧就是從鏈表頭部刪除一個元素

具體實現如下:

#include <stdio.h>// 單向循環鏈表定義 typedef struct ListNode{long long value;struct ListNode *next; }ListNode, *LinkList;// 定義兩個List 分別存儲 m 和 n 的值. LinkList m_ListHead; LinkList n_ListHead; int is_Empty(LinkList ListHead){/*int count=0;LinkList List_tmp=ListHead->next;while(List_tmp != ListHead){count++;List_tmp = List_tmp->next; } printf("當前鏈表元素個數 %d\n",count);*/// 單向循環鏈表next 等于自身時，為空 if(ListHead->next == ListHead){return 1;}return 0; }// 入棧,使用頭插法插入元素 void push(LinkList ListHead, long long num){LinkList List_tmp;List_tmp = (LinkList)malloc(sizeof(struct ListNode));List_tmp->value = num;List_tmp->next = ListHead->next;ListHead->next = List_tmp; }// 出棧, 從頭部刪除元素 void pop(LinkList ListHead){LinkList List_tmp;if( !is_Empty(ListHead) ){List_tmp = ListHead->next;ListHead->next = List_tmp->next;free(List_tmp); // 釋放元素} }void clear_List(LinkList ListHead){int count=0;LinkList List_tmp=ListHead->next;while(List_tmp != ListHead){ListHead->next = List_tmp->next;free(List_tmp);List_tmp = ListHead->next;count++;} printf("\n釋放了%d個鏈表元素！！！\n", count); }// 阿克曼函數實現 long long ack(long long m, long long n) {push(m_ListHead, m); // 將 m 入棧push(n_ListHead, n); // 將 n 入棧while( !is_Empty(m_ListHead) ) // 判斷 m 鏈表是否為空{// m != 0時，入棧 while(m != 0){if(n == 0){printf("[%s][%4d] 當前m=%lld, n=%lld, 即將入棧m-1=%lld, n=1 \n", __func__, __LINE__, m, n, m-1); m = m-1;n = 1;push(m_ListHead, m); // 將 m 入棧push(n_ListHead, n); // 將 n 入棧}else{// 使用 -1 代表 ack(m - 1, ack(m, n - 1)); 的情況 printf("[%s][%4d] 當前m=%lld, n=%lld, 即將入棧m-1=%lld, n=-1 \n", __func__, __LINE__, m, n, m-1); n = n-1;push(m_ListHead, m-1); // 將 m 入棧push(n_ListHead, -1); // 將 n 入棧} }// 當 m==0 時 出棧 printf("[%s][%4d] 當前m=%lld, n=%lld, 計算 n=n+1 = %lld\n", __func__, __LINE__, m, n, n+1); n = n+1;while( (!is_Empty(m_ListHead)) && (n_ListHead->next->value != -1)){printf("[%s][%4d] 當前m=%lld, n=%lld, 即將出棧 m =%lld, n=%lld \n", __func__, __LINE__, m, n, m_ListHead->next->value, n_ListHead->next->value); pop(m_ListHead);pop(n_ListHead);} // 處理 ack(m - 1, ack(m, n - 1));的情況，此時，獲取m-1 的值，彈出-1, 將當前n push 入棧 if((!is_Empty(m_ListHead))){m = m_ListHead->next->value;pop(n_ListHead); push(n_ListHead, n);}}return n; }int main(void) {long long m=0;long long n=0;// 分配 List 頭結點 m_ListHead = (LinkList)malloc(sizeof(struct ListNode));n_ListHead = (LinkList)malloc(sizeof(struct ListNode));m_ListHead->next = m_ListHead;n_ListHead->next = n_ListHead;while(m != -1){scanf("%d %d", &m, &n);printf("\n\n計算結果===> m=%lld,n=%lld 時, ack=%lld \n\n", m, n, ack(m, n));}// 釋放鏈表頭節點內存 free(m_ListHead);free(n_ListHead);return 0; }

實測結果為：

2 2 [ack][ 118] 當前m=2, n=2, 即將入棧m-1=1, n=-1 [ack][ 118] 當前m=2, n=1, 即將入棧m-1=1, n=-1 [ack][ 110] 當前m=2, n=0, 即將入棧m-1=1, n=1 [ack][ 118] 當前m=1, n=1, 即將入棧m-1=0, n=-1 [ack][ 110] 當前m=1, n=0, 即將入棧m-1=0, n=1[ack][ 125] 當前m=0, n=1, 計算 n=n+1 = 2 [ack][ 129] 當前m=0, n=2, 即將出棧 m =0, n=1[ack][ 125] 當前m=0, n=2, 計算 n=n+1 = 3 [ack][ 129] 當前m=0, n=3, 即將出棧 m =0, n=2 [ack][ 129] 當前m=0, n=3, 即將出棧 m =1, n=1 [ack][ 118] 當前m=1, n=3, 即將入棧m-1=0, n=-1 [ack][ 118] 當前m=1, n=2, 即將入棧m-1=0, n=-1 [ack][ 118] 當前m=1, n=1, 即將入棧m-1=0, n=-1 [ack][ 110] 當前m=1, n=0, 即將入棧m-1=0, n=1[ack][ 125] 當前m=0, n=1, 計算 n=n+1 = 2 [ack][ 129] 當前m=0, n=2, 即將出棧 m =0, n=1[ack][ 125] 當前m=0, n=2, 計算 n=n+1 = 3 [ack][ 129] 當前m=0, n=3, 即將出棧 m =0, n=2[ack][ 125] 當前m=0, n=3, 計算 n=n+1 = 4 [ack][ 129] 當前m=0, n=4, 即將出棧 m =0, n=3[ack][ 125] 當前m=0, n=4, 計算 n=n+1 = 5 [ack][ 129] 當前m=0, n=5, 即將出棧 m =0, n=4 [ack][ 129] 當前m=0, n=5, 即將出棧 m =1, n=3 [ack][ 118] 當前m=1, n=5, 即將入棧m-1=0, n=-1 [ack][ 118] 當前m=1, n=4, 即將入棧m-1=0, n=-1 [ack][ 118] 當前m=1, n=3, 即將入棧m-1=0, n=-1 [ack][ 118] 當前m=1, n=2, 即將入棧m-1=0, n=-1 [ack][ 118] 當前m=1, n=1, 即將入棧m-1=0, n=-1 [ack][ 110] 當前m=1, n=0, 即將入棧m-1=0, n=1[ack][ 125] 當前m=0, n=1, 計算 n=n+1 = 2 [ack][ 129] 當前m=0, n=2, 即將出棧 m =0, n=1[ack][ 125] 當前m=0, n=2, 計算 n=n+1 = 3 [ack][ 129] 當前m=0, n=3, 即將出棧 m =0, n=2[ack][ 125] 當前m=0, n=3, 計算 n=n+1 = 4 [ack][ 129] 當前m=0, n=4, 即將出棧 m =0, n=3[ack][ 125] 當前m=0, n=4, 計算 n=n+1 = 5 [ack][ 129] 當前m=0, n=5, 即將出棧 m =0, n=4[ack][ 125] 當前m=0, n=5, 計算 n=n+1 = 6 [ack][ 129] 當前m=0, n=6, 即將出棧 m =0, n=5[ack][ 125] 當前m=0, n=6, 計算 n=n+1 = 7 [ack][ 129] 當前m=0, n=7, 即將出棧 m =0, n=6 [ack][ 129] 當前m=0, n=7, 即將出棧 m =1, n=5 [ack][ 129] 當前m=0, n=7, 即將出棧 m =2, n=2計算結果===> m=2,n=2 時, ack=7-1 2 請按任意鍵繼續. . .

總結

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

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