欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

求一共有多少种方式系列问题(找零钱)

程序员文章站 2023-11-09 19:08:52
求一共有多少种方式系列问题(找零钱问题) 背景: 假设有四种面额的钱币 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种办法 相比之前的确实少了不少