【数据结构与算法之穷举法】案例

冷不防 2024-03-25 16:39 6阅读 0赞

#### 【数据结构与算法之穷举法】案例 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之穷举法】案例
         *   *   *  1 百钱白鸡
                 *  2 梅齐亚克的砝码问题

###### 1 百钱白鸡 ######

问题描述：一只公鸡值5钱，一只母鸡值3钱，三只雏鸡值1钱，现在要用100钱买100只鸡，请问公鸡、母鸡、雏鸡各买多少只？

Java代码实现描述：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: BuyChicken
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 15:08
     */
    
    public class BuyChicken {
        
    
        public static void buyChicken() {
        
    
            for (int x = 0; x <= 100; x++) {
        
                for (int y = 0; y <= 100; y++) {
        
                    for (int z = 0; z <= 100; z++) {
        
                        if ((15 * x + 9 * y + z == 300) && (x + y + z == 100)) {
        
                            System.out.println("公鸡: " + x + " 母鸡: " + y + "雏鸡: " + z);
                        }
                    }
                }
            }
        }
    
        public static void main(String[] args) {
        
    
            buyChicken();
    
        }
    
    }

运行结果

![在这里插入图片描述][185a3984083d4d9e96090acbffd1ae39.png_pic_center]

###### 2 梅齐亚克的砝码问题 ######

问题描述：一位商人有一个质量为40磅的砝码，一天，他不小心将这个砝码摔成了4块。吝啬的商人不愿意扔掉这个破碎的砝码，于是他仔细研究这4块砝码碎片，发现恰好每块砝码碎片的质量都是整数，而且各不相同，同时这四块砝码碎片可以在天平上称出1 - 40 磅的任意整数磅数。

编程求出这4 块碎片的质量各是多少？

注意用天平秤和直接用秤称还是有区别的。

比如称1磅，不是1磅就1磅的，

![在这里插入图片描述][067aea5167904faab90da276ec2e2ed1.png_pic_center]

这样才叫用天平称出1磅。所以公式 应该是  x 1 a + x 2 b + x 3 c + x 4 d = w , x 1 , x 2 , x 3 , x 4 ∈ \{ − 1 , 0 , 1 \} x\_1a + x\_2b + x\_3c + x\_4d = w , x\_1,x\_2,x\_3,x\_4 ∈\\\{-1,0,1\\\} x1a\+x2b\+x3c\+x4d=w,x1,x2,x3,x4∈\{ −1,0,1\}

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: WeightProblem
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 15:29
     */
    
    public class WeightProblem {
        
    
        // 判断砝码碎片组合(a,b,c,d)是否可以称出1-40的任意整数磅
        public static boolean isMeasurableOneToForty(int a, int b, int c, int d) {
        
            int weight;
    
            for (weight = 1; weight <= 40; weight++) {
        
                if (!isMeasurable(a, b, c, d, weight)) {
        
                    return false;
                }
            }
    
            return true;
        }
    
        // 判断砝码碎片组合(a,b,c,d)是否可以称出weight所表示的重量
        public static boolean isMeasurable(int a, int b, int c, int d, int weight) {
        
            int x1, x2, x3, x4;
            for (x1 = -1; x1 <= 1; x1++) {
        
                for (x2 = -1; x2 <= 1; x2++) {
        
                    for (x3 = -1; x3 <= 1; x3++) {
        
                        for (x4 = -1; x4 <= 1; x4++) {
        
                            if (x1 * a + x2 * b + x3 * c + x4 * d == weight) {
        
                                return true;
                            }
                        }
                    }
                }
            }
    
            return false;
        }
    
        public static void MeziakWeight() {
        
            int a, b, c, d;
            for (a = 1; a < 40; a++) {
        
                for (b = a + 1; b < 40; b++) {
        
                    for (c = b + 1; c < 40; c++) {
        
                        for (d = c + 1; d < 40; d++) {
        
                            if (isMeasurableOneToForty(a, b, c, d) && a + b + c + d == 40) {
        
                                System.out.println(a + ", " + b + ", " + c + ", " + d);
                            }
                        }
                    }
                }
            }
        }
    
        public static void main(String[] args) {
        
    
            MeziakWeight();
    
        }
    
    }

运行结果

![在这里插入图片描述][35e646ec912f4c9694c0b936fa0f4130.png_pic_center]

[185a3984083d4d9e96090acbffd1ae39.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a43febbaa96a404ab4673e0e53c2b667.png
[067aea5167904faab90da276ec2e2ed1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7c49fa97b23045cdb893602938f2738c.png
[35e646ec912f4c9694c0b936fa0f4130.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e6f127d7da0f459fa94c742622b018a7.png