用C++编写 编写程序，用1分、2分、5分的硬币凑成300元以下的钱数，要求硬币的数目最少。

Question

如题所述

Answer 1

硬币兑换问题能不能用贪心法来解，要依据硬币的面值而定，比如面值为1、6、10的就不可以，比如若兑换总金额为12，用2个面值为6的硬币就可以了，而贪心法则会选择一个面值为10的硬币和2个面值为1的硬币。
而LZ这里所列举的面值是可以使用贪心法的，粗略的证明如下：
首先，对于兑换金额为1、2、3、4、5的情况，很容易说明贪心法是最优的（使用硬币最少）；
如下使用归纳法，假设兑换总金额为1、2、……、k-1时都已解决，现在兑换金额为k（k>5），现在使用贪心法，使用一枚面值为5的硬币，然后剩下的兑换金额为k-5，而这个问题已经解决过，于是k的最少硬币数就是k-5的加1，设此值为opt(k)=opt(k-5)+1，假如它不是最优的，那么一定有另一种兑换方式，所使用的硬币更少，可以使用面值为2的硬币，得到opt(k-2)+1，也可以使用面值为1的硬币，得到opt(k-1)+1，对于本题，面值为k-1和面值为k-2不会比面值为k-5的用到的硬币更少（应为k-5比他们小3以上，而1+2<=3），故原解还是最优解。
综上所述，对于本题所列出的面值，贪心法可以得到最优解，代码如下：
#include<stdio.h>

int main(){
int coins[]={5,2,1};//所有硬币面值面值已按从大到小排序
int n;
while(1==scanf("%d",&n)){ //输入要兑换的面值
int cnt=0;
for(int i=0;i<3&&n>0;++i){
if(n>=coins[i]){
cnt+=n/coins[i];
n%=coins[i];
}
}
printf("min: %d\n",cnt);//输出硬币个数
}
return 0;
}
如若不能使用贪心法，本题一种常用的解法是动态规划，LZ可以随便找本算法书查阅，这里给出示例代码：
#include<stdio.h>

int main(){
int coins[]={1,2,5},num[30001];
num[0]=0;
for(int i=0;i<3;++i){
for(int j=coins[i];j<=30000;++j){
num[j]=num[j-coins[i]]+1;
}
}
int n;
while(1==scanf("%d",&n)){
printf("min: %d\n",num[n]);
}
return 0;
}
以上两段代码LZ的输入都要以分为单位。

Answer 2

是用C++编写的哦！一楼用的是C吧！！
#include<iostream>
using namespace std;

void main()
{
int m,sum=0,i,j,p,q;
float n,k;
do
{
cout<<"请输入你想要凑成的钱数（元）："<<endl;
cin>>n;
k=n*100;
}while(n>300);
m=k;
i=m/5;
p=m%5;
j=p/2;
q=p%2;
sum=i+j+q;
cout<<"共需要5分，2分，1分的钱数为:"<<i<<" : "<<j<<" : "<<q<<endl;
cout<<"总共是:"<<sum<<"个硬币！"<<endl;
}

OK啦！运行通过的！

Answer 3

#include <stdio.h>

int main(void)
{
int x;
int n=0;
printf("请输入钱的数目：");
scanf("%d",&x);

while(x>=5)
{
x=x-5;
n++;
}
while(x>=2)
{
x=x-2;
n++;
}
while(x>=1)
{
x=x-1;
n++;
}
printf("硬币数=%d\n",n);
return 0;
}
希望对你有帮助。本回答被网友采纳

Answer 4

很好解啊，先算5分的个数，余数在除2，剩下就是1分的