POJ——放苹果

时间:2022-09-04 09:11:31
总时间限制: 
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——放苹果的更多相关文章

  1. POJ 放苹果问题&lpar;递归&rpar;

    首先我们想象有一个函数count  f(m,n)可以把m个苹果放到n个盘子中. 根据 n 和 m 的关系可以进一步分析: 特殊的m <=1|| n <= 1时只有一种方法: 当 m &lt ...

  2. POJ 1664 放苹果

    放苹果 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 24985   Accepted: 15908 Description ...

  3. poj 1664 放苹果(递推)

    题目链接:http://poj.org/problem? id=1664 放苹果 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions ...

  4. poj 1664 放苹果 递归

    题目链接: http://poj.org/problem?id=1664 题目描述: 有n个苹果,m个盒子,盒子和苹果都没有顺序,盒子可以为空,问:有多少种放置方式? 解题思路: 当前有n个苹果,m个 ...

  5. POJ --- 1164 放苹果

    放苹果 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 24947   Accepted: 15887 Description ...

  6. poj 1664放苹果(递归)

    放苹果 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 37377   Accepted: 23016 Description ...

  7. poj 1664 放苹果 &lpar;划分数&rpar;

    题意:中文题目,不解释... 题解: 第一种方法是暴力深搜:枚举盘子1~n放苹果数量的所有情况,不需要剪枝:将每次枚举的情况,即每个盘的苹果数量,以字典序排序,然后存进set里 以此去重像" ...

  8. poj 1664 放苹果(dfs&rpar;

    放苹果 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 30284   Accepted: 19098 Description ...

  9. openjudge(POJ)-1664 放苹果

    对于n个盘子,m个苹果,我们要么在每个盘子上都放苹果,要么至少有一个盘子不放. 一个盘子不放就是f(m,n-1),全部都放的时候苹果就变成了n-m个,但是盘子的数目是不变的,因为此时还没有产生方案数, ...

随机推荐

  1. &lowbar;&lowbar;attribute&lowbar;&lowbar;

    转来的: http://www.cnblogs.com/astwish/p/3460618.html __attribute__ 你知多少? GNU C 的一大特色就是__attribute__ 机制 ...

  2. Server&period;Transfer和Response&period;Redirect区别

    根本上,Response是叫浏览器去重新转向到指定的网页,而Server自然是发生在服务器端为主了,因此会有以下区别:1. Server.Transfer只能够转跳到本地虚拟目录指定的页面,而Resp ...

  3. codevs2622数字序列( 连续子序列最大和O(n)算法)

    /* 算法描述:维护一个s[p]表示累加和 并且更新最大值ans 如果s[p]<0 则从p+1重新累加 证明:设某个区间的起点和终点分别为s t 分两种情况 1.t<p:设s2表示1到s的 ...

  4. DataGridView大扩展——显示行号

    原文 DataGridView大扩展——显示行号 在DataGridView 的实际使用中,经常需要标示出行号,这样可以比较醒目地看到当前信息.不过DataGridView 在绘制 DataGridV ...

  5. C&num;正则学习

    正则的力量无法小觑,短短的几个字符,往往胜过几十行的代码,大大可以简化我们冗余的代码. 以前在js里用正则比较多,今天来熟悉下C#中正则的使用方法,权当笔记了! 如果把正则当做一门语言的话,那么正则的 ...

  6. C&num;默认参数原理探究

    起因 写这一篇的起因是想要通过新增默认参数来代替以前的方法,结果发现尽管在调用时写起来一样,实际上也没有被当做同样的方法,两个方法大致如下: // 先前的方法-删除 private static st ...

  7. Android技术框架——Dagger2

    Dagger2 是一个Android依赖注入框架.没错依赖注入,学习过spring的同学看到这词,应该是挺熟悉的.当然既然是Android的课题,我们就来聊聊Dagger2 ,android开发当前非 ...

  8. Cow Cycling 动态规划

    1552: Cow Cycling 时间限制(普通/Java):1000MS/10000MS     内存限制:65536KByte总提交: 39            测试通过:20 描述 The ...

  9. 从集合中查找最值得方法——max&lpar;&rpar;&comma;min&lpar;&rpar;&comma;nlargest&lpar;&rpar;&comma;nsmallest&lpar;&rpar;

    从集合中查找最值得方法有很多,常用的方法有max(),min(),nlargest(),nsmallest()等. 一.max()和min() 1.1 入门用法 直接使用max(),min(),返回可 ...

  10. Hibernate的核心接口

    Hibernate5个核心接口 所有Hibernate应用中都会访问Hibernate的5个核心接口 Configuration接口:配置Hibernate,根启动Hibernate,创建Sessio ...