Re: [非關] 有請演算法獵人

看板Hunter作者vic0701 (維險人物)時間13年前 (2013/03/26 14:25)推噓15(15推 0噓 1→)

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

8x8找4x4不太需要演算法，換個題目好了，比較通用一些。題目：已知 8x8 數列建置方法，就跟題目一樣。給你一個值 n ，請你求以 n 為首的 a x b 的長方形。如 n = 14 , a = 2 , b = 4 output => 14 15 36 37 38 39 44 45 我先給大略解法好了，有興趣的再討論。先對 n 做分解， if n = 14 = 4^2 * 0 + 4^1 * 3 + 4^0 * 2 可以表示為 < 0,3,2 > 則以他為首的 2 x 4 的矩形為 <0,3,2> <0,3,3> <2,1,0> <2,1,1> <2,1,2> <2,1,3> <2,3,0> <2,3,1> 自己帶回去 4^2 * a + 4^1 * b + 4^0 * c，應該會跟答案一樣。演算法： 1.對n做 4 進位表示式, <Zn,Zn-1,.., Z1,Z0>。 2.for i = 1 to a { //迴圈填入要求的方塊值 3. for j = 1 to b { 4. if( i == 1 && j == 1 ) A[i,j] = <Zn, Zn-1,...,Z0>; //最左上角 5. otherwise{ 6. if( j == 0 ) { //開始填入矩形最上面的值： A[i,j] = MOV_RIGHT( A[i-1,j] ) } 7. if( i == 0 ) { //填入矩形最左邊的值: A[i,j] = MOV_DOWN( A[i,j-1] ) } 8. otherwise{ A[i,j] = A[i-1,j] + A[i,j-1] - A[i-1,j-1] } 9. } 10.DEF MOV_RIGHT( <An, An-1,...,A0> ){ 11. Carry = 1 12. for( i = 0 ; i < n && Carry == 1 ; i++ ){ 13. if Ai == 0 , Ai = 1 ,and Carry = 0 14. if Ai == 1 , Ai = 0 ,and Carry = 1 15. if Ai == 2 , Ai = 3 ,and Carry = 0 16. if Ai == 3 , Ai = 2 ,and Carry = 1 17. } return <An, An-1, ....,A0> } 18.DEF MOV_DOWN( <An, An-1,...,A0> ){ 19. Carry = 1 20. for( i = 0 ; i < n && Carry == 1 ; i++ ){ 21. if Ai == 0 , Ai = 2 ,and Carry = 0 22. if Ai == 1 , Ai = 3 ,and Carry = 0 23. if Ai == 2 , Ai = 0 ,and Carry = 1 24. if Ai == 3 , Ai = 1 ,and Carry = 1 25. } return <An, An-1, ....,A0> } 以上，應該就可以正確的把座標值給算出來了，有了座標值，在轉換成十進位。核心是把這個矩陣當作一個地圖座標，有 0,1,2,3 項次。所以對 00 01 來說，就是 <0> <1> 02 03 <2> <3> 對 00 01 04 05 => <0,0> <0,1> <1,0> <1,1> 依此類推 02 03 06 07 <0,2> <0,3> <1,2> <1,3> 08 09 12 13 <2,0> <2,1> <3,0> <3,1> 10 11 14 15 <2,2> <2,3> <3,2> <3,3> 作標可表示為，如<3,1>來說，就是第三象限中的第一象限。所以我們可以用這個座標系統很快的找到所有數字。但是在這個座標軸移動，已經不像x,y座標軸一樣，x+1 或是 y+1 那麼簡單。我們要按照座標軸的象限來跑，也就是0的右邊是1, 1的右邊是 0的概念。但是看到 1,3 的右邊，已經是其他象限的區域了，所以我們有了借位的概念。這也是這個座標軸在計算位置的精隨，借位真正的意思是，往上一層的象限做移動。舉例 <2,1> 的右邊，先計算 1的右邊是 0，這裡發生一個借位，也就是他的右邊其實已經跨了一個比較大的象限了，所以 <2,1>的2 需要往右移動到 3的象限象限的橫跨可能發生不只一次，可以考慮原問題中的 15 26 37 48 這四個特殊點，就知道有些情況借位需要有兩次(跨兩次區域)。舉例來說 <0,3,3> 的右邊就是 <1,2,2>，跨了一個 2x2 的象限的跟 4x4 的象限。反正這個個問題研究所不會考，大家隨便看看就好了 :D。清明愉快不要插我IP >.^ ※ 引述《imitatefish (宅魚||雜魚)》之銘言： : 00 01 04 05 16 17 20 21 : 02 03 06 07 18 19 22 23 : 08 09 12 13 24 25 28 29 : 10 11 14 15 26 27 30 31 : 32 33 36 37 48 49 52 53 : 34 35 38 39 50 51 54 55 : 40 41 44 45 56 57 60 61 : 42 43 46 47 58 59 62 63 : 8x8的陣列內容是長這樣 : 我如果要任意框一個4x4出來 : 例如 : 03 06 07 18 : 09 12 13 24 : 11 14 15 26 : 33 36 37 48 : 知道03 要產生出一組pattern : 有沒有簡單的演算法可以找出來?? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.216.180