141: C语言训练-百钱百鸡问题 标题

原题链接：C语言训练-百钱百鸡问题

首先先来认识一下，何谓暴力破解法？是指从可能的解集合（空间）中一一列举各情况，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。

基本思路:
（1）建立问题的数学模型，确定问题的可能解的集合（可能解的空间）。

（2）逐一列出可能解集合中的元素，验证是否是问题的解。

优化方向：通过加强约束条件，缩小可能解的集合的规模。
按照暴力破解法的思想，我们首先会想到的就是直接所有循环破解，管你牛鬼蛇神。

解法一：
1.抽象出数学模型，这里指的就是方程组

设公鸡为x，母鸡为y,小鸡为z，

鸡： x+y+z=100

钱： 5x+3y+1/3z=100

2.代码

#include<iostream>using namespace std;int main(){    int x,y,z;    for(x=0;x<=20;x++)//公鸡不会超过20只        for(y=0;y<=34;y++)//母鸡不会超过34只            for(z=0;z<=100;z++)//小鸡不会超过100只                if((x+y+z)==100 && (5*x+3*y+z/3)==100&&z%3==0)//同时要满足z是3的整数cout<<"cock="<<x<<","<<"hen="<<y<<","<<"chicken="<<z<<endl;    return 0;}

算法分析：显然，该算法嵌套三重循环，算法复杂度为O(n^3), 循环次数为20*34*100，数量级为10^4，这种算法根本不能满足我们的需求。所以聪明一点的人可能会想到要减少一个循环的嵌套，以此降低算法复杂度。

解法二：
1.减少一个循环的嵌套，模型不变，进一步优化算法

2.代码

#include<iostream>using namespace std;int main(){    int x,y,z;    for(x=0;x<=20;x++)//公鸡不会超过20只        for(y=0;y<=34;y++)//母鸡不会超过34只        {            z=100-x-y;//根据x,y可求出z            if(z==(300-15*x-9*y)&&z%3==0)cout<<"cock="<<x<<","<<"hen="<<y<<","<<"chicken="<<z<<endl;        }                            return 0;}
算法分析：显然，该算法嵌套二重循环，算法复杂度为O(n^2), 循环次数为20*34，数量级为10^2，这种算法比上一算法足足降低了2个数量级，可见循环嵌套越多，算法就越差。所以还需要继续优化，用我们的初中数学知识就OK.

解法三：1.每使用一个for(x)循环，就相当于将一个未知数(x)变成已知数（x）, 两个方程两个未知数，方程就具有可解性了， 这样就可以， 继续减少一个循环的嵌套

鸡： x+y+z=100

钱： 15x+9y+z=300

=>>7x+4y=100 ->y ->z

2.代码：

#include<iostream>using namespace std;int main(){    int x,y,z;    for(x=0;x<=20;x++)//公鸡不会超过20只    {        y=25-1.75*x;//先求y        z=100-x-y;//再求z        if(z==(300-15*x-9*y)&&z%3==0&&y>0&&&z>0)cout<<"cock="<<x<<","<<"hen="<<y<<","<<"chicken="<<z<<endl;    }    return 0;}
算法分析：显然，该算法只有一重循环，算法复杂度为O(n), 循环次数为20，数量级为10，这种算法比上一算法降低了1个数量级，说明该算法还是不错的，可以满足我们竞赛的需求。不过数学思维比较好的人，可以通过结果反过来继续优化。

通过上图的结果，我们发现 x以4递增，y以7递减, z以3递增，所以可以直接打印

#include<iostream>using namespace std;int main(){    int x,y,z;    for(int k=0;k<=3;k++)    {        x = 4 * k;        y = 25 - 7 * k;        z = 75 + 3 * k; cout<<"cock="<<x<<","<<"hen="<<y<<","<<"chicken="<<z<<endl;    }    return 0;}
算法分析：这种算法可以说是接近最优了，不过在AC的时候，强烈建议使用解法三，因为你不可能一开始就知道结果是什么和有多少种解法，以上是我对该算法的理解，如果你觉得还有优化的细节，欢迎留言，一同进步。

赠人玫瑰，手有余香。点个赞吧。^-^
蟹蟹，有问题请留言。