程序设计灵魂算法概要.pptx

《程序设计灵魂算法概要.pptx》由会员分享，可在线阅读，更多相关《程序设计灵魂算法概要.pptx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主要内容主要内容算法的概念简单算法举例算法的特点算法的表示方法第1页/共32页程序设计包括两个方面内容：1.对数据的描述(数据结构)数据的类型数据的组织形式 2.对操作的描述(算法)程序程序=算法算法+数据结构数据结构+程序设计方法程序设计方法+语言工具和环境语言工具和环境 在设计一个程序时，要综合运用这几方面的知识。在设计一个程序时，要综合运用这几方面的知识。算法是灵魂，数据结构是加工对象，语言是工具。算法是灵魂，数据结构是加工对象，语言是工具。计算机科学家沃思(Nikiklaus Wirth)公式：数据结构数据结构+算法算法=程序程序第2页/共32页做任何事情都用一定的步骤，例如炒菜有以下

2、做任何事情都用一定的步骤，例如炒菜有以下几个步骤几个步骤：2 2.1.1算法的概念算法的概念第3页/共32页2 2.1.1算法的概念算法的概念 为解决一个问题而采取的方法和步骤，就为解决一个问题而采取的方法和步骤，就称为算法。称为算法。大学新生报到太极拳图解 计算机算法可分为：计算机算法可分为：数值运算算法、非数值运数值运算算法、非数值运算算法。算算法。数值运算数值运算 ：求数值解；求数值解；非数值运算：非数值运算：常用于事务管理领域，如图书常用于事务管理领域，如图书检索、人事管理、行车调度管理等。检索、人事管理、行车调度管理等。第4页/共32页 什么是程序设计？为计算机编写程序的过程。为计算

3、机编写程序的过程。程序设计最主要的工作就是程序设计最主要的工作就是算法设计算法设计。什么是程序设计语言？在程序设计过程中，用于编写程序的语言在程序设计过程中，用于编写程序的语言。问题定义问题定义总体总体/详细设计详细设计编程编程运行运行编写C语言程序的大体步骤：2 2.1.1算法的概念算法的概念第5页/共32页例：设计用算法实现 S=1+2+3+100算法1：开辟一存储单元 S 用S存放累加和 1、将累加单元 S 清零 2、把1加到 S 中 3、把2加入到S 中 100、把100加到 S 中 101、输出 S 中的结果 算法2：开辟一个累加单元 S，再开辟一个记数单元 iS1：将累加单元 S

4、清零S2：将记数单元 i 置一S3：将 i 加到 S 中S4：记数单元 i 的值增一S5：如果 i 的值等于100则执行下一步，否则转到第 S3S6：输出 S 的值2.2 算法举例第6页/共32页2.3 2.3 算法的特性算法的特性一个算法应当具有五大特性一个算法应当具有五大特性:1 1、有穷性、有穷性:算法包含的操作步骤有限算法包含的操作步骤有限2 2、确定性、确定性:算法每一步的操作步骤都是确定的，不能模棱两可算法每一步的操作步骤都是确定的，不能模棱两可3 3、有零个或多个输入有零个或多个输入:在执行算法时从外界取得必要的信息在执行算法时从外界取得必要的信息4 4、有一个或多个输出：、有一

5、个或多个输出：即算法的求解即算法的求解5 5、有效性：、有效性：算法中每一个步骤都应当能有效执行算法中每一个步骤都应当能有效执行第7页/共32页1、自然语言描述法：3、伪码方法：2、图示法：（2）算法结构图（N-S 图）（1）算法流程图2.4 算法的表示方法4、计算机语言第8页/共32页2.4 2.4 算法的表示方法算法的表示方法1、自然语言描述法：自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现“歧义性”。Q：将分别装有醋(A杯)和酱油(B杯)的两个杯子里面的内容交换。分析：借用第三个杯子（空杯）第9页/共32页（1）算法流程图采用具有

