找零钱问题的贪心策略.txt

很高兴成为这里的一员,我将继续努力,多多上传好的代码,文件里有一些自己写的,也有一些收集的程序,基本上都有解释.

//找零钱问题的贪心策略
//2004.9.10 
//YCL
#include<iostream.h>
void main()
{
 int count1=0,count2=0,count3=0,count4=0;//记录各种币值的数目
 int pay;                                //应付钱数
 int x;                                  //应找钱数
 do{
  cout<<"Now,You have 1 dollar.How much(cent)do you want to pay?";
  cin>>pay;
  if(pay<0)
   cout<<"I think you are stupid!"<<endl;
  else
   if(pay>100)
    cout<<"You don't have enough money!"<<endl;
 }while(pay<0||pay>100);                 //正确输入  
 x=100-pay;
 if(x<100)
 {
  while(x>=25&&x>0)                  //25美分币值的数目
  {                  
   count1++;
   x-=25;
  }
        while(x>=10&&x>0)                  //10美分币值的数目
  {
   count2++;
   x-=10;
  }
        while(x>=5&&x>0)                   //5美分币值的数目
  {
   count3++;
   x-=5;
  }
  while(x>0)                         //1美分币值的数目
  {
   count4++;
   x-=1;
  }
 }
 else
  cout<<"You don't buy anything!"<<endl;
 if(count1!=0||count2!=0||count3!=0||count4!=0)
 {
  cout<<"The shopper will give you:"<<endl;
  cout<<count1<<"coins of 25 cents"<<endl;
     cout<<count2<<"coins of 10 cents"<<endl;
  cout<<count3<<"coins of 5 cents"<<endl;
        cout<<count4<<"coins of 1 cents"<<endl;
 }
}