要求用java代码!有n元,全部兑成任意数目的1角,2角,5角组合,一共有几种组合,请使用递归法来解答!有java代码
参考: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;
}
}