/* 题目
按以下所示规律把1-N*N个数填入N*N的方阵中：
  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 
*/

#include <stdio.h>
#include <assert.h>
#include <string.h>
/*
解析：
 上三角形
 a(0)=   1     = 1    + 0 
 a(1)=  2 3    = a(0) + 1, a(0) + 1 + 1
 a(2)= 4 5 6   = a(1) + 2, a(1) + 2 + 1, a(1) + 2 + 2
 a(3)=7 8 9 10 = a(2) + 3, a(2) + 3 + 2, a(2) + 3 + 2, a(2) + 3 + 3
 ...
 a(n)= sum_n(n), sum_n(n) + 1, sum_n(n) + 2, ..., sum_n(n) + n
 反转序列为
 a(n)= sum_n(n), sum_n(n) + n - 1, sum_n(n) + n - 2, ..., sum_n(n) + n - 3
 
 bn数组中
 bn(0, 0) = a(0)(0)
 bn(0, 1) = a(1)(1)
 bn(0, 2) = a(2)(2)

 bn(1, 0) = a(1)(0)
 bn(1, 1) = a(2)(1)

 下三角形,与上三角形对称
 bn(n, n) = max - bn(0, 0);
 bn(n - 1, n) = max - bn(1, 0);
 bn(n , n - 1) = max - bn(0, 1);
*/

int sum_n(int n)
{
    return 1 + (n * (n + 1))/ 2;
}

int rev(int n, int m)
{
    return ((m + n) & 0x1) ? m : n;
}

int bn(int n, int m)
{
    return sum_n(n + m) + rev(m, n);
}

void snake_array(int *p, int m)
{
    int max_v = m * m + 1; 
    for(int i = 0; i < m; ++i)
    {
        for (int j = 0; j < m - i ; ++j)
        {
            int value = bn(j, i);
            (p + i * m)[j] = value;
            (p + (m - i - 1) * m)[m - j - 1] = max_v - value;
        }
    }
}

void test()
{
    int correct[25] =
    {
        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
    };

    int test[25] = {0};
    snake_array(test, 5);
    assert(0 == memcmp(test, correct, sizeof(correct)));

}
void print_square(int *p, int m)
{
    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            printf("%3d ", (p + i * m)[j]);
        }
        puts("");
    }
}

int main(int argc, char *argv[])
{
    test();

    static const int N = 5;
    int array[N * N] = {0};
    snake_array(array, N);
    print_square(array, N);
 return 0;
}

评论