算法-程序的灵魂课件

1、2022/7/28课件1第2章 程序的灵魂-算法2第2章 程序的灵魂-算法2-1 算法的概念（理解）2-2 简单算法举例（理解）2-3 算法的特性（理解）2-4 怎样表示一个算法(熟练掌握)2-5 结构化程序设计方法（了解）3第2章 程序的灵魂-算法 本章要点算法的概念 算法的表示结构化程序设计方法 4一个程序应包括两个方面的内容:对数据的描述：数据结构(data structure)对操作的描述：算法(algorithm)著名计算机科学家沃思提出一个公式: 数据结构 + 算法 = 程序 数据结构算法结构化程序设计方法语言工具完整的程序设计应该是:2-1 算法52-1 算法定义：算法是指为解决

2、一个问题而采取的方法和步骤。分类：数值运算算法和非数值运算算法算法有优劣 为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。62-2 简单算法举例例1-1 计算任意长方形的面积例1-2 计算 1x2x3x4x5=？例1-3 计算1-1/2+1/3-.+1/99-1/100=？例1-4 判断一个数是否素数算法描述7计算任意长方形的面积问题分析：输入长和宽计算面积=长X宽输出面积数据存放：长-len，宽-wid，面积-area设计算法：输入len和wid的值；计算area =lenwid；输出面积area的值；8求12345=？步骤1：先求12

3、，得到结果2步骤2：将步骤1得到的乘积2再乘以3，得到结果6步骤3：将6再乘以4，得24步骤4：将24再乘以5，得120太繁琐如果要求121000，则要写999个步骤9 S1：使p=1 S2：使i=2 S3：使pi，乘积仍放在变量p中，可表示为：pi=p S4：使i的值加1，即i+1 = i。 S5：如果i5，返回步骤S3；否则，算法结束。最后得到p的值就是5!的值。可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设p为被乘数，i为乘数。用循环算法来求结果, 算法可改写： 10S1：1 = pS2：3 = iS3：pi =

4、pS4：i+2 = iS5：若i1001，返回S3。否则，结束。 如果题目改为：求1351001算法只需作很少的改动：算法简练111-1/2+1/3-.+1/99-1/100=？提示：首先考虑实现1+2+3+4+100其次考虑实现1/1+1/2+1/3+1/4+.+1/100最后考虑实现1/1-1/2+1/3-1/4+.+1/100思路：S1：SUM=0,I=1S2：SUM=SUM+ IS3： I=I+1S4：如果I=100则转 S2 ，否则转 S5S5：打印SUM的值1/ I,P=1P*1/I,P=-P;12判断一个数是否素数分析：本题要点是先搞清楚什么是素数。思路：输入一个大于3的正整数N

5、定义一个变量 I 从 2N-1 ，I 每取一个值做：如果N能被I整除则中断循环，N不是素数；否则 I继续取下一个值；若当I取完所有值都不能整除N，则N是素数一个正整数，若不能被除1和它本身以外的任何整数整除，则是素数。132.3 算法的特性有穷性 指一个算法经过有限步骤后停止（或在合理范围内）确定性 算法的每一步都应当是确定的，无歧义的有效性 算法的每一步计算机都能有效执行有0个或多个输入 一个算法可以没有输入，即执行时无需输入信息有1个或多个输出 一个算法必须有输出，运算过程或运算结果142.4 怎样表示一个算法常用的算法描述方法：带序号的自然语言描述，易懂却不直观，不严格。流程图：灵活、自

6、由、形象、直观，可表示任何算法。15一、结构化程序设计的三种基本结构 三种基本结构：顺序、选择、循环，用这三种基本结构作为表示一种良好算法的基本单元。结构化程序设计方法16二、相关术语 程序：使用语言给计算机的一组指令序列。 结构化程序：用三种基本结构组成的程序就是结构化程序。 程序设计：为求解特定问题而编写的正确有效的程序。 程序设计语言：编写程序所用的语言。结构化程序设计方法171、顺序结构 例如：a=3; b=4; c=a+b;操作的步骤按照书写的顺序执行AB结构化程序设计方法三、三种基本结构182、选择结构 例如：if(x!=0) y=sin(x)/x; else y=1;PABYN结

7、构化程序设计方法三、三种基本结构193、循环结构:根据条件P决定是否重复执行循环体中的操作 例如：sum=0； i=1; while (i=100) sum+=i; i+; 先判断后执行NAPY结构化程序设计方法三、三种基本结构20循环结构例如：sum=0； i=1; do sum+=i; i+; while (i=100)先执行后判断PNAY结构化程序设计方法三、三种基本结构21结构化程序设计方法二、三种基本结构特点：只有一个入口和一个出口；结构内每一部分都有机会执行到；结构内不存在“死循环”。注：以上三种基本结构顺序组成的算法结构可以解决任何复杂的问题。22常用的算法描述方法：N-S图（盒

8、图）：特点是完全去掉了带箭头的流程线，算法的所有处理步骤都写在一个大矩形框，表示简单，符合结构化思想。AT P F A B当P1成立 A A直到P2成立 处理 判断 循环23N-S图：ABAB顺序结构PABYNY P N A B选择结构24N-S图：当型循环直到型循环当P1成立 AAP1Y A直到P2成立PYANN25常用的算法描述方法：伪代码：用介于自然语言与计算机语言之间的文字及符号来描述算法，特点是方便、易懂、便于向计算机语言过渡。26学习建议：流程图和N-S图一定要熟练掌握，伪代码表示法在学习完基本的流程控制语句后也经常使用。27例题：计算s=n，写出其算法 S=0,n=1n=100输出SN开始结束S=S+nn=n+1Y100n=1流程图描述：自然语言描述：1、0 S单元 2、1 n单元3、s+n s4、n+1 n5、判断n100？是，转3；否则转66、 输出 S的值 28例题：计算s=n，写出其算法 100n=1伪代码描述：NS图描述：n100？s+n sn+1 n输出S的值0 s1 nBegin s nwhile n 100s+n s n+1 n