资源描述：
《软件技术基础第一章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Chap01算法信息科学与技术学院程勇2009年秋课程提纲Chap00课前导学Chap01算法Chap02基本数据结构及其运算Chap03查找与排序技术Chap04资源管理技术Chap05数据库技术Chap06应用软件设计与开发技术Chap07课程复习本章提纲1.1算法基本概念1.2算法描述语言1.3算法设计基本方法1.4算法复杂度分析1.5课后作业1.6本章小结算法定义算法是什么？ß一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，明确的，此顺序将在有限的次数下终止。-ShiliangXuß算法是解决某个特定问题的一种方法或一
2、个过程。ß算法是任何定义好了的计算程式，它取某些值或值的集合作为输入，并产生某些值或值的集合作为输出。-ThomasH.Cormen算法的特性可行性ß算法中每一个步骤都是可实现的；ß算法执行的结果能达到预期的目的；确定性ß算法的每一步骤必须有清楚的语义，即无二义性。有穷性ß算法必须在执行有限个步骤之后终止。输入ß一个算法有零个或多个数据输入。输出ß一个算法产生一个或多个输出。算法基本要素两种基本要素组成：ß算法控制结构o顺序结构o选择结构o循环结构ß数据的运算与操作o算术运算(+,-,*,/)o逻辑运算(&&,
3、
4、,!)o关系运算(>
5、,>=,<,<=,==,!=)o数据传输(赋值,输入,输出)算法设计过程通过对问题进行详细地分析，抽象出相应的数学模型;确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法;选用某种语言将算法转换成程序;调试并运行这些程序;算法描述语言算法描述语言是一种面向人而非机器的算法描述工具，其他的描述工具还有：ß传统流程图ßN-S结构化流程图ß伪代码算法描述语言要求ß具有良好的可读性ß无歧义性ß容易转换为程序设计语言算法描述语言(续)算法描述语言语法ß符号与表达式o符号是字母开头的字母数字组合，表示变量名、数组名和语句标号o算术
6、运算符(+、-、*、/)o关系运算符(==、!=、<、>、<=、>=)o逻辑运算符(and、or、not)ß赋值语句oa=bß控制转移语句oifcthenoifcthenelse算法描述语言(续)ß循环语句owhileoforodo-whileß其他语句o复合语句oreturnoexitoread(input)owrite(output)栈操作例子isEmpty(S)//判断栈是否为空1if(top[S]==0)2thenreturntrue;3elsereturnfalse;Push(S,x)//入栈操作1top[S]=top[S]
7、+1;2S[top[S]]=x;Pop(S)//出栈操作1if(isEmpty(S))2thenerror“underflow”;3else{4top(S)=top[S]-1;5returnS[top[S]+1];6}算法设计基本方法列举法归纳法递推法递归法减半递推技术回溯法列举法基本思想ß根据提出的问题，列举出所有可能的解，并根据问题中所给定的约束，检验那些解是需要的，那些是需要排除的，输出符合要求的解。特点ß比较简单ß适合解空间较小的问题ß常用户解决“是否存在”或“有多少种可能”等类型的问题难点ß优化列举方案百鸡问题问题描述ß设每
8、只母鸡值3元，每只公鸡值2元，两只小鸡值0.5元。现要用100元钱买100只鸡，共有多少种购买方案。基本思路ß列举出所有的方案，输出符合约束(100元购买100只鸡)的方案，设买母鸡i只，公鸡j只，小鸡k只,并要求有3*i+2*j+0.5*k=100。百鸡问题(续)fori＝0to100doforj＝0to100dofork＝0to100do{sum＝i＋j＋k;value＝3*i＋2*j＋0.5*k;if(sum==100&&value==100)thenoutput(i,j,k);}return0;总循环次数为1013百鸡问题(续
9、)fori=0to33doforj=0to50-1.5*ido{k=100-i-j;if(3*i＋2*j＋0.5*k==100)thenoutput(i,j,k);}return0;33总循环次数为∑(511.5*)−≈i894i=0归纳法基本思想ß通过列举少量的特殊情况，经过分析，找出一般的关系。特点ß归纳法比列举法更能反映问题的本质;ß可以解决列举量为无限的问题;ß需要对归纳得到的结论加以必要的证明;递推法基本思想ß从已知初始条件出发，逐次推出所要求的各中间结果和最后结果，其中初始条件或是问题本身给定，或是通过对问题的分析而得到。
10、特点ß递推关系往往是归纳分析的结果;ß递推法在数值计算中极为常见;难点ß需要注意数值计算中的稳定性问题;定积分计算例子计算定积分n1xId==x,0n,1,2,,?20n∫0x+5递推关系一1I=−5*Inn−1n递推关
