標(biāo)題: 螺旋隊(duì)列算法分析 [打印本頁]
作者: bibi 時(shí)間: 2015-4-18 20:18
標(biāo)題: 螺旋隊(duì)列算法分析
問題描述：
設(shè)1的坐標(biāo)是（0，0），x方向向右為正，y方向向下為正，例如，7的坐標(biāo)為（-1，-1），2的坐標(biāo)為（1，0）。編程實(shí)現(xiàn)輸入任意一點(diǎn)坐標(biāo)（x，y），輸出所對(duì)應(yīng)的數(shù)字！
問題解決：
規(guī)律能看出來，問題就在于如何利用它。很明顯這個(gè)隊(duì)列是順時(shí)針螺旋向外擴(kuò)展的，我們可以把它看成一層一層往外延伸。第 0 層規(guī)定為中間的那個(gè) 1，第 1 層為 2 到 9，第 2 層為 10 到 25，注意到 1、9、25、……不就是平方數(shù)嗎？而且是連續(xù)奇數(shù)（1、3、5、……）的平方數(shù)。這些數(shù)還跟層數(shù)相關(guān)，推算一下就可以知道第 t 層之內(nèi)一共有 (2t-1)^2 個(gè)數(shù)，因而第 t 層會(huì)從 [(2t-1)^2] + 1 開始繼續(xù)往外螺旋。給定坐標(biāo) (x,y)，如何知道該點(diǎn)處于第幾層？層數(shù) t = max(|x|,|y|)。
知道了層數(shù)，接下來就好辦多了，這時(shí)我們就知道所求的那點(diǎn)一定在第 t 層這個(gè)圈上，順著往下數(shù)就是了。要注意的就是螺旋隊(duì)列數(shù)值增長(zhǎng)方向和坐標(biāo)軸正方向并不一定相同。我們可以分成四種情況——上、下、左、右——或者——東、南、西、北，分別處于四條邊上來分析。
東|右：x == t，隊(duì)列增長(zhǎng)方向和 y 軸一致，正東方向（y = 0）數(shù)值為 (2t-1)^2 + t，所以 v = (2t-1)^2 + t + y
南|下：y == t，隊(duì)列增長(zhǎng)方向和 x 軸相反，正南方向（x ＝ 0）數(shù)值為 (2t-1)^2 + 3t，所以 v ＝ (2t-1)^2 + 3t - x
西|左：x == -t，隊(duì)列增長(zhǎng)方向和 y 軸相反，正西方向（y ＝ 0）數(shù)值為 (2t-1)^2 + 5t，所以 v = (2t-1)^2 + 5t - y
北|上：y == -t，隊(duì)列增長(zhǎng)方向和 x 軸一致，正北方向（x ＝ 0）數(shù)值為 (2t-1)^2 + 7t，所以 v ＝ (2t-1)^2 + 7t + x
其實(shí)還有一點(diǎn)很重要，不然會(huì)有問題。其它三條邊都還好，但是在東邊（右邊）那條線上，隊(duì)列增加不完全符合公式！注意到東北角（右上角）是本層的最后一個(gè)數(shù)，再往下卻是本層的第一個(gè)數(shù)，那當(dāng)然不滿足東線公式啊。所以我們把東線的判斷放在最后（其實(shí)只需要放在北線之后就可以），這樣一來，東北角那點(diǎn)始終會(huì)被認(rèn)為是北線上的點(diǎn)。
下面給出第 t 層的圖示說明：
//螺旋隊(duì)列問題
#include <iostream>
using namespace std;
#define max(a,b) ((a)>(b) ? (a) : (b))
#define abs(a) ((a)>0 ? (a) : -(a))
#define square(a) ((a)*(a))
//輸入坐標(biāo)，輸出對(duì)應(yīng)的數(shù)字
int Spiral_Queue(int x, int y){
int val; //該坐標(biāo)對(duì)應(yīng)的數(shù)值
int t = max(abs(x),abs(y)); //該坐標(biāo)所在的層數(shù)
if(y == -t) //北邊（北邊的判斷分支要先于東邊，這是為了東北角最大值考慮的）
val = square(2*t-1)+7*t+x;
else if(y == t) //南邊
val = square(2*t-1)+3*t-x;
else if(x == -t) //西邊
val = square(2*t-1)+5*t-y;
else if(x == t) //東邊
val = square(2*t-1)+t+y;
return val;
}
| 歡迎光臨 (http://www.raoushi.com/bbs/) |
Powered by Discuz! X3.1 |