現金找零方式的總數（sicp）

pf_miles 發布于2019-08-22 11:23 / 3220人閱讀

問題：現有現金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];得出的結果是一樣的，也就是說零錢的隨便怎么排序都可以。

云服務器 GPU云服務器阿里云的現金能取么 SICP 找零錢貪心算法java找零

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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