美国货币找零机

挑战

在美国，货币由美元（$）组成，纸币面额包括$1、$2、$5、$10、$20、$50、$100、$500 和$2000。银行希望找出柜员在向客户支付特定金额时，每种面额应使用多少张钞票，以使处理的钞票总数最少。请编写一个程序，列出用户输入金额对应的每种面额的钞票数量。

注意：此处使用贪心算法可以得到最优解，因为给定的纸币面额系统是规范的（canonical）。

示例 1

请输入要支付的金额：
12345

numofnotes[] = { 0, 0, 1, 0, 2, 0, 3, 0, 6}

面额明细：

2000 × 6 = 12000
100 × 3 = 300
20 × 2 = 40
5 × 1 = 5

示例 2

请输入要支付的金额：
23418

numofnotes[] = { 1, 1, 1, 1, 0, 0, 4, 2, 11}

面额明细：

2000 × 11 = 22000
500 × 2 = 1000
100 × 4 = 400
10 × 1 = 10
5 × 1 = 5
2 × 1 = 2
1 × 1 = 1

编程练习

请尝试独立完成此挑战。如果无法解决，可参考下方提供的解答与说明。

1void numtender ( int amount, int * numofnotes ) 
2{
3	int den[ ] = { 1, 2, 5, 10, 20, 50, 100, 500, 2000 } ;
4	
5	// 你的代码写在这里 ...
6
7	/* 你需要在代码中填充 numofnotes 数组，
8	使得其中每个值对应 den 数组中相应面额的数量 */
9}

编程解答

以下代码提供了上述挑战的解决方案及详细解释。

1#include <iostream>
2#include <iomanip>
3
4void numtender ( int, int[] ) ;
5
6int main() {
7	int arr[9]= {-1, -1, -1, -1, -1, -1, -1, -1, -1};
8	int den[ ] = { 1, 2, 5, 10, 20, 50, 100, 500, 2000 } ;
9	numtender(12345, arr);
10	for (int i = 0; i<9; i++)
11	{
12		std :: cout << den[i] << " -> " << arr[i] << std ::  endl;
13	}
14}
15
16void numtender ( int amount, int * numofnotes ) 
17{
18	int den[ ] = { 1, 2, 5, 10, 20, 50, 100, 500, 2000 } ;
19	
20	/* 检查无效金额 */
21	if ( amount <= 0 ) {
22		for (int i = 0 ; i <= 8 ; i++)
23		{
24			numofnotes[i]=0;
25		}
26		return ;
27	}
28
29	/* 从最大面额开始，逐个计算每种面额所需数量，并填入 numofnotes 数组 */
30	for ( int i = 8 ; i >= 0 ; i-- ) 
31	{
32		if ( amount >= den[i] ) 
33		{
34			numofnotes[i] = amount / den[i] ;			
35			amount = amount % den[i] ;
36			if ( amount == 0 ) 
37				break ;
38		}
39	}
40
41	/* 若某些面额未使用，则将对应计数从 -1 改为 0 */
42	for (int i = 0 ; i <= 8 ; i++)
43	{
44		if(numofnotes[i]==-1){
45			numofnotes[i]=0;
46		}
47	}
48}

解释

程序在 numtender( ) 函数中定义了一个包含所有面额的数组 den[ ]。然后通过一个循环，从最大面额（即 2000）开始，依次计算每种面额所需的张数。

注意：按从大到小的顺序处理至关重要，这样才能确保最终使用的钞票总数最少。

示例：

金额 = 12345
den[ ] = { 1, 2, 5, 10, 20, 50, 100, 500, 2000 }
numofnotes[ ] = { 0, 0, 1, 0, 2, 0, 3, 0, 6 }

说明：

观察 numofnotes[ ] 数组可知，支付 12345 元最少需要：6 张 2000 元、3 张 100 元、2 张 20 元、1 张 5 元，其余面额均无需使用。