先看下題目：

電影院買票排隊，票價50，排隊的人中攜帶50元的有20個人，攜帶100的有10個人，售票處開始時沒有余額， 問最多有多少種排隊方式使得售票處能夠找的開(攜帶相同數額的人交換位置算一種排隊方式)。

畫圖的話比較容易理解，二叉圖，根節點為50，然后往下排列，從根節點到葉子節點即為一個排隊方式。設f(m,n)，其中m為50的個數，n為100的個數，f(m,n)表示排隊方式，當m>=20或者n>=10時，排隊結束，這是再插入節點只有一種方式，當m>n時，有兩個子節點，分別時50和100，當m==n時，只有一個節點，即50節點。這樣能夠得到遞歸公式。

int f(int m50, int n100, int m, int n) {if (m50 == m || n == n100)return 1;else if (m50 > n100)return f(m50+1, n100, m, n) + f(m50, n100+1, m, n);else if (m50 == n100) return f(m50+1, n100, m, n);elseprintf("邏輯錯誤！");return 0; }

二叉圖：

?

通過遞歸公式也很容易得到遞推的方法，f[m][n] = f[m-1][n] + f[m][n-1],這里m>=n，邊界條件f[m][0] = 1, f[m][n] = 0（m< n）。

這里最好使用遞推來解決，因為遞推使用兩層循環，時間復雜度為O(n^2)，使用遞歸的話時間復雜度為O(3^n)，差距太大。

這道題還有一種擴展，擴展題目增加了約束條件，"第五位必須是50，第八位必須是100"，如果還是使用二叉圖來看可能不是那么容易分析，我們可以使用下面的圖來分析：

橫坐標為50，縱坐標為100，坐標圖上的點f[m][n]表示排隊方式，約束條件是在f(4,1)和f(3,2)這個點，沒有約束條件情況下

f(4,1) = f(4,0) + f(3,1)，f(3,2) = f(3,1) + f(2,2)，即有從左到右和從下到上兩種方式，根據約束條件，到達f(4,1)這個點不能是f(4,0)，因為第五位必須是50，同理可以看到f(3,2)不能由f(3,1)得到，對于第八位是100的約束，可以采用同樣的分析方法，在遞歸或者遞推處理中針對這幾個點做特殊處理。帶約束條件的擴展題通過圖2可能更容易理解。

下面是普通排隊和擴展題的c代碼：

/* * 排隊問題*/#include <stdio.h> #define NUM 100int f(int m50, int n100, int m, int n) {if (m50 == m || n == n100)return 1;else if (m50 > n100)return f(m50+1, n100, m, n) + f(m50, n100+1, m, n);else if (m50 == n100) return f(m50+1, n100, m, n);elseprintf("邏輯錯誤！");return 0; }void main() {int i,j,m,n,k[NUM][NUM]={0};//遞歸處理printf("分別輸入持有50和100幣值的人數："); scanf("%d %d", &m, &n);printf("當持有50的人數為%d，持有100的人數為%d，總的排隊方式有：%d\n",m,n, f(1,0,m,n));//遞推方式for (i = 1; i <= m; i++)k[i][0] = 1;for (j = 1; j <= n; j++) for (i = 0; i < j; i++)k[i][j] = 0;for (i = 1; i <= m; i++)for (j = 1; j <= n && j <= i; j++)k[i][j] = k[i-1][j] + k[i][j-1];printf("當持有50的人數為%d，持有100的人數為%d，總的排隊方式有：%d\n",m,n, k[m][n]); }

帶約束條件的擴展題：

/** 帶約束條件的排隊問題*/#include <stdio.h>#define NUM 100void main() {int i,j,m,n,k[NUM][NUM]={0};printf("分別輸入持有50和100幣值的人數："); scanf("%d %d", &m, &n);//遞推方式for (i = 1; i <= 7; i++)k[i][0] = 1;for (j = 1; j <= n; j++) for (i = 0; i < j; i++)k[i][j] = 0;for (i = 1; i <= m; i++)for (j = 1; j <= n && j <= i; j++){if ((i == 4 && j == 1) || (i == 3 && j == 2) )k[i][j] = k[i-1][j];if((i == 7 && j == 1) ||(i == 6 && j == 2)||(i == 5 && j == 3))k[i][j] = k[i][j-1];else k[i][j] = k[i-1][j] + k[i][j-1];}printf("當持有50的人數為%d，持有100的人數為%d，總的排隊方式有：%d\n",m,n, k[m][n]); }

參考資料：

1.?數據結構?: C語言版/ 嚴蔚敏，吳偉民編著

=============================================================================================

Linux應用程序、內核、驅動開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結

以上是生活随笔為你收集整理的递归与递推 普通排队问题及带约束条件的排队问题 c代码的全部內容，希望文章能夠幫你解決所遇到的問題。

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