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

[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: 140.113.216.180
推 jackace:太漂亮了 要我就建表了
推 imitatefish:真漂亮的解法  113推一下XDDD
推 Keywayly:太強了 XD 113友情推
推 getting:快推，不然別人會說我看不懂
推 p52189:酷炫
推 iamnotgm:我看不懂 樓樓上解釋一下
推 vowpool:樓上可以用對n分解的方式 算出整個陣列數字 然後找出規律
推 ruemann:哦哦哦  跟我想的一樣                              (囧
推 rtoybox:略懂 略懂~
推 htaedamay:嗯嗯 原來如此
推 Bruce78522:就是這樣沒錯 我也是這麼解的
→ pinkygiveme:仔細想想，跟我的解法類似，只是換個說法，嗯嗯
推 ru04ul4:跟我想得差不多嘛
推 Comebuy:果然就是這樣                                有看沒有懂
推 XOEX:沒什麼  我兒子都這麼解的
推 Lucky0105:獵人版.... 哈哈哈 笑了