算法之暴力求解

迷南。 2022-06-14 08:54 236阅读 0赞

# 算法之暴力求解 #

*  **暴力求解的简单解释**：  
    
    
     *  很多问题都可以”暴力解决”——不用太动脑筋，把所有的可能性都列举出来，然后一一实验。尽管这样的方法显得很”笨”，但却可以常常行之有效。

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

*  **简单枚举**：  
    
    
     *  在枚举复杂对象之前，让我们先尝试着枚举一些相对简单的东西，如整数，字串等。
     *  **除法**：
     *  输入正整数n, 按从小到大的顺序排列输出形如abcde/fghij = n的表达式，其中a~j恰好为数字0~9的一个排列，2 <= n <= 79。
     *  样例输入:
     *  62
     *  样例输出：
     *  79564/01283 = 62
     *  94736/01528 = 62
     *  分析：
     *  枚举0~9的所有排列？没这个必要。只需要枚举fghij就可以算出abcde，然后判断所有数字都不相同即可。不仅程序简单，而且枚举量从10！= 3628800降低点至不到1万。由此可见，即使是采用暴力枚举，也是需要进行认真分析问题的。

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

*  代码:

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int n;
    int arr[2][5];
    int ans;
    
    void get_arr(int a[], int num)
    {
        for (int i = 4; i > 0; i --) {
            a[i] = num%10;
            num /= 10;
        }
        a[0] = num;
    }
    
    bool check()
    {
        int cnt[10] = {
       0};
        for (int i = 0; i < 2; i ++) {
            for (int j = 0; j < 5; j ++) {
                if (arr[i][j] >= 10 || ++cnt[arr[i][j]] > 1) return false;
            }
        }
        return true;
    }
    
    void print()
    {
        for (int i = 0; i < 5; i ++)
            printf("%d", arr[0][i]);
        printf(" / ");
        for (int i = 0; i < 5; i ++)
            printf("%d", arr[1][i]);
        printf(" = %d\n", n);
    }
    
    int main(void)
    {
        int t = 0;
        while (cin >> n && n) {
            if (t++) puts("");
            ans = 0;
            for (int y = 1234; y <= 50000; y++) {
                int x = y * n;
                get_arr(arr[0], x);
                get_arr(arr[1], y);
                if (check()) {
                    ans++;
                    print();
                }
            }
            if (!ans) printf("There are no solutions for %d.\n", n);
        }
    
        return 0;
    }

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

*  **简单分析一下程序的实现**：  
    
    
     *  **`main`**:
     *  输入n，判断输入的n是否准确；
     *  `if(t++) puts("");`输出一个换行符，在进行每一步操作之后。也就是`t`这个参数变量对于程序的运行效果没有影响， 只是加上之后会更加使得你的程序规范化。
     *  `y = 1234; y <= 50000; y++`y是fghij的数表示，因为知道了fghij之后，由于自己输入的n，所以abcde也就知道了。在算法分析中也体现出来了。
     *  `get_arr`的介绍:

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

> JackDan9 Thinking  
> 算法竞赛入门经典