PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] reduce, 字串, hash

看板Prob_Solve (計算數學 Problem Solving)作者yauhh (喲)時間12年前 (2012/09/15 01:49)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/1

※ 引述《wsx02 ()》之銘言： : 2. 字串 http://ppt.cc/GL16 : 請問有人知道這個問題應該解嗎? Q: Given a string S, and we determine if the string S satisfies the following conditions a. S contains repeated characters such as xxxyy form (x and y are characters) ... 就是用狀態機解決. "xxxyy" 生成狀態有六種: S0: "" S1: "x" S2: "xx" S3: "xxx" S4: "xxxy" S5: "xxxyy" 由 S1, S2 依順序到 S5, 每個狀態都是前一個狀態尾端加一個文字. 參與這個狀態機的資料分為三類: 'x', 'y', 最後 / 代表非 'x' 也非 'y'的其他文字. 我說 Sn 狀態遇到某個文字 m, 要跑到 Sn+ 狀態, 是以下列式子表達: Sn(m) = Sn+ 這樣的式子叫做狀態轉換. 一個狀態轉換會代表一種情況 c, 把情況 c 加進以上式子,寫成 (Sn(m) = Sn+): c 叫做從 Sn 狀態遇到某個文字 m, 結果跑到 Sn+ 狀態, 並且拋回一個 c 代表是否完成. 然後,我會列出以下的狀態轉換來用. (S0('x') = S1): false (S0('y'), S0(/) = S0): false (S1('x') = S2): false (S1('y'), S1(/) = S0): false (S2('x') = S3): false (S2('y'), S2(/) = S0): false (S3('x') = S3): false (S3('y') = S4): false (S3(/) = S0): false (S4('x'), S4(/) = S0): false (S4('y') = S0): true (S5('x') = S1): false (S5('y'), S5(/) = S0): false 實作上我會用一個常值字串 "xxxyy", 用一個整數 len 描述六種狀態的文字長度. 用類似 C 語言的寫法: char[] state_str = "xxxyy" enum state { S0, S1, S2, S3, S4, S5 }; enum state len = S0; bool transit(char m) { bool result = false; switch (len) { case S0: if (m = 'x') len = S1; else len = S0; break; case S1: if (m = 'x') len = S2; else len = S0; break; case S2: if (m = 'x') len = S3; else len = S0; break; case S3: if (m = 'x') len = S3; else if (m = 'y') len = S4; else len = S0; break; case S4: len = S0; if (m = 'y') result = true; break; case S5: if (m = 'x') len = S1; else len = S0; break; } return result; } 所以判斷式可以這樣寫: bool contain(char[] S, char[] xxxyy = "xxxyy") { int i; bool result; xxxyy = "xxxyy"; len = S0; for (i=0; i< strlen(S); i++) { result = transit(S[i]); if (result == true) break; } return result; } 當然,這樣只回答 "xxxyy" 格式並不夠. 題目中講的格式是 "such as xxxyy form," 答題最好是再上一層,可以隨著格式不同,程式自己定義狀態轉換規則. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 36.226.98.45