資訊專欄INFORMATION COLUMN
問題：現(xiàn)有現(xiàn)金a，并且有n種面額的零錢，問，共有多少種找零方式。
問題細化：現(xiàn)有現(xiàn)金1元，并且有50分，25分，10分，5分，1分五種面額，用這5種零錢組成1元，共有多少種方式？
如果把n種零錢按照某種順序排列（如50分，25分，10分，5分，1分，不一定升序或降序，也可以亂序），那么問題可以轉(zhuǎn)化為：
現(xiàn)金a用除第一種零錢之外其他面額的找零方式數(shù)目
加上
現(xiàn)金a-d用所有面額的找零方式數(shù)目，其中d為第一種零錢的面額
為什么？什么邏輯？有點暈，看不懂？沒關(guān)系接著往下看。
上面的邏輯等同于
使用第一種零錢的次數(shù)為0次，現(xiàn)金a找零方式數(shù)目
加上
使用第一種零錢的次數(shù)為>=1次，現(xiàn)金a找零方式數(shù)目
如果減去1個第一種零錢，那么等價于"使用第一種零錢的次數(shù)為>=0次，現(xiàn)金a-d找零方式數(shù)目"，亦即"現(xiàn)金a-d用所有面額的找零方式數(shù)目，其中d為第一種零錢的面額"
弄明白上面的邏輯，就看例子吧：以50分，25分，10分，5分，1分為序列，現(xiàn)金額度為1元，則找零方式總數(shù)
等于
1元完全不用50分 + 50分用50，25，10，5，1分//現(xiàn)在第一種零錢為50分
等于
1元完全不用50分 + (50分完全不用50分 + 0分用50，25，10，5，1分)//現(xiàn)在第一種零錢為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分)// 現(xiàn)在硬幣總數(shù)只有4種,第一種是25分 + (50分完全不用25分 + 25分用25，10，5，1分)// 現(xiàn)在硬幣總數(shù)只有4種,第一種是25分
等于
(1元完全不用25分 + (75分完全不用25分 + 50分用25，10，5，1分))// 現(xiàn)在硬幣總數(shù)只有4種,第一種是25分 + (50分完全不用25分 + (25分完全不用25分 + 0分用25，10，5，1分))// 現(xiàn)在硬幣總數(shù)只有4種,第一種是25分
。。。。一直循環(huán)下去
代碼實現(xiàn)（js）
const kindsOfCoins = [1, 5, 10, 25, 50];
/**
* 如果amount正好為0
* 現(xiàn)金amount，用kinds種硬幣的找零方式總數(shù)，
* 等于現(xiàn)金amount，用除了第一種硬幣之外其他硬幣的找零方式總數(shù) + 現(xiàn)金amount - d用所有硬幣的找零方式總數(shù)（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 硬幣種類數(shù)
* @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];得出的結(jié)果是一樣的，也就是說零錢的隨便怎么排序都可以。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/92304.html
摘要：函數(shù)和所生成的過程來源譯者飛龍協(xié)議函數(shù)是計算過程的局部演化模式。在這一章中，我們會檢測一些用于簡單函數(shù)所生成過程的通用模型。也就是說，遞歸函數(shù)的執(zhí)行過程可能需要再次調(diào)用這個函數(shù)。 3.2 函數(shù)和所生成的過程 來源：3.2 Functions and the Processes They Generate 譯者：飛龍 協(xié)議：CC BY-NC-SA 4.0 函數(shù)是計算過程的局部演化...
摘要：實踐指南函數(shù)的藝術(shù)來源譯者飛龍協(xié)議函數(shù)是所有程序的要素，無論規(guī)模大小，并且在編程語言中作為我們表達計算過程的主要媒介。目前為止，我們討論了函數(shù)的形式特性，以及它們?nèi)绾问褂谩５谝恍忻枋龊瘮?shù)的任務(wù)。 1.4 實踐指南：函數(shù)的藝術(shù) 來源：1.4 Practical Guidance: The Art of the Function 譯者：飛龍 協(xié)議：CC BY-NC-SA 4.0 函...
摘要：畢竟，為什么別人做了錯事，需要你來買單呢于是門羅誕生了。為什么呢記住，當(dāng)我們說門羅基于系統(tǒng)時，已經(jīng)使得它與比特幣截然不同。 開始之前，給大家介紹一個資源：Monero——基于環(huán)簽名（Ring Signatures）技術(shù)的虛擬貨幣，內(nèi)容更加干練高效，也更拔高。而下面的內(nèi)容則針對的受眾更廣，可能消化的門檻低些 :)。 原文: What is Monero? The Ultimate Be...
摘要：引言交易是比特幣的核心所在，而區(qū)塊鏈的唯一目的，也正是為了能夠安全可靠地存儲交易。比特幣使用了一個更加復(fù)雜的技術(shù)它將一個塊里面包含的所有交易表示為一個，然后在工作量證明系統(tǒng)中使用樹的根哈希。 翻譯的系列文章我已經(jīng)放到了 GitHub 上：blockchain-tutorial，后續(xù)如有更新都會在 GitHub 上，可能就不在這里同步了。如果想直接運行代碼，也可以 clone GitHu...
摘要：遞歸列表可以使用遞歸函數(shù)最為自然地操作，就像它們的名稱和結(jié)構(gòu)表示的那樣。處理遞歸列表遞歸列表結(jié)構(gòu)將列表表示為首個元素和列表的剩余部分的組合。例如，我們可以使用高階遞歸函數(shù)將樹的每個葉子平方，它的結(jié)構(gòu)類似于。成員測試會遞歸遍歷整個列表。 3.3 遞歸數(shù)據(jù)結(jié)構(gòu) 來源：3.3 Recursive Data Structures 譯者：飛龍 協(xié)議：CC BY-NC-SA 4.0 在第二...
閱讀 2476·2019-08-30 15:52
閱讀 2265·2019-08-30 12:51
閱讀 2866·2019-08-29 18:41
閱讀 2850·2019-08-29 17:04
閱讀 844·2019-08-29 15:11
閱讀 1777·2019-08-28 18:02
閱讀 3632·2019-08-26 10:22
閱讀 2537·2019-08-26 10:12
