C程序设计 (第四版) 谭浩强 习题 6.7
习题 6.7 输出“魔方阵”。所谓魔方阵是指这样的方阵,它的每一行、每一列和对角线之和均相等。例如,三阶魔方阵位
8 1 6 3 5 7 4 9 2 \begin{aligned}8 \ \ \ \ 1 \ \ \ \ 6\\3 \ \ \ \ 5 \ \ \ \ 7\\4 \ \ \ \ 9 \ \ \ \ 2\end{aligned} 8 1 63 5 74 9 2
要求输出 1 1 1~ n 2 n^2 n2的自然数构成的魔方阵。
IDE工具:VS2010
Note: 使用不同的IDE工具可能有部分差异。
代码块
方法:使用数组
三种情况:
- 奇数阶魔方阵
- 数字1放在第1行中间位置
- 数字2到最后一个数字,数字的行数比前1个数字的行数-1,数字的列数比前1个数字的列数+1
- 如果前1个数字的行数为1,当前数字行数为n
- 如果前1个数字的列数为n,当前数字列数为1
- 如果当前位置已排定数字,当前数字放在前1个数字下方,即列数不变,行数+1
- 非4倍偶数阶
- 魔方阵十字划分为4个奇数阶魔方阵
- 每个奇数阶魔方阵应用之前的算法
- 4个奇数阶魔方阵依次填入整个魔方阵,顺序为左上、右下、右上、左下
- 4倍偶数阶
- 偶数阶魔方阵划分为多个4*4魔方阵
- 从第一个位置填入数字1,但每个4*4魔方阵对角线的数字先不填入,先存入一个临时数组
- 按照顺序填完数字后,将对角线填入临时数组的逆序输出数字
- 对角线条件: (行数%4 == 列数%4) || (行数+列数)%4 == 3
#include <stdio.h>
#include <stdlib.h>
#define N 3 //设定阶数
void output(int matrix[][N], int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
printf("%5d", matrix[i][j]);
}
printf("\n");
}
}
//奇数阶魔方阵算法
void oddOrderMatrix(int matrix[][N], int startRow, int endRow, int startCol, int endCol, int startNum, int endNum){
int row, col, tmpRow, tmpCol;
row = startRow;
col = (endCol - startCol) / 2 + startCol;
matrix[row][col] = startNum;
for(int i = startNum + 1; i <= endNum; i++){
tmpRow = row;
tmpCol = col;
row -= 1;
col += 1;
if(row < startRow){
row = endRow;
}
if(col == endCol + 1){
col = startCol;
}
if(matrix[row][col] != 0){
row = tmpRow + 1;
col = tmpCol;
}
matrix[row][col] = i;
}
}
//非4倍偶数阶魔方阵算法
void evenOrderMatrixNon4Times(int matrix[][N], int n){
int num[4];
for(int i = 0; i < 4; i++){
num[i] = n * n * (i + 1) / 4;
}
oddOrderMatrix(matrix, 0, n/2-1, 0, n/2-1, 1, num[0]);
oddOrderMatrix(matrix, n/2, n-1, n/2, n-1, num[0]+1, num[1]);
oddOrderMatrix(matrix, 0, n/2-1, n/2, n-1, num[1]+1, num[2]);
oddOrderMatrix(matrix, n/2, n-1, 0, n/2-1, num[2]+1, num[3]);
}
//4倍偶数阶魔方阵算法
void evenOrderMatrix4Times(int matrix[][N], int n){
int i, j, k;
int temp[N*4];
int num = 1;
for(i = 0, k = 0; i < n; i++){
for(j = 0; j < n; j++){
if((i % 4 == j % 4) || ((i + j) % 4 == 3)){
temp[k++] = num;
}
else{
matrix[i][j] = num;
}
num++;
}
}
k--;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(matrix[i][j] == 0){
matrix[i][j] = temp[k];
k--;
}
}
}
}
int main(){
int matrix[N][N] = {0};
if(N % 2 != 0){
oddOrderMatrix(matrix, 0, N-1, 0, N-1, 1, N*N);
}
if(N % 2 == 0 && N % 4 != 0){
evenOrderMatrixNon4Times(matrix, N);
}
if(N % 2 == 0 && N % 4 == 0){
evenOrderMatrix4Times(matrix, N);
}
output(matrix, N);
system("pause");
return 0;
}