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

Re: [問題] 從二進位判斷數字是否被5整除

看板Prob_Solve (計算數學 Problem Solving)作者yauhh (舉杯邀鼠長共飲長江奶)時間16年前 (2008/10/03 22:10)推噓2(2推 0噓 6→)

留言8則, 3人參與討論串2/6 (看更多)

※ 引述《neverfly (neverfly)》之銘言： : 我想要建一個automata，可以輸入二進位的值， : 如果該值能被5整除就接受。 : 但是我想了很久，實在想不出來二進位下，能被5整除的數有什麼特性。 : 列了前幾個出來 : 101 1010 1111 10100 11001 11110 100011 101000 : 101101 110010 110111 111100 1000001 1000110 1001011 1010000 : 1010101 1011010 1011111 1100100 …… : 只發現了有每八個，末三碼會重覆這個特性， : 不過似乎還是不能直接檢查出來一串二進位的值是否被5整除。 : 請問有人能解決這個問題嗎？我的想法: 由高位往低位方向讀資料,例如 11001 = 25, 讀 1 -> 1 -> 0 -> 0 -> 1 順序. 狀態分為接受與不接受, 此外,狀態附帶一個 n 值代表根據已經讀入的部份二進位數值決定的十進位數值, 例如, 對 11001 已讀入 110 時, 狀態的 n 值是 6. 輸入的意義是,遇到 0, 代表 n*2; 遇到 1, 代表 n*2+1 Transition 有三個項目要關心: 1) 讀入的二進位數字, 2) 狀態 n 的求值, 3) 結果接受或不接受, 以下用 (t1, t2, t3) 表達三個項目. Automata為: (1, n, F) [unacceptable] <------(1)-------- S:[accepted] |^ |^ | | ^ ^ |^ || || +-----------(0)-------------+ | || || || | (0, n*2, (n*2)%5 = 0) | || Ｕ || +-------------(1)-----------+ || (0, n*2, (n*2)%5 /= 0) (1, n*2+1, (n*2+1)%5 = 0) || || ＵＵ (1, n*2+1, (n*2+1)%5 /= 0) (0, n, T) S是起動狀態, 起動時 n = 0. 這個automata有下列特性: 1. 0 整除 5. 2. 任一unacceptable狀態遇到下一個 0 一定是unacceptable. (不確定) 也就是,任一unacceptable狀態只有遇到下一個 1 才可能accepted. 3. 任一accepted狀態遇到下一個 0 一定是accepted. 4. 任一accepted狀態遇到下一個 1 一定是unacceptable. (以上特性是畫出具體的 0,1,2,...,25 狀態機而觀察到的) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.160.111.154 ※ 編輯: yauhh 來自: 218.160.111.154 (10/03 22:18)