百钱百鸡问题

问题：公鸡5块钱一只，母鸡3块钱一只，小鸡一块钱3只，现在有100块钱购买100只鸡，请问可以买多少只公鸡、多少只母鸡、多少只小鸡？

解题思路：

依据题目提供的线索我们可以知道： 

如果100块钱只买公鸡可以买20只，那么公鸡的取值范围在0——20之间。

如果100块钱只买母鸡可以买33只，那么母鸡的取值范围在0-——33之间。

1. 公鸡+母鸡+小鸡 = 100 （100块钱可以买公鸡、母鸡和小鸡）

2.5x公鸡 + 3x母鸡 + 小鸡/3 = 100 

 

思路1：

1.第一层循环遍历100块钱购买公鸡的数量20只.

2.第二层循环遍历100块钱购买母鸡的数量33只.

3.第三层循环遍历小鸡数量范围（0-100）

public class Lesson1 {

    public void test() {
        int cock, hen, chicken;
        for (cock = 0; cock <= 20; cock++) {
            for (hen = 0; hen <= 33; hen++) {
                for (chicken = 0; chicken <= 100; chicken++) {
                    boolean cond1 = 5 * cock + 3 * hen + chicken / 3 == 100;
                    boolean cond2 = cock + hen + chicken == 100;
                    boolean cond3 = chicken % 3 == 0;
                    if (cond1 && cond2 && cond3) {
                        System.out.printf(String.format("公鸡 = %d,母鸡=%d,小鸡=%d\n", cock, hen, chicken));
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Lesson1 lesson1 = new Lesson1();
        lesson1.test();
    }
}
运行结果
公鸡 = 0,母鸡=25,小鸡=75
公鸡 = 4,母鸡=18,小鸡=78
公鸡 = 8,母鸡=11,小鸡=81
公鸡 = 12,母鸡=4,小鸡=84

 不难发现，上面的解题思路采用了3层循环，这样会导致计算时间过长，那么接下来我们优化一下，依照题目我们可以知道单纯购买可以买公鸡20只，母鸡33只，那么第三层循环就可以直接使用100-公鸡-母鸡=小鸡，因此优化算法如下：

public class Lesson2 {

    public void test() {
        int cock, hen, chicken;
        for (cock = 0; cock <= 20; cock++) {
            for (hen = 0; hen <= 33; hen++) {
                //剩下的是小鸡的数量
                chicken = 100 - hen - cock; 
                boolean cond1 = 5 * cock + 3 * hen + chicken / 3 == 100;
                boolean cond2 = chicken % 3 == 0;
                if (cond1 && cond2) {
                    System.out.printf(String.format("公鸡 = %d,母鸡=%d,小鸡=%d\n", cock, hen, chicken));
                }
            }
        }
    }

    public static void main(String[] args) {
        Lesson2 lesson2 = new Lesson2();
        lesson2.test();
    }
}

 最后，我们是否能够根据数据计算只使用一次循环来实现呢？

实际上也就是需要手动的化繁为简，求解3元一次方程组

cock + hen + chicken = 100

5cock + 3hen + (1/3)chicken = 100 → 消除chicken分母，多项式两边都乘以3 得出

15cock + 9hen + chicken = 300 ，方程组3元化2元求hen的值（减去cock + hen + chicken = 100）得到

14cock + 8hen = 200, 最终hen = 25-(7/4)cock。同理，算出小鸡chicken = 75+(3/4)cock.

目前为止算出的结果如下

hen = 25-(7/4)cock

chicken = 75+(3/4)cock

因此我们的算法可以更进一步简化，把cock带入到for循环体内即可

public class Lesson3 {

    public void test() {
        int cock, hen, chicken;
        for (cock = 0; cock <= 20; cock++) {
            hen = 25 - (7 * cock) / 4;
            chicken = 75 + (3 * cock) / 4;
            if (hen > 0 && chicken > 0) {
                boolean cond1 = 5 * cock + 3 * hen + chicken / 3 == 100;
                boolean cond2 = chicken % 3 == 0;
                if (cond1 && cond2) {
                    System.out.printf(String.format("公鸡 = %d,母鸡=%d,小鸡=%d\n", cock, hen, chicken));
                }
            }
        }
    }

    public static void main(String[] args) {
        Lesson3 lesson3 = new Lesson3();
        lesson3.test();
    }
}
运行结果
公鸡 = 0,母鸡=25,小鸡=75
公鸡 = 4,母鸡=18,小鸡=78
公鸡 = 8,母鸡=11,小鸡=81
公鸡 = 12,母鸡=4,小鸡=84

 

总结，同一个问题有不同的解决方法，如果能用最优的方法达到更高的执行效率是指的花时间去调整的。程序设计不仅仅是一门技术，更是一门艺术。第三种方案循环执行了20次，有没有更优的方法来减少循环的次数呢？ 答案当然是肯定有的，不知道读者有没有发现每次执行的结果只有4条，那么是不是意味着我们只需要执行4次呢？ 如何优化的问题请读者思考一下吧，本篇文章只是趣味算法的入门课，后面会持续更新，希望喜欢