snake algorithm java implementation

package aglo;

public class test {

        /**
         *  Describes a  :
         * 5 Line 5 column snake-like algorithm
         * (0,0)(4,4)- Line 1 and countdown  1 Difference between rows  4
         * (1,0)(4,3)(0,1)(3,4)- Line 2 and countdown  2 Difference between rows  3
         * (0,2)(2,4)(1,1)(3,3)(2,0)(4,2)- The first 3 rows and countdown  3 Difference between rows  2
         * (3,0)(4,1)(2,1)(3,2)(1,2)(2,3)(0,3)(1,4)- The fourth row and countdown  4 Difference between rows  1
         *  Section 5 behavior segmentation line
         *  According to the above description, obtain the following algorithm
         */
        /**
         *  Description of second  :
         * dao Variable functions  :
         *  The main calculation downward diagonal coordinate values  .
         *  For example,  :5 Line 5 columns
         * {
                   (0,0)                  -- Known as line  0
                   (1,0)(0,1)             -- Known as line  1
           (0,2)(1,1)(2,0)        -- Known as line  2
           (3,0)(2,1)(1,2)(0,3)   -- Known as line  3
           }--- All coordinates on the diagonal
       (0,4)(1,3)(2,2)(3,1)(4,0)--- Here called diagonal  4
           {
                  (4,1)(3,2)(2,3)(1,4)  -- Known as line  5
                  (2,4)(3,3)(4,2)       -- Known as line  6
                  (4,3)(3,4)            -- Known as line  7
                  (4,4)                 -- Known as line  8
           }--- Downward diagonal all coordinates
           dao The maximum value of the variable is line  * Column
            Get all the coordinates of the diagonal values by dao variables and  temp Variable functions
         */
        /**
         * @param irow  Line
         * @param icol  Column
         * @param sheLength  Sections snake segment, which is line with diagonal
         */
        public void sheAglo(int irow,int icol,int sheLength){
                int row = 0,col = 0;
                int ban = (sheLength-1)/2+1;
                int array[][] = new int[irow][icol];
                int m = 1,num = ban - 1;
                int dao = irow*icol;
                for(int i=0;i<ban;i++){
                        row = col = i;
                        int  temp = dao-i;// The first n rows downward diagonal values from  dao-i Start
                        if(i%2==0){             // Handling double-row
                                /**
                                 * (0,0)
                                 * (0,2)(1,1)(2,0)
                                 *  Characteristic is the increment, decrement column rows
                                 */
                                while(col>=0){
                                        System.out.print("["+(i-col)+"]["+(col)+"]("+m+"),");
                                        if(i!=ban-1){// This is the diagonal
                                                System.out.print("["+(i-col+num)+"]["+(col+num)+"]("+(temp++)+"),");
                                        }
                                        array[i-col][col] = m;
                                        dao--;
                                        col--;
                                        m++;
                                }
                        }else if(i%2!=0){// Handle single-line
                                /**
                                 * (1,0)(0,1)
                                 * (3,0)(2,1)(1,2)(0,3)
                                 *  Characteristics are diminishing, incrementing column rows
                                 */
                                while(row>=0){
                                        System.out.print("["+(row)+"]["+(i-row)+"]("+m+"),");
                                        if(i!=ban-1){
                                                System.out.print("["+(row+num)+"]["+(i-row+num)+"]("+(temp++)+"),");
                                        }
                                        array[row][i-row] = m;
                                        dao--;
                                        row--;
                                        m++;
                                }
                        }
                        num--;
                        System.out.println();
                }
        }

        public static void main(String args[]){
                test test = new test();
                test.sheAglo(6,6,11);
        }

}

The algorithm can only support the rows, columns, the same matrix.

References 1:

In describing the algorithm before the 5 * 5 to see the following table:

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

The above table is easy to see that law. Is the upper left corner of the first cell from the beginning (starting 1), and then extend the upper right corner to bottom left diagonal. Starting with the next to last, then top to bottom. Start by number in ascending order. That is a slash on each of several groups of figures were as follows:

1,234,567,891,011,121,314 15 16 17 1,819,202,122,232,425

As the first top to bottom (1 can be seen as top to bottom), from bottom to top, much like a snake, therefore, the digital form can also be known as the Snake matrix. Now with a method (or function), method parameter is a int type, that n, method returns a two-dimensional array, said to number of forms received from Relay.

In fact, the algorithm is not complicated, just were obtained from 1 to n ^ 2 in each number corresponding to the two-dimensional array of coordinates on it. Acquire a 5-line 5 of this form, the calculated above corresponds to the coordinates of each array (starting position is 0).

Group 0 Group 1

Group 2

Group 3

Group 4

Group 5

Group 6

Group 7

Group 8

1
23

