李寧的極客世界

隨筆 - 312, 文章 - 14, 評論 - 1393, 引用 - 0

數據加載中……

生成n*n蛇形矩陣的算法

本文為原創，如需轉載，請注明作者和出處，謝謝！

在描述算法之前，先看看下面的5*5的表格：

1	3	4	10	11
2	5	9	12	19
6	8	13	18	20
7	14	17	21	24
15	16	22	23	25

    上面的表格很容易看出規律。就是從左上角第一個格開始（起始為1），然后延右上角到左下角的斜線。先從下到上，再從上到下。開始按數字遞增排列。也就是說每一個斜線上分別有如下幾組數字：

1    2 3     4 5 6       7 8 9 10      11 12 13 14 15          16 17 18 19      20 21 22      23 24       25

    由于是先從上到下（1可以看做是從上到下），再從下到上，很象一條蛇，因此，該數字表格也可稱為蛇形矩陣。現在要與一個方法（或函數），方法的參數是一個int類型，表示n，方法返回一個二維數組，表示要獲得的往返接力數字表格。
    實際上，這個算法并不復雜，只需要從分別獲得1至n^2中每個數字對應的二維數組的坐標就可以了。先拿這個5行5列的表格來說，求出上面每組數組對應的坐標（起始位置為0）。

第0組
第1組
第2組
第3組
第4組
第5組
第6組
第7組
第8組

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19
20 21 22
23 24
25

(0,0)
(1,0)   (0,1)
(0,2) (1,1)   (2,0)
(3,0)   (2,1)   (1,2)   (0,3)
(0,4)   (1,3)   (2,2)   (3,1)   (4,0)
(4,1)   (3,2)   (2,3)   (1,4)
(2,4)   (3,3) (4,2)
(4,3)   (3,4)
(4,4)

從上面的從標可以看出一個規律。左上角的半個表格（以對角線分界）的橫坐標和縱坐標從0開始，每一組增1，直到增至表格的邊界（n - 1），而且是交替的，也就是說，偶數行是列增，行減小，行+列=組的索引。而右下角的4組數字雖然行、列也是交替增長的，但遞減的行或列總是從(n - 1)開始（對于本例，是從4開始），而遞增的行或列總是從index - n + 1開始，其中index表示組的索引。這就可以得出一個算法。實現代碼如下：

public static int[][] getGrid(int n)
{
    int[][] array = new int[n][n];
    int row = 0, col = 0, m = 1;
    //  用于控制奇偶組，false表示偶組，true表示奇組
    boolean isRow = false;
    //  i表示當前組的索引，從0開始
    for (int i = 0; i < (2 * n - 1); i++)
    {
        row = i;
        while (row >= ((i < n) ? 0 : i - n + 1))
        {
            //  如果處理的是右下角表格中的數字，行或列最大不能超過n-1
            if (row > (n - 1))
                row = n - 1;
            col = i - row;
            if (isRow)
                array[row][col] = m;
            else  //  將row變成列，將col變成行
                array[col][row] = m;
            m++;
            row--;
        }
        //  切換奇偶組
        isRow = !isRow;
    }
    return array;
}

另一種算法

上面實現的算法需要循環N*N次才可以生成蛇形矩陣。但仔細分析一下，還可以稍微變換一下這個算法，使循環次數減小至N*N/2。我們上學時曾學過用高斯的方法計算1+2+3+...+100， 1 + 100 = 101，2 + 99 = 101，...，50+51 = 101，因此，結果是101 * 50 = 5050。很方便。我們這個算法也可采用類似的方法。仔細觀察上面5*5的數字表格發現，算出左上角的矩陣中每一個數字后，都可以直接獲得右下角度某個位置的數字。例如在(0,0)位置的1，可以向到(4,4)位置的25，(1,2)位置的9可以得到(3,2)位置的17。我們發現，每一對數之和都為26。而且它們坐標的關系是(row,col)，(n - row - 1, n - col - 1)。因此，只要得到左上角的半個矩陣，就可以得出右下角的另外半個矩陣。如果n為奇數，對角線中間的一個數（在5*5的矩陣中是13）與之對應的數是其自身。好，我們看看改進的算法的實現：

