題目描述：
把M個同樣的球放入N個同樣的袋中，允許有的空著不放，問共有多少种放法（用K表示）
例如：M=7，N=3時，K=8。在這裡（5，1，1）與（1，5，1）是同一种放法。
問：M=8，N=5時，K為多少？
解題思路：
從數學方法考慮：
第一步：假設都放入1個袋中，則只有1种放法；
第二步：假設放入2個袋中，則每個袋中至少有1個，相當於8-2=6個球放入2個袋中，即把6分解成2個數（含0），有4种放法；
第三步：假設放入3個袋中，則每個袋中至少有1個，相當於8-3=5個球放入3個袋中，即把5分解成3個數（含0），有5种放法；
第四步：假設放入4個袋中，則每個袋中至少有1個，相當於8-4=4個球放入4個袋中，即把4分解成4個數（含0），有5种放法；
第五步：假設放入5個袋中，則每個袋中至少有1個，相當於8-5=3個球放入5個袋中，即把3分解成5個數，有3種方法。
總數為1+4+5+5+3=18種。
從編程角度考慮：
如果只有1個袋子，則只有1种放法，所以if(n==1) return 1;
如果n>m，即袋子是多的，則相當於把m個球放入m個袋中，多出來的n-m個袋子是空的；
如果m>n，此時可列遞歸如下：
把m個球放入n個袋中，相當於有空袋子的放法與不空袋子的放法之和，即空1個袋子時，放法為fun(m,n-1); 不空袋子時，相當於先在每個袋子中放入1個球，然後再把m-n個球放入n個袋中，所以fun(m,n)=fun(m,n-1)+fun(m-n,n);
當m==n時，列出邊界條件返回1。
完整代碼如下：
#include
using namespace std;
int fun(int m,int n);
int main()
{
int m,n;
cin>>m>>n;
cout<分享到:
