- 又稱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;
}
}
}
}
}
}
Post Views (since April 2021) : 869