2 lafengwnagzi lafengwnagzi 于 2014.11.25 21:34 提问

有n元,全部兑成任意数目的1角,2角,5角组合,一共有几种组合,请使用递归法来解答

要求用java代码!有n元,全部兑成任意数目的1角,2角,5角组合,一共有几种组合,请使用递归法来解答!有java代码

1个回答

devmiao
devmiao   Ds   Rxr 2014.11.25 22:13

参考:http://www.iteye.com/problems/18290

public class Counter extends TestCase {
public void testCounter() {
Counter counter = new Counter();

    assertEquals(1, counter.count(1, 100) + 1);
    assertEquals(51, counter.count(2, 100) + 1);
    assertEquals(10, counter.count(5, 10) + 1);

    System.out.println(counter.count(5, 100) + 1);
    System.out.println(counter.count(10, 100) + 1);
    System.out.println(counter.count(20, 100) + 1);
    System.out.println(counter.count(50, 100) + 1);
}

private int count(int step, int total) {
    if (step <= 1) {
        return 0;

    } else {
        int currentNumber = total / step; // 当前可取值的个数

        int count = currentNumber;

        for (int i = 0; i < currentNumber; i++) {
            int sub = this.count(this.getNextStep(step), total - (i * step));
            count += sub;
        }

        return count;
    }
}

private int[] steps = { 50, 20, 10, 5, 2, 1 };

private int getNextStep(int current) {
    for (int i = 0; i < steps.length; i++) {
        if (current == steps[i]) {
            return steps[i + 1];
        }
    }
    return 0;
}

}

lafengwnagzi
lafengwnagzi 谢谢,大神
大约 3 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!