RUC_JudgeOnline 1007 n元钱的构成方法数

RUC_JudgeOnline 1007 n元钱的组成方法数

?

n元钱的组成方法数

?

Description

使用1角、2角和5角的硬币组成n元钱。编程输出有多少种组成方法。

Input

共一行，为钱数n（元）(n<=10)。

Output

共一行，为方案数m。

Sample Input

?

1

?

Sample Output

?

10

?

Source

习题6-8

问题分析

此题可以用枚举和递归来解决问题。

方法A：枚举法。使用双重循环将所有i*5+j*2<n*10.的情况枚举出来。就是要求的最终方案数目。因为剩下的1的数目是已经确定了的。见参考程序A。

方法B：递归法。每次都使用一种钱币来组成n元钱的一部分。然后对剩下的进行再组成。由于这个递归比较简单，看程序就能读懂了。就不多写分析记录了。

参考程序A（枚举）

#include<iostream>using namespace std;const int cost[4]={0,1,2,5};int ans[4];void search(int k,int q);int num=0;int main(){int n;cin>>n;search(3,10*n); cout<<num<<endl;return 0;} void search(int k,int q) { if(k==0) { if(q==0) { num++;  } return; }  for(int i=0;i<=q/cost[k];i++) { ans[k]=i; search(k-1,q-i*cost[k]); } }

?