6、特定含义的图框和流线表示算法 直观形象，易于理解2、图示法：2.4 算法的表示方法起止框：起止框：算法的开始和结束算法的开始和结束一般处理框：一般处理框：表示赋值、加减等操作表示赋值、加减等操作判断框：判断框：根据给定的条件决定执行几根据给定的条件决定执行几条路径中的某一条路径条路径中的某一条路径输入输出框：输入输出框：表示输入输出操作表示输入输出操作流程线：流程线：表明程序流程的方向表明程序流程的方向第10页/共32页结构化程序设计的三种基本结构结构化程序设计的三种基本结构:顺序、选择和循环顺序、选择和循环 顺序结构（1）算法流程图Q：键盘输入两个数x1和x2，要求交换后实现输出。开始x1，

7、x2Temp=x1X1=x2X2=Tempx1，x2结束开始输入x1，x2Temp=x1x1=x2x2=Tempx1，x2结束第11页/共32页选择结构（1）算法流程图Q：键盘输入任意数并输出其平方根。开始X1X1=0Y1=sqrt(x1)Y1结束NY开始x1x1=0Y1=sqrt(x1)Y1结束NY第12页/共32页当型(While型)循环结构 直到型(Until型)循环（1）算法流程图第13页/共32页例例1:1:将求将求5!5!的算法用流程图表示的算法用流程图表示算法：s1:使t=1 s2:使i=2 s3:使t*i，乘积仍放在变量t中。s4:使i的值加1 s5:如果i不大于5，返回重新执

8、行步骤3以及其后的步骤4和5，否则算法结束。最后得到的t值就是5!5!的值。的值。第14页/共32页 例例2:2:对一个大于或等于对一个大于或等于3 3的正整数，判断它是否是一个素数的正整数，判断它是否是一个素数。分析：分析：判断一个数n(n3)是否素数的方法：将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。概念：概念：所谓素数，是指除了1和该数本身之外，不能被其它任何整数整除的数。例如，13是素数。因为它不能被2，3，4，12整除。第15页/共32页算法描述：S1S1：输入：输入n n的值的值S2S2：i=2 i=2（i i作为除数）作为除数）S3S3：n

9、 n被被i i除，得余数除，得余数r rS4S4：如果：如果r=0r=0，表示，表示n n能被能被i i整除，整除，则打印则打印n n“不是素数不是素数”，算法结，算法结束。否则执行束。否则执行S5S5S5S5：i+1ii+1iS6S6：如果：如果in-1in-1，返回，返回S3S3。否则。否则打印打印 n n“是素数是素数”。然后结束。然后结束。第16页/共32页流程图小结流程图小结流程图是表示算法的较好的工具。一个流程图包括以下几部分：(1)表示相应操作的框；(2)带箭头的流程线；(3)框内外必要的文字说明。缺点：占用篇幅较多，尤其是算法比较复杂时，画流程图既费时又不方便第17页/共32页

