买东西过程中，卖家经常需要找零钱。现用代码实现找零钱的方法，要求优先使用面额大的纸币，假设卖家有足够数量的各种面额的纸币。
下面给出的算法比较简单，也符合人的直觉：把找零不断地减掉小于它的最大面额的纸币，直到找零为0为止。
package test.change; public class Program
{
public static void main(String[]args)
{
splitChange(69);
} //找零钱算法
public static void splitChange(int change)
{
//输入参数校验
if(change<1)
{
System.out.println("Invalid input.");
return;
} int copy=change;
//纸币的面值，必须降序排列
int[]notes={100,50,20,10,5,1};
//找零所需要的每张纸币的数量
int[]pieces=new int[notes.length];
//下面是主要的步骤
while(change>0)
{
for(int i=0;i<notes.length;i++)
{
if(change>=notes[i])
{
change=change-notes[i];
pieces[i]+=1;
break;
}
}
}
//结果输出
System.out.print(String.format("Your change is %d,\n%d=",copy,copy));
StringBuilder sb=new StringBuilder();
for(int i=0;i<pieces.length;i++)
{
if(pieces[i]>0)
sb.append(String.format("%d*%d piece(s)+", notes[i],pieces[i]));
}
String msg=sb.toString();
msg=msg.substring(0, msg.length()-1);
System.out.println(msg);
}
}
测试结果：
Your change is 69,
69=50*1 piece(s)+10*1 piece(s)+5*1 piece(s)+1*4 piece(s)
找零69，包括有50元纸币1张，10元纸币1张，5元纸币1张，1元纸币4张。
另外一种递归的方法：
public static int returnChange(int n)
{
if(n<=0)
return 0;
int[]notes={1,2,5,10,20,50,100};
int len=notes.length;
for(int i=len-1;i>=0;i--)
{
if(n>=notes[i])
return returnChange(n-notes[i])+1;
}
return 0;
}