算法大作业.doc

算法大作业 计科14-4 田池军 5011210422目录一、概述21.2、试验环境21.3、适时地推运算的步骤21.4、递推算法的框架描述3二、实验设计32.1、双幂序列32.2、摆动数列5三、总结63.1、关于算法实验6四、参考文献7一.概述在纷繁变幻的世界中，所有的事物都会随着时间的变化而产生变化。许多现象的的变化都是有规律可循的，这种规律往往呈现出前因后果的关系。递推关系就是体现了这一变化规律。 递推算法的基本思想就是把一个复杂的庞大的计算过程转化成简单的多次重复的过程。该算法充分利用了计算机不知疲倦的特点，从头开始一步步的推出问题的最终结果。使用递推算法编程，即可使程序简便，又可以节约时间。 递推算法的首要问题是得到相邻的数据项之间的关系，机递推关系。它针对于这样一种问题：问题的解决可以分为若干个步骤，每个步骤都产生一个子集（部分结果），每个子解都是有前面若干个子解组成的。我们把这种有前面的子解得出后面的子解的规则成为递推关系。递推关系是一种搞笑的数据模型，是组合数学中的一个重要的解决办法，在组合计数中有着广泛的应用。在概率方面利用递推关系可以解决一类基本事件个个数较大的概率问题。在对多项式的求解过程中，很多情况可以使用递推算法来实现的。在行列式方面，某些N阶行列式只用初等变幻可以解决，但如果用递推算法求解显得更为容易。 递推关系不仅在个数学分支中发挥着重要的任务，有他所体现的递推思想在各学科领域中更是显示出独特的魅力。1. 实验环境语言：C+ IDE:VC6.0 操作系统： Windows XP 内存：512M CPU情况：频率20081.6G 一级缓存128K，二级缓存512K2.实施地推运算的步骤1）：确定递推变量应用递推算法解决问题，要根据问题的具体实际设置递推变量。递推变量可以简单的变量，也可以是一维或多维数组。2）：建立递推关系 递推关系是指如何从变量的前一些值推出其下一些值或从变量的后一些值推出推出其上一些值得公式（或关系）。 递推关系是递推的依据，是解决递推问题的关键。这些问题，其递推关系是明确的，大多数实际问题并没有现成的明确的递推关系，需要根据问题的具体条件，不断尝试推理，才能确定问题的递推关系。3）：确定初始条件对确定的递推变量，要根据问题最简单情形的数据确定递推变量的初始值，这是地推的基础。4）：对递推过程进行控制 递推过程不能无休止的执行下去。递推过程在什么时候结束，满足什么条件结果，这是递推算法必须考虑的递推过程控制问题。3.递推算法的框架描述 1）简单顺推算法（即从前往后推） 2）简单逆推算法（即从后往前推） 3）二维数组顺推算法4） 多关系分级递推算法二. 实验设计 本次试验主要探讨双幂序列以及幂积序列这两个涉及幂的典型案例的求解1. 双幂数列1) 案例提出设x，y为非负整数，设计集合M=2x,3y|x=0,y=0的元素由小到大排列的双幂数列第n项与前n项之和。双幂序列的程序实现/双幂数列求解#includevoid main()int k,n,t,p2,p3;double a,b,s,f100;printf(求数列的第n项与前n项和,请输入n:);scanf(%d,&n);f1=1;p2=0;p3=0;a=2;b=3;s=1;for(k=2;k=n;k+)if(a=0,y=0 的元素不大于指定整数N的个数，并求这些元素从小到大排序的第m项。程序设计#includevoid main()int i,n,max,a10000;printf(请输入项数n:);scanf(%d,&n);a1=1;max=0;for(i=2;imax) max=ai;printf(a(%d)=%dn,n,an);printf(摆动数列前%d项中最大项有:,n);for(i=2;i=n;i+)if(ai=max) printf(a(%d)=,i);printf(%dn,max);测试结果已知数列：a(1)=1,a(2i)=a(i)+1,a(2i+1)=a(i)+a(i+1);i为整数，试求该数列的第m() 项与前n项中哪些项大？最大值多少？三.总结 关于算法通过一学期学习算法结课了回头想想，算法这门课，说句实话，真的没学到什么东西，上课的时候看着书中的分析过程，在听着李旭老师那幽默的讲课方式，感觉会，但是自己一上手做却发现在没有老师的指导下，真的不知道该如何下手，很迷茫，很无助。通过这一现象，使我联想到现在的我们，有人说大学是一个平台，有的人通过这个平台，走向了另一个更大的舞台，但也有很多人而走这个平台上掉下去。现在的大学生非常非常的多，我们上大学就是为了将来招上份好工作，为自己幸福生活打下基础。大学主要是靠自学，考老师在课堂上讲的根本学不到东西，好多时候，听老师讲课的时候，什么都会，自己下来的时候却不知道如何下手，造成了眼高手低，这个现象是非常不好的。所以以后无论在学习或生活中，一定要一步一个脚印。 关于实验 通过本次实验，是我知道并了解了，算法的基本步骤，分析过程。到最后得出结果，这是一个非常困难的过程，我们不应该只为了得到最后的结果，而忽视掉其中的过程，过程是最重要的，我们要了解和熟练的掌握，算法的分析过程，授之以鱼，不如授之以渔，只知道了方法，才能更好的去学习。 参考文献 王红梅.算法设计与分析.北