首先我要吐槽一下牛客网的草稿功能,刚才我写本篇文章,由于跳转到别的页面而没被保存,这是什么***垃圾的功能。 这道题首先来说我没有做出来,我最初的设想是排列组合,可能这种方法可以解决这道题,但是敢肯定的是这不是最优解, 当我用递归的思路想时,最初的设想是分三种情况(m>n)(m<n)(m==n),每种情况的有着不同的处理方法。代码如下
p++;
number(m,m);
return ;
}else if(m>n){
p++;
number(m-n,n);
return ;
}else if(m==n){
p++;
number(m,n-1);
return ;
}
这段代码是错误的,错误点就在于每一情况的处理方法不同,如果非要按这个逻辑写的话,每一个if下边的代码是return number(m,n-1)+number(m-n,n),因为不管这三种情况的哪一种,其处理逻辑都分为盘子有为空,或者盘子都用一个苹果占满这两种 情况,而最小的原子问题的处理逻辑就是这个。如果说要用数学证明其逻辑,我本人由于数学功底薄弱无法给予证明,遇到这种问题也是靠猜想。
if(m<0 || n<0 ){
return 0;
}
if(m==1 ||n==1){
return 1;
}
return number(m,n-1)+number(m-n,n);
}
int main(void){
int n=0,m=0;
while(cin>>m>>n){
p=0;
cout<<number(m,n)<<endl;
}
return 0;
}
还有一种写法,这是我最后的倔强,多多少少也要把p 加近代码中去
if(m<0 || n<0 ){
return ;
}
if(m==1 ||n==1){
p++;
return ;
}
number(m,n-1);
number(m-n,n);
return ;
}