算法导论
课程实验
练手题二幻方矩阵
学号：SG13225146
姓名：张添程
日期：2013.11.21
目录
实验要求 (3)
实验设计与实现 (4)
设计思路 (4)
输入的判定 (4)
幻方矩阵的实现 (5)
幻方矩阵的输出 (6)
幻方矩阵的验证 (7)
实验结果 (9)
实验总结 (12)
参考资料 (12)
附录——程序源代码 (13)
幻方矩阵
学号：SG13225146 姓名：张添程
实验要求
幻方是一种很有意思的数字矩阵，在很早著名的九宫八卦阵就与幻方有关。
幻方的定义为：
1 到N*N 的整数填入N*N的方格中，每行和每列以及对角线的数字之和必须是相等的。你作为八卦公司的顶级程序员，现在需要你解决一个问题，将任意奇数阶的幻方找出来。
输入：
输入包括多个测试集，每行为一个正奇数N(1 <= N < 1000)，0作为输入的结束且不需要处理。
输出：
对于输入的每一个N，输出一个它所对应的N阶幻方，如果存在多个，任意一个即可。
每个幻方为N*N的矩阵，
对于每个幻方，每行输出幻方的一行，每行中的数字之间用一个或多个空格分开。不同的幻方之间用一个空行分开。
Sample Input
1
3
Sample Output
1
4 9 2
3 5 7
8 1 6
实验设计与实现
设计思路
算法采用二维数组来代替矩阵，使用百度百科中的幻方矩阵在N为奇数时的实现算法，即使用斜45度算法来实现。
程序结构上使用while(1)实现无限循环，在输入n = 0时终止，在输入n > 0且为奇数时输出幻方矩阵，在其他情况显示输入错误。
实验代码参照《高质量C/C++编程指南》标准格式书写。
输入的判定
当输入为0时终止，当输入为正奇数数输出幻方矩阵，其他情况输出输入错误。
幻方矩阵的实现
N 为奇数时
(1) 将1放在第一行中间一列;
(2) 从2开始直到n×n止各数依次按下列规则存放：
按45°方向行走，如向右上
每一个数存放的行比前一个数的行数减1，列数加1
(3) 如果行列范围超出矩阵范围，则回绕。
例如1在第1行，则2应放在最下一行，列数同样减1;
(4) 如果按上面规则确定的位置上已有数，或上一个数是第1行第n列时，则把下一个数放在上一个数的下面。
初始化矩阵。
幻方矩阵的实现：左上45度移动算法。
幻方矩阵的输出
按行输出一维数组使用空格间隔，按列输出二维数组。
幻方矩阵的验证
分别求每行的各元素之和。
分别求每列的各元素之和。
分别求两条对角线的各元素之和。
观察各行、列、对角线之和是否相等。
实验结果
按照题目要求输入1、3、0（0为终止条件），显示结果。
输入5观察结果。
输入7观察结果。
输入偶数、负数和0观察结果。验证错误判定与终止条件。
极限情况性能验证（按照题目要求验证n=999）。
实验总结
通过实验，加深了对二维数组的理解。
实验思考了2天左右，从开始写代码到调试完成花了大约2个小时，对个人的算法能力与代码能力都有提高。
个人对本程序还是比较满意的，但是算法的实现是参考的百度百科完成的，并非自己独立思考出来的，所以比较遗憾。
后续如果有时间和精力的划会加入偶数的幻方矩阵的实现。
参考资料
1、《高质量C/C++编程指南》————————————————————林锐
2、百度百科——魔方矩阵
附录——程序源代码
/********************************************************************/ /* Copyright (C) SSE-USTC, 2013-2014 */ /* */ /* FILE NAME : 幻方矩阵.cpp */ /* PRINCIPAL AUTHOR : Zhangtiancheng SG13225146 */ /* LANGUAGE : C */ /* TARGET ENVIRONMENT : ANY */ /* DATE OF FIRST RELEASE : 2013/11/21 */ /* DESCRIPTION : N为奇数的幻方矩阵的实现 */ /********************************************************************/
/*
* Revision log:
*
* Created by Zhangtiancheng,2013/11/25
* Debug and Test by Zhangtiancheng,2013/11/25
*
*/
#include
#include
#define N 1000
int main()
{
printf("————————幻—方—矩—阵————————\n");
printf("—————————SG13225146—————————\n");
int n = 0;
while(1)
{
printf("Please input the step of the martix:\n");
scanf("%d", &n);
/*程序终止条件*/
if (n == 0)
{
printf("The End\n");
return 0;
}
/*幻方矩阵的实现*/
else if (n > 0 && n % 2 == 1 && n < N)
{
int *a[N-1];
int b[N-1] = {0}, c[N-1] = {0}, d[2] = {0};
int i = 0, j = 0, k = n / 2;
for (i = 0; i <= 999; i++)
a[i] = (int *)malloc(sizeof(int) * (N - 1));
for (i = 0; i <= 999; i++)
{
for (j = 0; j <= 999; j++)
a[i][j] = 0;
}
j = 0;
a[j][k] = 1;
/*幻方矩阵的实现：左上45度移动算法*/
for(i=1; i { j = j-1; k = k-1; if(j<0) j += n; if(k<0) k += n; while(a[j][k]!=0) { k++; j = j+2; if(k>n-1) k = 0; if(j>n-1) j = j - n; } a[j][k] = i + 1; } /*幻方矩阵的输出*/ for(j=0; j { for(k=0; k { printf("%2d ",a[j][k]); } printf("\n"); } /*幻方矩阵的验证：行、列、对角线和的输出*/ for(j=0; j { for(k=0; k { b[j] += a[j][k]; } printf("第%d行之和：%2d\n",j + 1,b[j]); } for(k=0; k { for(j=0; j { c[k] += a[j][k]; } printf("第%d列之和：%2d\n",k + 1,b[k]); } for(j=0; j { k = j; d[0] += a[j][k]; } printf("左上右下对角线之和：%2d\n",d[0]); for(j=0; j { k = n - 1 - j; d[1] += a[j][k]; } printf("左下右上对角线之和：%2d\n",d[1]); } /*输入错误判定*/ else { printf("The input is error!\n"); } } }
相关主题
文本预览