计算机科学导论数据结构与算法.ppt

开始输出S的值结束输入RR?S-R?SR≥0YN选择输入R输出S的值R?S-R?SYR≥0N例：求给定数R的绝对值第93页，共115页，星期日，2025年，2月5日例:给定K值，求T=1+2+3+…+K开始输出T的值结束输入KT+I?TI+1?II≤KYN1?I，0?T循环输入K输出T的值I≤K1?I，0?TT+I?TI+1?I第94页，共115页，星期日，2025年，2月5日伪代码是算法的一种类似英语的表示法。它是部分英语和部分结构化代码的组合。英文代码部分采用不严格的语法，很容易看懂；代码部分包含基本算法结构（顺序、选择和循环）的扩展形式。目前还没有伪代码的标准。3.伪代码第95页，共115页，星期日，2025年，2月5日伪代码描述算法的一般组成：算法头：算法的名字。目的、条件和返回值：目的：有关算法要做什么的简短说明前置条件：列出算法所有前驱条件后置条件：指出算法产生的影响返回值：算法返回的结果或无返回值语句序号：表示语句之间的附属关系。第96页，共115页，星期日，2025年，2月5日例：用伪代码描述在一数列中找最小值的算法Algorithm（算法）：FindingSmallestPurpose（目的）：在一数列中找最小值Pre（前置条件）：Listofnumbers（数列）Post（后置条件）：NoneReturn（返回值）：Thesmallest32416a:S321算法：设数列中第一个数为最小值S，然后用后续数依次与S比较，若比S小，则用该数替换原S的值，全部比较完成后S即最小值。第97页，共115页，星期日，2025年，2月5日1.Setsmallesttothefirstnumber2.Loop(notendoflist)2.1if(nextnumbersmallest)2.1.1setsmallesttonextnumber2.2endif3.endloop4.returnsmallestEndFindingSmallest数列?ai(i=1,5)a1?S,2?ii≤5YaiSNai?Si+1?i返回最小值S第98页，共115页，星期日，2025年，2月5日1.数列?ai(i=1,5)2.a1?S,2?i3.while(i≤5)3.1if(aiS)thenai?Sendif3.2i+1?iendwhile4.returnS伪代码不一定按上述严格的格式，且可以使用汉字，只要把算法表达清楚即可。数列?ai(i=1,5)a1?S,2?ii≤5YaiSNai?Si+1?i返回最小值S第99页，共115页，星期日，2025年，2月5日s=a[1];i=2;while(i=5){if(a[i]s)s=a[i];i=i+1;}returns;数列?ai(i=1,5)a1?S,2?ii≤5YaiSNai?Si+1?i返回最小值S4.计算机语言第100页，共115页，星期日，2025年，2月5日计数累加值交换求最大（小）值四、基本算法穷举迭代递推递归第101页，共115页，星期日，2025年，2月5日1.穷举法基本思想首先根据问题的部分条件预估计出答案的范围在预估计的答案范围内，对所有可能的情况逐一验证。若某个情况使验证符合题目的全部条件，则该情况是本题目的一个答案。第102页，共115页，星期日，2025年，2月5日分析：假设a,b分别代表父亲和儿子的年龄，x年后a=2b。根据人的寿命，x取值为：1,2,…,150 问题：父亲今年30岁，儿子今年6岁，在父亲有生之年中，多少年后父亲的年龄是儿子的2倍？算法：1.考察x可能的范围：x=1，2，…，150；2.30+x?a,6+x?b3.若a=2b，则输出x。第103页，共115页，星期日，2025年，2月5日开始结