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

看板Hunter作者chz (稻草人騎士)時間13年前 (2013/03/27 01:32)推噓4(4推 0噓 6→)

留言10則, 5人參與討論串3/4 (看更多)

幫忙把這個問題一般化：觀察可以發現這個方陣在 2^k by 2^k的大小時對所有元素 mod 4^(k-1)，可以把方陣分成四個一樣的部分 (左上，右上，左下，右下) 比如說 00 01 02 03 長度是 2^1=2, mod 4^(1-1)=1後變成 00 00 00 00 00 01 04 05 02 03 06 07 08 09 12 13 10 11 14 15 長度是2^2=4, mod 4^(2-1)=4後變成 00 01 00 01 02 03 02 03 00 01 00 01 02 03 02 03 也就是說，mod 4^(k-1)的值往右往下皆是 2^(k-1)一循環定義左上角是(0,0)，往右是加上(1,0)，往下是加上(0,1) 每一個座標其實是一個特殊的二進位其中x座標和y座標分別是二進位中的奇數位和偶數位舉例來說 14_10 = 1110_2 = 8+4+2 奇數位是 10_2 = 2_10 偶數位是 11_2 = 3_10 所以14的座標就是(2,3) 同樣的給定座標也可以轉回數字 (3,5) 是 (011_2,101_2)　所以值是 100111_2=39_10 如此一來，只要這個矩陣的值的規則不變對於任意的座標(x,y)都可以轉換成值，值也可以轉換回座標。 ※ 引述《vic0701 (維險人物)》之銘言： : 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: 114.36.89.131

推

vic0701

03/27 08:25, , 1^F

03/27 08:25, 1^F

→

chz

03/27 13:01, , 2^F

03/27 13:01, 2^F

→

chz

03/27 13:02, , 3^F

03/27 13:02, 3^F