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

apache2007 2008-02-11 07:38:42

开发一个递归方法，确定将一定数量的钱（以分为单位）转换成两角五分的硬币，一角硬币，五分和一分硬币的方法总数。例如，假设总钱数为17分，那么共有6种方法。
1角，7分
1角，1五分，2一分
3五分，2一分
2五分，7一分
1五分，12一分
17一分

最好给出源代码，或者给些提示也好，谢谢。

...全文

350 8 打赏收藏转发到动态举报

写回复

用AI写文章

8 条回复

切换为时间正序

请发表友善的回复…

发表回复

咖啡小子 2012-08-01

打赏
举报

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 ;

}
}

mxx123 2008-02-15

打赏
举报

学习

yaos 2008-02-14

打赏
举报

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

老紫竹 2008-02-13

打赏
举报

更新一下算法，主要是没考虑，硬币分类的最大面值可能超过找零的总和

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

  }

}

zhangyu_fox 2008-02-12

打赏
举报

紫竹，人家要求是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
是重复的
不知道为什么啊
您再看看？

apache2007 2008-02-11

打赏
举报

.....分硬币是个形式，你就当有2角五分吧...

DirectRay 2008-02-11

打赏
举报

竹子，有两毛五的硬币啊？

老紫竹 2008-02-11

打赏
举报

呵呵，请参考哦！

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

  }

}