程序设计及算法表示.ppt

第三章程序设计及算法表示,3程序设计及算法表示,内容本章简单介绍程序设计的基本步骤和算法及其表示方法基本组成重点介绍设计简单程序的一般方法重点：程序设计的基本概念，结构化程序设计的三种基本结构,3-1程序设计的有关内容,程序设计(programming)：,C语言编程,解决实际问题,方法、途径,工具,目的,基本概念,程序（program）：为解决某一问题而设计的一系列指令，能被计算机识别和执行。语言（language）：用于传达信息的表示方法、约定和规则的集合。是人们交流信息的工具和媒介。程序设计语言：人与计算机打交道时交流信息的一类媒介和工具，由语句（statement）组成。语句（statement）：组成语言的基本单位，包含语法和语义两个方面。语法(syntax)：定义构造语言的正确的表达式或句子所需的各种规则。语义(semantic)：对构成语言成分的含义的定义和说明。,程序设计的基本步骤,分析问题确定处理方案确定算法算法的程序化上机调试整理资料文档,分析问题,已知条件确定问题的类型分析运行环境,数值型问题非数值型问题（排序、查找）,已知条件结果,由结果判断,可行性分析,确定处理方案,如果是数值型问题如果是非数值型问题选择方法应考虑处理方案的效率,确定处理方案，也就是建立相应的数学模型。物理状态的数据化（方程）,排序、查找选择相应算法和执行方法,运算速度内存空间,示例：,例（鸡兔同笼）：,已知一笼鸡兔，鸡（cock）、兔（rabit）的头（heads）和脚（feet）的数目，求鸡和兔各有多少只？,首先分析问题：,已知：head,feet求：cock,rabit数值型问题可行,确定处理方案：数值型列方程（建立数学模型）,确定算法,确定处理步骤这里所说的算法不仅指计算的方法，还包括解决问题时从什么地方入手，经过哪些处理步骤，何时结束的全过程。算法设计：,算法的程序化,编写程序,上机调试,调试(debug)是检测、定位、并排除错误或故障的过程静态错误的调试：在编译连接阶段的错误。动态错误调试：运行阶段出现的错误。程序测试（testing）检查程序功能是否正确的过程语法错误：编写和输入过程中的错误算法错误：由算法导致的执行操作错误,示例：,如前例（鸡兔同笼）,55,5.54.5,13-3,BUG,整理资料,用于软件设计时，作相应的程序说明和文档说明,3-2算法及其表示方法,内容：算法是使用不同编程语言都要必备的基本编程理念，本节从全局出发，介绍了让计算机解决实际问题的方法和步骤，以便形成一个适用于计算机的解决问题的思维方式。,3-2-1算法,程序=数据结构+算法程序=算法+数据结构+程序设计方法+语言工具和环境计算机算法：数值运算算法、非数值运算算法。算法要素：正确、简单。,算法的基本概念,算法(algorithm)：是对特定问题求解步骤的一种描述。算法示对操作的描述，对于我们而言，算法是确定的、有限的步骤。从内容上，算法就是包括从什么地方入手、经过哪些处理步骤、何时结束的整个处理过程。,算法的特征,确定性不能含糊其词，不能产生歧义有限性有穷性，计算机可以执行输入（零个或多个）输出（一个或多个）有效性,3-2-2简单算法举例,例2.1求1*2*3*4*5,简单算法举例,例2.2有50个学生,将成绩在80分以上者打印出来.ni代表第i个学生的学号,gi代表成绩。,简单算法举例,例2.3计算并输出2000-2050年之间的闰年,闰年的条件如下：能被4整除，但不能被100整除；即能被100整除又能被400整除;,3-2-3算法的表示方法,算法表示：1.自然语言2.专用工具（流程图表示）3.伪代码4.计算机语言,算法的流程图表示,传统流程图符号：,流程图符号表示的算法实例：,问题：求12+22+502,伪代码表示的算法实例：,问题：求12+22+502,开始输入n的值置sum初值为0置i初值为1当in，执行下面操作：sum=i*i+sumi=i+1打印sum的值结束,BEGININPUTnsum=0i=1WHILEi=nsum=sum+i*ii=i+1PRINTsumEND,计算机语言表示的算法实例,问题：求12+22+502,3-2-4结构化程序设计方法,三种基本结构：顺序结构、选择结构、循环结构,三种基本结构的特点,只有一个入口只有一个出口；结构内每一部分都有机会被执行；不存在死循环；,符合上述特点的算法称为结构化算法,结构化程序设计方法,结构化程序：用高级语言表示的结构化算法；优点：便于书写、阅读、修改维护，从而可以提高程序的可靠性结构化程序设计强调程序设计风格的程序设计方法的规范化，要想达到这一目的，可采取结构化程序设计方法结构化程序设计方法自顶向下；逐步求精；模块化设计；结构化编码；,N-S流程图,取消了流程线，规定只能自上而下执行顺序结构先执行A操作，再执行B操作；,N-S流程图,选择结构P代表条件，P成立时执行A操作，否则执行B操作；,N-S流程图,循环结构（当型循环）条件P成立时反复执行A操作，直到P为假结束循环；,N-S流程图,循环结构（直到型循环）反复执行A操作，直到条件P为假结束循环；（Basic中为直到P为真结束）,应用举例,例3-1：统计某一班35名同学某门功课不及格人数。,已知：未知：确定处理方案（算法类型）：算法步骤：,35个成绩score不及格人数m,非数值型，统计类,Step1:输入某个学生成绩Score,重复35次循环结构计数n,判断n=35，成立执行Step1/2,Step3:n=n+1,判断n=35，成立执行Step1/2/3,初始化变量：n=0,m=0,应用举例,例3-1：统计某一班35名同学某门功课不及格人数。,1、分析n=n+12、分析n35