递归实现,显示用1分、2分和5分的硬币凑成1元,一共有多少种方法。"/>
用递归实现,显示用1分、2分和5分的硬币凑成1元,一共有多少种方法。
一:选择题分析:
541种 分情况讨论
x为一分钱,y为2分钱,z为5分钱
设:ax+by+cz=100
我们从最大的5分钱来讨论,c可取[0,20]的整数.
当c取0时,b可取[0,50]一共51种,对应的a也是51个,那么该组解为51
当c取1时,b可取[0,47]一共48种,对应的a也是48个,那么该组解为48
当c取2时,b可取[0,45]一共46种,对应的a也是46个,那么该组解为46
当c取3时,b可取[0,42]一共43种,对应的a也是43个,那么该组解为43
当c取4时,b可取[0,40]一共41种,对应的a也是41个,那么该组解为41
当c取5时,b可取[0,37]一共38种,对应的a也是38个,那么该组解为38
当c取6时,b可取[0,35]一共36种,对应的a也是36个,那么该组解为36
当c取7时,b可取[0,32]一共33种,对应的a也是33个,那么该组解为33
当c取8时,b可取[0,30]一共31种,对应的a也是31个,那么该组解为31
......
当c取20时,b只能取0,a也只能取0,那么该组解为1
是不是看的头大了?其实这类问题都是有规律的,取几个算一下解你就发现当c往上取的时候各位数以1,3,6,8循环,最高到51.
那么直接(1+3+6+8)x5+10x4+20x4+30x4+40x4+51=541
二:递归代码实现
方法一:
#include <stdio.h>
int a[3]= {1,2,5};
int fun(int s,int n){
int count=0;
int i;
if(n>2){
if(s==0)
return 1;
else
return 0;
}else{
for(i=0;s>=i*a[n];i++){
count = count + fun(s-i*a[n],n+1);
}
}
return count;
}
int main(){
printf("%d\n",fun(100,0));
return 0;
}
方法二:容易理解,从上往下进行递归
#include <stdio.h>
int ans = 0;
int a[3]={5,2,1};
void dfs(int s,int m){
int i;
if(s==0){
ans++;
return ;
}
for(i=m;i<3;i++){
if(s>=a[i])
dfs(s-a[i],i);
}
}
int main(){
ans = 0;
dfs(100,0);
printf("%d",ans);
return 0;
}
更多推荐
用递归实现,显示用1分、2分和5分的硬币凑成1元,一共有多少种方法。
发布评论