10、（2）算法结构图（N-S 图）1）顺序顺序 结构框图一系列顺序执行的操作2）选择选择 结构框图若条件成立，则执行操作；否则执行操作。条件成立操作不成立操作2、图示法：a=3;b=4;c=a+b;if (x y)z=x;else z=y;第18页/共32页）循环结构框图直到型循环：先做后判循环体直到条件成立重复执行操作，直到条件成立则退出本循环，执行下一操作。当型循环：先判后做循环体当条件成立当条件成立，则重复执行操作，直到条件不成立为止。sum=0;i =1;while(i 10)sum=sum+i;i=i+1;sum=0;i=0;do sum=sum+i;i=i+1;while(i 100输

11、出结果S循环体 第20页/共32页例例4 4：某班学生：某班学生3030人人 ，将成绩大于，将成绩大于8080分者打印其学号和成绩分者打印其学号和成绩 算法描述：i=1 i=i+1 直到 i 30 用Ni表示第i个学生的学号;用Gi表示第i个学生的成绩是打印N i,G i 否算法结构图：s1.将i置一s2.输入Ni，Gi s7.i的值增一s8.如果 i 31 返回第6步;否则算法结束G i 80s6.如果 Gi 80则打印Ni,Gi否则不打印s4.如果i30s3.i的值增一第21页/共32页例例5 5：已知：已知 N=50 N=50，计算，计算 算法结构图1：算法结构图2：S=0S=0N=0N

12、=0N=N+1N=N+1直到 N=50当 N 5 0S=S+S1S=S+S1输出结果S输出结果S直 到 型 当 型第22页/共32页N-SN-S图表示算法的优点图表示算法的优点比文字描述直观、形象、易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N-S流程图中的上下顺序就是执行时的顺序。用N-S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。第23页/共32页例：判定例：判定2000200025002500年中的每一年是否闰年，将结果输出。年中的每一年是否闰年，将结果输出。将该算法分别用自然语言，流程图和

13、将该算法分别用自然语言，流程图和N-SN-S图分别进行描述。图分别进行描述。分析：闰年的条件分析：闰年的条件 (1)能被4整除，但不能被100整除的年份都是闰年，如1996,2004年是闰年；(2)能被100整除，又能被400整除的年份是闰年。如1600,2000年是闰年。不符合这两个条件的年份不是闰年。第24页/共32页设设y y为被检测的年份，算法可表示如下为被检测的年份，算法可表示如下：S1S1：2000 2000 y yS2S2：若：若y y不能被不能被4 4整除，则输出整除，则输出y y“不是闰年不是闰年”。然后转到。然后转到S6S6。S3S3：若：若y y能被能被4 4整除，不能被

14、整除，不能被100100整除，则输出整除，则输出y y“是闰年是闰年”。然。然后转到后转到S6S6。S4S4：若：若y y能被能被100100整除，又能被整除，又能被400400整除，输出整除，输出y y“是闰年是闰年”，否，否则输出则输出“不是闰年不是闰年”。然后转到然后转到S6S6。S5:S5:输出输出y y“不是闰年不是闰年”。S6S6：y+1 y+1 y yS7S7：当：当y2500y2500时，转时，转S2S2继续执行，如继续执行，如y y25002500，算法停止。，算法停止。第25页/共32页判定闰年的算法用流程图表示：用流程图表示算法要比用文字描述算法逻辑清晰、易于理解。第26

15、页/共32页判定闰年的算法用N-S图表示第27页/共32页3、伪代码l概念：伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。l特点：它如同一篇文章一样，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便、格式紧凑，也比较好懂，也便于向计算机语言算法(即程序)过渡。l用处：适用于设计过程中需要反复修改时的流程描述。第28页/共32页开始 置t的初值为1 置i的初值为2 当i=5，执行下面操作：使t=ti 使i=i+1 循环体到此结束 输出t的值 结束也可以写成以下形式：BEGIN算法开始 1t 2 i while i5 ti t i+1 i print

16、 t END算法结束例：求例：求5!5!用伪代码表示算法用伪代码表示算法第29页/共32页4 4、计算机语言表示、计算机语言表示#include void main()int a;printf(input a number:”);scanf(“%d”,&a);if(a%2=0)printf(“a=%d is evenn”,a);else printf(“a=%d is oddn”,a);例例:输入一个整数输入一个整数a a，判断它是偶数还是奇数判断它是偶数还是奇数?第30页/共32页1、什么是结构化程序？用高级语言表示的结构化算法，用三种基本结构组成的程序必然是结构化的程序。2、结构化程序设计方法的思路：把大的复杂的问题逐步分解成简单的容易处理的小问题。3、采用那些方法可得到结构化的程序？（1）自顶向下（2）逐步细化（3）模块化设计（4）结构化编码2.5 结构化程序设计方法第31页/共32页感谢您的观看！第32页/共32页