一个叫赵三的青年把自己的名字改成了赵C, 一个叫牛二的青年看见了, 心里痒痒的...

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

摘要: 递归解决换零钱问题的具体代码实现, 提供了两种实现, 一种面向对象式, 一种面向过程式, 使用 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 为零钱列表.

继续阅读

用递归解决冒泡排序问题

摘要: 用递归的方式来实现的冒泡排序程序.

冒泡排序是种很简单的排序方式. 如果用循环方式, 通常就是两层循环.

由于两层循环都是与元素个数 N 线性相关, 所以可以简单估算出它的时间复杂度是 O(N2), 通常而言, 这是较糟糕的复杂度.

当然, 这也几乎是所有简单方式的宿命, 想简单就别想效率高!

前面篇章说到递归也是一种循环, 所以普通循环能解决的问题, 用递归也能解决. 我们来看看怎么写出它来.

继续阅读

猛然发现今天已经是耶稣哥的生日了. Jesus! How time flies!