C語言實現魔方陣程式碼及解析
問題描述編寫程式，實現如下表所示的5-魔方陣。
| 17 | 24 | 1 | 8 | 15 |
| 23 | 5 | 7 | 14 | 16 |
| 4 | 6 | 13 | 20 | 22 |
| 10 | 12 | 19 | 21 | 3 |
| 11 | 18 | 25 | 2 | 9 |
5-魔方陣
問題分析
所謂“n-魔方陣”，指的是使用1〜n2共n2個自然數排列成一個n×n的方陣，其中n為奇數；該方陣的每行、每列及對角線元素之和都相等，併為一個只與n有關的常數，該常數為n×(n2+1)/2。
例如4-魔方陣，其第一行、第一列及主對角線上各元素之和如下：
- 第一行元素之和：17+24+1+8+15=65
- 第一列元素之和：17+23+4+10+11=65
- 主對角線上元素之和：17+5+13+21+9=65
而 n×(n2+1)/2=5×(52+1)/2=65 可以驗證，5-魔方陣中其餘各行、各列及副對角線上的元素之和也都為65。
假定陣列的行列下標都從0開始，則魔方陣的生成方法為：在第0行中間置1，對從2開始的其餘n2-1個數依次按下列規則存放：
(1) 假定當前數的下標為(i，j)，則下一個數的放置位置為當前位置的右上方，即下標為(i-1，j+1)的位置。
(2) 如果當前數在第0行，即i-1小於0，則將下一個數放在最後一行的下一列上，即下標為(n-1，j+1)的位置。
(3) 如果當前數在最後一列上，即j+1大於n-1，則將下一個數放在上一行的第一列上，即下標為(i-1，0)的位置。
(4) 如果當前數是n的倍數，則將下一個數直接放在當前位置的正下方，即下標為(i+1，j）的位置。
演算法設計
在設計演算法時釆用了下面一些方法：
- 定義array()函式，array()函式的根據輸入的n值，生成並顯示一個魔方陣，當發現n不是奇數時，就加1使之成為奇數。
- 使用動態記憶體分配與釋放函式malloc()與free()，在程式執行過程中動態分配與釋放記憶體，這樣做的好處是使程式碼具有通用性，同時提高記憶體的使用率。
在分配記憶體時還要注意，由於一個整型數要佔用兩個記憶體，因此，如果魔方陣中要存放的數有max個，則分配記憶體時要分配2*max個單元，從而有malloc(max+max)。在malloc()函式中使用max+max而不是2*max是考慮了程式執行的效能。
顯然應該使用二維陣列來表示魔方陣，但雖然陣列是二維形式的，而由於記憶體是一維線性的，因此在存取陣列元素時，要將雙下標轉換為單個索引編號。在程式中直接定義了指標變數來指向陣列空間，即使用malloc()函式分配的記憶體。
下面是完整的程式碼：
#include<stdio.h>
#include<stdlib.h>
int array(int n)
{
int i, j, no, num, max;
int *mtrx;
if(n%2 == 0) /*n是偶數，則加1使其變為奇數*/
{
n=n+1;
}
max=n*n;
mtrx=(int *)malloc(max+max); /*為魔方陣分配記憶體*/
mtrx[n/2]=1; /* 將1存入陣列*/
i=0; /*自然數1所在行*/
j=n/2; /*自然數1所在列*/
/*從2開始確定每個數的存放位置*/
for(num=2; num<=max; num++)
{
i=i-1;
j=j+1;
if((num-1)%n == 0) /*當前數是n的倍數*/
{
i=i+2;
j=j-1;
}
if(i<0) /*當前數在第0行*/
{
i=n-1;
}
if(j>n-1) /*當前數在最後一列，即n-1列*/
{
j=0;
}
no=i*n+j; /*找到當前數在陣列中的存放位置*/
mtrx[no]=num;
}
/*列印生成的魔方陣*/
printf("生成的%d-魔方陣為:",n);
no=0;
for(i=0; i<n; i++)
{
printf("\n");
for(j=0; j<n; j++)
{
printf("%3d", mtrx[no]);
no++;
}
}
printf("\n");
free(mtrx);
return 0;
}
int main()
{
int n;
printf("請輸入n值:\n");
scanf("%d", &n);
array(n); /*呼叫array函式*/
return 0;
}
執行結果：
linuxidc@linuxidc:~$ ./linuxidc
請輸入n值:
5
生成的5-魔方陣為:
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
知識點補充
在解決該問題時，採用的是動態分配記憶體的方式，並使用了指標變數mtrx來指向二維陣列中的元素。在演算法設計中，要儲存魔方陣需要一個二維陣列，因此再給出直接使用二維陣列來生成8-魔方陣的程式。
直接使用二維陣列生成5-魔方陣的程式碼如下：
#include<stdio.h>
#define N 8
int main()
{
int a[N][N]={0}, i, j, k, t, x, y;
i=0; /*自然數1的行標*/
j=N/2; /*自然數1的列標*/
t=N-1; /*最後一行、最後一列的下標*/
for(k=1; k<=N*N; k++)
{
a[i][j]=k;
x=i;
y=j;
if(i == 0)
i=t;
else
i=i-1;
if(j != t)
j=j+1;
else
j=0;
if(a[i][j]!=0)
{
i=x+1;
j=y;
}
}
printf("linuxidc.com生成的8-魔方陣為：");
for(i=0; i<N; i++)
{
printf("\n");
for(j=0; j<N; j++)
{
printf("%3d", a[i][j]);
}
}
printf("\n");
return 0;
}
示例輸出如下：
linuxidc.com生成的8-魔方陣為：
41 43 53 63 1 11 21 31
42 52 62 8 10 20 30 40
51 61 7 9 19 29 39 49
60 6 16 18 28 38 48 50
5 15 17 27 37 47 57 59
14 24 26 36 46 56 58 4
23 25 35 45 55 0 3 13
32 34 44 54 64 2 12 22
Linux公社的RSS地址 ： ofollow,noindex" target="_blank">https://www.linuxidc.com/rssFeed.aspx
本文永久更新連結地址： https://www.linuxidc.com/Linux/2018-10/155082.htm