アルゴリズムの暴力の解

アルゴリズムの暴力の解

暴力解の簡単な解釈:

多くの問題は「暴力的に解決できる」--あまり頭を悩まず、すべての可能性を列挙し、一つ一つ実験する.このような方法は「愚か」に見えるが、よく有効にすることができる.

単純列挙:

複雑なオブジェクトを列挙する前に、整数、文字列など、比較的簡単なものを列挙してみましょう.

除算:

は正の整数nを入力し、abcde/fghij=nのような出力形の式を小さい順に並べ、ここでa~jはちょうど0~9の1つの配列であり、2<=n<=79である.

サンプル入力:

62

サンプル出力:

79564/01283 = 62

94736/01528 = 62

分析:

列挙0~9のすべての配列?そんな必要はない.fghijを列挙するだけでabcdeを算出し、すべての数字が異なると判断すればよい.プログラムが簡単なだけでなく、列挙量は10!=3628800は1万未満に下がった.暴力的な列挙を用いても、問題を真剣に分析する必要があることがわかる.

コード:

#include 
#include 
#include 
#include 
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);
}

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);
    }

    return 0;
}

プログラムの実装を簡単に分析します.

main :

入力nは、入力nが正確か否かを判断する.

if(t++) puts("");は、各ステップの操作後に改行を出力する.つまりtというパラメータ変数はプログラムの実行効果に影響しませんが、加えてプログラムを規範化します.

y = 1234; y <= 50000; y++ yはfghijの数表示で、fghijを知ってから、自分で入力したnなのでabcdeでもわかります.アルゴリズム解析にも現れた.

get_arrの紹介:

JackDan 9 Thinkingアルゴリズムコンテスト入門経典