【北理乐学】铺地板
【题目描述】
有一名室内装潢工程队的配料员。他的伙伴们喜欢采用“之”字型的方式铺大理石地砖，图案例如下：
1 2 6 7 15
3 5 8 14 16
4 9 13 17 22
10 12 18 21 23
11 19 20 24 25
如何用C 语言生成这样的图形。
【题目分析】
初见该题本以为是需要对奇偶进行分类处理（一般看见图形题就需要考虑这一方面），但幸运的是，这道题似乎不需要我们对奇偶进行讨论，似乎所有的用例都是奇数，所以我们只对奇数处理即可。下面我贴两组代码，一个是按贴地板的顺序依次填充的，另一部分则是运用递归对通项进行求解。
【常规解法】
#include <stdio.h>
#include <string.h>
#define maxn 20
int a[maxn][maxn];
int main(){
memset(a,0,sizeof(a));
int n, i=0,x,y;
scanf("%d",&n);
a[x=0][y=0]=++i;
while(i<n*n/2){
if(y+1<=n){
a[x][++y]=++i;
}
while(y-1>=0&&x+1<=n){
a[++x][--y]=++i;
}
if(x+1<=n){
a[++x][y]=++i;
}
while(y+1<=n&&x-1>=0){
a[--x][++y]=++i;
}
}
while(i<n*n){
if(y+1<n&&0==a[x][y+1]){
a[x][++y]=++i;
}
while(y+1<n&&x-1>=0&&0==a[x-1][y+1]){
a[--x][++y]=++i;
}
if(x+1<n&&0==a[x+1][y]){
a[++x][y]=++i;
}
while(y-1>=0&&x+1<n&&0==a[x+1][y-1]){
a[++x][--y]=++i;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%3d",a[i][j]);
}
printf("\n");
}
return 0;
}
【递归解法】
#include<stdio.h>
int go(int i, int j,int n) {
if (i + j > n + 1)return n * n + 1 - go(n + 1 - i, n + 1 - j, n);
int s = (i + j - 2) * (i + j - 1) / 2;
if ((i + j) % 2)return s + i;
return s + j;
}
int main() {
int i, j, n;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
for (j = 1; j < n; j++)printf("%2d ", go(i, j, n));
printf("%2d\n", go(i, n, n));
}
return 0;
}
【Hint】
看似递归的代码比常规解法精简许多，但是要思考的量却的确比常规解法大，同时采用递归，可能内存消耗会出乎意料的大（这也是递归最大的弊端），仍有重复子问题（即递归基）的多次计算，感兴趣的可以查查Dynamic Programming（简称DP），可以大幅度降低该问题的运行时间。
