《c语言程序设计(包云)c第2章算法.ppt》由会员分享，可在线阅读，更多相关《c语言程序设计(包云)c第2章算法.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、C C程序设计程序设计程序设计程序设计第2章 程序的灵魂-算法1/16/20231/16/20231 1第第1 1章章 C C语语言言概概述述第2章 程序的灵魂算法16-Jan-23主要内容主要内容2.1 算法的概念算法的概念2.2 简单算法举例简单算法举例2.3 算法的特性算法的特性2.4 算法的表示算法的表示2.5 结构化程序设计方法结构化程序设计方法2第2章 程序的灵魂算法16-Jan-232.1 算法的概念算法的概念数据和操作的关系：数据和操作的关系：数据是操作的对象，操作的目的是对数据进行加工，以得到期望的结果。数据是操作的对象，操作的目的是对数据进行加工，以得到期望的结果。#inc
2、lude“stdio.h”void main()int a,b,c;scanf(%d,%d,&a,&b);if(ab)c=a;if(ab)c=a;else c=b;else c=b;printf(“max=%dn,c);对数据的描述对数据的描述:在程序中在程序中要指定数据的类型和数据要指定数据的类型和数据的组织形式，即数据的结的组织形式，即数据的结构。构。对操作的描述对操作的描述:即操作步即操作步骤，也就是算法。骤，也就是算法。1.1.引例引例一个程序应包括的两个方面：3第2章 程序的灵魂算法16-Jan-232.1 算法的概念算法的概念 （1 1）著名计算机科学家沃斯（）著名计算机科学家沃斯
3、（Nikiklaus WirthNikiklaus Wirth）提出了一个公式：）提出了一个公式：数据结构+算法=程序 （2 2）设计程序时，还要考虑采用好的设计方法）设计程序时，还要考虑采用好的设计方法-结构化程序设计方法。结构化程序设计方法。因此有：因此有：程序=数据结构+算法+程序设计方法+语言工具和环境2.2.程序的构成程序的构成所谓程序，简单讲就是一组计算机能识别和执行的指令。所谓程序，简单讲就是一组计算机能识别和执行的指令。算法是灵魂；数据（结构）是加工对象；算法是灵魂；数据（结构）是加工对象；语言是工具；编程需要采取合适的方法。语言是工具；编程需要采取合适的方法。以上以上4 4个
4、方面是一个程序设计人员应具备的知识。设计一个程序时要个方面是一个程序设计人员应具备的知识。设计一个程序时要综合运用这几方面的知识。综合运用这几方面的知识。本门课程重点讲述算法的设计。(注意数据结构这门课程）4第2章 程序的灵魂算法16-Jan-232.1 算法的概念算法的概念3.3.算法的概念算法的概念 广义地说，为解决一个问题而采取的方法和步骤，就称为广义地说，为解决一个问题而采取的方法和步骤，就称为算法。（算法。（用计算机解决问题的步骤，即计算机算法。用计算机解决问题的步骤，即计算机算法。）计算机算法可分为两大类：计算机算法可分为两大类：n数值算法数值算法n求方程的根n求函数的定积分n非数
5、值算法非数值算法n图书检索n人事管理算法解决算法解决做什么做什么和和怎么做怎么做的问题。的问题。程序中的按一定顺序列出的操作语句，就是算法的体现。5第2章 程序的灵魂算法16-Jan-232.2 简单算法举例简单算法举例例例2.12.1：求：求1 12 23 34 45 5最原始的方法：步骤步骤1 1：求求1 12,2,得结果得结果2 2。步骤步骤2 2：将第将第1 1步得到的结果再乘以步得到的结果再乘以3,3,得结果得结果6 6。步骤步骤3 3：将第将第2 2步得到的结果再乘以步得到的结果再乘以4,4,得结果得结果2424。步骤步骤4 4：将第将第3 3步得到的结果再乘以步得到的结果再乘以5
6、,5,得得120120。如果按照此方法，求如果按照此方法，求1 12 23 3.100100，要写多少步？，要写多少步？99步！步！6第2章 程序的灵魂算法16-Jan-23改进的方法（或通用的方法）：改进的方法（或通用的方法）：先设两个变量先设两个变量p p和和i i，p p代表被乘数，代表被乘数，i i代表乘数。并且将每一步乘积直代表乘数。并且将每一步乘积直接放入被乘数变量接放入被乘数变量p p中。用循环算法求结果。中。用循环算法求结果。步骤步骤1 1：令：令p=1p=1 步骤步骤2 2：令：令i=2i=2 步骤步骤3 3：使：使p pi,i,并将乘积放入并将乘积放入p p中。通常表示为中
7、。通常表示为p pi=pi=p 步骤步骤4 4：使：使 i i 的值加的值加1 1，表示为，表示为 i+1=i i+1=i 步骤步骤5 5：如果：如果i i 不大于不大于5 5，返回到步骤，返回到步骤3 3继续向下执行；否则算法结束。继续向下执行；否则算法结束。p p中的值即最后结果。中的值即最后结果。2.2 简单算法举例简单算法举例采用此方法，采用此方法，求求1 12 23 3.100100，如何？，如何？简练！简练！7第2章 程序的灵魂算法16-Jan-23例例2.22.2：有两个数：有两个数a,ba,b，按从大到小的顺序打印它们。，按从大到小的顺序打印它们。步骤步骤1 1：输入输入a,b
8、a,b的值；的值；步骤步骤2 2：如果如果ab,ab,则先打印则先打印a a，再打印，再打印b b；否则，先打否则，先打 印印b b，再，再 打印打印a a；算法结束。；算法结束。详细例题见课本详细例题见课本16-1816-18页。页。2.2 简单算法举例简单算法举例8第2章 程序的灵魂算法16-Jan-23 算法的5个特性：n 有穷性：一个算法应包含有限的操作步骤，而不能是有穷性：一个算法应包含有限的操作步骤，而不能是无限的。无限的。n 确定性：算法中的每一个步骤都应当是确定的，而不确定性：算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。应当是含糊的、模棱两可的。n 有零个或
9、多个输入：所谓输入是指在执行算法时需要有零个或多个输入：所谓输入是指在执行算法时需要从外界取得必要的信息。从外界取得必要的信息。n 有一个或多个输出：算法的目的是为了求解，有一个或多个输出：算法的目的是为了求解，“解解”就是输出。就是输出。n 有效性：算法中的每一个步骤都应当能有效的执行，有效性：算法中的每一个步骤都应当能有效的执行，并得到结果。并得到结果。2.3 算法的特性算法的特性9第2章 程序的灵魂算法16-Jan-232.4 算法的表示算法的表示2.4.1用自然语言表示用自然语言表示2.4.2用流程图表示用流程图表示2.4.3用用N-S图表示图表示2.4.4用伪代码表示用伪代码表示2.
10、4.5用计算机语言表示用计算机语言表示10第2章 程序的灵魂算法16-Jan-23用自然语言表示算法用自然语言表示算法例例2.12.1和例和例2.22.2的算法是用自然语言写的。的算法是用自然语言写的。自然语言指人们日常使用的语言，如汉语、英语等。自然语言指人们日常使用的语言，如汉语、英语等。用自然语言表示算法的特点：通俗易懂，但不严谨，用自然语言表示算法的特点：通俗易懂，但不严谨，容易产生歧义。容易产生歧义。除非问题很简单，一般不用自然语言描述算法。除非问题很简单，一般不用自然语言描述算法。11第2章 程序的灵魂算法16-Jan-23用流程图表示算法用流程图表示算法流程图采用一些图形框表示算
11、法要表述的各种操作。流程图采用一些图形框表示算法要表述的各种操作。美国国家标准化协会美国国家标准化协会ANSIANSI规定了一些常用的流程图符号：规定了一些常用的流程图符号：起止框起止框处理框处理框判断框判断框输入输出框输入输出框流程线流程线注释注释连接点连接点或或12第2章 程序的灵魂算法16-Jan-23用流程图表示算法举例用流程图表示算法举例例2.3 计算1x3x11的值 步骤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继续向下执行；否则算法结束。
12、p中的值即最后结果。开始1=p1=ip i=p i+2=ii11真结束假输出p的值13第2章 程序的灵魂算法16-Jan-23例2.2 有两个数a,b，按从大到小的顺序打印它们。步骤步骤1 1：输入a,b的值；步骤步骤2 2：如果ab,则先打印a，再打印b；否则，先打印b，再打印a；算法结束。真假开始ab结束输出b,a的值输入a,b的值输出a,b的值用流程图表示算法举例用流程图表示算法举例14第2章 程序的灵魂算法16-Jan-23三种基本结构三种基本结构-顺序结构顺序结构顺序结构：顺序结构：BA虚线框内是一个顺序结构。虚线框内是一个顺序结构。AB两个框是顺序执行的：两个框是顺序执行的：按图中
13、所画的框的顺序，先执按图中所画的框的顺序，先执行行A操作，再执行操作，再执行B操作。操作。15第2章 程序的灵魂算法16-Jan-23选择结构选择结构虚线框内是一个选择结构虚线框内是一个选择结构,也称为分支也称为分支结构。结构。此结构包括一个选择框，框中写有一个此结构包括一个选择框，框中写有一个条件，根据给定的条件是否成立，从而条件，根据给定的条件是否成立，从而选择执行选择执行A A框还是框还是B B框。框。条件PAB成立不成立条件PA成立不成立三种基本结构三种基本结构-选择结构选择结构B操作为空时，画成直线16第2章 程序的灵魂算法16-Jan-23循环结构（当型循环结构（当型-while型
14、）型）虚线框内是一个当型循环结构。虚线框内是一个当型循环结构。当给定的条件成立时，执行当给定的条件成立时，执行A框中的操作；框中的操作；执行完执行完A操作后，判条件操作后，判条件P是否成立；是否成立；如果仍成立，继续执行如果仍成立，继续执行A操作；操作；如此反复执行如此反复执行A框中的操作，直到条件框中的操作，直到条件P不成立为止。不成立为止。三种基本结构三种基本结构-循环结构循环结构条件PA不成立17第2章 程序的灵魂算法16-Jan-23循环结构（直到型循环结构（直到型-until型）型）虚线框内是一个直到型循环结构。虚线框内是一个直到型循环结构。先执行先执行A A框中的操作；框中的操作；
15、执行完执行完A A操作后，判条件操作后，判条件P P是否成立；是否成立；如果不成立，继续执行如果不成立，继续执行A A操作；操作；如此反复执行如此反复执行A A框中的操作，直到条件框中的操作，直到条件P P成立为止。成立为止。条件PA成立三种基本结构三种基本结构-循环结构循环结构18第2章 程序的灵魂算法16-Jan-23以上以上3种基本结构，有以下共同特点：种基本结构，有以下共同特点：1）只有一个入口。）只有一个入口。2）只有一个出口。）只有一个出口。3）结构内的每一个部分都有机会被执行到。）结构内的每一个部分都有机会被执行到。4）结构内不存在）结构内不存在“死循环死循环”。19第2章 程序
16、的灵魂算法16-Jan-23用基本结构的组合表示算法，从而去掉了流程线。避免了用基本结构的组合表示算法，从而去掉了流程线。避免了随意的跳转。随意的跳转。19731973年两名美国学者提出了一种新的流程图形式，并用二年两名美国学者提出了一种新的流程图形式，并用二人名字的第一个字母组合命名了该流程图。即人名字的第一个字母组合命名了该流程图。即N-SN-S流程图，流程图，也称盒图。也称盒图。三种基本结构的表示：三种基本结构的表示：用N-S图表示算法表示算法AB P成立 AB不成立A当条件P成立时A直到条件P成立20第2章 程序的灵魂算法16-Jan-23用用N-SN-S流程图表示举例流程图表示举例这
17、两个操作之间是顺序关系1=P1=i直到 i11 p x i=p i+2=i打印P的值这是一个顺序结构这是一个循环结构上述算法由基上述算法由基本结构组成本结构组成例2.3 计算1x3x11的值 步骤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中的值即最后结果。21第2章 程序的灵魂算法16-Jan-23用伪码表示算法用伪码表示算法伪码伪码 是用一种介于自然语言和计算机语是用一种介于自然语言和计算机语言之间的文字和符号来描述算法
18、。言之间的文字和符号来描述算法。（类（类PascalPascal语言或者类语言或者类C C语言）语言）好处好处前面的算法可用伪码表示为：前面的算法可用伪码表示为：开始开始 置置p的初值为的初值为1 置置i的初值为的初值为1 当当i 小于小于11时，执行下面的操作：时，执行下面的操作：使使 p=p x i 使使 i=i+2 打印打印 p 的值的值结束结束书写方便，格式紧凑，易懂，便书写方便，格式紧凑，易懂，便于向计算机语言过渡。目前使用于向计算机语言过渡。目前使用的比较多，特别是在科技论文中。的比较多，特别是在科技论文中。22第2章 程序的灵魂算法16-Jan-232.4.5用计算机语言表示算法
19、用计算机语言表示算法只有用计算机语言描述的算只有用计算机语言描述的算法才能被计算机的编译环境法才能被计算机的编译环境识别，并被处理、执行。识别，并被处理、执行。用计算机语言表示算法必须用计算机语言表示算法必须严格遵守所用语言语法规则。严格遵守所用语言语法规则。前面几种描述算法的方法对前面几种描述算法的方法对文字等格式要求不严，一般文字等格式要求不严，一般来说，只要能示意就行。来说，只要能示意就行。例例2.3用用C语言表示为：语言表示为：#include int main()int p,i;p=1;i=1;while(ip3=ip i=p i+2=ii101真结束假输出p的值这两个操作之间是顺序
20、关系这是一个循环结构这是一个顺序结构上述算法由基上述算法由基本结构组成本结构组成例2.3 计算1x3x11的值 步骤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中的值即最后结果。27第2章 程序的灵魂算法16-Jan-23作作 业业分析问题分析问题 确定解决方案确定解决方案建立数学模型建立数学模型设计算法设计算法用计算机语言描述算法（即写出源程序）用计算机语言描述算法（即写出源程序）上机调试源程序：经过上机调试源程序：经过编辑、编译、连接、运行，得到可执行的程序。得到可执行的程序。运行程序，得到需要的结果。运行程序，得到需要的结果。课本课本3636页页2.42.4、2.52.5、2.62.6、2.82.828