用递归实现，显示用1分、2分和5分的硬币凑成1元，一共有多少种方法。

递归实现，显示用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;
}