456

78910

1112131415

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)

From the above we can see a pattern from the standard. Half the upper left corner of the form (with diagonal boundaries) of the horizontal and the vertical axis starting at 0, each group by one, until the border to form (n - 1), and is alternating, that is, even line is the column increase, decrease row, row + column = group index. The bottom right corner of the 4 groups although the figures are rows, columns are alternating growth, but decreasing the row or column is always from the (n - 1) started (for this example, starting from 4), while increasing the row or column is always from the index - n + 1 start, which index the index of that group. An algorithm which can be drawn. To achieve the code below:

public static int[][] getGrid(int n)
{
int[][] array = new int[n][n];
int row = 0, col = 0, m = 1;
// Used to control the parity group, false indicates that even groups ,true Represents a singular group
boolean isRow = false;
// i Represents the index of the current groups, from 0 Start
for (int i = 0; i < (2 * n - 1); i++)
{
row = i;
while (row >= ((i < n) ? 0 : i - n + 1))
{
// If the processing is the lower-right corner of the table of figures, the row or column up n-1
if (row > (n - 1))
row = n - 1;
col = i - row;
if (isRow)
array[row][col] = m;
else // Use the row into columns , The col into line
array[col][row] = m;
m++;
row--;
}
// Switch parity group
isRow = !isRow;
}
return array;
}

Another algorithm

The algorithm needs to achieve the above cycle of N * N times we can generate serpentine matrix. But a closer look, you can also change what the algorithm slightly, so that cycle times reduced to N * N / 2. We had learned in school to use Gauss's method, 1 +2 +3 +...+ 100, 1 + 100 = 101,2 + 99 = 50 +51 = 101 ,..., 101, so the result is 101 * 50 = 5050. Very convenient. Our algorithm also could use a similar approach. Carefully observe the figures above 5 x 5 table was found, calculate the upper-left corner of the matrix after each number, can directly access a location in the lower right corner the number of degrees. For example, in (0,0) position 1, may apply to the (4,4) position 25, (1,2) position of 9 can be (3,2) position of 17. We found that the number of each and all of the 26. And they coordinate the relationship is (row, col), (n - row - 1, n - col - 1). Therefore, as long as get the upper left corner of the half matrix, we can draw the other half of the matrix lower right corner. If n is odd, the diagonal middle of a number (in the 5 * 5 matrix of 13) with the corresponding number is its own. Well, we look to improve the algorithm implementation:

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 Indicates that you want to calculate the snake-like matrix in the largest numbers, for 5*5 The number is for the matrix 13
for (int i = 0; m < number1; i++)
{
row = i;
while (row >= 0)
{
col = i - row;
if (isRow)
{
array[row][col] = m;
// Fill and m is the number that corresponds to another
array[n - row - 1][n - col - 1] = number2 - m;
}
else
{
array[col][row] = m;
// Fill and m is the number that corresponds to another
array[n - col - 1][n - row - 1] = number2 - m;
}
m++;
if(m >= number1) break;
row--;
}
isRow = !isRow;
}
return array;
}

Although the above algorithm will cycle times reduced by half, but increased the calculation of each cycle, so the algorithm does not increase the overall efficiency. As for the use of algorithms which can be based on actual conditions.

If you want to output n = 10 the number of forms, you can use int [] [] grid = getGrid (10) or int [] [] grid1 = getGrid1 (10), will get the same result. Output grid and grid1, see if it is the result of the following:

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 6.2 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

Source: http://tech.ddvip.com/2009-09/1253593588133921.html

References 2:

Matrix it can say a few snake, snake-like matrix of several types, this is one of the following:
1267
35813
491 214
10,111,516
It was such a matrix has attracted a few days, of course, I think this is the most like "snake" in Kazakhstan serpentine matrix.
Then, write some code yourself, can be considered to achieve this effect, but the algorithm is too complicated for the above

for loop sets a for loop, look at all his halo, and then surf the Internet and write a few masters, and finally found following this very simple, unfortunately do not know Who is this big cow. .
Realization is very simple and clear, I want to say is that this not only to achieve N * N of the square, slightly transform can achieve N * M matrix,

This irregular serpentine also fun Ha ~
The following are the three Figure 4 * 4 squares, 5 * 3 matrix and 3 * 5 matrix, followed by two good Kanma \ (^ o ^) / ~

snake algorithm java implementation
snake algorithm java implementation
snake algorithm java implementation

The following code is attached, of course, I write not brought, and, not embarrassed about. . . . .

C + + Language: snake

