首页 > ACM题库 > 九度OJ > 九度-1160-放苹果[解题代码]
2013
12-13

九度-1160-放苹果[解题代码]

题目来源:2011年北京大学计算机研究生机试真题

题目描述:

把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

cpp 代码如下:
#include <stdio.h>
int f(int a,int b){
	if(a<0)
		return 0;
	else if(a==0 || b==1)
		return 1;
	else
		return f(a,b-1)+f(a-b,b);//有空盘 和 无空盘(即每个盘先放一个)
}
int main(){
	int n;
	int a,b;
	while(scanf("%d",&n)!= EOF){
		for(int i=0; i<n; i++){
			scanf("%d %d",&a,&b);
			printf("%d\n",f(a,b));
		}
	}
	return 0;
}

/**************************************************************
	Problem: 1160
	User: coder
	Language: C
	Result: Accepted
	Time:0 ms
	Memory:912 kb
****************************************************************/


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确