public static int[][] getGrid1(int n)
{
    int[][] array = new int[n][n];
    int row = 0, col = 0, m = 1;
    int number1 =  (n * n / 2 + n * n % 2);
    int number2 = n * n + 1;
    boolean isRow = false;
    //  number1表示要計算的蛇形矩陣中最大的數字，對于5*5矩陣來說該數是13
    for (int i = 0; m < number1; i++)
    {
        row = i;
        while (row >= 0)
        {
            col = i - row;
            if (isRow)
            {
                array[row][col] = m;
                //  填充與m對應的另外一個數
                array[n - row - 1][n - col - 1] = number2 - m;
            }
            else
            {
                array[col][row] = m;
                //  填充與m對應的另外一個數
                array[n - col - 1][n - row - 1] = number2 - m;

            }
            m++;
            if(m >= number1) break;
            row--;
        }
        isRow = !isRow;
    }
    return array;
}

   上面的算法雖然將循環次數減少了一半，但每次循環的計算量增加了，因此，算法總體效率并沒有提高。至于使用哪個算法，可根據實際情況決定。
   如果想輸出n=10的數字表格，可以使用int[][] grid = getGrid(10)或int[][] grid1 = getGrid1(10)，會得到同樣的結果。輸出grid和grid1，看看是不是下面的結果：

1	3	4	10	11	21	22	36	37	55
2	5	9	12	20	23	35	38	54	56
6	8	13	19	24	34	39	53	57	72
7	14	18	25	33	40	52	58	71	73
15	17	26	32	41	51	59	70	74	85
16	27	31	42	50	60	69	75	84	86
28	30	43	49	61	68	76	83	87	94
29	44	48	62	67	77	82	88	93	95
45	47	63	66	78	81	89	92	96	99
46	64	65	79	80	90	91	97	98	100

哪位還有更好的算法，請跟貼。可以使用任何語言實現。

《Android開發完全講義（第2版）》（本書版權已輸出到臺灣）
http://product.dangdang.com/product.aspx?product_id=22741502

《Android高薪之路：Android程序員面試寶典》http://book.360buy.com/10970314.html

新浪微博：http://t.sina.com.cn/androidguy 昵稱：李寧_Lining

posted on 2009-07-24 11:04 銀河使者閱讀(8691) 評論(7) 編輯收藏所屬分類: java 、algorithm 、原創

# re: 獲得N^2個往返接力數字表格的算法回復 更多評論

acm中的蛇形矩陣

2009-07-24 21:05 | 飛翔天使

# re: 生成蛇形矩陣的算法回復 更多評論

public class Hello {
 
     public static void main(String[] args) {
         final int N = 6;
         for(int i = 0; i < N; i++) {
             for(int j = 0, m = 0; j < N; j++) {
                 if(j >= i) {
                     boolean b = j % 2 == 0;
                     m = (b ? (j + 1) * (j + 1) : j * j + 1) + (b ? -i : i);
                 } else {
                     boolean b = i % 2 == 0;
                     m = (b ? i * i + 1 : (i + 1) * (i + 1)) + (b ? j : -j);
                 }
                 System.out.printf("%2d ", m);
             }
             System.out.println();
         }
    }
}

2009-07-25 01:30 | 菜菜寶寶

# re: 生成蛇形矩陣的算法回復 更多評論

 1  2  9 10 25 26
 4  3  8 11 24 27
 5  6  7 12 23 28
16 15 14 13 22 29
17 18 19 20 21 30
36 35 34 33 32 31

哎，不好意思，看錯題了，生成這樣子的了。

2009-07-25 01:35 | 菜菜寶寶

# re: 生成n*n蛇形矩陣的改進算法[未登錄] 回復 更多評論

這個問題需要填充N*N個數，所以必須有N*N次操作，從這一層看來，沒有改進的余地。你改進的算法只是減少了循環次數，卻在每次循環中加倍了操作，還增加了很多判斷，我以為，這樣速度反而會慢呢。

2009-07-26 10:51 | lanxiazhi

# re: 生成n*n蛇形矩陣的改進算法回復 更多評論

@lanxiazhi
測了一個，這兩個算法的效率差不多。不過改進后的算法看起來更好點，至少在while后面沒那么多計算了，哈。

