贪婪算法的(最少个数)找零钱算法

/*
* 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;
        }
    }
}

本文地址：http://com.8s8s.com/it/it24679.htm