N阶魔阵问题数据结构课程设计.doc

《N阶魔阵问题数据结构课程设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、N阶魔阵问题2011年6月14日数据结构课程设计一、实验题目给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，…，n2组成。魔阵的每行元素之和，每列元素之和以及主、副对角线之和均相等。既对于给定的奇数n以及i=1，2，3，…，n。魔阵a满足以上条件。要求：要求输出结果的格式要具有n阶方阵的形式。提示：依次将自然数填入方阵中，共填n轮，每轮填n次。第一轮的第一次，将1填入方阵的中间一行的最后一列位置。设前一次填入的位置是aij。（1）每轮中第2至第n次将数填入ai+1,j+1,若遇到下列情况之一，则填写位置按以下

2、规则调整：①.aij是最后一列（即j=n）位置，则将下一个数填入ai+1，1；②.aij是最后一行（即i=n）位置，则将下一个数填入a1，j+1；（2）新一轮的第一次填入a1,j-1.二、实验目的一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；二、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；三、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；五、输出一个奇数N阶的具有矩阵形式魔阵。三、

3、实验内容（一）需求分析1.定义一个整形变量order存放魔术矩阵的阶数order为一整形变量，是通过键盘来进行输入的阶数，也是进行分析的条件，可通过形参的值传递到子函数中，再对魔术矩阵按照进行排列，要求如下：n阶魔方矩阵是将自然数放置在一个的方阵中，同时要保证该矩阵每行﹑每列及两条主对角线（即主对角线和副对角线）上的数值之和相等的要求。这似乎是一件比较复杂的事情，其实，求解“魔方矩阵”（奇数阶）有一个很巧妙的算法，这个算法的描述如下：（1）初始化“魔方矩阵”，即将所有元素置为0；（2）首先将1放置在第1行的中间位置。（3）将之间的整数按照下列

4、规则依次放置在方阵中：如果上一个数值所放置的位置的右上方为空（该位置还没有放置数值），则当前数值被放置在一个数值的右上方；否则被放置在上一个数的正下方。很显然，“魔方矩阵”中的数据具有明显的二维排列关系，因此应该选用二维数组表示待求解的“魔方矩阵”。（4）对于给定的奇数n以及，魔方矩阵满足的条件用数学表示如下：定义为整型，将其返回，在主程序中打印出来。（5）显示“魔方矩阵”；2.算法流程图在主函数中定义order为整型，由键盘输入；定义整型变量row，column来描述数组插入的位置；开始输入order初始化输入的是偶数超出取值范围row=0

5、;column=order/2将1置于第1行中间NY右上方空计算右上方的下标count+1count计算正下方的下标放置countYYNcount≤N2count输出matrix结束（二）概要设计（1）定义的存储结构描述：首先在函数首部定义：#defineMAXSIZE31定义一个数组matrix[MAXSIZE][MAXSIZE];对n阶魔术矩阵进行存储；其中matrix[MAXSIZE][MAXSIZE]的参数类型为整型，此数组的最大值定义为31，如果超出则会发生错误，定义一个整型变量order，将order的值传到形参，在算法中对ord

6、er阶的矩阵排列，使其满足下列条件：因此称这样的矩阵为魔术矩阵；在算法程序中定义matrix[MAXSIZE][MAXSIZE];其中定义为整型，将其返回，在主程序中打印出来。算法分析：①．下面一段程序是用来限制输入的魔方矩阵的阶数所用：if(order>MAXSIZE){printf("取值超出范围：");printf("*******************************");}elseif(order%2==0){printf("输入有错误，请重新输入：");printf("**************

7、*****************");}②．下面一段程序是求解N阶魔方矩阵最关键的部分：首先将1放置在第1行的中间位置。将之间的整数按照下列规则依次放置在方阵中：如果上一个数值所放置的位置的右上方为空（该位置还没有放置数值），则当前数值被放置在一个数值的右上方；否则被放置在上一个数的正下方。row=0;/*startoffromthemiddle*/column=order/2;/*ofthefirstrow.*/for(count=1;count<=order*order;count++){matrix[row][column]=coun

8、t;/*putnext#*/if(count%order==0)/*movedown?*/row++;/*YES,movedownonerow*/else{/*co