2009-07-26 11:39 | 銀河使者

# re: 生成n*n蛇形矩陣的算法回復 更多評論

void shetian(int n)
{ int a[50][50],i,j,k,t;
k=0;
t=1;
while (k<=n*2)
{
for(i=k;i>=0;i--)
for(j=0;j<=k;j++)
if((i+j==k)&&(i<=n-1)&&(j<=n-1))
if(k%2==0) a[j][i]=t++;
else a[i][j]=t++; k++;
}
for(i=0;i<=n-1;i++)
{ for(j=0;j<=n-1;j++)
printf("%d ",a[i][j]);
printf("\n");}
}
初學不知道行不？

2009-08-11 16:51 | 彪子

# re: 生成n*n蛇形矩陣的算法 回復 更多評論

public class test {
public static void main(String[] args) {
int[][] array = new int[10][10];
for (int row = 0; row < 10; row++) {
for (int col = 0; col < 10; col++) {
if ((col + row) < 10) {
if ( ( col + row + 1 ) % 2 == 1 ) {
array[row][col] = (1+( col + row + 1 ))/2*( col + row + 1 )-col;
array[9-row][9-col] = 101-array[row][col];
} else {

array[row][col] = (1+( col + row ))/2*( col + row )+col+1;
array[9-row][9-col] = 101-array[row][col];
}
}
}
System.out.println();
}

for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
System.out.print(array[i][j]+"\t");
}
System.out.println();
}
}
}

2009-08-12 22:32 | tonny

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: Android開發（1）：隨機繪制彩色實心圓關于Android中傳遞數據的一些討論《Android/OPhone 開發完全講義》連載（10）：Sqlite數據庫《Android/OPhone開發完全講義》連載（8)：收到短信了，我該做點什么？《Android/OPhone開發完全講義》連載（7)：使用SharedPreferences存取復雜數據實用Android開發工具和資源精選中國移動開發者社區專訪：學習Android的兩大法寶可循環顯示圖像的Android Gallery組件移動互聯網的新寵：Android之繽紛世界《人人都玩開心網：Ext JS+Android+SSH整合開發Web與移動SNS》銷售排名第4，發篇ExtJS的文章(拖放樹結點)慶祝下

李寧的極客世界

生成n*n蛇形矩陣的算法

《Android開發完全講義（第2版）》（本書版權已輸出到臺灣）

《Android高薪之路：Android程序員面試寶典 》http://book.360buy.com/10970314.html

評論

# re: 獲得N^2個往返接力數字表格的算法 回復 更多評論

# re: 生成蛇形矩陣的算法 回復 更多評論

# re: 生成蛇形矩陣的算法 回復 更多評論

# re: 生成n*n蛇形矩陣的改進算法[未登錄] 回復 更多評論

# re: 生成n*n蛇形矩陣的改進算法 回復 更多評論

# re: 生成n*n蛇形矩陣的算法 回復 更多評論

# re: 生成n*n蛇形矩陣的算法 回復 更多評論

導航

公告

常用鏈接

留言簿(126)

我參與的團隊

隨筆分類(818)

隨筆檔案(310)

文章分類(1)

文章檔案(8)

相冊

ADSL、3G查詢

CSDN

eclipse

ibm

Java EE

Linux

Web

云服務

代理網站

關注的網站

協議

喜歡的Blog

國內廣告平臺

圖書出版

在線培訓

開發工具

微博客戶端

手機鈴聲

操作系統

數學

文件格式

源碼資源

移動（Mobile）

編程語言

英語學習

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

《Android高薪之路：Android程序員面試寶典》http://book.360buy.com/10970314.html

# re: 獲得N^2個往返接力數字表格的算法回復更多評論

# re: 生成蛇形矩陣的算法回復更多評論

# re: 生成蛇形矩陣的算法回復更多評論

# re: 生成n*n蛇形矩陣的改進算法[未登錄] 回復更多評論

# re: 生成n*n蛇形矩陣的改進算法回復更多評論

# re: 生成n*n蛇形矩陣的算法回復更多評論

# re: 生成n*n蛇形矩陣的算法回復更多評論