求一共有多少种方式系列问题（找零钱问题）
背景：
假设有四种面额的钱币
1 元、2 元、5 元和 10 元，一共给我 10 元
那您可以奖赏我 1 张 10 元，或者 10 张 1 元
或者 5 张 1 元外加 1 张 5 元等等
如果考虑每次奖赏的金额和先后顺序
那么最终 一共有多少种不同的奖赏方式呢？看到了一个这样的问题，想用Java代码解决一下
本方案用到了递归的方式计算
下面用Java代码做了个实现
考虑每次奖赏的金额和先后顺序
public class Allprobability {
public static void main(String [] args){
//设置数额
int a = 10;
get(a,"");
System.out.println("over");
}
private static int m = 0;
/**
* 计算后面可能发生的概率
* @param num 剩余
* @param s 缓冲字符串
*/
private static void get(int num ,String s){
//0 直接输出
if(num == 0) System.out.println("第"+(++m)+"种方法"+s);
//1
if(num>=1){
get(num-1,s+" "+1);
}
//2
if(num>=2){
get(num-2,s+" "+2);
}
//5
if(num>=5){
get(num-5,s+" "+5);
}
//10
if(num>=10){
get(num-10,s+" "+10);
}
}
}以上代码输出结果为：
第1种方法 1 1 1 1 1 1 1 1 1 1
第2种方法 1 1 1 1 1 1 1 1 2
第3种方法 1 1 1 1 1 1 1 2 1
......
第127种方法 5 2 2 1
第128种方法 5 5
第129种方法 10
over真的不做不知道一做吓一跳啊 才数字10就有这么多结果
考虑重复
我又加了个Info类
这里面存着4种货币的数量和一个缓存的num值
import java.util.LinkedList;
import java.util.List;
public class Allprobability2{
/** 结果 **/
private static List<Info> infos = new LinkedList<>();
public static void main(String [] args){
//设置数额
get(new Info(10));
System.out.println("over");
}
private static int m = 0;
private static void get(Info s){
int num = s.getNum();
//0 直接输出
if(s.getNum() == 0) {
if (!s.hasIt())System.out.println("第"+(++m)+"种方法 "+s);
}
//1
if(s.getNum()>=1){
get(s.cp().add(1).setNum(num-1));
}
//2
if(num>=2){
get(s.cp().add(2).setNum(num-2));
}
//5
if(num>=5){
get(s.cp().add(5).setNum(num-5));
}
//10
if(num>=10){
get(s.cp().add(10).setNum(num-10));
}
}
//将结果封装为一个结果类
static class Info{
public Info(int num){this.num = num;}
public Info(int a1, int a2, int a5, int a10) {
this.a1 = a1;
this.a2 = a2;
this.a5 = a5;
this.a10 = a10;
}
int num,a1,a2,a5,a10 = 0;
public boolean hasIt(){
for (Info i : infos){
if(i.equals(this))return true;
}
infos.add(this);
return false;
}
public int getNum(){return this.num;}
public Info setNum(int num){this.num = num;return this;}
public Info cp(){
return new Info(this.a1,this.a2,this.a5,this.a10);
}
public Info add(int a){
if(a==1)a1++;
if(a==2)a2++;
if(a==5)a5++;
if(a==10)a10++;
return this;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Info info = (Info) o;
if(!(this.a1==info.a1))return false;
if(!(this.a2==info.a2))return false;
if(!(this.a5==info.a5))return false;
if(!(this.a10==info.a10))return false;
return true;
}
@Override
public String toString() {
return"1元的："+a1+"个，2元的"+ a2+"个，5元的"+a5+"个，10元的"+a10+"个";
}
}
}
这一次输出结果
第1种方法 1元的：10个，2元的0个，5元的0个，10元的0个
第2种方法 1元的：8个，2元的1个，5元的0个，10元的0个
第3种方法 1元的：6个，2元的2个，5元的0个，10元的0个
第4种方法 1元的：5个，2元的0个，5元的1个，10元的0个
第5种方法 1元的：4个，2元的3个，5元的0个，10元的0个
第6种方法 1元的：3个，2元的1个，5元的1个，10元的0个
第7种方法 1元的：2个，2元的4个，5元的0个，10元的0个
第8种方法 1元的：1个，2元的2个，5元的1个，10元的0个
第9种方法 1元的：0个，2元的5个，5元的0个，10元的0个
第10种方法 1元的：0个，2元的0个，5元的2个，10元的0个
第11种方法 1元的：0个，2元的0个，5元的0个，10元的1个
over考虑完重复结果 只有11种办法 相比之前的确实少了不少
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
