使用蛮力法求解数字迷问题（类似ABCAB*A = DDDDDD）

朱雀 2022-05-28 04:59 638阅读 1赞

#### 蛮力法概述 ####

> 蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述>和所涉及的概念定义。是基于计算机运算速度快这一特性，在解决问题时采用的一种“懒惰”的策略。把问题的所有情况或所有过程交给计算机去一一尝试，从中找到问题的解。

#### 特性 ####

> (1)理论上，蛮力法可以解决可计算领域的各种问题。
> 
> (2)蛮力法经常用来解决一些较小规模的问题。
> 
> (3)对于一些重要的问题(如排序、查找、串匹配)，蛮力法可以设计一些、合理的算法，这些算法具有实用价值，而且不受输入规模的限制。
> 
> (4)蛮力法可以作为某类问题时间性能的下界，来衡量同样问题的其他算法是否具有更高的效率。

#### 设计思想 ####

> 蛮力法所依赖的最基本技术是扫描技术，依次处理元素是蛮力法的关键，依次处理每个元素的方法是遍历。虽然设计很高效的算法很少来>自于蛮力法，基于以下原因，蛮力法也是一种重要的算法设计技术:
> 
> (1)理论上，蛮力法可以解决可计算领域的各种问题。对于一些非常基>本的问题，例如求一个序列的最大元素，计算n个数的和等，蛮力法>是一种非常常用的算法设计技术。
> 
> (2)蛮力法经常用来解决一些较小规模的问题。如果需要解决的问题规模不大，用蛮力法设计的算法其速度是可以接受的，此时，设计一个>更高效算法的代价是不值得的。
> 
> (3)对于一些重要的问题(例如排序、查找、字符串匹配)，蛮力法可以产生一些合理的算法，他们具备一些实用价值，而且不受问题规模的>限制。
> 
> (4)蛮力法可以作为某类时间性能的底限，来衡量同样问题的更高效算法。**（参考百度百科）**

--------------------

> 我们经常会遇到类似于比赛，给定一定的条件，预测名次等这种问题，这种问题往往让人无从下手，但如果采用蛮力法策略，将每种可能的情况一一遍历，利于计算机运算快的这一特性，从而筛选出合乎题意要求的答案，这种例子书上列举的相对比较多，这里就不废话了。同样我们经常也会遇到给定一个由字母组成的计算式或者用语言描述，但可以转化为数字求值的问题，让我们推算对应的数值。这类问题往往通过蛮力法都可以解决,下面看两个典型的例子。

Ⅰ ）求这样两个数据：5位数=2\*4位数，9个数字互不相同。

> 这是一个典型的，用语言描述，但可以转化为数字求值的问题。我们可以把这个题抽象为一个算术表达式：ABCD \* 2 = EFGHI;同样我们可以确定A的取值范围为A：5~9;其他的取值范围为0~9，这个题目的条件比较简单9个数字各不相同，我们可以使用穷举法，将可能的值 一一尝试从而得出结论。

**源代码**

#include<stdio.h>
    
    int main()
    {
        int a, b, c, d, e, f, g, h, i;
        int m, n;
        for (a = 5; a <= 9; a++)            //一一列举可能的取值
        for (b = 1; b <= 9; b++)
        for (c = 1; c <= 9; c++)
        for (d = 1; d <= 9; d++)
        for (e = 1; e <= 9; e++)
        for (f = 1; f <= 9; f++)
        for (g = 1; g <= 9; g++)
        for (h = 1; h <= 9; h++)
        for (i = 1; i <= 9; i++)
        {
            //由于if语句里边的条件比较多，使用续行符（\+Enter）将其隔开
            if (a != b&&a != c&&a != d&&a != e&&a != f&&a != g&&a != h&&a != i\
                &&b != c&&b != d&&b != e&&b != f&&b != g&&b != h&&b != g&&b != i\
                &&c != d&&c != e&&c != f&&c != g&&c != h&&c != i\
                &&d != e&&d != f&&d != g&&d != h&&d != i\
                &&e != f&&e != g&&e != h&&e != i\
                &&f != h&&f != g&&f != i\
                &&g != h&&g != i\
                &&h != i)
            {
                m = a * 1000 + b * 100 + c * 10 + d;
                n = e * 10000 + f * 1000 + g * 100 + h * 10 + i;
                if (n == m * 2)
                {
                    printf("%d * %d =%d \n", m, 2, n);
                }
    
            }
        }
        return 0;
    }

