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

摘要:递归解决换零钱问题的具体代码实现,提供了两种实现,一种面向对象式,一种面向过程式,使用 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 了,基本就差确定一下类型就差不多了。

代码实现

下面将给出一个 Java 的实现。Java 是一种面向对象的语言,有强大的类型抽象机制,我们可以将上述形式化结果翻译成面向对象的实现。

我不清楚大家平时喜欢面向什么编程,我反正是面向显示器编程,偶尔面向键盘一下。

面向对象的实现

上述结果基本上只是差了类型(type or class)没有确定。

抽象数据类型(ADT:Abstract Data Type)

对一个类型(类)来说,是对行为(behavior)属性(property)的一种抽象与封装。

行为刻画了一个类的功能,是对外的主体部分;(在 Java 中,即对应成员方法(member method)

属性则关系到内部的具体实现,通常应该对外隐藏。(在 Java 中,即对应成员变量(member field)

引入自定义类型

直接将 amount 视作 Amount 类型,cashList 则为 CashList 类型。再仔细推敲一下,cashList 中的 cash 其实也就是 amount,或者说 amount 其实也就是 cash。

这会更好地与现实接轨。

因此,可引入两种自定义类型 Cash 和 CashList:

public class Cash {
    private int value;
    
    public Cash(int value) {
        this.value = value;
    }
}

public class CashList {
    private List<Cash> list = new ArrayList<Cash>();
    
    public CashList(Cash ... cashes) {
    	// TODO ...
    }
}

其实也就是分别对 Integer 以及 Array(或者说 ArrayList)的轻量封装,这样我们就能加入自定义的行为。

确定类型的行为(方法)

现在考虑行为,基本上,前述描述中已经基本刻画了两种类型的行为。

比如,isNegative,isZero 是 Cash 类中的方法,containsOnlyOneCash 等则是 CashList 中的方法。

将前述伪代码拷贝到类定义中,稍加修改就可以让 IDE 为我们自动生成那些方法定义了。

严格地说,对 Cash 类而言,其实只要对外提供一个方法即可,这是外界唯一关心的方法:

public int getCountOfChanges(CashList list)

至于 isZero 之类的,只是一些内部辅助实现,定为 private 即可。

public class Cash {
	// ...
	
	// 对外接口
	public int getCountOfChanges(CashList list) { /*...*/ }

	// 内部递归实现
	private int caseOfChanges(Cash cash, CashList list) { /*...*/ }

	private boolean isNegative() { /*...*/ }

	private boolean isZero() { /*...*/ }

	private boolean canBeChangedWith(Cash cash) { /*...*/ }

    private Cash subtractBy(Cash cash) { /*...*/ }
}

public class CashList {
	// ...
	
    public boolean containsOnlyOneCash() { /*...*/ }
    
    public Cash getTheOnlyOneCash() { /*...*/ }
    
    public CashList newCashListWithoutFirstCash() { /*...*/ }

    public Cash getFirstCash() { /*...*/ }
}

引入枚举 enum 类型

再考虑到 cash 的种类是有限的,直接就用 enum 枚举代替了,只提供有限几个实例(instance)

public enum Cash {
    CASH_100(100), CASH_50(50), CASH_20(20), CASH_10(10), CASH_5(5), CASH_1(1);

	private int value;
	
	private Cash(int value) {
		this.value = value;
	}
	
	// ...
}

这样客户端代码就无法 new 出形形色色的 Cash,只能用这里定义好的,我们也免去了检查输入合法性的麻烦。

image

泛化的零钱 GenericCash

Cash 变为 enum 后,由于递归演算涉及到了一些中间结果:

比如求 coc(100, [20, 5, 1]) 时经约减会出现 coc(80, [20, 5, 1]) 之类的,显然 80 不是 enum 中的一员。

为此,引入一个新的类型 GenericCash,

Java 中的范型称为 Generic type,这里用 generic 表示一般化的零钱,也即递归运算过程中才会出现的那些。

也正好把 isZero 等方法也打包到它的内部去:

class GenericCash {

    // ...
	
	public int getCountOfChanges() {}
    
	private int caseOfChanges(GenericCash genericCash, CashList list) {}

	private boolean canBeChangedWith(Cash cash) {}

    private boolean isNegative() {}
    
    private GenericCash subtractBy(Cash cash) {}

    private boolean isZero() {}
}

这样,Cash 类就显得很简洁了。

局部内部类(local inner class)

考虑到只是在方法内部才会用到 GenericCash,外部根本不需要知道这个类的存在,直接把它扔在方法内部定义,

public enum Cash {
	// ...
	
	// 对外接口
	public int getCountOfChanges(final CashList list) {
		// 方法内部类
		class GenericCash {
			// ...
		}
		
		return new GenericCash().getCountOfChanges();
	}
}

这样,即便是 Cash 类中的其它地方也不知道这个类的存在。(也无需知道)

最终结果

一个完整的结果如下:

Cash 类:

public enum Cash {
    CASH_100(100), CASH_50(50), CASH_20(20), CASH_10(10), CASH_5(5), CASH_1(1);

    private int value;
    
    private Cash(int value) {
        this.value = value;
    }
    
    // ================ 第二种方式,更加对象化,把第一种方式中的int类型的genericCash包装成类
    public int getCountOfChanges(final CashList list) {
        /**
         * 一般化的现金值,在运算中,我们会逐步分割要换的零钱,这会导致出现一些中间值
         * 举个例子,把100换成[20, 10, 5],在运算中将出现把100分成80+20的情况,然后将计算把“80”换成[20,10,5]的情况
         * 这里的80就是一般化的现金值,在实际中不会存在,但在我们的运算中会有意义。
         * 
         * 这是一个方法内部类,仅仅只用于也只能用于这个方法中。
         *
         */
        class GenericCash {
            private int value;
            
            private GenericCash() {
                // 由于是内部类,可以直接引用所在类的私有成员变量
                value = Cash.this.value;
            }
            
            // 供递归调用时使用的构造函数
            private GenericCash(int value) {
                this.value = value;
            }
            
            private boolean canBeChangedWith(Cash cash) {
                // 由于是内部类,可以直接引用cash的私有成员变量
                return value % cash.value == 0;
            }

            private boolean isNegative() {
                return value < 0;
            }
            
            private GenericCash subtractBy(Cash cash) {
                return new GenericCash(value - cash.value);
            }

            private boolean isZero() {
                return value == 0;
            }
            
            private int getCountOfChanges() {
                // 由于是内部类,这里直接引用外围方法的list变量,这也是它为何要设置成final的原因
                return caseOfChanges(this, list);
            }
            
            private int caseOfChanges(GenericCash genericCash, CashList list) {
                if (genericCash.isNegative()) {
                    return 0;
                }
                if (genericCash.isZero()) {
                    return 1;
                }
                if (list.containsOnlyOneCash()) {
                    return genericCash.canBeChangedWith(list.getTheOnlyOneCash()) ? 1 : 0;
                }
                return caseOfChanges(genericCash.subtractBy(list.getFirstCash()), list)
                        + caseOfChanges(genericCash, list.newCashListWithoutFirstCash());
            }
        }
        
        // 由于内部类的关系,在这里完全不用向里面传递任何参数
        return new GenericCash().getCountOfChanges();
    }
}

CashList 类

public class CashList {

    private List<Cash> list = new ArrayList<Cash>();
    
    public CashList(Cash ... cashes) {
        if (cashes == null || cashes.length == 0) {
            throw new IllegalArgumentException("请传入至少一个参数!");
        }
        List<Cash> cashList = Arrays.asList(cashes);
        for (Cash cash : cashList) {
            if (!list.contains(cash)) {
                list.add(cash);
            } else {
                throw new  IllegalArgumentException("重复的参数!" + cash);
            }
        }
    }
    
    public boolean containsOnlyOneCash() {
        return list.size() == 1;
    }
    
    public Cash getTheOnlyOneCash() {
        return list.get(0);
    }
    
    /**
     * 获取不带第一个元素的新list
     * 如果当前是[20, 10, 5, 1],那么将得到[10, 5, 1]
     * @return
     */
    public CashList newCashListWithoutFirstCash() {
        List<Cash> dest = new ArrayList<Cash>(list);
        dest.remove(0);
        
        // new Cash[0] 只是为能推导出泛型类型,本身并无其它意义
        //也可以使用强制类型转换: new CashSet((Cash[]) dest.toArray());
        return new CashList(dest.toArray(new Cash[0]));
    }

    public Cash getFirstCash() {
        return list.get(0);
    }    
}

面向过程的实现

当然,如果觉得对于这个不大的问题,面向对象方式显得笨重低效,可以简单给出一个较为过程式的实现,比如直接使用 int 和 array,也不需要对象了,直接就是 static  的方法。

public static int caseOfChanges(int cash, int[] cashes) {
        if (cash < 0) {
            return 0;
        }
        if (cash == 0) {
            return 1;
        }
        if (cashes.length == 1) {
            return cash % cashes[0] == 0 ? 1 : 0;
        }
        // 递归调用
        return caseOfChanges(cash - cashes[0], cashes)
                + caseOfChanges(cash, Arrays.copyOfRange(cashes, 1, cashes.length));
    }

比起对象式的实现,这个显得简洁多了。(当然,考虑到健壮性,还需要多做些检查才行。)

另:这里还是进行了数组的复制,如果能再引入一个 index 参数,则可以避免复制数组。

测试

以下是一些测试,把 100 元换成 50,20,10,5,1 元总共有 343 种不同结果:

// ========== 对象式实现的测试
@Test
public void testGetCountOfChanges() {
    CashList list = new CashList(CASH_1, CASH_5);
    assertThat(CASH_10.getCountOfChanges(list)).isEqualTo(3);
}

@Test
public void testManyCountNoOrder() {
    // 顺序并不重要
    CashList list = new CashList(CASH_10, CASH_5, CASH_20, CASH_1, CASH_50);
    assertThat(CASH_100.getCountOfChanges(list)).isEqualTo(343);
}

// ========== 过程式,静态式实现的测试
@Test
public void testZeroCountStaticWay() {
    assertThat(Cash.caseOfChanges(50, new int[] {20})).isEqualTo(0);
}

@Test
public void testOneCountStaticWay() {
    assertThat(Cash.caseOfChanges(100, new int[] {20})).isEqualTo(1);
}

@Test
public void testManyCountStaticWay() {
    assertThat(Cash.caseOfChanges(100, new int[] {50, 20, 10, 5, 1})).isEqualTo(343);
}

注:零钱的顺序其实并不会影响最终结果。

结论?

再次,由于篇幅过长,推迟到下一篇中再去对比这两种实现的优劣,以及对前述的问题分析作些回顾总结。

发表评论

电子邮件地址不会被公开。