计算机算法课程设计.docVIP

一 前言 算法研究是计算机科学的核心。近年来，算法领域取得了很多重要的进展。这些进展包括快速算法的开发，如发明了傅立叶变换快速算法，以及不存在有效算法的本质问题的惊人发现。这些结果点燃了计算机学者对算法研究的兴趣。算法设计与分析已成为一个受到广泛注意的领域。 这学期老师带领我们学了很多算法，比如排序法、分治法、分支界限法、回溯法、贪心算法、动态规划…等。可能是学习不够深入，所以掌握的算法并不多，本文将重点探讨利用数组元素穷举法解决一些关于矩阵中每一行最大值的问题。 二 正文 2.1设计的目的和意义 通过一学期对《计算机算法的设计与分析》这门课程的学习，我认为老师不按课本来讲课，确有一定道理，因为这门课程给我的感觉是很难，老师尽量没有用课本上的程序，而是自己写一些简单的程序用自己对算法的理解来授课，这一点值得我们的肯定，本文设计的目的一部分是对自己学习一学期这门课程的一个交代，另一部分是对付出过辛勤劳动的老师一个交代，希望自己的劳动也能得到老师的肯定和支持。 2.2设计内容 已知：有一个3*4矩形。 求：每一行中的最大值并与第一列交换。 2.3设计思路 穷举法就是在循环控制的条件下，依次参与运算，看能不能满足条件，能满足条件的就打印出来，不能满足就不打印。 下面是思路的具体步骤： 首先，定义一个二维数组，用来存放3*4矩形，即定义int aa[3][4]。 然后，在每维4个元素之间比较，第一元素和第二元素比较谁大，谁大谁就和第三元素比较，再看谁大，再用大者跟第四元素对比···这样就可以找到这维数中的最大值。 最后，用这个最大值和第一个数进行交换就是了。利用这种方法对其他维数进行比较，并进行交换，这样就可以解决问题了。 因为每维数组都要求最大值并进行交换，所以要用双重for语句，进行“穷举法”对比，最后找到最大值，从而进行交换。最后还要用双重for语句输出交换后的该两维数组。 下面用一个简单的实例对算法进行分析，如第一行四个元素（9,8,7,11）的比较，如图： 由上图可知第一行的最大值是11,然后将11与第一列第一个元素交换 由上图可知第二行的最大值是6，然后将6与第一列第二个元素交换 由上图可知第三行的最大值是25，不用交换，即其本身 由于每维数组都要求最大值进行交换，所以要用双重for语句，进行“穷举法”对比，最后找到最大值，从而进行交换。 1)利用双for循环语句进行穷举法对比找到每一行的最大值，并把最大值赋给aa[x][p] 代码如下： for(x=0;x=2;x++) { p=0; for(y=1;y=3;y++){ if(aa[x][y]aa[x][p]) {p=y; 2）最把大值与第一个元素交换，代码如下： t=aa[x][0]; aa[x][0]=aa[x][p]; aa[x][p]=t; 3)最后输出交换后的数组，代码如下： for(x=0;x=2;x++) {for(j=0;j=3;j++) printf(%d\t ,aa[x][j]); printf(%d\t ,aa[x][p]); printf(\n); 4)算法代价分析 由主函数的穷举法可知，时间复杂度为O(3*3)=O(9),最后输出的时间复杂度为O(3*4)=O(12),由此可知，其时间复杂度为O(n2),与最优时间复杂度O(nlog2n)有点差别,还有待改进。 2.4实现方案程序 1)实现方案的完整程序如： void main() { int a,x,y,p,j,t; int aa[3][4] = {{9,8,7,11},{4,6,2,1},{25,3,19,10}};/定义二维数组 for(x=0;x=2;x++) { p=0; for(y=1;y=3;y++){ if(aa[x][y]aa[x][p]) {p=y;/ 利用双for循环语句进行穷举法对比找到每一行的最大值，并把最大值赋给aa[x][p] t=aa[x][0]; aa[x][0]=aa[x][p]; aa[x][p]=t;/ 最把大值与每一行第一个元素交换 } } } for(x=0;x=2;x++) {for(j=0;j=3;j++) printf(%d\t ,aa[x][j]); pri