现在的位置: 首页 > 综合 > 正文

1.1–暴力破解法

2018年04月29日 ⁄ 综合 ⁄ 共 1103字 ⁄ 字号 评论关闭

这个大家都很熟悉了,也应该是入门时学过的最简单的算法了,,

    暴力破解法:也叫穷举法,穷举法的基本思想是根据题目的部分条件确定答案的大致范围,并在此范围内对所有可能的情况逐一验证,直到全部情况验证完毕。若某个情况验证符合题目的全部条件,则为本问题的一个解;若全部情况验证后都不符合题目的全部条件,则本题无解。穷举法也称为枚举法。

    用穷举法解题时,就是按照某种方式列举问题答案的过程。针对问题的数据类型而言,常用的列举方法一有如下三种:
(1)顺序列举 是指答案范围内的各种情况很容易与自然数对应甚至就是自然数,可以按自然数的变化顺序去列举。

(2)排列列举 有时答案的数据形式是一组数的排列,列举出所有答案所在范围内的排列,为排列列举。

(3)组合列举 当答案的数据形式为一些元素的组合时,往往需要用组合列举。组合是无序的。

列出两道非常简单的经典题目:

    1.鸡兔同笼问题。

        EX:鸡和兔子共有40只,脚共有120只,求各有几只鸡,几只兔?

    思路很简单,从0开始一一列举就好,直到把所有符合条件的解都找出来为止

    【注】 用大写字母来表示固定的常量,如头数和脚数是良好的编程习惯


# include<cstdio>
# include<iostream>

using namespace std;

int main(void)
{
    int HEAD = 50;
    int FOOT = 120;

    int x, y;
    for ( x = 0;x <= HEAD;x++ )
    {
        y = 50-x;
        if ( x*2+y*4 == 120 )
        printf("%d %d",x,y);

    }
    return 0;
}

2.韩信点兵问题:
        EX:军队大概有1000+的人,5人一组剩1人,7人一组剩2人,8人一组剩3人,问军队共有多少人?

    依然是暴力枚举的思想,看你怎么处理这个初始值了,如果能知道人数的上界就不错了,目前只知道题目的下界。。。

# include<cstdio>
# include<iostream>
# include<algorithm>

using namespace std;

int main(void)
{
    for ( int i = 1000;i <= 2000;i++ )
    {
        if ( i%5 == 1 && i%7 == 2 && i%8 == 3 )
            cout<<i<<endl;
        else
            continue;
    }


    return 0;
}

好了,,,就是这两道例题了,大家仔细想想其中的思想和所涵盖的方法。。。当然,这种算法必然存在了很

多不必要的枚举,这样一来,即使是能一秒钟计算1W亿次的计算机,也会大大减少了它的运行速度,那么就需要我们通过剪枝来一步一步的仔细处理和筛选,从而让计算机更加快速的计算出我们

我们所要求的结果。

    

抱歉!评论已关闭.