递归调用

Question

有六种不同面值的硬币 1分，2分，5分，1角，2角，5角，用找这六个不同面值的硬币组合成一元的，写一个方法得到组合的方案次数

Answer 1

这其实就是自然数拆分的算法，其实是一样的，只不过把数字换成了硬币面值并且面额固定。
下面的算法是自然数拆分的，你参考下吧。

[code="java"]
public class ChaiFenShu {

/**
 * 存储拆分好的数字
 */
int store[] = new int[1000];
int Count = 0;

/**
 * 
 * @param numberToSplit
 *            需要拆分的数
 * @param currentBit
 *            拆分的进度
 */
public void SplitNumber(int numberToSplit, int currentBit) {
    int restNumberToSplit;

    for (int i = store[currentBit - 1] + 1; i <= numberToSplit; i++) { // 从比上一个拆分的数大1开始继续拆分
        store[currentBit] = i;  // 将这个数计入结果中
        restNumberToSplit = numberToSplit - i;  // 剩下的数是n-i

        if (restNumberToSplit == 0 && currentBit > 1) { // 如果已经没有剩下的了，并且进度(总的拆分个数)大于1，说明已经得到一个结果。
            increaseCount();
            printCurrentSplit(currentBit);
        } else {
            SplitNumber(restNumberToSplit, currentBit + 1); //否则将剩下的数进行进度为m+1拆分。
        }

        store[currentBit] = 0; // 取消本次结果，进行下一次拆分。
    }

    //否则不进行拆分了
}

/**
 * 增加计数
 * @param currentBit
 */
private void increaseCount() {
    Count++;
    System.out.println();
}

private void printCurrentSplit(int currentBit){
    for (int j = 1; j <= currentBit; j++) {
        System.out.print(" " + store[j]);
    }
}

public void print() {
    System.out.println();
    for (int i = 1; i < store.length && store[i] != 0; i++) {
        System.out.print(" " + store[i]);
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    ChaiFenShu chaiFenShu = new ChaiFenShu();
    chaiFenShu.SplitNumber(15, 1);
    chaiFenShu.print();

}

}
[/code]