递归解决换零钱问题--代码实现

摘要: 递归解决换零钱问题的具体代码实现, 提供了两种实现, 一种面向对象式, 一种面向过程式, 使用 Java 语言.

在上一篇中, 经过深入分析, 已经得出一个能够递归的形式化的结果, 现在则准备给出一个具体实现.

结果回顾

前述结果如下:

caseOfChange(amount, cashList) { 
	// base case
	if (amount.isNegative()) { // 负数 
	    return 0; 
	} 
	if (amount.isZero()) { // 0元 
	    return 1; 
	}
	if (cashList.containsOnlyOneCash()) { // 只有一种零钱时 
        if (amount.canBeChangedWith(cashList.getTheOnlyOneCash())) { // 能换时, 即能整除 
            return 1;
        } else { 
            return 0; 
        } 
    }
	
	// recursive case
	return caseOfChange(amount.subtractBy(cashList.getFirstCash()), cashList)
    	+ caseOfChange(amount, cashList.newCashListWithoutFirstCash());
}

其实已经大体 OK 了, 基本就差确定一下类型就差不多了.

继续阅读

递归解决换零钱问题(1)--问题分析

摘要: 用递归方式解决求换零钱种数的问题.

以下是我们的问题:

把 100 元用 50 元, 20 元, 10 元, 5 元, 1 元去换, 总共有几种换法?

形式化(formalize)

为了简化叙述, 把问题记为 coc(100, [50, 20, 10, 5, 1]).

coc: case of change 或者 count of change(change 在英文中有零钱的意思)

为使问题更具有一般性, 参数化具体值, 得到:

caseOfChange(amount, cashList)

其中 amount 为金额, cashList 为零钱列表.

继续阅读