/*
* Copyright (c) 2004
* All rights reserved.
*
* 文件名称： Change.cpp
* 文件标识： 见配置管理计划书
* 摘 要： 贪婪算法的(最少个数)找零钱算法
* 假设提供了数目不限的面值为25美分, 10美分, 5美分, 及1美分的硬币
* 求找1-99美分的算法
*
* 当前版本： 1.0
* 作 者： 田东
* 完成日期： 2004年12月5日
*
* 取代版本： 1.0
* 原 作 者： 输入原作者（或修改者）名字
* 完成日期： 2004年12月5日
*/
#include <iostream>
using namespace std;
void print(int, int);
int main(void)
{
const int n25 = 25;
const int n10 = 10;
const int n5 = 5;
const int n1 = 1;
int n, i;
for(;;)
{
cout<<endl<<"input the number of change(1-99)(0 to quit):"<<endl;
cin>>n;
if(n == 0)
{
break;
}
if(n < 1 || n > 99)
{
continue;
}
print(n, 0);
for(i=0; n >= n25; i++)
{
n -= 25;
}
if(i > 0)
{
print(n25, i);
}
for(i=0; n>=10; i++)
{
n -=10;
}
if(i > 0)
{
print(n10, i);
}
for(i=0; n>=5; i++)
{
n -= 5;
}
if(i > 0)
{
print(n5, i);
}
for(i=0; n>=1; i++)
{
n -= 1;
}
if(i > 0)
{
print(n1, i);
}
}
system("pause");
return 0;
}
void print(int nx, int i)
{
if(i == 0)
{
cout<<nx<<" = 0";
}
else
{
cout<<" + $"<<nx;
if(i > 1)
{
cout<<"*"<<i;
}
}
}