d762 - 10344 - 23 out of 5
題目描述
題目要求判斷給定的五個整數，透過插入 +, -, * 運算子，是否能得到結果為 23 的運算式。數字的排列順序可以任意更換。
解題思路
此題採用暴力解法。首先，生成五個數字的所有排列組合。對於每個排列，使用遞迴方式嘗試所有可能的運算子組合（+, -, *）。遞迴的過程中，逐步計算運算式的值，如果找到一個結果等於 23 的運算式，則輸出 "Possible"，並停止搜尋。如果遍歷完所有排列和運算子組合後，仍然找不到結果等於 23 的運算式，則輸出 "Impossible"。
複雜度分析
- 時間複雜度: O(5! * 3^4) = O(120 * 81) = O(9720)。 5! 是排列的數量，3^4 是四個運算子的組合數量。
- 空間複雜度: O(5)。主要用於儲存五個數字的陣列和遞迴的呼叫堆疊。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int a[5],ans;
void dfs(int it,int sum){
if(it==4||ans){
if(sum==23)ans=1;
return;
}
++it;
dfs(it,a[it]+sum);
dfs(it,sum-a[it]);
dfs(it,a[it]*sum);
}
int main(){
while(cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4]){
if(!a[0]&&!a[1]&&!a[2]&&!a[3]&&!a[4])break;
ans=0;
sort(a,a+5);
do{
dfs(0,a[0]);
if(ans)break;
}while(next_permutation(a,a+5));
if(ans)
cout << "Possible\n";
else
cout << "Impossible\n";
}
}