C语言程序设计及程序代码第2章算法ppt课件.ppt

程序的灵魂——算法 uu算法的概念uu简单算法举例 uu算法的特性uu怎样表示一个算法uu结构化程序方法uu总结 2.1 算法的概念n n程序通常包含的内容有：程序通常包含的内容有：程序通常包含的内容有：程序通常包含的内容有： n n（（（（1 1〕数据的描述：指定数据的类型和组织形式〔数〕数据的描述：指定数据的类型和组织形式〔数〕数据的描述：指定数据的类型和组织形式〔数〕数据的描述：指定数据的类型和组织形式〔数据结构）据结构）据结构）据结构） n n（（（（2 2〕操作的描述：编程的操作步骤，也称算法〔〕操作的描述：编程的操作步骤，也称算法〔〕操作的描述：编程的操作步骤，也称算法〔〕操作的描述：编程的操作步骤，也称算法〔algorithm) algorithm) n n操作的目的：对数据进行加工处理，以便得到结果操作的目的：对数据进行加工处理，以便得到结果操作的目的：对数据进行加工处理，以便得到结果操作的目的：对数据进行加工处理，以便得到结果 n n厨师做菜肴：厨师做菜肴：厨师做菜肴：厨师做菜肴： n n （（（（1 1〕配料：制作菜肴所需的原料〕配料：制作菜肴所需的原料〕配料：制作菜肴所需的原料〕配料：制作菜肴所需的原料 n n （（（（2 2〕步骤：制作某项菜肴时将原料按规定的步骤〕步骤：制作某项菜肴时将原料按规定的步骤〕步骤：制作某项菜肴时将原料按规定的步骤〕步骤：制作某项菜肴时将原料按规定的步骤加工成所需的菜肴加工成所需的菜肴加工成所需的菜肴加工成所需的菜肴2.1 算法的概念n n著名计算机科学家沃思提出一个公式：n n 数据结构+算法=程序n n再加上程序设计方法和语言环境 n n 程序=算法+数据结构+程序设计方法+语言工具和环境2.1 算法的概念n n做任何事情都有一定的步骤。

为解决一个问题而采做任何事情都有一定的步骤为解决一个问题而采取的方法和步骤，就称为算法取的方法和步骤，就称为算法n n计算机算法：计算机能够执行的算法计算机算法：计算机能够执行的算法n n计算机算法可分为两大类：计算机算法可分为两大类：n n数值运算算法：求数值的解数值运算算法：求数值的解 ；；n n非数值运算算法：事务管理领域非数值运算算法：事务管理领域2.2 简单算法举例n n例例例例2.12.1：：：：1×2×3×4×5 1×2×3×4×5 n n 原始算法原始算法原始算法原始算法: S1:: S1:求求求求1×21×2得结果得结果得结果得结果2 2 n n S2: S2:将将将将2×32×3得结果得结果得结果得结果6 6 n n S3: S3:将将将将6×46×4得结果得结果得结果得结果24 24 n n S4: S4:将将将将24×524×5得结果得结果得结果得结果120 120 n n 上述方法虽正确上述方法虽正确上述方法虽正确上述方法虽正确, ,但较烦琐但较烦琐但较烦琐但较烦琐n n解决此类问题的通用方法是：解决此类问题的通用方法是：解决此类问题的通用方法是：解决此类问题的通用方法是： n n 设两个变量：设两个变量：设两个变量：设两个变量： p p 存放被乘数和结果存放被乘数和结果存放被乘数和结果存放被乘数和结果 i i 存存存存放乘数放乘数放乘数放乘数 n n S1 S1：：：：p=1 p=1 n n S2 S2：：：：i=2 i=2 n n S3 S3：：：：p×ip×i→→→→p p n n S4 S4：：：：i+1i+1→→→→i i n n S5 S5：若：若：若：若i<=5 i<=5 返回返回返回返回s3 s3 否则算法结否则算法结否则算法结否则算法结束。

束n n此算法较上面的算法具有通用性和灵活性此算法较上面的算法具有通用性和灵活性此算法较上面的算法具有通用性和灵活性此算法较上面的算法具有通用性和灵活性2.2 简单算法举例n n例例例例2.4 2.4 求求求求1-1/2+1/3-1/4+...+1/99-1/1001-1/2+1/3-1/4+...+1/99-1/100n n 算法如下算法如下算法如下算法如下 ：：：： n n S1: sign=1 S1: sign=1 n n S2: sum=1 S2: sum=1 n n S3: deno=2 S3: deno=2 n n S4: sign=(-1)×sign S4: sign=(-1)×sign n n S5: term=sign×(1/deno) S5: term=sign×(1/deno) n n S6: sum=sum+term S6: sum=sum+term n n S7: deno=deno+1 S7: deno=deno+1 n n S8: S8: 若若若若deno<=100deno<=100返回返回返回返回s4,s4,否则算法结束。

