例27 回旋方陣
問題描述
撰寫程式，生成從內到外是連續的自然數排列的回旋方陣，例如，當n=3和n=4時的回旋方陣如下圖1所示，
圖1 由內到外回旋方陣
輸入格式
一個正整數n（1≤n≤20），
輸出格式
N階滿足要求的由內到外回旋方陣，輸出時共n行，每行n個數，每個數占4列，
輸入樣例
5
輸出樣例
21 20 19 18 17
22 7 6 5 16
23 8 1 4 15
24 9 2 3 14
25 10 11 12 13
（1）編程思路1，
觀察圖1及樣例，由內到外回旋方陣的構造方法是：先將1填入方陣的中心位置（即i=(n-1)/2; j=(n-1)/2; a[i][j]=1），然后其余數的填寫可以看成由向下填充（列號不變、行號加1，即i++）、向右填充（行號不變、列號加1，即j++）、向上填充（行號減1、列號不變，即i--）和向左填充（行號不變、列號減1，即j--）四個子程序不斷交替完成的，
例如，圖1所示的4階由內到外回旋方陣可以看成由向下填充（2）、向右填充（3）、向上填充（4、5）、向左填充（6、7）、向下填充（8、9、10）、向右填充（11、12、13）、向上填充（14、15、16）這7個子程序完成的，
n階由內到外回旋方陣可以看成由4個子程序交替進行來完成的，這4個子程序依次為向下填充、向右填充、向上填充、向左填充，用變數d來表示，其取值為1、2、3或4，1表示向下填充，2表示向右填充，3表示向上填充，4表示向左填充，每個子程序結束后，切換填充方向，方式為：d++，若d>4，d=1，
在這一序列子程序中，第1、2子程序填寫1個數，第3、4子程序填寫2個數，第5、6子程序填寫3個數，第7、8子程序填寫4個數，…，直到最后一個數n2填寫完畢，
（2）源程式1，
#include<stdio.h>
int main()
{
int a[20][20]={0},i,j,k=1,n,x,d,cnt;
scanf("%d",&n);
i=(n-1)/2; j=(n-1)/2;
a[i][j]=k++;
d=1;cnt=1;x=0;
while (k<=n*n)
{
switch (d)
{
case 1:i++;
a[i][j]=k++;
x++;
if (x==cnt)
d=2,x=0;
break;
case 2:j++;
a[i][j]=k++;
x++;
if (x==cnt)
d=3,x=0,cnt++;
break;
case 3:i--;
a[i][j]=k++;
x++;
if (x==cnt)
d=4,x=0;
break;
case 4:j--;
a[i][j]=k++;
x++;
if (x==cnt)
d=1,x=0,cnt++;
break;
}
}
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
printf("%4d",a[i][j]);
printf("\n");
}
return 0;
}
（3）編程思路2，
觀察1所示的由內到外回旋方陣，可以看出，n階由內到外回旋方陣可以看成是自然數n*n~1由外向內遞減填充數字而構造成，
構造時，奇數階方陣從左下角開始（即row=n-1、col=0），回圈經過向上填充、向右填充、向下填充和向左填充的程序，直到全部數字填充完畢；偶數階方陣從右上角開始（即row=0、col=n-1），回圈經過向下填充、向左填充、向上填充和向右填充的程序，直到全部數字填充完畢，由于奇數階和偶數階填充順序有差異，定義一個變數s作為標志，s==1時，表示進行向下填充和向左填充；s==-1表示進行向上填充和向右填充，奇數階構造時，s初值為-1；偶數階時為1，
為了清楚地標記出每次填充結束的位置，定義x1、x2、y1和y2這四個變數來分別保存向上、向下、向左和向右填充的邊界，初始時， x1=0、y1=0、x2=n、y2=n，
例如，向上填充時，回圈程序為
while(row>=x1) // 向上填充
{
a[row][col]=num；
row--； // 行號減1、列號不變，向上填充
num--；
}
一次向上填充結束后，x1加1（即x1++），這樣向上填充的上邊界增大了，下次就會少填一行， 同時修改row和col，即row--、col--，從而得到向左填充的起點，
由于奇數階方陣先向上填充，這樣當向左填充時，最底行的左下角已經填有數字，因此，向左填充的邊界的初始值應為1（即y1=1），同理，偶數階方陣的初始向右填充的邊界y2=n-1，
（4）源程式2，
#include<stdio.h>
int main()
{
int row,col,a[20][20]={0},n,num;
int x1,x2,y1,y2,s;
// x1：填充上邊界 x2：填充下邊界
// y1：填充左邊界 y2：填充右邊界
// s：陣列元素升降標記，s等于l為升，s等于-1為降
scanf("%d",&n);
num=n*n;
x1=0; y1=0; x2=n; y2=n;
if (n%2==0) { row=0;col=n-1; y2=n-1; s=1;}
else { row=n-1; col=0; y1=1; s=-1;}
while (num>=1)
{
if(s==1)
{
while (row<x2) // 向下填充
{ a[row][col]=num--;row++; }
row--; col--; // 得到向左填充的起點
x2--; // 向下填充的下邊界縮小
while (col>=y1) // 向左填充
{ a[row][col]=num--;col--; }
col++; row--; // 得到向上填充的起點
y1++; // 向左填充的左邊界增大
s=-1; // 切換升降標志
}
else
{
while(row>=x1) // 向上填充
{ a[row][col]=num--; row--; }
row++; col++; // 得到向右填充的起點
x1++; // 向上填充的上邊界增大
while (col<y2) // 向右填充
{a[row][col]=num--;col++;}
col--; row++; // 得到向下填充的起點
y2--; // 向右填充的右邊界縮小
s=1; // 切換升降標志
}
}
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
printf("%4d",a[i][j]);
printf("\n");
}
return 0;
}
習題27
27-1 由外向內回旋方陣
問題描述
撰寫程式，生成從外到內是連續的自然數排列的回旋方陣，例如，當n=3和n=4時的回旋方陣如下圖2所示，
圖2 由外向內回旋方陣
輸入格式
一個正整數n（1≤n≤20），
輸出格式
N階滿足要求的由外向內回旋方陣，輸出時共n行，每行n個數，每個數占4列，
輸入樣例
5
輸出樣例
1 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
5 6 7 8 9
（1）編程思路，
由外向內回旋方陣可以通過對方陣的每一圈的各邊的各個元素順序賦值來完成，每一圈的賦值又依次包含4個順序的程序，
1）一圈的左列從上至下遞增賦值，一直賦值到超過最底行（即row==n）或下一位置已經賦值了（即a[row+1][col]！=0），
while(row+1<n && !a[row+1][col])
a[++row][col]=++num; // 列號col不變，行號row遞增，數num遞增
2）一圈的下行從左至右遞增賦值，一直賦值到超過最右列（即col==n）或下一位置已經賦值了（即a[row][col+1]！=0），
while(col+1<n&&!a[row][col+1])
a[row][++col]=++num; // 行號row不變，列號col遞增，數num遞增
3）一圈的右列從下至上遞增賦值，一直賦值到超過最頂列（即row==-1）或下一位置已經賦值了（即a[row-1][col]！=0），
while(row-1>=0&&!a[row-1][col])
a[--row][col]=++num; // 行號row遞減，列號col不變，數num遞增
4）一圈的上行從右至左遞增賦值，一直賦值到超過最左列（即col==-1）或下一位置已經賦值了（即a[row][col-1]！=0），
while(col-1>=0&&!a[row][col-1])
a[row][--col]=++num; // 行號row不變，列號col遞減，數num遞增
初始時，row=0、col=0、num=1，
（2）源程式，
#include<stdio.h>
int main()
{
int a[20][20]={0};
int n,row,col,num=0;
scanf("%d",&n);
num=a[row=0][col=0]=1; // 第0行第0列輸入起始1
while(num<n*n) // 陣列中的數不超過n*n
{
while(row+1<n && !a[row+1][col]) // 向下填充
a[++row][col]=++num;
while(col+1<n&&!a[row][col+1]) // 向右填充
a[row][++col]=++num;
while(row-1>=0&&!a[row-1][col]) // 向上填充
a[--row][col]=++num;
while(col-1>=0&&!a[row][col-1]) // 向左填充
a[row][--col]=++num;
}
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
printf("%4d",a[i][j]);
printf("\n");
}
return 0;
}
27-2 間斷折疊方陣
問題描述
n階間斷折疊方陣是把從起始數1開始的n2個整數折疊為n行n列的n階方陣：起始數1置于方陣的左上角，然后從起始數開始遞增，每一層從第1行開始，先豎向下再折轉向左，層層折疊地排列為間斷折疊方陣，
例如，當n=4和n=5時的間斷折疊方陣如下圖3所示，
圖3 間斷折疊方陣
輸入格式
一個正整數n（1≤n≤20），
輸出格式
N階滿足要求的間斷折疊方陣，輸出時共n行，每行n個數，每個數占4列，
輸入樣例
5
輸出樣例
1 2 5 10 17
4 3 6 11 18
9 8 7 12 19
16 15 14 13 20
25 24 23 22 21
（1）編程思路，
定義一個二維陣列a保存方陣的各元素，從給定的起始數1開始，按遞增1取值，根據間斷折疊方陣的構造特點給二維陣列a[n][n]賦值，
起始數1賦值給a[0][0]，
除a[0][0]外，n階方陣還有疊折的n-1層：
第i層（i=1、2、…、n-1）的起始位置為（0，i），隨后列號col不變行號row遞增（即向下填寫），至row=i時折轉；轉折后，行號row不變列號col遞減（即向左填寫），至col=0時該層結束，在每一位置分別按遞增值賦值給a[row][col]，
具體程序描述為：
a[0][0]=1;
num=2;
for(i=1;i<m;i++) // 方陣共m層
{
row=0; col=i; // 確定每層起始位置
a[row][col]= num++;
while(row<i) a[++row][col]=num++; // 先向下填
while(col>0) a[row][--col]=num++; // 再向左填
}
（2）源程式，
#include<stdio.h>
int main()
{
int i,m,num,row,col,a[20][20];
scanf("%d",&m);
a[0][0]=1;
num=2;
for (i=1;i<m;i++) // 方陣共m層
{
row=0; col=i;
a[row][col]=num++;
while(row<i) a[++row][col]=num++;
while(col>0) a[row][--col]=num++;
}
for (i=0;i<m;i++)
{
for (int j=0;j<m;j++)
printf("%4d",a[i][j]);
printf("\n");
}
return 0;
}
27-3 回轉折疊方陣
問題描述
n階回轉折疊方陣是把起始數1置于方陣的左上角，然后從起始數開始遞增，偶數層從第1行開始，先豎向下再折轉向左；奇數層從第1列開始，先橫向右再豎向上，呈首尾連接，層層折疊地排列為回轉折疊方陣，例如，當n=4和n=5時的回轉折疊方陣如下圖4所示，
圖4 回轉折疊方陣
輸入格式
一個正整數n（1≤n≤20），
輸出格式
N階滿足要求的回轉折疊方陣，輸出時共n行，每行n個數，每個數占4列，
輸入樣例
5
輸出樣例
1 2 9 10 25
4 3 8 11 24
5 6 7 12 23
16 15 14 13 22
17 18 19 20 21
（1）編程思路，
回轉折疊方陣構造程序的奇數層（注意：由于陣列下標從0開始，因此程式中層號也從0開始）與間斷折疊構造程序相同，偶數層構造方法改變為：該層的起始位置為（i，0），隨后行號row不變列號col遞增（即向右填寫），至col=i時折轉；轉折后，列號col不變行號row遞減（即向上填寫），至row=0時該層結束，在每一位置分別按遞增值賦值給a[row][col]，具體描述為：
if (i%2==0)
{
row=i;col=0; // 確定偶數層的起始位置
a[row][col]=num++;
while(col<i) a[row][++col]=num++; // 先向右填
while(row>0) a[--row][col]=num++; // 再向上填
}
（2）源程式，
#include<stdio.h>
int main()
{
int i,m,num,row,col,a[20][20];
scanf("%d",&m);
a[0][0]=1;
num=2;
for(i=1;i<m;i++) // 方陣共m層
{
if (i%2==1)
{
row=0; col=i;
a[row][col]=num++;
while(row<i) a[++row][col]=num++;
while(col>0) a[row][--col]=num++;
}
else
{
row=i;col=0;
a[row][col]=num++;
while(col<i) a[row][++col]=num++;
while(row>0) a[--row][col]=num++;
}
}
for (i=0;i<m;i++)
{
for (int j=0;j<m;j++)
printf("%4d",a[i][j]);
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/51132.html
標籤：C