首页 > 代码库 > 换零钱的方法
换零钱的方法
现有面值分别为 1分， 5分， 10分， 25分， 50分 的五种硬币， 问一枚一块钱的硬币换成这几种硬币有几种换法。
先要明确一个事实， 总的换法一定等于 使用某一种硬币的换法和不使用某一种硬币的换法之和。
前者需要先将总数减去一定使用的那种硬币的面值， 再来讨论剩下的兑换方法。
后者需要先将硬币的种类减一， 再来讨论剩下硬币的兑换方法。
而归约的最终结果无非三种：
硬币总数为 0， 则返回一种方案。
硬币总数小于 0， 则返回 0 种方案。
硬币种类为0， 则返回 0 种方案。
schme 实现：
(define (count-change amount) (cc amount 5))(define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (< kinds-of-coins 1)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))(define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50)))(count-change 100)C++ 实现：
#include <iostream>using namespace std;int FirstDenomination (const int &kinds_of_coins){ switch (kinds_of_coins) { case 1: return 1; case 2: return 5; case 3: return 10; case 4: return 25; default: return 50; }}int CountChange (const int &amount , const int &kinds_of_coins){ if (amount == 0) { return 1; } else if (amount < 0 || kinds_of_coins < 1) { return 0; } else { auto rest_kinds_of_coins = kinds_of_coins - 1; auto rest_amount = amount - FirstDenomination (kinds_of_coins); return ( CountChange(amount , rest_kinds_of_coins) + CountChange(rest_amount , kinds_of_coins)); }}int WaysToChange (const int &amount){ return move(CountChange (amount, 5));}int main (){ cout << move(WaysToChange (100)); cout << endl; return 0;}
换零钱的方法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。