n*nヘビ行列を生成するアルゴリズム

ソース:http://www.blogjava.net/nokiaguy/archive/2009/07/24/288163.html
 
アルゴリズムを記述する前に、次の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 13 15 16 17 18 20 21 22 24 25は、まず上から下(1は上から下と見なすことができます)、さらに下から上へ、蛇のように見えます.そのため、この数値テーブルは、蛇行列とも呼ばれる.メソッド(または関数)と、メソッドのパラメータはintタイプで、nを表し、メソッドは2次元配列を返し、取得する往復リレーの数値テーブルを表します.実際,このアルゴリズムは複雑ではなく,1〜n^2の各数字に対応する2次元配列の座標をそれぞれ得るだけでよい.まずこの5行5列の表を持って、上の各配列に対応する座標(開始位置は0)を求めます.
上の基準から法則が見えます.左上隅の半分の表(対角線で区切られた)の横座標と縦座標は0から始まり、各グループは表の境界(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;

}

もう1つのアルゴリズム上で実装されたアルゴリズムは,ヘビ行列を生成するために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[][grid 1=getGrid 1(10)を使用すると、同様の結果が得られます.gridとgrid 1を出力し、次の結果かどうかを確認します.
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