求一共有多少种方式系列问题(找零钱)
程序员文章站
2022-06-19 21:08:43
求一共有多少种方式系列问题(找零钱问题) 背景: 假设有四种面额的钱币 1 元、2 元、5 元和 10 元,一共给我 10 元 那您可以奖赏我 1 张 10 元,或者 10 张 1 元 或者 5 张 1 元外加 1 张 5 元等等 如果考虑每次奖赏的金额和先后顺序 那么最终 一共有多少种不同的奖赏方 ......
求一共有多少种方式系列问题(找零钱问题)
背景:
假设有四种面额的钱币 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种办法 相比之前的确实少了不少
上一篇: 形容高兴的句子整理