否则算法结束否则算法结束否则算法结束2.2 简单算法举例【例【例2.52.5】对一个大于或等于】对一个大于或等于3 3的正整数，判断它是的正整数，判断它是不是一个素数不是一个素数 S1: S1: 输入输入n n的值的值 S2: i=2 S2: i=2 S3: n S3: n被被i i除，得余数除，得余数r r S4: S4:如果如果r=0r=0，表示，表示n n能被能被i i整除，则打印整除，则打印n“n“不是素不是素数数” ”，算法结束；否则执行，算法结束；否则执行S5S5 S5: i+1 S5: i+1→→i i S6: S6:如果如果i≤n-1i≤n-1，返回，返回S3S3；否则打印；否则打印n“n“是素数是素数” ”；；然后算法结束然后算法结束 2.2 简单算法举例【例【例2.52.5】对一个大于或等于】对一个大于或等于3 3的正整数，判断它是的正整数，判断它是不是一个素数不是一个素数 S1: S1: 输入输入n n的值的值 S2: i=2 S2: i=2 S3: n S3: n被被i i除，得余数除，得余数r r S4: S4:如果如果r=0r=0，表示，表示n n能被能被i i整除，则打印整除，则打印n“n“不是素不是素数数” ”，算法结束；否则执行，算法结束；否则执行S5S5 S5: i+1 S5: i+1→→i i 改进：改进： S6: S6:如果如果i≤ sqrt(n)i≤ sqrt(n)，返回，返回S3S3；否则打印；否则打印n“n“是素是素数数”;”;然后算法结束然后算法结束2.3 算法的特性n n有穷性：有限的操作步骤和合理的计算时间。

n n确定性：不应当产生“歧义性”n n有零个或多个输入n n有一个或多个输出：算法的输出不一定就是计算机的打印输出n n有效性：如除数不得为零2.4 怎样表示一个算法 n n自然语言表示n n传统流程图表示n nN-S流程图表示 n n伪代码表示 n n计算机语言表示 2.4 怎样表示一个算法 自然语言： 世界上男人没有了女人就慌了 世界上男人没有了，女人就慌了 世界上，男人没有了女人，就慌了2.4 怎样表示一个算法n n用流程图表示算法用流程图表示算法 n nANSIANSI规定的流程图符号，已为世界各国采用，规定的流程图符号，已为世界各国采用，用图框表示操作，用图形表示算法用图框表示操作，用图形表示算法 2.4 怎样表示一个算法n n【例【例2.62.6】将例】将例2.12.1的算的算法用流程图表示法用流程图表示1×2×3×4×51×2×3×4×52.4 怎样表示一个算法n n例例2.9 2.9 用流程图算法求用流程图算法求2.4 2.4 2.4 怎样表示一个算法n n例例 2.10: 2.10: 用流程图算法判断素数用流程图算法判断素数此处应该填此处应该填写什么写什么？？2.4 怎样表示一个算法n n例例 2.10: 2.10: 用流程图算法判断素数用流程图算法判断素数n-1,sqr(n)n-1,sqr(n)2.4 怎样表示一个算法n n可以看出流程图所包含的部分可以看出流程图所包含的部分: : n n （（1 1〕图框：表示相应操作；〕图框：表示相应操作； n n （（2 2〕流程线：表示操作的先后顺序；〕流程线：表示操作的先后顺序； n n （（3 3〕框内外必要的文字说明。

〕框内外必要的文字说明 n n流程图表示算法：流程图表示算法： n n 优点：形象直观、表示清晰，各框之间逻辑关优点：形象直观、表示清晰，各框之间逻辑关系清楚系清楚 n n 缺点：流程图占篇幅较多，当算法复杂时，画缺点：流程图占篇幅较多，当算法复杂时，画流程图费时且不方便流程图费时且不方便 2.4 怎样表示一个算法n n算法的三种基本结构算法的三种基本结构n n (1) (1) 顺序结构顺序结构 2.4 怎样表示一个算法n n算法的三种基本结构算法的三种基本结构n n (2) (2) 选择结构选择结构 2.4 怎样表示一个算法n n算法的三种基本结构算法的三种基本结构----循环结构循环结构 n n ①①当〔当〔whilewhile〕型循环结构〕型循环结构 ①当〔while〕型循环结构 功能：给定条件P1成立时，执行A， 执行完后再判断条件是否成立，如 此反复，直到某次P1条件不成立为止三种结构的共点： 当型循环实现当型循环实现5 5个数的个数的打印打印 输出用传统流程输出用传统流程图算法实现图算法实现确实可以？确实可以？确实可以？确实可以？2.4 怎样表示一个算法n n算法的三种基本结构算法的三种基本结构----循环结构循环结构 n n ②②直到型〔直到型〔UntilUntil〕循环〕循环 ①当〔while〕型循环结构 功能：给定条件P1成立时，执行A， 执行完后再判断条件是否成立，如 此反复，直到某次P1条件不成立为止三种结构的共点： 直到型循环直到型循环实现实现5 5个数个数的打印的打印 输出输出用传统流程用传统流程图算法实现图算法实现2.4 怎样表示一个算法n n三种结构的共点：三种结构的共点： n n (1) (1)只有一个入口只有一个入口 n n (2) (2)只有一个出口只有一个出口. . n n (3) (3)结构内的每一部分都有机会被执行到结构内的每一部分都有机会被执行到n n每一框内应有一条从入口到出口的路径通过每一框内应有一条从入口到出口的路径通过n n (4) (4)结构内不能存在死循环结构内不能存在死循环 2.4 怎样表示一个算法n n用用N--SN--S流程图表示顺序结构流程图表示顺序结构n n用用N--SN--S流程图表示选择结构流程图表示选择结构n n用用N--SN--S流程图表示循环结构流程图表示循环结构2.4 怎样表示一个算法n n用用N-SN-S流程图表示算法讨论上述各例流程图表示算法讨论上述各例2.4 怎样表示一个算法算法用伪代码表示:例2.16 求5! 算法用伪代码表示 BEGIN〔算法开始） 1→t 2→i While i<=5 { t×i →t i+1 →i } print t END〔算法结束）2.4 怎样表示一个算法n n用计算机语言表示算法 2.5结构化程序n n结构化程序：就是用高级语言表示的算法，三种基结构化程序：就是用高级语言表示的算法，三种基本结构组成的程序必然是结构化程序。

