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<stdio.h>
const int cost[3]={1,2,5};
int main()
{
	int n;
	scanf("%d",&n);

	int num=0;
	int i,j;
	for(i=0;i<=n*10/cost[2];i++)
	{
		int max_j = (n*10-i*(cost[2]))/cost[1];
		for(j=0;j<=max_j;j++)
			num++;
	}

	printf("%d",num);
	return 0;
}

 参考程序B（递归）

#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]);
	 }
 }

 后面的递归代码是四年前写的，所以没有追求效率问题。