研究研究算法--递归算法(poj1664)

一、前言

感叹计算机的强大!

二、题意

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法

三、分析

利用动态规划的思想,假如将7个苹果放进3个盘子里,可以分2种情况考虑:

1,空着一个盘子不放,即将7个苹果放进2个盘子里;

2,先每个盘子均放进一个苹果,再按照本规则继续放下去。

于是有递推公式:F(X,Y)=F(X,Y-1)+F(X-Y,Y)

参考的这哥们博客,贴个地址,尊重作者。他是不是抄来的,我不关心。

http://blog.163.com/soonhuisky@126/blog/static/15759173920103114930895/

四、编程

#include "stdio.h"
#include "stdlib.h"
int f(int m,int n);
int main(int argc, char const *argv[]) {

  char *fmt = (char *)malloc(sizeof(char)*20);
  int m,n;
  printf("%s\n", "enter m and n : ");
  fgets(fmt,20,stdin);
  sscanf(fmt,"%d  %d",&m,&n);
  printf("m is %d,n is %d\n", m ,n);

  printf("res is %d \n", f(m,n));
  return 0;
}

// m --> n
int f(int m,int n){
  if( m == 0 || n == 1) return 1;
  if(m<n) return f(m ,m);
  return f(m,n-1) + f(m-n , n);
}

五、测试下

enter m and n : 
7 7
m is 7,n is 7
res is 15

六、结尾

感叹计算机的强大!多运用计算机思维!



打赏作者

发表评论

电子邮件地址不会被公开。 必填项已用*标注