首页 > 代码库 > 蛇形排列

蛇形排列

原题

自然数采用蛇形排列方式填充到数组中。将自然数1、2、3…、N*N逐个顺序插入方阵中适当的位置,这个过程沿斜列进行。将斜列编号为0、1、2…、2n(以i标记,n=N-1),如下面的数据排列,这个排列为蛇形排列。

1   3    4    10

2   5    9    11

6   8   12   15

7  13  14   16

我的思路

观察以下坐标:

(0,0)                                     和为0

(1,0) (0,1)                             和为1

(0,2) (1,1) (2,0)                     和为2

(3,0) (2,1) (1,2) (0,3)             和为3

(1,3) (2,2) (3,1)                     和为4      --> (0,4) (1,3) (2,2) (3,1) (4,0)

(3,2) (2,3)                             和为5      --> (5,0) (4,1) (3,2) (2,3) (1,4)

(3,3)                                     和为6      --> (0,6) (1,5) (2,4) (3,3) (4,2) (5,1) (6,0)

不难发现只要在同一斜行上的数字,其对应数组行列下标之和总是相等的。

注意,当和为4或者大于4时,填充数字时要注意越界问题,因此我在程序中特意写了一个宏来判断。

实现代码

/*************************************************************************    > File Name: testmain.c    > Author: KrisChou    > Mail:zhoujx0219@163.com     > Created Time: Sun 17 Aug 2014 09:04:42 PM CST ************************************************************************/#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 4#define IS_LEGAL(row,col) ((row) >= 0 && (row) < N && (col) >= 0 && (col) < N )void print(int (*arr)[N]);void fill(int (*arr)[N]);int main(int argc, char *argv[]){    int arr[N][N];    memset(arr,0,sizeof(arr));    fill(arr);    print(arr);    return 0;}void print(int (*arr)[N]){    int i,j;    for(i = 0; i < N; i++)    {        for(j = 0; j < N; j++)        {            printf("%3d",arr[i][j]);        }        printf("\n");    }}void fill(int (*arr)[N]){    int sum;    int row,col;    int num = 0;    for(sum = 0; sum < 2 * N - 1; sum++)    {        if(sum % 2 == 0)        {            for(row = 0; row < N; row++)            {                col = sum - row;                if(IS_LEGAL(row,col))                {                    arr[row][col] = ++num;                }            }        }else        {            for(row = sum; row >=0; row--)            {                col = sum - row;                if(IS_LEGAL(row,col))                {                    arr[row][col] = ++num;                }            }        }    }}