d618 - 有限狀態自動機（Finite State Machine）
題目描述
題目描述了一個有限狀態自動機，初始狀態為 1。給定一個由數字 1 到 7 組成的字符串，表示狀態轉移序列。根據題目中定義的狀態轉移規則，模擬狀態的變化，並輸出最終到達的狀態。如果某個轉移無效，則忽略該轉移，保持當前狀態不變。
解題思路
這道題的核心是模擬有限狀態自動機的狀態轉移過程。程式碼使用一個整數變數 ans 來表示當前狀態，初始值為 1。然後，遍歷輸入字符串 a 中的每個字符，根據字符的值和當前狀態 ans，更新 ans 的值。如果轉移無效，則保持 ans 不變。最終，輸出 ans 的值，即最終狀態。程式碼直接根據題目描述的狀態轉移規則進行模擬，使用一系列的 if-else if 語句來判斷狀態轉移是否有效。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入字符串的長度。因為程式碼需要遍歷字符串中的每個字符。
- 空間複雜度: O(1)，因為程式碼只使用了幾個整數變數來存儲狀態和長度，空間使用不隨輸入大小變化。
程式碼
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
string a;
while(n--){
cin >> a;
int al=a.length(),ans=1;
for(int i=0;i<al;++i){
if(a[i]=='1')
ans=1;
else if(a[i]=='2')
if(ans==1||ans==5||ans==6||ans==7)
ans=2;
else if(a[i]=='3')
if(ans==1||ans==5||ans==6||ans==7||ans==4)
ans=3;
else if(a[i]=='4')
if(ans==1||ans==5||ans==6||ans==7||ans==3)
ans=4;
else if(a[i]=='5')
if(ans==1||ans==5||ans==6||ans==7)
ans=5;
else if(a[i]=='6')
if(ans==1||ans==5||ans==6||ans==7)
ans=6;
else
if(ans==1||ans==5||ans==6||ans==7)
ans=7;
}
cout << ans << "\n";
}
}