a291 - nAnB problem
題目描述
題目描述了一個猜數字遊戲，目標是判斷使用者猜測的四位數字密碼與正確密碼相符的數字個數。輸出格式為 pAqB，其中 p 代表位置和數值都正確的數字個數，q 代表數值正確但位置錯誤的數字個數。
解題思路
此題採用模擬的方式，逐一比較猜測的密碼與正確密碼。首先，計算位置和數值都正確的數字個數 (A)。然後，計算數值正確但位置錯誤的數字個數 (B)。為了避免重複計算，在計算 B 時，需要將已經匹配的數字標記為已使用。程式碼直接模擬了這個過程，對於每一位數字進行比較，並更新 A 和 B 的值。
複雜度分析
- 時間複雜度: O(n) 其中 n 是輸入的密碼嘗試次數。對於每次嘗試，程式碼需要遍歷四個數字進行比較，因此每次嘗試的時間複雜度是 O(1)。
- 空間複雜度: O(1) 程式碼使用固定大小的陣列來儲存密碼，空間複雜度是常數級別。
程式碼
#include <iostream>
using namespace std;
int main(){
int a[4],b[4],c[4],n,A=0,B=0;
while(scanf("%d %d %d %d",&c[0],&c[1],&c[2],&c[3])>0){
scanf("%d",&n);
for(;n>0;n--){
a[0]=c[0];
a[1]=c[1];
a[2]=c[2];
a[3]=c[3];
scanf("%d",&b[0]);
if(b[0]==a[0]){
a[0]=-1;b[0]=-1;A++;
}
scanf("%d",&b[1]);
if(b[1]==a[1]){
a[1]=-1;b[1]=-1;A++;
}
scanf("%d",&b[2]);
if(b[2]==a[2]){
a[2]=-1;b[2]=-1;A++;
}
scanf("%d",&b[3]);
if(b[3]==a[3]){
a[3]=-1;b[3]=-1;A++;
}
if(A<4){
if(b[0]!=-1){
if(b[0]==a[1]){
b[0]=-1;a[1]=-1;B++;
}
else if(b[0]==a[2]){
b[0]=-1;a[2]=-1;B++;
}
else if(b[0]==a[3]){
b[0]=-1;a[3]=-1;B++;
}
}
if(b[1]!=-1){
if(b[1]==a[0]){
b[1]=-1;a[0]=-1;B++;
}
else if(b[1]==a[2]){
b[1]=-1;a[2]=-1;B++;
}
else if(b[1]==a[3]){
b[1]=-1;a[3]=-1;B++;
}
}
if(b[2]!=-1){
if(b[2]==a[1]){
b[2]=-1;a[1]=-1;B++;
}
else if(b[2]==a[0]){
b[2]=-1;a[0]=-1;B++;
}
else if(b[2]==a[3]){
b[2]=-1;a[3]=-1;B++;
}
}
if(b[3]!=-1){
if(b[3]==a[1]){
b[3]=-1;a[1]=-1;B++;
}
else if(b[3]==a[0]){
b[3]=-1;a[0]=-1;B++;
}
else if(b[3]==a[2]){
b[3]=-1;a[2]=-1;B++;
}
}
}
printf("%dA%dB\n",A,B);
A=0;B=0;
}
}
}