snake algorithm java implementation

sponsored links
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 ->
  • del.icio.us
  • StumbleUpon
  • Digg
  • TwitThis
  • Mixx
  • Technorati
  • Facebook
  • NewsVine
  • Reddit
  • Google
  • LinkedIn
  • YahooMyWeb

Related Posts of snake algorithm java implementation

  • hibernate using c3p0 connection pooling

    Private http://www.lifevv.com/tenyo/doc/20070605102040991.html c3p0 for open source's JDBC connection pool, with the release hibernate. This article describes how to use the hibernate configuration in c3p0. c3p0 connection pool configuration is v ...

  • Hibernate configuration parameters hibernate.hbm2ddl.auto

    Hibernate in the configuration file: <properties> <property name="hibernate.hbm2ddl.auto" value="create" /> </ properties> Parameter Description: validate load hibernate, the authentication to create a database t ...

  • Build flex + spring + blazeds + hibernate application

    Build flex + spring + blazeds + hibernate application First, set up the project blazeds 1, will blazeds.war extract to a directory, such as: myflex /; 2, set up java works were such as: MyFlex, in the orientation of selection create project from exis ...

  • Hibernate connection pool configuration

    Hibernate connection pool configuration <! - Jdbc -> <property name="connection.driver_class"> oracle.jdbc.driver.OracleDriver </ property> <property name="connection.url"> jdbc: oracle: thin: @ 10.203.14.132:15

  • hibernate generic generic DAO

    package org.lzpeng.dao; import java.io.Serializable; import java.util.List; import org.hibernate.Criteria; import org.hibernate.Query; import org.hibernate.criterion.Criterion; import org.springside.modules.orm.hibernate.Page; /** * * @version 2009-1-10 *

  • First Hibernate Example

    Curd a simple example. Source does not contain the dependent libraries, or playing too much of the package. PO object Note: One must have the default constructor 2 non-final modified. Otherwise useless lazy loading. UserDAOImpl category code, and other co

  • Struts2 + hibernate + spring problem user log in

    dao layer services layer action jsp <tr> <td align="center"> <b> user name: </ b> </ td> <td> <s: textfield name = "czyNumber" cssClass = "textstyle" theme = "simple" size = &q

  • Hibernate secondary cache

    Hibernate cache: 2-bit cache, also known as process-level cache or SessionFactory level cache, secondary cache can be shared by all of the session Cache configuration and the use of: Will echcache.xml (the document code in hibernate package directory ...

  • Hibernate's lazy strategy

    hibernate Lazy strategy can be used in: <class> tag, it can be true / false Tags can <PROPERTY> values true / false type of necessary tools to enhance <set> <list> can tag values true / false / extra <many-to-one> <on ...

blog comments powered by Disqus
Recent
Recent Entries
Tag Cloud
Random Entries