> **运行结果**  
> ![这里写图片描述][SouthEast]

Ⅱ ） 编写算法解如下数字迷。  
![这里写图片描述][SouthEast 1]

>        们可以通过上边的式子确定Ａ，Ｂ，Ｃ，Ｄ对应的值的范围，由于最后乘积为６位数说以Ａ的值最小为３（考虑前边运算有进位）。  
>        所以对应的取值范围为Ａ：３～９，Ｂ：０～９，Ｃ：０～９，Ｄ：０～９；同时我们可以注意到ＡＢＡＢＣ中万位数和百位数的值相等都为Ａ，同样千位和十位的数组都为Ｂ。我们可以把这看作是题目给的一个隐含条件。在使用蛮力法的时候，可以找到的条件越多，越有利于得到正确的答案。对于这个题如果采用乘法运算，我们需要同时考虑ＡＢＣＤ对应的值。为了提高效率，我们可以将上式简单变形为：ＤＤＤＤＤＤ／Ａ＝ＡＢＣＡＢ，这时我们只需要枚举Ｄ和Ａ的可能取值，定义一个变量Ｅ由于存放ＤＤＤＤＤＤ的值，那么**Ｅ＝Ｄ＊１０００００＋Ｄ＊１００００＋Ｄ＊１０００＋Ｄ＊１００＋Ｄ＊１０＋Ｄ。**  
> 定义变量Ｆ用于存放ＡＢＣＡＢ的值。则**Ｆ＝Ａ×１００００＋Ｂ×１０００＋Ｃ×１００＋Ａ×１０＋Ｂ**；  
> ＡＢＡＢＣ（F）中万位数和百位数的值相等都为Ａ，同样千位和十位的数组都为Ｂ,对于ABCAB（F）万位A=F/10000,十位A=F%100/10,我们可以得出条件：**（F/10000==A&&F%100/10==A）**,对于千位和十位的数组都为Ｂ得出条件**（F % 10 == F / 1000 % 10）**我们将这些条件用C语句表达出来，就可以使用蛮力法求出对应结果。
> 
> 源代码

#include<stdio.h>
    
    int main()
    {
        int A, B, C, D;
        int E, F;
        for (A = 3; A <= 9; A++)         //A的取值范围为3~9
        {
            for (D = 1; D <= 9; D++)
            {
                //将DDDDDD用E来表示
                E = D * 100000 + D * 10000 + D * 1000 + D * 100 + D * 10 + D;
                if (E % A == 0)
                {
                    F = E / A;     //F=ABCAB
                    //万位数和十位数相等值为A
                    if (F / 10000 == A && (F % 100 / 10 == A)) 
                    {
                        //千位数和个位数相等（B）
                        if (F % 10 == F / 1000 % 10)
                        {
                            //输出结果
                            printf("%d * %d = %d\n", F, A, E);
                        }
                    }
                }
            }
        }
        return 0;
    }

> **运行结果**

![这里写图片描述][SouthEast 2]

> 结果为：37037 \* 3 =111111，即：A=3，B=7，C=0，D=1

#### 简单总结 ####

> 对于类似的字母表达式求值问题，我们无从下手时可以考虑使用蛮力法，将各种可能出现的结果通过循环语句一一尝试相邻，利用计算机快速的运行效率求解，在求解过程中要尽可能多并准确的找到相应的约束条件，找到的条件越多，越有利于得出正确的结论，虽然蛮力法相对效率比较低，但对于求解某些问题来说，不失为一种较好的策略。

[SouthEast]: /images/20220528/aad94c983ca842f089cf21e0a0034db8.png
[SouthEast 1]: /images/20220528/8e5ce019623645a4a03a999bc542d6e7.png
[SouthEast 2]: /images/20220528/86e7caee667c421cbca199782c1bd0ee.png