Re: [中譯] ProjectEuler 361 Subsequence of Thue-M

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (-858993460)時間14年前 (2011/12/10 04:00)推噓1(1推 0噓 0→)

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

寫一下我解這題的心路歷程好了 XD 引文後有雷 ※ 引述《babufong (嗶嗶)》之銘言： : 361. Subsequence of Thue - Morse sequence : http://projecteuler.net/problem=361 : Thue - Morse sequence {Tn} 是一個二進位制的數列，他符合以下條件： : T0 = 0 : T2n = Tn : T2n+1 = 1 - Tn : 我們可以知道 {Tn} 的前幾項是這樣的： : 01101001100101101001011001101001.... : 定義 {An} 是一個整數數列，而他的每一項用二進位制表示都有出現在 {Tn} 之中 : 舉例來說，十進位制的 18 用二進位制表示就是 10010 : 10010 出現在 T8 到 T12 之間，所以 18 是 {An} 的其中一項 : 14 用二進位制表示為 1110，而 1110 從未出現在 {Tn} 中，故 14 不是 {An} 其中一項 : An 的前幾項我們也知道了，如下： : n 0 1 2 3 4 5 6 7 8 9 10 11 12 ... : An 0 1 2 3 4 5 6 9 10 11 12 13 18 ... : 我們還能證明出 A100 = 3251 而 A1000 = 80852364498 : 18 : 請計算出 Σ A10^k 的末九位 : k=1 一開始我是用了另一個等價的 T_n 的定義在做: 從"0"開始把目前有的字串 0 1 反轉之後接到後面無限接下去就是 T_n 於是在想到底什麼型式是不會出現的很容易找到了 111 000 11011 00100 但發現 1101011 0010100 這種也要時我果斷放棄後來回到原來的定義才發現原來直接用"延伸"的方式去找就好例如 10010 這一串表示前面必然有個地方有 10010 => 100 這個字串在用類似的道理就可以知道所有夠長的字串都能夠由某個較短的字串做以下四個動作之一得到: (1) 做 1 -> 10, 0 -> 01 (2) 做 1 -> 10, 0 -> 01 但去尾 (3) 做 1 -> 01, 0 -> 10 但截頭 (4) 做 1 -> 01, 0 -> 10 但截頭去尾例如 100 做 (1) 得到 100101 做 (2) 得到 10010 做 (3) 得到 11010 做 (4) 得到 1101 仔細比較得到的這四個數會發現永遠有 (4) < (2) < (3) < (1) < 長一點字串的 (4) 因此我們會得到結論長度 4 的字串前半段是長度 2 做 (1) 後半段是長度 3 做 (4) 長度 5 的字串前半段是長度 3 做 (2) 後半段是長度 3 做 (3) 長度 6 的字串前半段是長度 3 做 (1) 後半段是長度 4 做 (4) 依此類推這樣一來長度 n 的字串的個數 S(n) 就是如下的數列 1 2 3 5 6 8 10 11 12 14 16 18 20 21 22 23 24 ... (這就是我在前篇推文提到的數列) 它的遞迴關係是 S(2n) = S(n)+S(n+1) n≧2 S(2n+1) = 2S(n+1) n≧2 S(1) = 1, S(2) = 2, S(3) = 3 那麼根據上面得到的這個規則 A_n 就只要去求 S(n) 的前幾項和到正好超過再去計算它是那個長度的哪個位置是前半還是後半是由長度多少字串的第幾個延伸來的就可以知道它是什麼字串結果 A_{10^15} 因為用 Mathematica 直接生字串生到記憶體炸掉了...XD 這中間為了節省時間我做了非常多數學計算甚至把上面這數列的前 N 項和寫了一個公式出來 (由於這數列等於 1.5n-1.5 加上一個很有規律升降的數列前 N 項和可以由 Σ(1.5n-1.5) 再去調整這樣就有公式了) 但無論如何總是快不起來就算記憶體不炸掉要算出 A_{10^18} 也要半小時回頭看到題目發現範例特別把 18 (10010) 出現在 T_8 ~ T_12 給說出來這才打醒我不必要去記整個字串去記它在字串的哪裡就好了... 而根據給定的 T_n 的定義這個延伸的動作就變得像是乘以 2 一樣簡單不過要從在哪裡的字串去求出那一位是什麼也讓我想了一會兒然後我才想起一件很重要的事: T_n 其實還有另一個等價定義 T_n = {1, 若 n 的二進位表示法中 1 的個數為奇數 {0, 若 n 的二進位表示法中 1 的個數為偶數也就是俗稱(?)的 Parity 利用這一點給定範圍之後我能夠一位一位算過去求餘數發現這一點之後我改用 C 寫求 Parity 的部份我特別寫了一支小小的組合語言副程式嵌進去利用了組合語言裡會根據結果的 Parity 設定旗標的功能直接讀出我要的 Parity (這個副程式組譯之後只有 20 byte 算是滿自豪的 XD 所以就直接寫成字串後當成函式來呼叫了) 不過跑出來的結果還是不對 (這個時候 A_{10^18} 只要約一分鐘就能有結果) 一直到 utomaya 的推文 (A_{10^18} 約是 11 億位二進位) 之後我回頭檢查算式才發現原來是計算上面那數列的前 N 項和的公式的中間結果溢位了... 把這個溢位改掉之後才終於得到正確答案 orz 總計從我開始解這題的星期日開始邊忙要交的作業邊解然後還跨過了這週四某科的期中考一直到現在下一題快出來了才把這題幹掉...orz -- 來去把 360 也幹掉拿最新五題的成就 @_@ -- LPH [acronym] = Let Program Heal us -- New Uncyclopedian Dictionary, Minmei Publishing Co. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.91