经典c语言课件第2章算法.ppt

第二章第二章l l 主要内容2.1 2.1 算法的概念算法的概念2.2 2.2 简单算法举例简单算法举例2.3 2.3 算法的特性算法的特性2.4 2.4 怎样表示一个算法怎样表示一个算法2.5 2.5 程序化设计方法程序化设计方法 一个程序应包括两个方面的内容:对数据的描述：数据结构(data structure)对操作的描述：算法(algorithm)著名计算机科学家沃思提出一个公式:数据结构数据结构+算法算法=程序程序数据结构算法程序设计方法语言工具数据结构算法程序设计方法语言工具完整的程序设计应该是:上述四个方面中：上述四个方面中：算法是灵魂；数据结构是加工对象；语言是工具；编程需要采取合适的方法。算法解决算法解决做什么做什么和和怎么做怎么做的问题。的问题。程序中的按一定顺序列出的操作语句，就是算法的程序中的按一定顺序列出的操作语句，就是算法的体现。体现。通过本门课，大家学会使用通过本门课，大家学会使用c语言的语法编写不太复语言的语法编写不太复杂的杂的c程序。程序。算法的概念算法的概念用计算机解决问题的步骤，即计算机算法。例2.1 求12345 改进算法：改进算法：S1:S1:使使t=1t=1S2:S2:使使i=2i=2S3:S3:使使ti,ti,乘积仍然放在变量乘积仍然放在变量t t中，可表示为中，可表示为titit tS4:S4:使使i i的值的值+1+1，即，即i+1i+1i iS5:S5:如果如果i5,i5,返回重新执行返回重新执行 步骤步骤S3S3以及其后的以及其后的S4S4和和S5S5；否则，算法结束。否则，算法结束。原始方法：原始方法：步骤步骤1 1：先求：先求1 12 2，得到结果得到结果2 2。步骤步骤2 2：将步骤：将步骤1 1得到的乘得到的乘积积2 2乘以乘以3 3，得到，得到结果结果6 6。步骤步骤3 3：将：将6 6再乘以再乘以4 4，得，得2424。步骤步骤4 4：将：将2424再乘以再乘以5 5，得，得 120 120。i：第个学生学号：第个学生学号i：第个学生成绩：第个学生成绩S1:1iS2:如果如果gi80，则打印，则打印ni和和gi，否则不打印，否则不打印S3:i+1iS4:若若i50,返回返回S2，否则，结束。，否则，结束。例例2.2 2.2 有有5050个学生，要求将他们之中成绩在个学生，要求将他们之中成绩在8080分以上者分以上者打印出来。打印出来。闰年的条件：能被4整除，但不能被100整除的年份；能被100整除，又能被400整除的年份；例例2.判定判定20002500年中的每一年是否闰年，将结果输出。年中的每一年是否闰年，将结果输出。S1:2000yS2:若y不能被4整除，则输出y“不是闰年”，然 后转到S6S3:若y能被4整除，不能被100整除，则输 出y“是闰年”，然后转到S6S4:若y能被100整除，又能被400整除，输 出y“是闰年”否则输出y“不是闰年”，然后转到S6S5:输出y“不是闰年”。S6:y+1yS7:当y2500时,返回S2继续执行，否则，结束。C C程序设计程序设计 第二章第二章 程序的灵魂算程序的灵魂算法法例例2.2.求求S1:sigh=1S2:sum=1S3:deno=2S4:sigh=(-1)sigh S5:term=sigh(1/deno)S6:sum=sum+termS7:deno=deno+1S8:若若deno100，返回，返回S4；否则，结束。；否则，结束。算法的特性算法的特性有穷性：一个算法应包含有限的操作步有穷性：一个算法应包含有限的操作步骤而不能是无限的骤而不能是无限的确定性：算法中每一个步骤应当是确定确定性：算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的的，而不能应当是含糊的、模棱两可的输入输入:有零个或多个输入有零个或多个输入输出输出:有一个或多个输出有一个或多个输出有效性：算法中每一个步骤应当能有效有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果地执行，并得到确定的结果小结：小结：流程图是表示算法的较好的工具。一个流程图包括以下几部分：(1)表示相应操作的框；(2)带箭头的流程线；(3)框内外必要的文字说明。算法的表示算法的表示用自然语言表示用自然语言表示用流程图表示（传统流程图和用流程图表示（传统流程图和N-S图）图）用伪代码表示用伪代码表示用计算机语言表示用计算机语言表示结构化程序的三种基本结构：结构化程序的三种基本结构：顺序、选择、循环结构顺序、选择、循环结构（一）用自然语言表示算法（一）用自然语言表示算法上节中讨论的例1和例2的算法是用自然语言写的。自然语言指人们日常使用的语言，如汉语、英语等。用自然语言表示算法的特点：通俗易懂，但不严谨，容易产生歧义。除非问题很简单，一般不用自然语言描述算法。（二）（二）用流程图表示算法用流程图表示算法流程图采用一些图形框表示算法要表述的各种操作。流程图采用一些图形框表示算法要表述的各种操作。美国国家标准化协会美国国家标准化协会ANSIANSI规定了一些常用的流程图符号：规定了一些常用的流程图符号：起止框 处理框 输入输出框 流程线 或判断框 连接点 注释 开始结束例例1 1的算法用流程图来表示的算法用流程图来表示计算1 x 3x5x.x11的值 步骤1：令p=1 步骤2：令i=1 步骤3：使p x i,并将乘积放入p中。通常表示为 p x i=p 步骤4：使 i 的值加2，表示为 i+2=i 步骤5：如果i 不大于11，返回到步骤3继续向下执行；否则算法结束。p中的值即最后结果。开始1=p1=ip i=p i+2=ii11真结束假输出p的值例例2 2的算法用流程图来表示的算法用流程图来表示有两个数a,b，按大小顺序打印它们。步骤步骤1 1：输入a,b的值；步骤步骤2 2：如果ab,则先打印a，再打印b；否则，先打印b，再 打印a；算法结束。真假开始ab结束输出b,a的值输入a,b的值输出a,b的值（三）三种基本结构（三）三种基本结构顺序结构：BA虚线框内是一个顺序结构。AB两个框是顺序执行的：按图中所画的框的顺序，先执行A操作，再执行B操作。选择结构也称为分支结构。虚线框内是一个选择结构。此结构包括一个选择框，框中写有一个条件，根据给定的条件是否成立，从而选择执行A框还是B框。例如：条件可以是i101条件PAB成立不成立条件PA成立不成立B操作为空时，画成直线（三）三种基本结构（三）三种基本结构循环结构（当型-while型）虚线框内是一个当型循环结构。当给定的条件成立时，执行A框中的操作；执行完A操作后，判条件P是否成立；如果仍成立，继续执行A操作；如此反复执行A框中的操作，直到条件P不成立为止。条件PA成立不成立（三）三种基本结构（三）三种基本结构循环结构（直到型-until型）条件PA成立不成立虚线框内是一个直到型循环结构。先执行A框中的操作；执行完A操作后，判条件P是否成立；如果不成立，继续执行A操作；如此反复执行A框中的操作，直到条件P成立为止。（三）三种基本结构（三）三种基本结构（四）结构化程序设计方法（四）结构化程序设计方法三种基本结构的共同点：三种基本结构的共同点：只有一个入口；一个出口；结构内每一部分都有机会被执行。结构内不存在死循环。如条件永远成立时，就成了死循环已经证明，用上述三种基本结构顺序组成的已经证明，用上述三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。算法结构，可以解决任何复杂的问题。由基本结构构成的算法属于由基本结构构成的算法属于结构化结构化的算法的算法只要符合上述的四个特点的结构，都称为基只要符合上述的四个特点的结构，都称为基本结构。本结构。对例对例1 1算法的流程图的结构化分析算法的流程图的结构化分析计算1 x 3x5x.x101的值 步骤1：令p=1 步骤2：令i=3 步骤3：使p x i,并将乘积放入p中。通常表示为 p x i=p 步骤4：使 i 的值加2，表示为 i+2=i 步骤5：如果i 不大于101，返回到步骤3继续向下执行；否则算法结束。p中的值即最后结果。开始1=p3=ip i=p i+2=ii101真结束假输出p的值这两个操作之间是顺序关系这是一个循环结构这是一个顺序结构上述算法由基上述算法由基本结构组成本结构组成对例对例2 2算法的流程图的结构化分析算法的流程图的结构化分析有两个数a,b，按大小顺序打印它们。步骤步骤1 1：输入a,b的值；步骤步骤2 2：如果ab,则先打印a，再打印b；否则，先打印b，再 打印a；算法结束。真假开始ab结束输出b,a的值输入a,b的值输出a,b的值这是一个选择结构上述算法由基上述算法由基本结构组成本结构组成用基本结构的组合表示算法，从而去掉了流程线。用基本结构的组合表示算法，从而去掉了流程线。避免了随意的跳转。避免了随意的跳转。19731973年两名美国学者提出了一种新的流程图形式，年两名美国学者提出了一种新的流程图形式，并用二人名字的第一个字母组合命名了该流程图。并用二人名字的第一个字母组合命名了该流程图。即即N-SN-S流程图，也称盒图。流程图，也称盒图。三种基本结构的表示：三种基本结构的表示：P成立 AB（五）用（五）用N-SN-S流程图表示算法流程图表示算法AB不成立A当条件P成立时直到条件P1成立A前面的算法用前面的算法用N-SN-S流程图来表示流程图来表示计算1 x 3x5x.x11的值 步骤1：令p=1 步骤2：令i=1 步骤3：使p x i,并将乘积放入p中。通常表示为 p x i=p 步骤4：使 i 的值加2，表示为 i+2=i 步骤5：如果i 不大于11，返回到步骤3继续向下执行；否则算法结束。p中的值即最后结果。这两个操作之间是顺序关系1=P1=i直到 i11 p x i=p i+2=i打印P的值这是一个顺序结构这是一个循环结构上述算法由基上述算法由基本结构组成本结构组成N-SN-S图表示算法的优点图表示算法的优点比文字描述直观、形象、易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N-S流程图中的上下顺序就是执行时的顺序。用N-S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。小结：小结：一个结构化的算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转)；一 个非结构化的算法可以用一个等价的结构化算法代替，其功能不变。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。（六）用伪码表示算法（六）用伪码表示算法伪码伪码 是用一种介于自然语言和计算机语言之间的文字和符号来描述算法。好处：好处：书写方便，格式紧凑，易懂，便于向计算机语言过渡。前面的算法可用前面的算法可用伪码表示为：伪码表示为：开始 置p的初值为1 置i的初值为1 当i 小于11时，执行下面的操作：使 p=p x i 使 i=i+2 打印 p 的值结束（七）用计算机语言表示算法（七）用计算机语言表示算法只有用计算机语言描述的算法才能被计算只有用计算机语言描述的算法才能被计算机的编译环境识别，并被处理、执行。机的编译环境识别，并被处理、执行。用计算机语言表示算法必须严格遵守所用用计算机语言表示算法必须严格遵守所用语言的语法规则。语言的语法规则。前面几种描述算法的方法对文字等格式要前面几种描述算法的方法对文字等格式要求不严，一般来说，只要能示意就行。求不严，一般来说，只要能示意就行。前面的算法用前面的算法用c c语言表示语言表示#include void main()int p,i;p=1;i=1;while(i=11)p=p*i;i=i+2;五、程序设计步骤五、程序设计步骤分析问题 确定解决方案建立数学模型设计算法用计算机语言描述算法（即写出源程序）上机调试源程序：经过编辑、编译、连接、编辑、编译、连接、运行运行，得到可执行的程序。（参看教科书第7页上的图1.1 上机步骤）运行程序，得到需要的结果。应当强调说明：写出了C程序，仍然只是描述了算法，并未实现算法。只有运行程序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。2.5 2.5 结构化程序设计方法结构化程序设计方法一个结构化程序 就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。结构化程序设计方法的基本思路是：把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。自顶向下，逐步细化方法的优点：考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。模块设计的方法：模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。子模块一般不超过50行。划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。实验一实验一C程序设计入门程序设计入门目的要求：目的要求：l了解了解TurboC2.0的集成开发环境，学习如何在的集成开发环境，学习如何在TurboC2.0中中编辑、编译、连接、运行与调试编辑、编译、连接、运行与调试C程序；程序；2通过运行简单通过运行简单C程序，初步了解程序，初步了解C源程序的特点。源程序的特点。实验内容：实验内容：1.首先在首先在e盘建立以自已学号命名（注意文件夹名或文件名都盘建立以自已学号命名（注意文件夹名或文件名都不要超过不要超过8个字符，也不要用汉字）的目录，以后自已编辑个字符，也不要用汉字）的目录，以后自已编辑和调试的有关和调试的有关C的源文件可保存在这个目录下。的源文件可保存在这个目录下。2.启动启动TurboC2.0，输入教材第一章例，输入教材第一章例1.1程序，并进行编译程序，并进行编译和运行。和运行。注意观察：在此过程中，系统是用何命令进行编译和运行的？注意观察：在此过程中，系统是用何命令进行编译和运行的？编译和连接后所得到的目标程序的后缀是什么？同时请注意编译和连接后所得到的目标程序的后缀是什么？同时请注意相应的目标程序存放在何处？相应的目标程序存放在何处？3.输入并运行教材第一章例输入并运行教材第一章例1.2，了解如何在运行时向程序中的，了解如何在运行时向程序中的变量输入数据。变量输入数据。4.输入并运行教材第一章例输入并运行教材第一章例1.3。5.输入并运行自已编写的程序输入并运行自已编写的程序(教材第一章教材第一章P14三三编程题编程题)。*实验二实验二C基本数据类型及运算基本数据类型及运算目的要求：目的要求：l掌握掌握C语言中整型、字符型、实型变量的定义及赋值；语言中整型、字符型、实型变量的定义及赋值；2学会使用学会使用C的有关运算符及相关表达式；的有关运算符及相关表达式；3进一步熟悉进一步熟悉TurboC2.0的集成开发环境。的集成开发环境。实验内容：实验内容：1.编写一个程序，从键盘接收编写一个程序，从键盘接收3个实数（分别为个实数（分别为10.0、20.0、5.0），），输出这输出这3个数的和个数的和s、乘积、乘积t和平均值和平均值a。2.编程。要求用户输入两个整数编程。要求用户输入两个整数a、b（分别为（分别为20、10），），读取用读取用户从键盘输入的值，然后：户从键盘输入的值，然后：1)用整数输出这两个数的和、差；用整数输出这两个数的和、差；2)用长整型输出这两个数的积，用用长整型输出这两个数的积，用float输出商；输出商；3)用整数输出这两个数的余数，用用整数输出这两个数的余数，用float输出平均值。输出平均值。3.将第将第2题中的程序修改，使整数题中的程序修改，使整数a、b的值分别为的值分别为10、20，再运行，再运行程序，分析程序运行结果，并给出说明程序，分析程序运行结果，并给出说明*。实验三实验三C简单程序设计简单程序设计目的要求：目的要求：l掌握数据输入输出的方法。掌握数据输入输出的方法。2能正确使用各种格式转换符。能正确使用各种格式转换符。实验内容：实验内容：1.编写一个程序，从键盘接收一个一位的整型数，经转编写一个程序，从键盘接收一个一位的整型数，经转换，用字符函数换，用字符函数putchar输出。例如，输入整数输出。例如，输入整数5，程，程序运行后输出字符序运行后输出字符5。2.编程。输入半径，计算球体表面积（编程。输入半径，计算球体表面积（）和球体积）和球体积（）。）。3.编写一个程序，要求通过键盘给编写一个程序，要求通过键盘给6个变量赋值，然个变量赋值，然后将变量的值在屏幕上打印输出。这六个变量的值分后将变量的值在屏幕上打印输出。这六个变量的值分别为：别为：10,10,40000,a,3.14,hello。