- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 把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
- 找递推关系:设f(m,n)表示m个苹果放入n个盘子,若n>m,则至少有n-m个空盘子,f(m,n)=f(m,m)
- 若n<=m 有两种情况,一是有一个空盘子f(m,n)=f(m,n-1)
- 二是所有盘子都放了苹果,等于把每个盘子都拿掉一个苹果后的值f(m,n)=f(m-n,n);
- 两种情况加一起就是f(m,n)=f(m,n-1)+f(m-n,n);
- 递归终止条件一是m=0,二是n=1;
/*
解题分析:
设f(m,n) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)
当n<=m:不同的放法可以分成两类:
1、有至少一个盘子空着,即相当于f(m,n) = f(m,n-1);
2、所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即f(m,n) = f(m-n,n).
而总的放苹果的放法数目等于两者的和,即 f(m,n) =f(m,n-1)+f(m-n,n)
递归出口条件说明:
当n=1时,所有苹果都必须放在一个盘子里,所以返回1;
当没有苹果可放时,定义为1种放法;
递归的两条路,第一条n会逐渐减少,终会到达出口n==1;
第二条m会逐渐减少,因为n>m时,我们会return f(m,m) 所以终会到达出口m==0.
*/
#include<stdio.h> int fun(int m,int n) //m个苹果放在n个盘子*有几种方法
{
if(m==||n==) //因为我们总是让m>=n来求解的,所以m-n>=0,所以让m=0时候结束,如果改为m=1,
return ; //则可能出现m-n=0的情况从而不能得到正确解
if(n>m)
return fun(m,m);
else
return fun(m,n-)+fun(m-n,n);
} int main()
{
int T,m,n;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
printf("%d\n",fun(m,n));
}
}
欢迎来我的个人网站:http://www.rxwcv.cn
POJ——放苹果的更多相关文章
-
POJ 放苹果问题(递归)
首先我们想象有一个函数count f(m,n)可以把m个苹果放到n个盘子中. 根据 n 和 m 的关系可以进一步分析: 特殊的m <=1|| n <= 1时只有一种方法: 当 m < ...
-
POJ 1664 放苹果
放苹果 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 24985 Accepted: 15908 Description ...
-
poj 1664 放苹果(递推)
题目链接:http://poj.org/problem? id=1664 放苹果 Time Limit: 1000MS Memory Limit: 10000K Total Submissions ...
-
poj 1664 放苹果 递归
题目链接: http://poj.org/problem?id=1664 题目描述: 有n个苹果,m个盒子,盒子和苹果都没有顺序,盒子可以为空,问:有多少种放置方式? 解题思路: 当前有n个苹果,m个 ...
-
POJ --- 1164 放苹果
放苹果 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 24947 Accepted: 15887 Description ...
-
poj 1664放苹果(递归)
放苹果 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 37377 Accepted: 23016 Description ...
-
poj 1664 放苹果 (划分数)
题意:中文题目,不解释... 题解: 第一种方法是暴力深搜:枚举盘子1~n放苹果数量的所有情况,不需要剪枝:将每次枚举的情况,即每个盘的苹果数量,以字典序排序,然后存进set里 以此去重像" ...
-
poj 1664 放苹果(dfs)
放苹果 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 30284 Accepted: 19098 Description ...
-
openjudge(POJ)-1664 放苹果
对于n个盘子,m个苹果,我们要么在每个盘子上都放苹果,要么至少有一个盘子不放. 一个盘子不放就是f(m,n-1),全部都放的时候苹果就变成了n-m个,但是盘子的数目是不变的,因为此时还没有产生方案数, ...
随机推荐
-
__attribute__
转来的: http://www.cnblogs.com/astwish/p/3460618.html __attribute__ 你知多少? GNU C 的一大特色就是__attribute__ 机制 ...
-
Server.Transfer和Response.Redirect区别
根本上,Response是叫浏览器去重新转向到指定的网页,而Server自然是发生在服务器端为主了,因此会有以下区别:1. Server.Transfer只能够转跳到本地虚拟目录指定的页面,而Resp ...
-
codevs2622数字序列( 连续子序列最大和O(n)算法)
/* 算法描述:维护一个s[p]表示累加和 并且更新最大值ans 如果s[p]<0 则从p+1重新累加 证明:设某个区间的起点和终点分别为s t 分两种情况 1.t<p:设s2表示1到s的 ...
-
DataGridView大扩展——显示行号
原文 DataGridView大扩展——显示行号 在DataGridView 的实际使用中,经常需要标示出行号,这样可以比较醒目地看到当前信息.不过DataGridView 在绘制 DataGridV ...
-
C#正则学习
正则的力量无法小觑,短短的几个字符,往往胜过几十行的代码,大大可以简化我们冗余的代码. 以前在js里用正则比较多,今天来熟悉下C#中正则的使用方法,权当笔记了! 如果把正则当做一门语言的话,那么正则的 ...
-
C#默认参数原理探究
起因 写这一篇的起因是想要通过新增默认参数来代替以前的方法,结果发现尽管在调用时写起来一样,实际上也没有被当做同样的方法,两个方法大致如下: // 先前的方法-删除 private static st ...
-
Android技术框架——Dagger2
Dagger2 是一个Android依赖注入框架.没错依赖注入,学习过spring的同学看到这词,应该是挺熟悉的.当然既然是Android的课题,我们就来聊聊Dagger2 ,android开发当前非 ...
-
Cow Cycling 动态规划
1552: Cow Cycling 时间限制(普通/Java):1000MS/10000MS 内存限制:65536KByte总提交: 39 测试通过:20 描述 The ...
-
从集合中查找最值得方法——max(),min(),nlargest(),nsmallest()
从集合中查找最值得方法有很多,常用的方法有max(),min(),nlargest(),nsmallest()等. 一.max()和min() 1.1 入门用法 直接使用max(),min(),返回可 ...
-
Hibernate的核心接口
Hibernate5个核心接口 所有Hibernate应用中都会访问Hibernate的5个核心接口 Configuration接口:配置Hibernate,根启动Hibernate,创建Sessio ...