递归调用 - ITeye问答

问答首页 → 综合技术

0 0

递归调用5

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

数据结构

2008年11月19日 21:11

tzheng517
33
0 0 0

2个答案按时间排序按投票排序

0 0

采纳的答案

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

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();

	}

}

2008年11月19日 22:47

soartju
469
0 0 4

添加评论

0 0

for (int i = store[currentBit - 1] + 1; i <= numberToSplit; i++)

循环这里换成 1分，2分，5分，1角，2角，5角就可以了

2008年11月19日 22:50

soartju
469
0 0 4

添加评论

已解决问题

未解决问题

排行榜

查看全部排名>>

递归调用5

2个答案按时间排序按投票排序

采纳的答案

相关推荐

相关推荐

已解决问题

未解决问题

排行榜

递归调用5

2个答案 按时间排序 按投票排序

采纳的答案

相关推荐

相关推荐

已解决问题

未解决问题

排行榜

2个答案按时间排序按投票排序