贪心算法解决找零钱问题

 

 

 

#include <iostream> #include <iterator> using namespace std; int arr[] = {100, 20, 10, 5, 1}; //零钱的种类 int N = sizeof(arr)/ sizeof(int);//零钱的个数 void Input(int &price, int &money); void Comput(int price, int money, int result[]); void Output(int arr[], int n); int main() { int price = 0; int money = 0; Input(price, money); int N = money - price; int *result = new int[N]; memset(result, 0, N*sizeof(int)); Comput(price, money, result); Output(result, N); delete []result; return 0; } /************************************************************************/ /* 函数功能：输入模块 参数：price表示所有商品的价格，money为顾客付的钱 */ /************************************************************************/ void Input(int &price, int &money) { cout<<"Please input the price of all good: "; cin>>price; cout<<"Please input the money: "; cin>>money; } /************************************************************************/ /* 函数功能：找零钱算法核心(利用贪心算法的思想) 参数：result存放结果 */ /************************************************************************/ void Comput(int price, int money, int result[]) { int i = 0; int changes = money - price; while (changes !=0 ) { if (changes >= 100) { result[i++] = 100; changes -= 100; } else if (changes >= 20) { result[i++] = 20; changes -= 20; } else if (changes >= 10) { result[i++] = 10; changes -= 10; } else if (changes >= 5) { result[i++] = 5; changes -= 5; } else { result[i++] = 1; changes -= 1; } } } /************************************************************************/ /* 函数功能：输出模块 参数：arr存放输出结果 */ /************************************************************************/ void Output(int arr[], int n) { int num = 1; int j = 0; for (int i=1; i<n; ++i) { if (arr[i] == arr[j]) { num++; } else { cout<<arr[j]<<"元 "<<num<<" 个"<<endl; num = 1; j = i; } } }