d618: 有限狀態自動機(Finite State Machine)
Tags :
Accepted rate : 195人/210人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-06-27 15:51

Content

有限狀態自動機(Finite State Machine)是由有限個狀態以及在這些狀態之間的轉移和動作等行為所組成的數學模型。

有限狀態自動機可以使用狀態轉移圖(State Transition Diagram)來表示,例如下面的狀態轉移圖,表示的是一個可以用來判斷二進位數是否具有偶數個 0 的有限狀態自動機。「沒有起點的箭頭」指向狀態 S1,表示狀態 S1 是開始狀態(Start State);狀態 S1 為雙重圓圈,表示狀態 S1 是接受狀態(Accept State)。

 

輸入二進位數,例如 10101,一開始的狀態是狀態 S1;讀到第一個 1 的時候,依然停留在狀態 S1;讀到第一個 0 的時候,移動到狀態 S2;讀到第二個 1 的時候,依然停留在狀態 S2;讀到第二個 0 的時候,移動到狀態 S1;讀到第三個 1 的時候,依然停留在狀態 S1;因為狀態 S1 是接受狀態,表示輸入的二進位數 10101 具有偶數個 0。

如果輸入的二進位數是 10010,最後會停留在狀態 S2。因為狀態 S2 不是接受狀態,所以我們可以知道二進位數 10010 不具有偶數個 0。

有限狀態自動機也可以使用狀態轉移表(State Transition Table)來表示,例如上面(上一頁)的狀態轉移圖可以表示為:

 


現在假設葆葆班長定義了以下狀態

  1. 立正 ( 起立 )
  2. 稍息
  3. 蹲下
  4. 坐下
  5. 向右轉
  6. 向左轉
  7. 向後轉

 另外

  • 狀態 2 時只能改變狀態為 1
  • 狀態 3, 4 時只可以互換或改變為狀態 1
  • 狀態 1, 5, 6, 7 時可以改變為任意狀態
Input

第一行為一整數 T ( T ≤ 20 )

代表下面有 T 組測試資料

每組測試資料一行字串 ( 由 1 ~ 7 組成,字元長度不超過 100 )

由左至右代表一連串的狀態轉移要求,請忽略無法進行轉移的部分 ( 假設起始狀態為 1 )

註:測試資料中的字串並不包含起始狀態。

(edited by magrady 2012/6/27) 

Output
輸出最後的狀態 ( 一個數字 )
Sample Input
3
1234
162146
121212121
Sample Output
2
4
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
 ¤ 相關題目內容取自 2009 NPSC 國中組決賽
Tags:
出處:
葆葆 [管理者:
maxyuan (葆葆老師)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」