算法問題 用SQL寫出當M*N時的螺旋矩陣算法
如下是一個4*4的矩陣:
1 12 11 10
2 13 16? 9
3 14 15? 8
4? 5? 6? 7
按照上面矩陣的規律, 請用SQL寫出當M*N時的矩陣算法
實現的sql和效果:
代碼:--------------------------------------------------------------------------------
SQL> -- 逆時針的
SQL> select --i,
? 2???????? sum(decode(j, 1, rn)) as co11,
? 3???????? sum(decode(j, 2, rn)) as co12,
? 4???????? sum(decode(j, 3, rn)) as co13,
? 5???????? sum(decode(j, 4, rn)) as co14
? 6??? from (select i, j, rank() over(order by tag) as rn
? 7??????????? from (select i,
? 8???????????????????????? j,
? 9???????????????????????? -- 逆時針螺旋特征碼 counter-clockwise
?10???????????????????????? case least(j - 1, 4 - i, 4 - j, i - 1)
?11?????????????????????????? when j - 1 then
?12??????????????????????????? (j - 1) || '1' || i
?13?????????????????????????? when 4-i then
?14??????????????????????????? (4 - i) || '2' || j
?15?????????????????????????? when 4 - j then
?16??????????????????????????? (4 - j) || '3' || (4 - i)
?17?????????????????????????? when i - 1 then
?18??????????????????????????? (i - 1) || '4' || (4 - j)
?19???????????????????????? end as tag
?20??????????????????? from (select level as i from dual connect by level <= 4) a,
?21???????????????????????? (select level as j from dual connect by level <= 4) b))
?22?? group by i
?23? /
????? CO11?????? CO12?????? CO13?????? CO14
---------- ---------- ---------- ----------
???????? 1???????? 12???????? 11???????? 10
???????? 2???????? 13???????? 16????????? 9
???????? 3???????? 14???????? 15????????? 8
???????? 4????????? 5????????? 6????????? 7
SQL> -- 順時針的
SQL> select --i,
? 2???????? sum(decode(j, 1, rn)) as co11,
? 3???????? sum(decode(j, 2, rn)) as co12,
? 4???????? sum(decode(j, 3, rn)) as co13,
? 5???????? sum(decode(j, 4, rn)) as co14
? 6??? from (select i, j, rank() over(order by tag) as rn
? 7??????????? from (select i,
? 8???????????????????????? j,
? 9???????????????????????? -- 順時針螺旋特征碼 clockwise
?10???????????????????????? case least(i - 1, 4 - j, 4 - i, j - 1)
?11?????????????????????????? when i - 1 then
?12??????????????????????????? (i - 1) || '1' || j
?13?????????????????????????? when 4 - j then
?14??????????????????????????? (4 - j) || '2' || i
?15?????????????????????????? when 4 - i then
?16??????????????????????????? (4 - i) || '3' || (4 - j)
?17?????????????????????????? when j - 1 then
?18??????????????????????????? (j - 1) || '4' || (4 - i)
?19???????????????????????? end as tag
?20??????????????????? from (select level as i from dual connect by level <= 4) a,
?21???????????????????????? (select level as j from dual connect by level <= 4) b))
?22?? group by i
?23? /
????? CO11?????? CO12?????? CO13?????? CO14
---------- ---------- ---------- ----------
???????? 1????????? 2????????? 3????????? 4
??????? 12???????? 13???????? 14????????? 5
??????? 11???????? 16???????? 15????????? 6
??????? 10????????? 9????????? 8????????? 7
----------------------------------------------------------------------------------------
以上兩種旋轉都是由外向內的, 如果有興趣也可以做成由內想外的
不過如果大家還要把結果90度旋轉, 在順序固定的情況下, 應該就是行列轉換的問題了
不過如果要做成圓形的, 我覺得不太可能了, 正n邊形倒是可以考慮, 不過要看n的值是多大, 如果趨于正無窮, 那就是圓了, ^_^
對了，jacky，能大概說一下這個螺旋特征碼的算法原理么？
--------------------------------------------------------------------------------
螺旋總要有個起點, 就用上面的那個結果來說明吧
起點是(1,1), 如果是順時針的話, 旋轉時依次走過的途徑是 上->右->下->左->上->右->下->左..., 知道最后在螺旋中心結束, 但是可以注意到旋轉是會越來越遠離外邊界
根據這個我們就可以獲取螺旋特征碼了
4*4的矩陣, 那么可以認為 i=1, j=1, i=4, j=4, 這就是這個螺旋的4個邊界, 順時針旋轉時, 離邊界越近, 那么順序就越靠前, 當距離邊界相同時, 邊界的優先級就要根據 上右下左(起點為1,1, 順時針旋轉的邊界優先級) 而定了, 如果這個也相同, 那么就要根據這個點離前一個邊界的距離而定, 離的越近, 優先級越高, 根據以上規則, 可以得出特征碼共有三位, 第一位代表距離邊界的距離, 第二位代表距離哪個邊界最近(我的sql中用1,2,3,4分別表示四個邊界), 第三位代表距離前一個邊界的距離(因為目的是為了排序, 計算時沒有嚴格按照這個距離值進行表示^_^)
對應上面螺旋特征碼的規則, 使用case least(...)判斷離邊界的距離和距離最近的邊界是那個邊界, when ... then后的取值再確定距離前一個邊界的距離, 這樣就完成了特征碼, 剩下的就是對特征碼排序和行列轉換了, 這個就不用說了吧, 大家應該都會了, ^_^
也來學一下JACKYWOOD兄, 寫一個SQL:
JACK的實現, 采用了行列轉換把生成的序列做成二維表, 所以要求列數是固定的, 若要實現N的矩陣的算法, 行列轉換正如其所言, 可以通過二個SQL實現.
現換一下思路, 用SYS_CONNECT_BY_PATH函數, 借用JACK的思路, 實現N的矩陣生成, 如下請各位指點:
代碼:--------------------------------------------------------------------------------
SQL> var n number;
SQL> exec :n := 3;
PL/SQL 過程已成功完成。
SQL> select replace(max(sys_connect_by_path(rank, ',')), ',') str
? 2???? from (select i, j,
? 3???????????????? to_char(rank() over(order by tag), '9999') as rank
? 4??????????? from (select i,
? 5???????????????????????? j,
? 6?????????????????? -- 逆時針螺旋特征碼 counter-clockwise
? 7???????????????????????? case least(j - 1, :n - i, :n - j, i - 1)
? 8???????????????????????? when j - 1 then
? 9??????????????????????????? (j - 1) || '1' || i
?10???????????????????????? when :n - i then
?11??????????????????????????? (:n - i) || '2' || j
?12???????????????????????? when :n - j then
?13??????????????????????????? (:n - j) || '3' || (:n - i)
?14???????????????????????? when i - 1 then
?15??????????????????????????? (i - 1) || '4' || (:n - j)
?16???????????????????????? end as tag
?17??????????????????? from (select level as i from dual connect by level <= :n) a,
?18???????????????????????? (select level as j from dual connect by level <= :n) b
?19???????????????? )
?20????????? )
?21???? start with j = 1
?22???? connect by j - 1 = prior j and i = prior i
?23???? group by i
?24???? order by i;
STR
-------------------------------------------------------------------------------------------------
??? 1??? 8??? 7
??? 2??? 9??? 6
??? 3??? 4??? 5
SQL> exec :n := 4;
PL/SQL 過程已成功完成。
SQL> /
STR
-------------------------------------------------------------------------------------------------
??? 1?? 12?? 11?? 10
??? 2?? 13?? 16??? 9
??? 3?? 14?? 15??? 8
??? 4??? 5??? 6??? 7
SQL> exec :n := 5;
PL/SQL 過程已成功完成。
SQL> /
STR
-------------------------------------------------------------------------------------------------
??? 1?? 16?? 15?? 14?? 13
??? 2?? 17?? 24?? 23?? 12
??? 3?? 18?? 25?? 22?? 11
??? 4?? 19?? 20?? 21?? 10
??? 5??? 6??? 7??? 8??? 9
SQL>
不妨也填足一下:
代碼:--------------------------------------------------------------------------------
SQL> exec :n := 5
PL/SQL 過程已成功完成。
SQL>? select replace(max(sys_connect_by_path(rank, ',')), ',') str
? 2????? from (select i, j,
? 3????????????????? case when rank() over(order by tag) - floor(:n * :n / 2) <= 0 then '???? '
? 4?????????????????????? else to_char(rank() over(order by tag) - floor(:n * :n / 2), '9999') end as rank,
? 5????????????????? min(j) over(partition by i) minj
? 6???????????? from (select i,
? 7????????????????????????? j,
? 8??????????????????? -- 順時針螺旋特征碼 counter-clockwise
? 9????????????????????????? case greatest(i - j, i + j - :n - 1, j - i, :n - i - j + 1)
?10????????????????????????? when i - j then
?11???????????????????????????? :n - (i - j) || '1' || i
?12????????????????????????? when i + j - :n - 1 then
?13???????????????????????????? :n - (i + j - :n - 1) || '2' || j
?14????????????????????????? when j - i then
?15???????????????????????????? :n - (j - i) || '3' || (:n - i)
?16????????????????????????? when :n - i - j + 1 then
?17???????????????????????????? :n - (:n - i - j + 1) || '4' || i
?18????????????????????????? end as tag
?19???????????????????? from (select level as i from dual connect by level <= :n) a,
?20????????????????????????? (select level as j from dual connect by level <= :n) b
?21?? --????????????????? where abs(i - j) < floor(:n / 2 + .6)
?22?? --??????????????????? and i + j between floor(:n / 2 + .6) + 1 and floor(:n / 2 + .6) + :n
?23???????????????? )
?24?????????? )
?25????? start with j = minj
?26????? connect by j - 1 = prior j and i = prior i
?27????? group by i
?28????? order by i;
STR
----------------------------------------------------------------------------------------------------------------------
????????????? 7
???????? 8?? 12??? 6
??? 1??? 9?? 13?? 11??? 5
???????? 2?? 10??? 4
????????????? 3
SQL> exec :n := 7;
PL/SQL 過程已成功完成。
SQL> /
STR
----------------------------------------------------------------------------------------------------------------------
????????????????? 10
???????????? 11?? 19??? 9
??????? 12?? 20?? 24?? 18??? 8
??? 1?? 13?? 21?? 25?? 23?? 17??? 7
???????? 2?? 14?? 22?? 16??? 6
????????????? 3?? 15??? 5
?????????????????? 4
已選擇7行。
SQL> exec :n := 9;
PL/SQL 過程已成功完成。
SQL> /
STR
----------------------------------------------------------------------------------------------------------------------
?????????????????????? 13
????????????????? 14?? 26?? 12
???????????? 15?? 27?? 35?? 25?? 11
??????? 16?? 28?? 36?? 40?? 34?? 24?? 10
??? 1?? 17?? 29?? 37?? 41?? 39?? 33?? 23??? 9
???????? 2?? 18?? 30?? 38?? 32?? 22??? 8
????????????? 3?? 19?? 31?? 21??? 7
?????????????????? 4?? 20??? 6
??????????????????????? 5
已選擇9行。
SQL> exec :n := 8
PL/SQL 過程已成功完成。
SQL> /
STR
----------------------------------------------------------------------------------------------------------------------
?????????????????? 5??? 4
????????????? 6?? 18?? 17??? 3
???????? 7?? 19?? 27?? 26?? 16??? 2
??? 8?? 20?? 28?? 32?? 31?? 25?? 15??? 1
???????? 9?? 21?? 29?? 30?? 24?? 14
???????????? 10?? 22?? 23?? 13
????????????????? 11?? 12
對于比較大的N值, 需對"順時針螺旋特征碼"的組成進行適當修改:
代碼:--------------------------------------------------------------------------------
1?? select replace(max(sys_connect_by_path(rank, ',')), ',') str
? 2????? from (select i, j,
? 3????????????????? case when rank() over(order by tag) - floor(:n * :n / 2) <= 0 then '???? '
? 4?????????????????????? else to_char(rank() over(order by tag) - floor(:n * :n / 2), '9999') end as rank,
? 5????????????????? min(j) over(partition by i) minj
? 6???????????? from (select i,
? 7????????????????????????? j,
? 8??????????????????? -- 逆時針螺旋特征碼 counter-clockwise
? 9????????????????????????? case greatest(i - j, i + j - :n - 1, j - i, :n - i - j + 1)
?10????????????????????????? when i - j then
?11???????????????????????????? chr(:n - (i - j)) || '1' || chr(i)
?12????????????????????????? when i + j - :n - 1 then
?13???????????????????????????? chr(:n - (i + j - :n - 1)) || '2' || chr(j)
?14????????????????????????? when j - i then
?15???????????????????????????? chr(:n - (j - i)) || '3' || chr((:n - i))
?16????????????????????????? when :n - i - j + 1 then
?17???????????????????????????? chr(:n - (:n - i - j + 1)) || '4' || chr(i)
?18????????????????????????? end as tag
?19???????????????????? from (select level as i from dual connect by level <= :n) a,
?20????????????????????????? (select level as j from dual connect by level <= :n) b
?21?? --????????????????? where abs(i - j) < floor(:n / 2 + .6)
?22?? --??????????????????? and i + j between floor(:n / 2 + .6) + 1 and floor(:n / 2 + .6) + :n
?23???????????????? )
?24?????????? )
?25????? start with j = minj
?26????? connect by j - 1 = prior j and i = prior i
?27????? group by i
?28*???? order by i
SQL> /
STR
-------------------------------------------------------------------------------------------------------------------
???????????????????????????????? 19
??????????????????????????? 20?? 40?? 18
?????????????????????? 21?? 41?? 57?? 39?? 17
????????????????? 22?? 42?? 58?? 70?? 56?? 38?? 16
???????????? 23?? 43?? 59?? 71?? 79?? 69?? 55?? 37?? 15
??????? 24?? 44?? 60?? 72?? 80?? 84?? 78?? 68?? 54?? 36?? 14
??? 1?? 25?? 45?? 61?? 73?? 81?? 85?? 83?? 77?? 67?? 53?? 35?? 13
???????? 2?? 26?? 46?? 62?? 74?? 82?? 76?? 66?? 52?? 34?? 12
????????????? 3?? 27?? 47?? 63?? 75?? 65?? 51?? 33?? 11
?????????????????? 4?? 28?? 48?? 64?? 50?? 32?? 10
??????????????????????? 5?? 29?? 49?? 31??? 9
???????????????????????????? 6?? 30??? 8
????????????????????????????????? 7
--------------------------------------------------------------------------------
想來是的, 這樣你看如何?
代碼:--------------------------------------------------------------------------------
1? select replace(max(sys_connect_by_path(rank, ',')), ',') str
? 2???? from (select i, j,
? 3???????????????? to_char(rank() over(order by tag), '9999') as rank
? 4??????????? from (select i,
? 5???????????????????????? j,
? 6?????????????????? -- 逆時針螺旋特征碼 counter-clockwise
? 7???????????????????????? case least(j - 1, &&1 - i, &1 - j, i - 1)
? 8???????????????????????? when j - 1 then
? 9??????????????????????????? (j - 1) || '1' || i
?10???????????????????????? when &1 - i then
?11??????????????????????????? (&1 - i) || '2' || j
?12???????????????????????? when &1 - j then
?13??????????????????????????? (&1 - j) || '3' || (&1 - i)
?14???????????????????????? when i - 1 then
?15??????????????????????????? (i - 1) || '4' || (&1 - j)
?16???????????????????????? end as tag
?17??????????????????? from (select level as i from dual connect by level <= &1) a,
?18???????????????????????? (select level as j from dual connect by level <= &1) b
?19???????????????? )
?20????????? )
?21???? start with j = 1
?22???? connect by j - 1 = prior j and i = prior i
?23???? group by i
?24*??? order by i
SQL> /
輸入 1 的值:? 5
原值??? 7:??????????????????????? case least(j - 1, &&1 - i, &1 - j, i - 1)
新值??? 7:??????????????????????? case least(j - 1, 5 - i, 5 - j, i - 1)
原值?? 10:??????????????????????? when &1 - i then
新值?? 10:??????????????????????? when 5 - i then
原值?? 11:?????????????????????????? (&1 - i) || '2' || j
新值?? 11:?????????????????????????? (5 - i) || '2' || j
原值?? 12:??????????????????????? when &1 - j then
新值?? 12:??????????????????????? when 5 - j then
原值?? 13:?????????????????????????? (&1 - j) || '3' || (&1 - i)
新值?? 13:?????????????????????????? (5 - j) || '3' || (5 - i)
原值?? 15:?????????????????????????? (i - 1) || '4' || (&1 - j)
新值?? 15:?????????????????????????? (i - 1) || '4' || (5 - j)
原值?? 17:?????????????????? from (select level as i from dual connect by level <= &1) a,
新值?? 17:?????????????????? from (select level as i from dual connect by level <= 5) a,
原值?? 18:??????????????????????? (select level as j from dual connect by level <= &1) b
新值?? 18:??????????????????????? (select level as j from dual connect by level <= 5) b
STR
--------------------------------------------------------------------------------------------
??? 1?? 16?? 15?? 14?? 13
??? 2?? 17?? 24?? 23?? 12
??? 3?? 18?? 25?? 22?? 11
??? 4?? 19?? 20?? 21?? 10
??? 5??? 6??? 7??? 8??? 9
SQL>--------------------------------------------------------------------------------
使用前, 給聲明m和n并賦值
代碼:--------------------------------------------------------------------------------
var n number;
var m number;
exec :n := &n; :m=&m;
with t as (
? select :n as n, :m as m from dual
)
select replace(max(sys_connect_by_path(rank, ',')), ',') str
? from (select i, j, to_char(rank() over(order by tag), '999999') as rank
????????? from (select i,
?????????????????????? j,
?????????????????????? -- 順時針螺旋特征碼 clockwise
?????????????????????? case least(i - 1, m - j, n - i, j - 1)
???????????????????????? when i - 1 then
????????????????????????? to_char(i - 1, 'fm0000') || '1' ||
????????????????????????? to_char(j - 1, 'fm0000')
???????????????????????? when m - j then
????????????????????????? to_char(m - j, 'fm0000') || '2' ||
????????????????????????? to_char(i - 1, 'fm0000')
???????????????????????? when n - i then
????????????????????????? to_char(n - i, 'fm0000') || '3' ||
????????????????????????? to_char(m - j, 'fm0000')
???????????????????????? when j - 1 then
????????????????????????? to_char(j - 1, 'fm0000') || '4' ||
????????????????????????? to_char(n - i, 'fm0000')
?????????????????????? end as tag
????????????????? from (select n, level as i from t connect by level <= n) a,
?????????????????????? (select m, level as j from t connect by level <= m) b))
?start with j = 1
connect by j - 1 = prior j and i = prior i
?group by i
-----------------------------------------------------------------------------------------------