现金找零方式的总数（sicp）

pf_miles 发布于2019-08-22 11:23 / 3120人阅读

问题：现有现金a，并且有n种面额的零钱，问，共有多少种找零方式。
问题细化：现有现金1元，并且有50分，25分，10分，5分，1分五种面额，用这5种零钱组成1元，共有多少种方式？

如果把n种零钱按照某种顺序排列（如50分，25分，10分，5分，1分，不一定升序或降序，也可以乱序），那么问题可以转化为：
现金a用除第一种零钱之外其他面额的找零方式数目
加上
现金a-d用所有面额的找零方式数目，其中d为第一种零钱的面额

为什么？什么逻辑？有点晕，看不懂？没关系接着往下看。

上面的逻辑等同于
使用第一种零钱的次数为0次，现金a找零方式数目
加上
使用第一种零钱的次数为>=1次，现金a找零方式数目
如果减去1个第一种零钱，那么等价于"使用第一种零钱的次数为>=0次，现金a-d找零方式数目"，亦即"现金a-d用所有面额的找零方式数目，其中d为第一种零钱的面额"

弄明白上面的逻辑，就看例子吧：以50分，25分，10分，5分，1分为序列，现金额度为1元，则找零方式总数
等于

1元完全不用50分 + 50分用50，25，10，5，1分//现在第一种零钱为50分

等于

1元完全不用50分 + (50分完全不用50分 + 0分用50，25，10，5，1分)//现在第一种零钱为50分

等于

1元用25，10，5，1分 + 50分用25，10，5，1分
//"完全不用50分"等价于"用25，10，5，1分"，“0分用50，25，10，5，1分”是0

等于

(1元完全不用25分 + 75分用25，10，5，1分)// 现在硬币总数只有4种,第一种是25分
+
(50分完全不用25分 + 25分用25，10，5，1分)// 现在硬币总数只有4种,第一种是25分

等于

(1元完全不用25分 + (75分完全不用25分 + 50分用25，10，5，1分))// 现在硬币总数只有4种,第一种是25分
+
(50分完全不用25分 + (25分完全不用25分 + 0分用25，10，5，1分))// 现在硬币总数只有4种,第一种是25分

。。。。一直循环下去

代码实现（js）

const kindsOfCoins = [1, 5, 10, 25, 50];

/**
 * 如果amount正好为0
 * 现金amount，用kinds种硬币的找零方式总数，
 * 等于现金amount，用除了第一种硬币之外其他硬币的找零方式总数 + 现金amount - d用所有硬币的找零方式总数（d为第一种硬币的面值）
 * amount为0，说明前一步amount-firstCoins正好为0，比如25-25，是1种找零方式，return 1
 * amount<0，说明前一步amount-firstCoins类似于10-25，不是找零方式，return 0
 * kinds===0，说明没有找零的硬币了，return 0
 * 
 * @param amount 总金额
 * @param kinds  硬币种类数
 * @returns {*}
 */
function countChange(amount, kinds) {
    const restKindsOfCoins = kindsOfCoins.slice(0, kinds);
    const firstCoins = restKindsOfCoins[kinds - 1];
    if (amount === 0) return 1;
    if (amount < 0) return 0;
    if (kinds === 0) return 0;
    return countChange(amount, kinds - 1) + countChange(amount - firstCoins, kinds);
}

console.log(countChange(100, 5));// 292

注意，如果const kindsOfCoins = [1, 5, 10, 25, 50];改为const kindsOfCoins = [50, 10, 5, 1, 25];得出的结果是一样的，也就是说零钱的随便怎么排序都可以。

服务器托管海外云主机阿里云的现金能取么 SICP 找零钱贪心算法java找零

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/92304.html

SICP Python 描述 3.2 函数和所生成的过程

摘要：函数和所生成的过程来源译者飞龙协议函数是计算过程的局部演化模式。在这一章中，我们会检测一些用于简单函数所生成过程的通用模型。也就是说，递归函数的执行过程可能需要再次调用这个函数。 3.2 函数和所生成的过程来源：3.2 Functions and the Processes They Generate 译者：飞龙协议：CC BY-NC-SA 4.0 函数是计算过程的局部演化...

lolomaco 2019-07-25 10:47 评论0 收藏0
SICP Python 描述 1.4 实践指南：函数的艺术

摘要：实践指南函数的艺术来源译者飞龙协议函数是所有程序的要素，无论规模大小，并且在编程语言中作为我们表达计算过程的主要媒介。目前为止，我们讨论了函数的形式特性，以及它们如何使用。第一行描述函数的任务。 1.4 实践指南：函数的艺术来源：1.4 Practical Guidance: The Art of the Function 译者：飞龙协议：CC BY-NC-SA 4.0 函...

lemon 2019-07-31 12:21 评论0 收藏0
什么是门罗币？终极入门指南

摘要：毕竟，为什么别人做了错事，需要你来买单呢于是门罗诞生了。为什么呢记住，当我们说门罗基于系统时，已经使得它与比特币截然不同。开始之前，给大家介绍一个资源：Monero——基于环签名（Ring Signatures）技术的虚拟货币，内容更加干练高效，也更拔高。而下面的内容则针对的受众更广，可能消化的门槛低些 :)。原文: What is Monero? The Ultimate Be...

tulayang 2019-06-27 18:16 评论0 收藏0
用 Go 构建一个区块链 -- Part 4: 交易（1）

摘要：引言交易是比特币的核心所在，而区块链的唯一目的，也正是为了能够安全可靠地存储交易。比特币使用了一个更加复杂的技术它将一个块里面包含的所有交易表示为一个，然后在工作量证明系统中使用树的根哈希。翻译的系列文章我已经放到了 GitHub 上：blockchain-tutorial，后续如有更新都会在 GitHub 上，可能就不在这里同步了。如果想直接运行代码，也可以 clone GitHu...

graf 2019-06-27 18:12 评论0 收藏0
SICP Python 描述 3.3 递归数据结构

摘要：递归列表可以使用递归函数最为自然地操作，就像它们的名称和结构表示的那样。处理递归列表递归列表结构将列表表示为首个元素和列表的剩余部分的组合。例如，我们可以使用高阶递归函数将树的每个叶子平方，它的结构类似于。成员测试会递归遍历整个列表。 3.3 递归数据结构来源：3.3 Recursive Data Structures 译者：飞龙协议：CC BY-NC-SA 4.0 在第二...

libin19890520 2019-07-25 10:47 评论0 收藏0