奇数阶魔方阵算法分析

PAGEPAGE1奇数阶魔方阵算法分析第一篇：奇数阶魔方阵算法分析C语言程序设计教案奇数阶魔方阵一、提出问题所谓“奇数阶魔方阵”是指n为不小于3的奇数的魔方阵。这类魔方阵的形式多样，这里我们仅讨论其中的一种形式的正规魔方阵。例如：3阶、5阶和7阶的魔方阵如图3–4所示。3039*********416357，461320XX，***2192***211***2414322314049图3–43阶5阶和7阶魔方阵***54443121120XX易知道，这三个魔方阵的魔方常数分别是15、65和175。现在要求给出：能让计算机自动输出类似图3–4所示的n阶奇数魔方阵的算法，其中n为任意给定的一个不小于3的奇数。二、简单分析决定“奇数阶魔方阵”的关键是要按要求决定其方阵中的各个数字。观察图3–4中的三个奇数阶魔方阵，不难发现：1．由于是正规魔方，故所填入的n2个不同整数依次为1、2、3、…、n2；2．各行、列和对角线上的数字虽各不相同，但其和却是相同的。这表明，其魔方常数可由公式n(n2+1)/2得到。3．数字在阵列中的次序，并没有遵从阵列单元的行、列下标的顺序，但数字“1”却始终出现在阵列第一行的正中间位置，而数字“n2”也始终出现在阵列第n行的正中间位置，这说明阵列中的数字排列应该是有一定规律的。通过对两个奇数阶魔方阵的简单分析，下面几个基本问题必须得到解决：◆奇数阶魔方阵中的数字有些什么规律？◆数字“1”的位置应如何确定？C语言程序设计教案三、设计准备1．奇数阶魔方阵中的数字规律通过对奇数阶魔方阵的分析，其中的数字排列有如下的规律：（1）自然数1出现在第一行的正中间；（2）若填入的数字在第一行（不在第n列），则下一个数字在第n行（最后一行）且列数加1（列数右移一列）；（3）若填入的数字在该行的最右侧，则下一个数字就填在上一行的最左侧；（4）一般地，下一个数字在前一个数字的右上方（行数少1，列数加1）；（5）若应填的地方已经有数字或在方阵之外，则下一个数字就填在前一个数字的下方。（一般地，n的倍数的下一个数字是在该数的下方。）816按照上述的规律，我们来完成3阶的魔方阵：3574921第一步：将“1”填入1行2列的位置，即（按规律（1））；1第二步：将“2”填入3(最后)行3(=2+1)列的位置，即（按规律2（2））；1第三步：将“3”填入2行1列的位置，即3（按规律（3））；21第四步：将“4”填入3行1列的位置（“3”的下面）；即3（按规律（5））422C语言程序设计教案1第五步：将“5”填入2行2列的位置；即35216（按规律（4））；4第六步：将“6”填入1行3列的位置，即352（按规律（4））；416第七步：将“7”填入2行3列的位置（“6”的下面），即357（按规律（5））；42816第八步：将“8”填入1行1列的位置，即357（按规律（3））；42816第九步：将“9”填入3行2列的位置，即357（按规律（2））。492至此，一个3阶魔方阵构造完成了。2．数字“1”的位置确定方法由于数字“1”要填写在魔方阵第一行的正中间，因此我们只需要确定第一行的正中间单元的列下标即可。考虑到对于一个奇数阶魔方阵来说，它的每一行都有奇数个位置，所以“正中间的位置”就必然存在。容易知道，一个n（为奇数）阶魔方阵第一行的正中间单元的列下标为整数(n+1)/2。于是数字“1”应填写在魔方阵列的第1行第(n+1)/2列处。C语言程序设计教案四、实施步骤1．算法编制的工作顺序：有了上述的设计准备，我们所要的算法可按如下的工作顺序编制：第一步：输入魔方阵的阶数n（为奇数），并以此定义一个二维数组；第二步：确定所谓“正中间位置”的列下标值，以及应填入的最大数字；第三步：进行完成魔方阵的填写工作；第四步：输出已完成的奇数阶魔方阵。2．变量设置：N：表示魔方阵的阶数（为奇数）；A：表示魔方阵的二维数组；I：数组A的行序号；J：数组A的列序号；R：填入的数字；S：对角线上各数字之和。3．参考框图：如图3–5所示。4．框图说明：整个框图应分为三个功能部分：第一个部分的功能是完成奇数N的输入，并定义二维数组，完成有关元素的数值计算，同时能实现当N不是奇数时自动结束。图3–5处理“奇数阶魔方阵”问题的框图第二个部分的功能是完成魔方阵的填写工作。填写并不是按数组A的下标顺序进行，而是通过对有关规律的判断确定下标I和J的不同值来进行。其中涉及到了判断“R是N的整数倍？”，这可以通过判断是否有等式R–INT(R/N)N=0成立来实现。第三个部分的功能是完成输出魔方阵和计算相应魔方常数的工作。计算相应魔方常数的工作是通过对魔方阵的对角线中各元素数值来实现，即在准备输出打印元素A(I,I)时，通过累加方式S=S+A(I,I)来实现。C语言程序设计教案5．参考算法第01步：输入非负整数N，并定义数组A(N,N)；第02步：若N–INT(N/2)2=0，则结束。第03步：让J(N+1)/2,CNN,且I1；第04步：让R1；第05步：若R>C,则执行第16步；第06步：让A(I,J)R；第07步：若R–INT(R/N)N=0,则执行第13步；第08步：让II–1；第09步：若I+1=1，则让IN；第10步：让JJ+1；第11步：若J–1N，则执行第15步；第12步：让J1,并执行第15步；第13步：让II+1。若I–1N，执行第15步；第14步：让I1；第15步：让RR+1，执行第05步；第16步：让S0,I1；第17步：若I>N,则执行第24步；第18步：让SS+A(I,I)；第19步：让J1；第20XX若J>N,则执行第13步；第21步：在位置4J处输出A(I,J)；第22步：让JJ+1，并执行第20XX第23步：换行，让I=I+1,并执行第17步；第24步：输出S，结束。参考算法的编制与框图稍有不同，但功能是一样的。其中：第01步至第03步为第一部分，完成奇数的输入，以及有关的准备工作。当输入的N不是奇数时，会自动结束。第04步至第15步完成魔方阵的填写工作。第16步至第24步完成输出魔方阵和计算相应魔方常数的工作。C语言程序设计教案五、评估反思应当说，奇数阶魔方阵的形式是多种多样的，这里我们仅仅只对其中的一种形式加以讨论。这里所编制的参考算法从理论上看可以实现对指定形式的任何大小“奇数阶魔方阵”的输出，但在实际输出时应考虑输出设备的相关条件。在参考算法中，第04步至第15步这部分是整个算法的核心部分，其功能是完成整个魔方的数字填入工作，因此其编制的思想、用到的一些处理方阵元素的技巧和经验，应引起我们的注意。1．充分利用规律间共同特性。在这部分里我们通过若干次对下标值的判断，巧妙地将奇数阶魔方阵应当遵循的规律（2）、（3）和（4）结合起来，使魔方阵的填写工作能得以顺利进行。这是因为奇数阶魔方阵要求的五个规律中，规律（2）、（3）和（4）与单元的下标有直接的关系。2．选择首次判断对象的要求。在这部分里我们首先进行的是对填入数字R是否是阶数N的整数倍的判断，这实际上是将奇数阶魔方阵的规律（5）作为主要的判断标准。那么为什么不用另外的四个规律来作为主要的判断标准呢？这主要是考虑到对于要填入的数字，在奇数阶魔方阵的五个规律中，只有规律（5）将该数字直接与阶数联系起来，而另外四个规律则没有（仅仅与填入单元的下标值有直接的联系）。这告诉我们，算法的编制应注意那些具有单一性特点的事实、特性或规律等等。3．有关魔方常数的得到。要得到魔方常数，最直接的方法是通过公式S=n(n2+1)/2来计算，但这样做不能显示整个魔方阵的构造是否正确。在参考算法中，我们是通过累加魔方阵对角线中各元素数值来实现的，这样做的好处有，其一是体现了数字累加方式在算法编制中的作用，其二是显示了所构造的魔方阵是否正确。当然，我们也可以通过累加魔方阵某行或某列中各元素数值来实现，只不过设计的步骤要稍多一些，因为需要从n行（列）中确定某行（列）的步骤。4．关于魔方阵的验证。本参考算法中没有设计利用魔方常数来判断所完成的方阵是否是魔方阵的步骤，但设计这一功能并不困难。比较方便的做法可以为：在第一部分加入用公式计算魔方常数的步骤，将第三部分分成输出方阵和验证方阵两部分。在验证部分里，设计分别计算各行、各列及对角线中各数字和的步骤，以及将这些数字和与前面计算出的魔方常数进行比较的步骤。若对此有兴趣，不妨自己动手试试。C语言程序设计教案六、要点回顾1．数学思想：构成奇数阶魔方阵应当遵循的五个规律；2．常用公式：判断“R是N的整数倍”的等式R–INT(R/N)N=0；3．算法技巧：利用累计方式计算魔方常数和完成魔方阵输出的方法。4．实用方法：判断整数R是否是整数N的整数倍的方法。第二篇：魔方阵实验报告<<魔方阵>>实验报告一．实验目的1.设计数据结构；2.设计算法完成任意n阶魔方阵的填数；3.分析算法的时间复杂度。二．实验内容魔方阵，又叫幻方阵，在我国古代称为“纵横图”。它是在一个n*n的矩阵中填入1到n*n的数字(n为奇数)，使得每一行，每一列，每条对角线的累加和都相等。三．程序代码源程序：#includevoidSquare(intn){inta[9][9];intp=0,q=(n-1)/2;a[0][q]=1;//在第0行的中间位置填1for(inti=2;i<=n*n;i++){p=(p-1+n)%n;//求i所在行号q=(q-1+n)%n;//求i所在列号if(a[p][q]>0){p=(p+2)%n;q=(q+1)%n;//这两句进行了修改，否者得不到正确的答案，切记切记！！}//如果位置(p,q)已经有数，填入同一列下一行a[p][q]=i;}for(p=0;p{for(q=0;qcout<cout<<'n';}}voidmain(){intn;cout<<=9):”;cin>>n;cout<0)p=(p+1)%n;，这个语句是错的。之所以会有这样的错误，是由于错误的理解了“如果位置(p,q)已经有数，填入同一列下一行”这一句的意思，这句的意思是填入原数的下面，而不是即将填入的那个数但又已填入数的那个数的下面。解决方法:将该语句改成：if(a[p][q]>0){p=(p+2)%n;q=(q+1)%n;}，这样就可以了。3.由于数组a[][]是在Square函数中定义的，因此将数组数据输出的语句就只能放在Square函数中实现。第三篇：C语言程序编程：输入奇数,输出n阶幻方矩阵#include#defineMAX100voidhuanFang(intn){inta[MAX][MAX]={0};//初始化数组都为0inti,j;intm,k;//当前位置intp,q;//下一个位置intdata=0;m=0;k=n/2;while(dataq=k+1;//右if(p<0&&q=0){//上出框//printf(“qianshangchu:p=%d,q=%dn”,p,q);p=n-1;//下边放//printf(“houshangchu:p=%d,q=%dn”,p,q);}elseif(p>=0&&p//printf(“qianyouchu:p=%d,q=%dn”,p,q);q=0;//左边放//printf(“houyouchu:p=%d,q=%dn”,p,q);}elseif(p<0&&q==n){//斜出框//printf(“qianxiechu:p=%d,q=%dn”,p,q);p=m+1;//下格填q=k;//printf(“houxiechu:p=%d,q=%dn”,p,q);}if(a[p][q]!=0){//排重//printf(“qianchongpai:p=%d,q=%dn”,p,q);p=m+1;//下格填q=k;//printf(“houchongpai:p=%d,q=%dn”,p,q);}m=p;k=q;}for(i=0;iprintf(“%d”,a[i][j]);}printf(“n”);}}voidmain(){intn;//判断是否输入的是奇数while(1){printf(“pleaseinputnjie,nisoddn”);scanf(“%d”,&n);if(n%2==1)break;}huanFang(n);}第四篇：数据结构算法设计与分析数据结构算法设计与分析、计算机网络、计算机组成原理、操作系统原理、编译原理、数据库原理及应用、软件工程、软件测试等计算机基础理论课程；网页制作、程序设计Java、JSP程序设计、Oracle、XML程序设计、计算机网络、SSH（Struts+Spring+Hibernate）框架、JavaEE程序设计、Ajax程序设计、Linux+PHP+MySQL程序设计、Android手机开发、UML系统分析与设计、性能测试、自动化软件测试、软件质量保证、毕业设计及项目综合实训等。数据结构、计算机网络、计算机组成原理、操作系统原理、编译原理、数据库原理及应用、金融学概论、西方经济学等基础理论课程；网页制作、程序设计Java、JSP程序设计、J2EE程序设计、SQLServer数据库、Oracle数据库、Linux操作系统、UML系统分析与设计、软件工程、XML程序设计、SSH框架、金融市场学、ERP财务管理、管理信息系统、投资银行学、商业银行学、国际金融管理、毕业设计及项目综合实训等专业课程。数据结构、计算机网络、计算机组成原理、操作系统原理、数据库原理及应用、软件工程、软件测试等计算机基础理论课程；网页制作、程序设计Java、JSP程序设计、J2EE程序设计、XML程序设计、Ajax程序设计、SSH框架、Android手机开发、Linux+PHP+MySQL程序设计、SQLServer数据库、Linux操作系统、UML系统分析与设计、软件项目管理、行业标准与规范、IT服务管理、IT职业英语、毕业设计及项目综合实训等专业课程第五篇：算法设计与分析学习心得算法设计与分析学习心得班级：物联网120XX姓名：刘潇学号：1030612129一、实验内容：这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题，动态生成二维数组，对话框下拉列表，排序问题。二、学习掌握：基本程序描述：（1）货郎担问题：货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有（n一1）！条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。货郎担的程序实现了利用穷举法解决货郎担问题，可以在城市个数和各地费用给定的情况下利用穷举法逐一计算出每一条路线的费用，并从中选出费用最小的路线。从而求出问题的解（2）费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是对包含具有约束条件的最优化问题的所有可行解的解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。（3）Mfc：在下拉列表框中添加内容程序，在下拉列表对应的函数中利用addstring添加需要的内容。首先定义下拉列表框为ccombox型，并定义其属性名，利用addstring函数可以任意添加需要的内容。a排序问题:快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(n㏒n)。算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。b对话框下拉列表：这个项目简单易懂，轻松实现。三.疑问与总结：货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用