
問題描述:
設(shè)1的坐標(biāo)是(0,0),x方向向右為正,y方向向下為正,例如,7的坐標(biāo)為(-1,-1),2的坐標(biāo)為(1,0)。編程實現(xiàn)輸入任意一點坐標(biāo)(x,y),輸出所對應(yīng)的數(shù)字!
問題解決:
規(guī)律能看出來,問題就在于如何利用它。很明顯這個隊列是順時針螺旋向外擴(kuò)展的,我們可以把它看成一層一層往外延伸。第 0 層規(guī)定為中間的那個 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 個數(shù),因而第 t 層會從 [(2t-1)^2] + 1 開始繼續(xù)往外螺旋。給定坐標(biāo) (x,y),如何知道該點處于第幾層?層數(shù) t = max(|x|,|y|)。
知道了層數(shù),接下來就好辦多了,這時我們就知道所求的那點一定在第 t 層這個圈上,順著往下數(shù)就是了。要注意的就是螺旋隊列數(shù)值增長方向和坐標(biāo)軸正方向并不一定相同。我們可以分成四種情況——上、下、左、右——或者——東、南、西、北,分別處于四條邊上來分析。
東|右:x == t,隊列增長方向和 y 軸一致,正東方向(y = 0)數(shù)值為 (2t-1)^2 + t,所以 v = (2t-1)^2 + t + y
南|下:y == t,隊列增長方向和 x 軸相反,正南方向(x = 0)數(shù)值為 (2t-1)^2 + 3t,所以 v = (2t-1)^2 + 3t - x
西|左:x == -t,隊列增長方向和 y 軸相反,正西方向(y = 0)數(shù)值為 (2t-1)^2 + 5t,所以 v = (2t-1)^2 + 5t - y
北|上:y == -t,隊列增長方向和 x 軸一致,正北方向(x = 0)數(shù)值為 (2t-1)^2 + 7t,所以 v = (2t-1)^2 + 7t + x
其實還有一點很重要,不然會有問題。其它三條邊都還好,但是在東邊(右邊)那條線上,隊列增加不完全符合公式!注意到東北角(右上角)是本層的最后一個數(shù),再往下卻是本層的第一個數(shù),那當(dāng)然不滿足東線公式啊。所以我們把東線的判斷放在最后(其實只需要放在北線之后就可以),這樣一來,東北角那點始終會被認(rèn)為是北線上的點。
下面給出第 t 層的圖示說明:
//螺旋隊列問題
#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),輸出對應(yīng)的數(shù)字
int Spiral_Queue(int x, int y){
int val; //該坐標(biāo)對應(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;
}
|