【題目描述】
有一名室內(nèi)裝潢工程隊的配料員。他的伙伴們喜歡采用“之”字型的方式鋪大理石地磚，圖案例如下：
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 語言生成這樣的圖形。
【題目分析】
初見該題本以為是需要對奇偶進行分類處理（一般看見圖形題就需要考慮這一方面），但幸運的是，這道題似乎不需要我們對奇偶進行討論，似乎所有的用例都是奇數(shù)，所以我們只對奇數(shù)處理即可。下面我貼兩組代碼，一個是按貼地板的順序依次填充的，另一部分則是運用遞歸對通項進行求解。
【常規(guī)解法】
#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】
看似遞歸的代碼比常規(guī)解法精簡許多，但是要思考的量卻的確比常規(guī)解法大，同時采用遞歸，可能內(nèi)存消耗會出乎意料的大（這也是遞歸最大的弊端），仍有重復(fù)子問題（即遞歸基）的多次計算，感興趣的可以查查Dynamic Programming（簡稱DP），可以大幅度降低該問題的運行時間。
