題目鏈接：http://poj.org/problem?id=1664

m個相同的蘋果放在n個相同的盤子里，有多少種不一樣的方法。

例如，3個蘋果放在4個盤子里有（3，0，0，0）（1，1，1，0）（2，1，0，0）3種方法。多出的1個盤子不影響結果。

4個蘋果放在3個盤子里（4，0，0）（3，1，0）（2，2，0）（2，1，1）

4個蘋果放在4個盤子里，{ 可以分解成全部盤子都擺上, 每個盤子里都至少有1個，f(m-n,n)，盤子有不擺的 f(m,n-1) }；f(4,4) = f(0,4) + f(4,3) = 1+4 = 5，（1，1，1，1）（4，0，0，0）（3，1，0，0）（2，2，0，0）（2，1，1，0）5種方法。f(0,n)表示每個盤子里都是一個蘋果的情況。

當m < n 時，f(m,n) = f(m,m)
當m >= n 時，f(m,n) = f(m-n,n) + f(m,n-1)

終止條件：
蘋果m = 1時，只有一種擺法
碟子n = 1時，只有一種擺法
m=n時，所有碟子都擺一個的擺法 f(m-n,n) = f(0,n) = 1

#include<iostream> using namespace std; unsigned long func(size_t apple, size_t disc) {if(apple == 1 || apple == 0 || disc == 1)return 1;if(apple < disc)return func(apple, apple);elsereturn func(apple, disc-1) + func(apple-disc, disc); } int main() {size_t t, apple, disc;cin >> t;while(t--){cin >> apple >> disc;cout << func(apple, disc) << endl;}return 0; }

總結

以上是生活随笔為你收集整理的POJ 1664 苹果放盘子（递归）的全部內容，希望文章能夠幫你解決所遇到的問題。

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