本结构组成的程序必然是结构化程序n n设计思路设计思路 n n– –自顶向下、逐步细化、模块化设计、结构化编码自顶向下、逐步细化、模块化设计、结构化编码 n n• •程序结构：程序结构： n n– –按功能划分为若干个基本模块，形成一个树状结按功能划分为若干个基本模块，形成一个树状结构 n n– –各模块间的关系尽可能简单，功能上相对独立；各模块间的关系尽可能简单，功能上相对独立；每一模块内部均是由顺序、选择和循环三种基本结每一模块内部均是由顺序、选择和循环三种基本结构组成 n n– –其模块化实现的具体方法是使用子函数〔子程序）其模块化实现的具体方法是使用子函数〔子程序） 2.5结构化程序n n例例2.222.22　将　将1 1到到10001000之间的素数打印出来埃拉托色尼筛法之间的素数打印出来埃拉托色尼筛法n n1 1　　2 2　　3 3　　4 4　　5 5　　6 6　　7 7　　8 8　　9 9　　1010　　1111　　1212　　1313　　1414　　1515　　1616　　1717　　1818　　······　　······\ \ 2　3 　5　 　7　 　9　 　 11　 　 13　 　15　 　 17　 　···　··· 　2　3　4　5　6　7　8　9　10　11　12　13　14　15　16　17　18　···　··· 2　3 　5　 　7　 　 　 　 11　 　 13　 　 　 　 17　 　···　···2.5结构化程序n n例例2.222.22　将　将1 1到到10001000之间的素数打印出来。

之间的素数打印出来n n1 1　　2 2　　3 3　　4 4　　5 5　　6 6　　7 7　　8 8　　9 9　　1010　　1111　　1212　　1313　　1414　　1515　　1616　　1717　　1818　　······　　······\ \1)1)1)1)挖去挖去挖去挖去1 1 1 1；；；；2)2)2)2)用下一个未被挖去的数　用下一个未被挖去的数　用下一个未被挖去的数　用下一个未被挖去的数　P P P P　去除后面的各数，把　　去除后面的各数，把　　去除后面的各数，把　　去除后面的各数，把　P P P P　的倍数挖掉；　的倍数挖掉；　的倍数挖掉；　的倍数挖掉；3)3)3)3)检查　检查　检查　检查　P P P P　是否小于　是否小于　是否小于　是否小于 sqrt(n) sqrt(n) sqrt(n) sqrt(n)的整数部分，如果是，则返回〔的整数部分，如果是，则返回〔的整数部分，如果是，则返回〔的整数部分，如果是，则返回〔2 2 2 2〕继续执行，否〕继续执行，否〕继续执行，否〕继续执行，否则就结束则就结束则就结束则就结束4)4)4)4)纸上剩下的数就是素数纸上剩下的数就是素数。

纸上剩下的数就是素数纸上剩下的数就是素数2.5结构化程序输入输入1 1～～n n把所有非素数去掉把所有非素数去掉打印全部素数打印全部素数ABC2.5结构化程序输入输入1 1～～n n把所有非素数去掉把所有非素数去掉打印全部素数打印全部素数ABC输入输入n ni=1i=1当当i<=ni<=nXi=iXi=ii=i+1i=i+12.5结构化程序输入输入1 1～～n n把所有非素数去掉把所有非素数去掉打印全部素数打印全部素数ABC将将X1X1去掉（使去掉（使X1X1＝＝0 0））i=2i=2当当i