【筆記】Complete Search 枚舉

  • 又稱Brute-force search(暴搜),是直觀的做法,藉由遍歷所有可能的情況,求得正確的答案,但經常有複雜度過高的問題,可以試著排除沒有必要嘗試的情況(剪枝 Pruning),以降低運算量
  • 【範例】 找出直角三角形
    • Input: 三角形三邊長的「邊長和」的下限 (L) 和上限 (R)。
    • Output: 所有符合條件的直角三角形邊長。
  • 【解題想法】
    • 預先假設三邊長有 a <= b <= c 的關係。
    • 三角形的任一邊長一定小於「邊長和」的一半。
  • 【練習】SPOJ ABCDEF題解
// Brute Force
#include <iostream>
using namespace std;

int main(){
    int L, R;
    int a, b, c;

    cin >> L >> R;
    for (a = 1; a <= R; a++){
        for (b = 1; b <= R; b++){
            for (c = 1; c <= R; c++){
                if (a+b+c >= L && a+b+c <=R){
                    if ((a*a + b*b) == c*c || (b*b + c*c) == a*a || (c*c + a*a) == b*b){
                        if (a <= b && b <= c)
                            cout << a << ' ' << b << ' ' << c << endl;
                    }
                }
            }
        }
    }
}

// 剪枝 Pruning
#include <iostream>
using namespace std;

int main(){
    int L, R;
    int a, b, c;

    cin >> L >> R;
    for (a = 1; a <= R/2; a++){
        for (b = a; b <= R/2; b++){
            for (c = b; c <= R/2; c++){
                if (a+b+c >= L && a+b+c <=R){
                    if ((a*a + b*b) == c*c || (b*b + c*c) == a*a || (c*c + a*a) == b*b){
                        cout << a << ' ' << b << ' ' << c << endl;
                    }
                }
            }
        }
    }
}
分享本文 Share with friends