暴力アルゴリズム

暴力アルゴリズム
1.アルゴリズム分析
多くの場合、問題のデータ量が大きくない場合は暴力的に処理することができます.
2.例題
acwing 116パイロット兄弟題意:「パイロット兄弟」というゲームは、プレイヤーが16個のハンドルを持つ冷蔵庫をスムーズに開く必要がある.各ハンドルは、オンまたはオフの2つの状態のいずれかであることが知られている.すべてのハンドルが開いているときだけ、冷蔵庫が開きます.ハンドルは4と表示できます.х4のマトリクスで、任意の位置[i,j]のハンドルの状態を変更できます.しかし、これにより、i行目およびj列目のすべてのハンドルの状態も変化する.冷蔵庫を開けるのに必要な切り替えハンドルの最小値を求めてください.问题解:ボタンは异或に相当するので、ボタンの顺番はどうでもいい.本題は16個のボタンしかなく,すべての場合を直接暴力することができ,その後,異種の値を先に処理し,暴力のたびにO(1)が最後の結果を調べることができる.コード:

#include 

using namespace std;

int change[10][10];
int state, now;

int get(int x, int y) {
    return x * 4 + y;
}

int main() {
    //         
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            for (int k = 0; k < 4; ++k) 
                change[i][j] += (1 << get(i, k)) + (1 << get(k, j));
            change[i][j] -= (1 << get(i, j));
        }
    }
    
    // state         
    for (int i = 0; i < 4; ++i) {
        string line;
        cin >> line;
        for (int j = 0; j < 4; ++j) {
            if (line[j] == '+') state += (1 << get(i, j));
        }
    }
    
    vector > res;
    for (int i = 0; i < 1 << 16; ++i) {  //          
        vector > tmp;
        int now = state;
        for (int j = 0; j < 16; ++j) {  //              
            if (i >> j & 1 ) {
                int x = j / 4, y = j % 4;
                now ^= change[x][y];
                tmp.push_back({x, y});
            }
        }
        
        //        0    
        if (!now && (res.empty() || res.size() > tmp.size())) res = tmp;
    }
    
    cout << res.size() << endl;
    for (auto r: res) cout << r.first + 1 << " " << r.second + 1 << endl;
    return 0;
}

acwing 1209帯分数題意:100は帯分数の形式として表すことができる:100=3+(frac{69258}{714})はまた、100=82+(frac{3546}{197})注意特徴:帯分数では、数字1〜9がそれぞれ出現し、1回しか出現しない(0を含まない)と表すことができる.このような帯分数は,100に11種類の表現がある.nを与え,nのバンド点数の表現数を求める.1≦n<10^6^問題解:1~9は数字ごとに1回しか現れないので、全配列で9!種は、暴力的に9つの数字をabcに分割し、構成されているバンド点数がnであるかどうかを判断すればよい.時間の複雑さ:9!*9^3^コード:

#include 

using namespace std;

int res = 0;
int n;
vector num;

void check() {
    int a = 0, b = 0, c = 0;
    for (int i = 1; i <= 7; ++i) {  // a   
        for (int j = 1; j <= 7; ++j) {  // b   
            int k = 9 - i - j;  // c   
            if (k <= 0) continue;
            a = 0, b = 0, c = 0;
            int pos = 0;
            for (int l = 0; l < i; ++l) a = a * 10 + num[pos++];  // a
            if (a > n) continue;
            for (int l = 0; l < j; ++l) b = b * 10 + num[pos++];  // b
            for (int l = 0; l < k; ++l) c = c * 10 + num[pos++];  // c
            if (b % c == 0 && a + b / c == n) {  //      n
                res++;
            }
        }
    }
    return;
}

int main() {
    cin >> n;
    num.push_back(1);
    num.push_back(2);
    num.push_back(3);
    num.push_back(4);
    num.push_back(5);
    num.push_back(6);
    num.push_back(7);
    num.push_back(8);
    num.push_back(9);
    check();
    while (next_permutation(num.begin(), num.end())) check();  //      
    cout << res << endl;
    return 0;
}