找回密碼
 立即注冊

QQ登錄

只需一步,快速開始

搜索
查看: 2344|回復(fù): 0
收起左側(cè)

螺旋隊列算法分析

[復(fù)制鏈接]
ID:77367 發(fā)表于 2015-4-18 20:18 | 顯示全部樓層 |閱讀模式


問題描述:
設(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;
}








回復(fù)

使用道具 舉報

您需要登錄后才可以回帖 登錄 | 立即注冊

本版積分規(guī)則

手機(jī)版|小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表