分硬币问题（用递归方法）

Question

 开发一个递归方法，确定将一定数量的钱（以分为单位）转换成两角五分的硬币，一角硬币，五分和一分硬币的方法总数。例如，假设总钱数为17分，那么共有6种方法。
1角，7分
1角，1五分，2一分
3五分，2一分
2五分，7一分
1五分，12一分
17一分最好给出源代码，或者给些提示也好，谢谢。

Answer 1

呵呵，请参考哦！
package test;import java.util.Stack;class Money {  int fen;
  int number;
}public class Temp {
  static Stack<Money> stack = new Stack<Money>();
  static int[] nums = new int[] { 10, 5, 2, 1 };  public static void fen(int target, int sum, int index) {
    for (int i = index; i < nums.length; i++) {
      int num = nums[i];
      Money m = new Money();
      m.fen = num;
      stack.push(m);
      while (sum + num <= target) {
        m.number++;
        if (sum + num == target) {
          showResult();
        }
        sum += num;
      }
      fen(target, sum, i + 1);
      stack.pop();
      sum -= m.fen * m.number;
    }
  }  private static void showResult() {
    for (Money m : stack) {
      if (m.number > 0) {
        System.out.print(m.fen + ":" + m.number + " ");
      }
    }
    System.out.println();
  }  public static void main(String[] input) throws Exception {
    fen(17, 0, 0);
  }
}我的答案比你猜测的多
10:1 5:1 2:1 
10:1 5:1 1:2 
10:1 2:3 1:1 
10:1 1:7 
5:3 2:1 
5:3 1:2 
2:8 1:1 
1:17 

Answer 2

紫竹，人家要求是25 10 5 1几种硬币
static int[] nums = new int[] { 25, 10, 5, 1 };
后
结果为：
10:1 5:1 1:2 
10:1 1:7 
5:3 1:2 
1:17 
10:1 5:1 1:2 
10:1 1:7 
5:3 1:2 
1:17 
是重复的
不知道为什么啊
您再看看？

Answer 3

更新一下算法，主要是没考虑，硬币分类的最大面值可能超过找零的总和
package test;import java.util.Stack;class Money {  int fen;
  int number;
}public class Fen {
  static Stack<Money> stack = new Stack<Money>();
  static int[] nums = new int[] { 25, 10, 5, 1 };  public static void fen(int target, int sum, int index) {
    Money m = null;
    for (int i = index; i < nums.length; i++) {
      int num = nums[i];
      if (num > target) { // 这里判断一下就可以了
        continue; 
      }
      m = new Money();
      m.fen = num;
      stack.push(m);
      while (sum + num <= target) {
        m.number++;
        if (sum + num == target) {
          showResult();
        }
        sum += num;
      }
      fen(target, sum, i + 1);
      stack.pop();
      sum -= m.fen * m.number;
    }
  }  private static void showResult() {
    for (Money m : stack) {
      if (m.number > 0) {
        System.out.print(m.fen + ":" + m.number + " ");
      }
    }
    System.out.println();
  }  public static void main(String[] input) throws Exception {
    fen(17, 0, 0);
  }
}

Answer 4

哎
那本中文的Standard ML书上有个简约算法
行就是Java的1/10
还保证正确
还保证通用

Answer 5

package StudyForDigui;
/*这是个输入多少美分，然后递归统计出换成一角五分 一分硬币的种数
 * */
import java.util.Scanner;public class ChangeMoney {
public static void main(String [] args){
Scanner input = new Scanner(System.in) ;
long yourmoney ;
long Zhongshu = 0 ;
System.out.println("输入你有多少money：");
yourmoney = input.nextLong() ;
Zhongshu = chang(yourmoney) ;

System.out.println(Zhongshu);
}
public static long chang(long money){
long part1 = 0 ;
long part2 = 0 ;
if (money < 25) {
return GetPart2(money);
}else {
part2 = GetPart2(money);
return chang(money - 25)+part2 ;
}
}
public static long GetPart2(long money)
{
long count = 0;
for (int i = (int)money/10; i >=0; i--) {
for (int j = (int )money /5 ; j >=0; j--) {
for (int j2 = (int)money; j2 >=0; j2--) {
if (10 * i+5*j+j2==money) {
count++ ;
}
}
}
}

return count ; 

}
}