本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請(qǐng)注明出處。

TIS-NET 第 17 關(guān)《動(dòng)態(tài)模式檢測(cè)器》（Dynamic Pattern Detector）關(guān)卡展示

本關(guān)的 IN.P 會(huì)給你一個(gè)模式序列，以 0 結(jié)尾，不過測(cè)試發(fā)現(xiàn)長(zhǎng)度固定為 3。

然后 IN.S 會(huì)給你源源不斷地提供一些數(shù)字，僅當(dāng)包括當(dāng)前數(shù)字在內(nèi)的近 3 個(gè)數(shù)字和 IN.P 完全匹配時(shí)，向 OUT 輸出 1，否則向 OUT 輸出 0。

本關(guān)沒有棧，同時(shí)還需要用節(jié)點(diǎn)記住 p[-2]、p[-1]、p[0]、s[-2]、s[-1]、s[0] 這六個(gè)值，和上一關(guān)相比甚至還要多記一個(gè)值。有點(diǎn)累了，干脆換一種方法——把連續(xù)的三個(gè)值映射成一個(gè)特征值（hash），然后對(duì)特征值進(jìn)行判等。這樣子的做法，雖然有概率會(huì)出錯(cuò)，但是寫起來不費(fèi)勁，而且最終的運(yùn)行效率很高。

這里，我們使用公式 ，將 p[-2]、p[-1]、p[0] 映射成特征值 4p[-2] + 2p[-1] + p[0]，將?s[-2]、s[-1]、s[0]?映射成特征值 4s[-2] + 2s[-1] + s[0]，然后比較兩個(gè)特征值是否一致。原先需要比較三組數(shù)是否一致，現(xiàn)在就只需要比較一組數(shù)了。

以上算法有概率得出錯(cuò)誤的結(jié)論。隨便舉一個(gè)反例：假如 p 序列是 [1, 2, 3]，s 序列是 [1, 3, 1] 時(shí)，計(jì)算可得 p 序列的特征值是 4×1 + 2×2 + 3 = 11，s 序列的特征值是 4×1 + 2×3 + 1 = 11，兩者的特征值相等，但兩者很明顯不是同一個(gè)序列。

本關(guān)的代碼如下：

IN.P 下方的節(jié)點(diǎn)接收 p[-2]、p[-1]、p[0] 的值，然后計(jì)算該序列的 hash 值：

計(jì)算完成后，不斷向右邊提供該常數(shù)（mov acc right, jmp 6）。

該節(jié)點(diǎn)右邊的節(jié)點(diǎn)純粹充當(dāng)傳輸 hash(p) 的橋梁（mov left right）。

IN.S 下方的節(jié)點(diǎn)用來向下傳輸?s[-2]、s[-1]、s[0]?和 hash(p) 的值。這里用到了和上一關(guān)類似的滾動(dòng)存儲(chǔ)法來維護(hù)序列中最近 3 個(gè)數(shù)的值。只是由于本關(guān)只需要維護(hù)前兩個(gè)數(shù)，所以復(fù)雜度相比于上一關(guān)大幅減少：

具體到代碼上：

1. A 節(jié)點(diǎn)將 s[-1] 傳下去后（mov acc down），

2. 用 s[0] 覆蓋 s[-1]（mov up acc）

3. 并往下傳（mov acc down），

4. 最后傳 hash(p)（mov left down）。

然后：

1. B 節(jié)點(diǎn)向 C 節(jié)點(diǎn)傳完 s[-2] 后（mov acc down），

2. 將 A 節(jié)點(diǎn)發(fā)來的 s[-1] 覆蓋 s[-2]（mov up acc）

3. 并傳給 C（mov acc down），

4. 再接下來的?s[0]（mov up down）

5. 和 hash(p) 則直接傳給 C，不保存（mov up down）。
   

右下角的節(jié)點(diǎn)會(huì)依次收到 s[-2]、s[-1]、s[0] 和 hash(p)，首先根據(jù)前 3 個(gè)值計(jì)算 hash(s)：

計(jì)算完成后，和后面發(fā)來的 hash(p) 做差值運(yùn)算（sub up）。只要差值不為 0，就說明 hash(s) 和 hash(p) 不相等，跳到第 10 行向 OUT 發(fā)送 0（jnz a, mov 0 down）；差值為 0 時(shí)，說明 hash(s) 和 hash(p) 相等，向 OUT 發(fā)送 1（mov 1 down, jmp 1）。

點(diǎn)擊左下角的【RUN】，運(yùn)行程序。本算法是投機(jī)取巧的算法，前三個(gè)固定的測(cè)試樣例能通過，但是最后的隨機(jī)樣例會(huì)有概率不通過：

如上圖所示，序列 [39, 33, 37] 和序列 [37, 39, 33] 不一樣，但因?yàn)樘卣髦狄粯樱?×39?+ 2×33?+ 37?= 4×37 + 2×39 + 33 =?259，所以錯(cuò)誤地輸出了一個(gè) 1。遇到這樣的情況，請(qǐng)點(diǎn)擊左下角的【STOP】停止運(yùn)行，然后再點(diǎn)擊【RUN】重新運(yùn)行一遍。隨便試幾次就能過了。

當(dāng)然你也可以選擇更不容易碰撞的特征值公式，比如?，來提高程序的穩(wěn)定性。