九度OJ—题目1160：放苹果
浏览数：15 /
时间：2015年06月11日
- 题目描述：
-
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
- 输入：
-
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
- 输出：
-
对输入的每组数据M和N，用一行输出相应的K。
- 样例输入：
-
1 7 3
- 样例输出：
-
8
- 答疑：
- 解题遇到问题?分享解题心得?讨论本题请访问：http://t.jobdu.com/thread-7883-1-1.html
基本思路：
令（m,n）表示m个苹果放到n个篮子里的种数，那么势必会有篮子空余、篮子都放两种情况。
1、假如有一个篮子空余，那么空余篮子相当于没用，那么（m,n）的问题就是把m个苹果放到n-1个篮子里的种数（m,n-1）
2、假如没有篮子空余，那么每个篮子至少应该有一个苹果，即剩下了m-n个苹果了，问题就变成了，把m-n个苹果放到n个篮子里的问题了（m-n,n）。
所以：（m,n）=（m,n-1）+ （m-n,n）;
#include <iostream>
using namespace std;
int fang(int k,int r)
{
if(k<0)
return 0;
if(r==1||k==1)
return 1;
return fang(k-r,r)+fang(k,r-1);
}
int main()
{
int k,r;
int n;
while(cin>>n)
{
for(;n!=0;n--){
cin>>k>>r;
cout<<fang(k,r)<<endl;
}
}
return 0;
}
/**************************************************************
Problem: 1160
User: vhreal
Language: C++
Result: Accepted
Time:0 ms
Memory:1520 kb
****************************************************************/郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