01 # include <iostream>
02 using namespace std;
03 const int MAX = 20;
04
05 int main ()
06 (
07 int m, n;
08 int a [MAX] [MAX];
09 cout <<"Enter matrix of rows and columns:" <<endl;
10 cin>> m>> n;
11
12 int i, j, s;
13 i = j = 0;
14 s = 1;
15 a [i] [j] = s + +;
16 while (s <= m * n)
17 (
18 / / shift to right
19 if (j <n - 1)
20 j + +;
21 else
22 i + +;
23 a [i] [j] = s + +;
24 / / lower left
25 while (i <m - 1 & & j> 0)
26 a [+ + i] [- j] = s + +;
27 / / Down
28 if (i <m - 1)
29 i + +;
30 else
31 j + +;
32 a [i] [j] = s + +;
33 / / upper right
34 while (j <n - 1 & & i> 0)
35 a [- i] [+ + j] = s + +;
36)
37 for (int i = 0; i! = M; + + i)
38 (
39 for (int j = 0; j! = N; + + j)
40 printf ("% 3.0d", a [i] [j]);
41 cout <<endl;
42)
43 return 0;
44)

Source: http://www.ihonk.cn/blog/2009/06/14/129 # more-129

<! - Page --><!-- page end ->

分类:Java 时间:2010-04-16 人气:437
分享到:
blog comments powered by Disqus

相关文章

  • public static void main (String args []) parameters 2010-05-15

    String args [] is the main function of main parameters, namely array of strings. Using eclipse in the editing, right-click to run the Java files in the Run As option, select Run Configurations. Main class in the Project and complete the project, resp

  • Why public static void main (String args []){} 2010-11-06

    main () is a Java program entry, program execution is the beginning of this entry. Class is a class member, main () method must be public members. So that it can be called in the execution environment. main () method does not produce the object can b

  • 浅析C#中的Main(String[] args)参数输入问题 2014-07-20

    本篇文章主要是对C#中的Main(String[] args)参数输入问题进行了详细的介绍,需要的朋友可以过来参考下,希望对大家有所帮助 指定相关的测试代码 首先,写一个用于测试的关于Main(String[] args)参数输入有关的代码类,如下: using System; public class Hello { public static void Main(String[] args) { switch (args[0]) { case "老板": Console.Write

  • Calls from non-public classes public class main method 2010-09-27

    class testArray{ public static void main(String args[]){ for(String s : args){ //args Accept from DynamicArray class from a string System.out.println(s); } } } public class DynamicArray{ public static void main(String args[]){ testArray.main(new Stri

  • Determine the number of symmetric or symmetric string (Java implementation) 2010-06-03

    Determine whether a number of symmetry, such as: 123321,2332, abccba so. Java code is as follows: public class SymmetryNumber { public static boolean isSymmetryNumber(long n) { String str = String.valueOf(n); return isSymmetString(str); } public stat

  • JAVA implementation in String.trim () method 2010-10-12

    Implement a simple String.trim (String s) method (clear space on both sides of a string). public class Term { public String trim1(String s) { char[] cArray = s.toCharArray(); int index = 0; for (int i = 0; i < cArray.length; i++) { if (cArray[i] != '

  • JAVA中int.String的类型转换 2012-04-08

    int -> String int i=12345; String s=""; 第一种方法:s=i+""; 第二种方法:s=String.valueOf(i); 这两种方法有什么区别呢?作用是不是一样的呢?是不是在任何下都能互换呢? String -> int s="12345"; int i; 第一种方法:i=Integer.parseInt(s); 第二种方法:i=Integer.valueOf(s).intValue(); 这两

  • How the eclipse of the main the String [] args parameter passed, and then export it 2010-12-26

    How the eclipse of the main the String [] args parameter passed, and then export it? In the Run menu to find Open Run dialog opens Select Java Application in the program need to run Select the Arguments Tab Enter the parameters in the Programe Argume

  • public void testStatementAddBatch () public void testConnCommit () 2011-09-01

    public void testStatementAddBatch() { Connection conn = null; Statement stmt = null; try { conn = getDBConnectionMsSqlBySuperAdmin(); stmt = conn.createStatement(); for(int i = 0; i < 100; i++) { String sql = " sql " + i; stmt.addBatch(sql);

  • String [] args = new String [] {sql.toString ()} 2011-06-29

    In this problem StringBuffer sql = new StringBuffer (); Which sql.toString results: 'Test User 1', 'male' String [] args = new String [] {sql.toString ()} args.length 1 results Obviously not what we need. Note: new String []{"","",&quo

iOS 开发

Android 开发

Python 开发

JAVA 开发

开发语言

PHP 开发

Ruby 开发

搜索

前端开发

数据库

开发工具

开放平台

Javascript 开发

.NET 开发

云计算

服务器

Copyright (C) codeweblog.com, All Rights Reserved.

CodeWeblog.com 版权所有 黔ICP备15002463号-1

processed in 0.451 (s). 12 q(s)