d913 - 1. 彈珠配置
題目描述
題目要求找出一個 1 到 6 的排列，使得這個排列滿足給定的六個猜測結果。每個猜測結果包含一個排列和該排列中數字正確放置的數量。
解題思路
這題採用暴力解法。由於彈珠只有 6 個，所以所有可能的排列數量只有 6! = 720 種。程式碼使用 next_permutation 函數產生所有可能的排列，然後對於每個排列，檢查它是否符合所有六個猜測結果。如果一個排列符合所有猜測結果，則輸出該排列並結束程式。
複雜度分析
- 時間複雜度: O(6! * 6) = O(4320)。因為需要產生所有 6! 個排列，並且對於每個排列，需要檢查 6 個猜測結果。
- 空間複雜度: O(6)。主要用於儲存
ans和chat陣列。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int ans[6]={1,2,3,4,5,6},chat[6][7];
int main(){
for(int i=0;i<6;++i){
for(int j=0;j<7;++j){
cin >> chat[i][j];
}
}
do{
bool c=1;
for(int i=0;i<6&&c;++i){
int tmp=0;
for(int j=0;j<6&&c;++j){
if(ans[j]==chat[i][j]){
++tmp;
}
}
if(tmp!=chat[i][6]){
c=0;
}
}
if(c){
for(int i=0;i<6;++i){
cout << ans[i] << " ";
}
cout << "\n";
break;
}
}while(next_permutation(ans,ans+6));
}