JAVA 递归找零钱

看了楼上的写法后，不甚满意，于是自己写了一种。

这个题目很有意思，相当有意思。

加上了比较详细的注释。

你试一试。

这种方法你能很明显的看出递归的特征。

可以随意传要找钱的总数，以及硬币面额可以增加或者减少。但是

硬币的面额要由小到大排列，就ok

注释加的有点多。。看起来有点累赘。不过能容易看。

package file

import java.util.ArrayList

import java.util.List

/**

* 递归得到找钱方案个数

* 思路为：

* 定义待找钱币类型。默认从小到大排列。

* 传入参数后，先获得最大的硬币面值。通过整除，得到可以有几种找钱情况

* 递归调用找钱，因为排除了最大面额硬币后的可找硬币以余额都发生了变化。可以看作一次新的找钱

* 最终得到所有的找钱方案。封装到List中返回。

* @version TestRePay.java v. 1.0.0 2010-10-26

* @author Andy

*/

public class TestRePay {

public static void main(String[]args){

int i = 150

int[] coinType = new int[]{1,5,10,25,50}

//调用递归方法

List<String>allResult = reCoins(coinType, i)

System.out.println("找钱方案的个数为："+allResult.size())

for(int j = 1 ,k = allResult.size()j<=kj++ ){

System.out.println("第"+j+"种找钱方案为："+allResult.get(j-1))

}

}

/**

* 通过递归，得到所有的方案数量

* author Andy

* date 2010-10-26 下午01:30:06

* @param coinType 可以找给客户的钱币的类型 为int数组

* @param totalMoney 待找钱的数量

* @return

*/

public static List<String>reCoins(int[]coinType , int totalMoney){

//获得最后一个，也就是默认为最大的一个钱币类型

int lastCoin = coinType[coinType.length-1]

//通过数组复制获得下一级调用时候的硬币类型

int[] newCoinType = new int[coinType.length-1]

System.arraycopy(coinType, 0, newCoinType, 0, newCoinType.length)

//获得针对当前硬币，也就是这个lastCoin 有几种找钱情况

int times = totalMoney/lastCoin

List<String>resultList = new ArrayList<String>()

//如果当前硬币的面值大于余额。但是手中还有更小面值的硬币，则递归调用找钱。

if(times==0&&coinType.length!=0){

List<String>childList = reCoins(newCoinType, totalMoney)

resultList.addAll(childList)

//进行遍历，得到带找钱的值

}else{

//最小面值了，所以，直接返回值

if(coinType.length==1){

resultList.add(" 1分*"+totalMoney+"个 ")

}else{

//不是最小面值，所以，要遍历下

for(int i=1i<=timesi++){

List<String>childList = null

int remainder = totalMoney-lastCoin*i//新余额

if(remainder != 0){

childList = reCoins(newCoinType, remainder)

for(String r:childList){

r = " "+lastCoin+"分*"+i+"个 " + r

resultList.add(r)

}

}else{

resultList.add(" "+lastCoin+"分*"+i+"个 ")

}

}

}

}

return resultList

}

}

加油，java的路 还有很长哦，呵呵

public getMin{

public int MinNumber=0

public int findMax(int[] a){

for(int i=0i<a.lengthi++){

if(a[i]==0) return a[--i]

}

return a[a.length-1]

}

public boolean Compare(int a,int b){

public boolean flag=true

if(a>b) flag=flase

return flag

}

public int getMinNumber(int[] M,int Money){

int[] findM=new int[M.length]

int index=0

for(int i=0i<M.lengthi++){

boolean f = this.Compare(M[i],money)

if(f) findM[index++]=M[i]

}

int max = this.findMax(findM)

MinNumber++

if((Money-max)!=0) {

getMinNumber(M,Money-max)

}

return MinNumber

}

public int[] Start(){

System.out.println("请输入查询组数")

int group=System.in.read()

int[] M={1,2,5,10,20,50,100}

int[] Result = new Int[group]

int index=0

while (group-- >0){

System.out.println("请输入金额")

int money=System.in.read()

Result[index++] = getMinNumber(M,money)

MinNumber=0

}

}

public void print(int[] MinNumber){

for(int i=0i<MinNumber.length.i++){

System.out.println(MinNumber[i]+" ")

}

}

}

public static void main(String[] args){

new getMin().print(new getMin().Start())

}

没测试啊，有问题请勿喷，呵呵

import java.awt.event.ActionEvent

import java.awt.event.ActionListener

import java.awt.event.KeyEvent

import java.awt.event.KeyListener

import javax.swing.JFrame

import javax.swing.JLabel

import javax.swing.JOptionPane

import javax.swing.JTextField

public class Test implements KeyListener {

JFrame jf = new JFrame("找零系统")

JLabel author = new JLabel("作者名:XXX")

JLabel priceLabel = new JLabel("价格:")

JLabel pmoneyLabel = new JLabel("付款:")

JTextField priceField = new JTextField()

JTextField pmoneyField = new JTextField()

JLabel gmoney = new JLabel()

public void init() {

jf.setLayout(null)

jf.setSize(170, 170)

jf.setResizable(false)

jf.setLocationRelativeTo(null)

jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE)

jf.setVisible(true)

author.setBounds(50, 10, 100, 30)

priceLabel.setBounds(10, 50, 30, 20)

pmoneyLabel.setBounds(10, 80, 30, 20)

priceField.setBounds(50, 50, 100, 20)

pmoneyField.setBounds(50, 80, 100, 20)

gmoney.setBounds(40, 110, 100, 20)

jf.add(author)

jf.add(priceLabel)

jf.add(pmoneyLabel)

jf.add(priceField)

jf.add(pmoneyField)

jf.add(gmoney)

priceField.addKeyListener(this)

pmoneyField.addKeyListener(this)

}

public static void main(String[] args) {

new Test().init()

}

public void keyPressed(KeyEvent e) {

}

public void keyReleased(KeyEvent e) {

if (!priceField.getText().equals("")

&& !pmoneyField.getText().equals("")) {

try {

float price = Float.parseFloat(priceField.getText())

float pmoney = Float.parseFloat(pmoneyField.getText())

gmoney.setText("找零:" + (pmoney - price) + "元")

} catch (NumberFormatException e1) {

JOptionPane.showMessageDialog(jf, "输入错误!", "出错了",

JOptionPane.ERROR_MESSAGE)

priceField.setText("")

pmoneyField.setText("")

gmoney.setText("")

}

} else {

gmoney.setText("")

}

}

public void keyTyped(KeyEvent e) {

}

}

---