/* 题目
按以下所示规律把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;
}
 分享到：
|