学生信息管理系统的设计与实现—校友录、留言板、学生信息管理、信息发布模块.doc
《学生信息管理系统的设计与实现—校友录、留言板、学生信息管理、信息发布模块.doc》由会员分享,可在线阅读,更多相关《学生信息管理系统的设计与实现—校友录、留言板、学生信息管理、信息发布模块.doc(55页珍藏版)》请在文库网上搜索。
1、erface .30Express thanks.32推箱子问题的设计与实现1第一章:概述1.1 课题来源对计算机科学来说,算法(Algorithm)的概念是至关重要的,大型软件系统的开发中,设计出有效地算法将起着决定性的作用。本课题来源于一个经典的小游戏推箱子,相信玩过的朋友都会对这个游戏有很深的感触。推箱子游戏在趣味性的同时要求玩家对游戏的每一步都有深入的思考,不然很容易就把箱子推进无法动弹的死角。抛开游戏性,我发现在游戏的过程中,要尽快找出推箱子的路径,其中蕴含着计算机算法解决现实问题的经典模式。进一步的思考和算法研究后,了解到分支限界法是解决该问题的最简单有效的方法,通过对该课题的研究
2、,可以在不失游戏趣味性的同时,熟悉算法解决实际问题的具体步骤,并且能在算法实现的过程中对算法做进一步的分析改进,尽可能地减少空间和时间资源。1.2 算法理论1.2.1 算法起源跟介绍“算法”即演算法的大陆中文名称出自周髀算经 ;而英文名称Algorithm 来自于 9 世纪波斯数学家 al-Khwarizmi,因为 al-Khwarizmi 在数学上提出了算法这个概念。 “算法”原为“algorism“,意思是阿拉伯数字的运算法则,在 18 世纪演变为“algorithm“。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是 Ada Byron 于 1842 年为巴贝奇分析机编写求解伯
3、努利方程的程序,因此 Ada Byron 被大多数人认为是世界上第一位程序员。因为查尔斯巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。 因为“well-defined procedure“缺少数学上精确的定义,19 世纪和 20 世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要作用的。推箱子问题的设计与实现2算法(Algorithm)是一系列解决问题的清晰指令,也就是说,能
4、够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。一个算法应该具有以下五个重要的特征: 1、有穷性: 一个算法必须保证执行有限步之后结束; 2、确切性: 算法的每一步骤必须有确切的定义; 3、输入:一个算法有 0 个或多个输入,以刻画运算对象的初始情况,所谓 0 个输入是指
5、算法本身定除了初始条件; 4、输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的; 5、可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。算法复杂度分析;同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 1、时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并
6、且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。 (2)时间复杂度 在刚才提到的时间频度中,n 称为问题的规模,当 n 不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模 n 的某个函数,用 T(n)表示,若有某个辅助函数 f(n),使得当 n 趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称 f(n)是 T(n)的同数量级函数。记作 T(n)=O(f(n),
7、称 O(f(n) 为算法的渐进时间复杂度,简称时间复杂度。 在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如 T(n)=n2+3n+4与 T(n)=4n2+2n+1 它们的频度不同,但时间复杂度相同,都为 O(n2)。 按数量级递增排列,常见的时间复杂度有: 常数阶 O(1),对数阶 O(log2n),线性阶 O(n), 线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),., k 次方阶 O(nk),指数阶 O(2n)。随着问题规模 n 的不断增大,上述时间复杂度不断增大,算法的执行效率越低。 推
8、箱子问题的设计与实现32、空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。1.2.2 常 用 经 典 算 法 简 介递 归 和 分 治 :分治的设计思想是将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。如果原问题可以分割成 k 个之问题,1k=n,并且这些子问题都可解,并可以利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方
9、便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易求出其解。动 态 规 划 :动态规划算法与分支法类似,其基本思想也是将待求解的问题分解成若干子问题,先求解子问题,然后由这些子问题的解得出原问题的解。与分治法不同的是,适合用动态规划法求解的问题,经分解得到的子问题往往不是相互独立的。若使用分治法来解决这些问题,则分解得到的子问题树木太多,以至于最后解决原问题需要耗费的时间成指数级增长。用分治发求解时,有些子问题被重复计算了很多次。如果我们能够保存已经得到的子问题的答案,而在需要的时候再找出已经求出的答案,这样就可以比表面大量的重复计算,
10、从而得到多项式时间算法。因此,动态规划算法适用于解决最优化问题,通常有四个步骤设计:1. 找出最优解的性质,并且刻画其结构特征。2. 递归地定义最优值。3. 自底向上的方式计算求出最优值。4. 格局计算最优值得到的信息,构造最优解。贪 心 算 法 :贪心算法通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部最好的选择,也就是贪心选择可以用贪心法解决的问题,一般包括两个基本性质:贪心选择性质和最优子结构性质。贪心选择性质:贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来实现。贪心算法通常以自顶向下的方式进行,以迭代的方式做出相继的贪心选择,每做一次
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 学生 信息管理 系统 设计 实现 校友录 留言板 信息 发布 模块