/*
 * DivideMoney.java Created on 2008-3-5
 * Copyright( c) 2006-2010 by BroadText
 * ALL Rights Reserved.
 */
package interest.divide;

/**
 * 开发一个递归方法，确定将一定数量的钱（以美分为单位）转换成两角五分的硬币，一角硬币，五分和一分硬币的方法总数。
 * 例如，假设总钱数为17分，那么共有6种方法。
 * 1角，7一分 
 * 1角，1五分，2一分 
 * 3五分，2一分 
 * 2五分，7一分 
 * 1五分，12一分 
 * 17一分
 * 
 * 为方便起见，可以理解为用25，10，5，1分解一个数，求一共有多少种分解方法
 * 
 * @author Sun Tao(suntao19830709@gmail.com)
 */
public class DivideMoney {
  
  private int[] divider = new int[]{1, 5, 10, 25};
  
  private static int k = 17;
  
  public static void main(String[] args) {
    DivideMoney divideMoney = new DivideMoney();
    System.out.println(divideMoney.divider( k));
  }
  
  public int divider(int num){
    return divider(num, divider[divider.length-1]);
  }
  
  /**
   * 
   * 
   * @author Sun Tao
   * @param num 分配的钱的总数，例如此例的17
   * @param dividerNum 分配的最大的钱币的数量，例如此例为25
   * @return
   */
  public int divider(int num, int dividerNum){
    int result = 0;
    //如果只用1分钱来分的话，那么分配的方法只有一种
    if(dividerNum == divider[0]){
      return 1;
    }
    //如果比较多个钱币的分配的时候，先用最大的钱币来分，例如，先用25来分，例如17，分25为0个，余数为17。
    //然后把余数 17，用10来分，根据num/dividerNum得到为两种情况，一种是0个10，一种是1个10，再把余数17，和7 分别用5来分，以此类推
    //最后分的结果全部加起来就是完整的分发的个数
    for(int i = divider.length - 1; i >= 1; i--){
      if(dividerNum == divider[i]){
        for(int j = 0; j <= num / dividerNum ; j++){
          result += divider((num - dividerNum*j), divider[i-1]);
        }
      }
    }
    return result;
  }
}

for(int i = divider.length - 1; i >= 1; i--){
      if(dividerNum == divider[i]){
        for(int j = 0; j <= num / dividerNum ; j++){
          result += divider((num - dividerNum*j), divider[i-1]);
        }
      }
    }

istimeto wrote:
楼上功底很深，呵呵！
不过我觉得，这个二重循环，完全可以避免的。只需要把参数 public int divider(int num, int dividerNum)中的dividerNum，改为当前可用的最大额的硬币所对应数组divider[] = new int[]{1, 5, 10, 25}的下标，当然前提是该数组要有序的，这样我看起来直观。