算法分析与设计----找钱问题代码.doc

文档介绍：#include<>
#include<>
//using namespace std;
//int sum(int x,char*a)
//{
// int sum=0;
// for(int i=0;i<x;i++)
// {
// sum+=a[1];
// }
// return sum;
//}
int zhaoqian(int J,int N,int *b)
{
int min=0;
int a1,a2;
if (J==0||N==0) return 0;
else if (N==1) return J/b[0];
else if(J/b[N-1]==0) return zhaoqian(J,N-1,b);
for(int i=0;i<J/b[N-1];i++)
{
a1=zhaoqian(J-b[N-1]*i,N-1,b)+i;
a2=zhaoqian(J-b[N-1]*(i+1),N-1,b)+i+1;
if (a1<a2)
min=a1;
else
min=a2;
}
return min;
}
void main()
{
int J,N; //钱的种类有1,3,4,5
int b[10];
int min;
int x;
cout<<"输入钱的种类数:";
cin>>N;
cout<<"输入钱的种类"<<endl;
for(int i=0;i!=-1;i++)
{
cin>>x;
if(x==-1) break;

else b[i]=x;
}
cout<<"要找的钱的总数:";
cin>>J;

min=zhaoqian(J,N,b);
cout<<"最少硬币数为:";
cout<<min;
}