问题

趣味数学
Questions in category: 趣味数学 (Recreational Mathematics).

找零钱问题

Posted by haifeng on 2018-06-07 08:55:17 last update 2018-06-07 08:59:48 | Answers (0) | 收藏


假设使用某国的货币(指纸币和硬币), 要得到 $x$ 元, 要求是使用最少的钞票和硬币. 将这种取法称为最优方案.

 

比如美国货币, 我们要找出 17 美元 61 美分.

方案:

  • 一张 10 元美钞;
  • 一张 5 元美钞;
  • 两张 1 元美钞;
  • 两个 25 分币;
  • 一个 10 分币;
  • 一个 1 分币.

 

对于美国货币系统, 可以证明对任意 $x$, 可以找到最优方案.

 


References:

Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, (Third Edition).

张怀勇 等译, 《数据结构与算法分析 C++ 描述》(第三版) [Chapter 10. Page. 296]