作者yauhh (喲)
看板Prob_Solve
標題Re: [問題] reduce, 字串, hash
時間Sat Sep 15 01:48:58 2012
※ 引述《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
1F：推 wsx02:謝謝 09/16 22:56