09程序设计语言初步第四章二ppt课件

1、 1第四章第四章 算法设计方法算法设计方法 24.1 算法的概念算法的概念4.2 算法的三种基本结构算法的三种基本结构4.3 算法的描述方法算法的描述方法4.4 结构化程序设计方法结构化程序设计方法4.5 算法设计实例研究算法设计实例研究提纲提纲 3 程序设计的目的和步骤程序设计的目的和步骤 算法的描述方式算法的描述方式 计算机算法及其特性计算机算法及其特性4.1 算法的概念算法的概念 44.1 算法的概念算法的概念一一. 程序设计的目的程序设计的目的计算机科学与技术学科的根本问题是：什计算机科学与技术学科的根本问题是：什么能够被有效地自动化么能够被有效地自动化 ；设计程序的根本目的：让计算机

2、帮助人们设计程序的根本目的：让计算机帮助人们自动地完成所要处理的复杂任务；自动地完成所要处理的复杂任务；程序设计两个核心问题：程序设计两个核心问题：“做什么与做什么与“怎怎么做么做” ；其中需求分析解决；其中需求分析解决“做什么做什么”，程，程序设计解决序设计解决“怎么做怎么做” 。 54.1 算法的概念算法的概念二二. 程序设计两步走程序设计两步走对复杂问题，直接写出能解决该问题的对复杂问题，直接写出能解决该问题的计算机程序是困难的，为此，人们在进计算机程序是困难的，为此，人们在进行程序设计时分两步走：行程序设计时分两步走：1算法设计：不使用程序设计语言，而使算法设计：不使用程序设计语言，而

3、使用一种较简单明了的表达方式例如自用一种较简单明了的表达方式例如自然语言设计出求解问题的步骤序列然语言设计出求解问题的步骤序列-算法。算法。2程序编写：根据设计并描述好的算法，程序编写：根据设计并描述好的算法，使用某种程序设计语言编写对应于该算使用某种程序设计语言编写对应于该算法的程序法的程序 。 6三三. 算法的概念算法的概念算法：是解决问题的步骤序列操作序列算法：是解决问题的步骤序列操作序列）。）。 4.1 算法的概念算法的概念起床起床穿衣、叠被穿衣、叠被去水房洗漱去水房洗漱回宿舍放洗漱用品回宿舍放洗漱用品骑车去食堂骑车去食堂排队买饭排队买饭吃饭吃饭交回餐具交回餐具骑车去教室骑车去教室描述

4、的是描述的是活动和过活动和过程程7:20前离开宿舍前离开宿舍7:50前离开食堂前离开食堂8:00前进入教室前进入教室描述的是操作执行后描述的是操作执行后的状态，通过状态的的状态，通过状态的转移来描述所执行的转移来描述所执行的操作。操作。可能的活动：可能的活动：起床、穿衣叠起床、穿衣叠被、洗漱等被、洗漱等可能的活动：可能的活动：骑车到食堂、骑车到食堂、排队买饭、吃排队买饭、吃饭、交回餐具饭、交回餐具 74.1 算法的概念算法的概念四四. 计算机算法及其特性计算机算法及其特性什么是计算机可执行的操作；什么是计算机可执行的操作；要在计算机能力集上进行算法设计；要在计算机能力集上进行算法设计；算法必须

5、具备的五个特性：算法必须具备的五个特性：可执行性：算法中的每一个步骤都是计算机可执行可执行性：算法中的每一个步骤都是计算机可执行的在计算机能力集范围内）的在计算机能力集范围内） ；确定性：算法中的每一个步骤，必须是明确定义的确定性：算法中的每一个步骤，必须是明确定义的，不得有任何歧义性，不得有任何歧义性 ；有穷性：算法必须在执行有穷步之后结束；有穷性：算法必须在执行有穷步之后结束； 有输入信息的说明：对加工对象提要求；有输入信息的说明：对加工对象提要求；有输出信息的步骤有输出信息的步骤 ：至少要输出问题答案。：至少要输出问题答案。 8例例1 求求12910 ，即，即10！ 算法思路：算法思路：

6、 计算机能力集只提供两数相乘的运算。计算机能力集只提供两数相乘的运算。 N！=N （N-1）！）！ 10！=10 9！=10 9 8！ =10 9 8 7！ =. =10 9 8 2 1! 先计算先计算1！、再计算！、再计算2!=2*1!、再计算、再计算3!=3*2!,以此类推，直到计算出以此类推，直到计算出10!=10*9!。 使用变量使用变量p 9例例1 求求12910 ，即，即10！第一种算法：第一种算法：S1(求求2!)：先求：先求21，得到结果，得到结果2并赋值给变量并赋值给变量p；即：；即：21p；S2 (求求3!) ：将步骤：将步骤S1得到的乘积得到的乘积pp=2再乘以再乘以3，

7、得结果，得结果6并并 赋值给变量赋值给变量p；即：；即： 3 pp；S3(求求4!)：将：将pp=6再乘以再乘以4，得，得24并赋值给变量并赋值给变量p；即：；即： 4pp；S4(求求5！)：将：将pp=24再乘以再乘以5，得，得120并赋值给变量并赋值给变量p；即：；即： 5pp；S9(求求10!)：将：将pp=362880)乘以乘以10，得，得3628800，10pp； 10#includemain() int p; p=2*1; /求求2!赋值给赋值给p p=3*p; /求求3!赋值给赋值给p p=4*p; p=5*p; p=6*p; p=7*p; p=8*p; p=9*p; p=10*

8、p; /求求10!赋值给赋值给p printf(%d,p); system(pause); return 0; 评价：求评价：求10!需要写需要写9个赋值操作，算法个赋值操作，算法过于繁琐！试想：过于繁琐！试想：求求1000！的算法！的算法 11 对算法进行抽象对算法进行抽象:核心操作就是两数相乘核心操作就是两数相乘ipp ，反复相乘，反复相乘10-1=9次，次，i初始值为初始值为2，p初始值为初始值为1，每相乘一次，每相乘一次i的值加的值加1。 根据上述分析，本题可利用循环结构求解：根据上述分析，本题可利用循环结构求解：第第1次循环用于求次循环用于求2！，第！，第2次循环在第次循环在第1次循

9、次循环基础上求环基础上求3！，！，,第第9次循环在第次循环在第8次循环基础次循环基础上求上求10！例例1 求求12910 ，即，即10！ 12定义两个变量定义两个变量p和和i，p代表阶乘结果代表阶乘结果,i代表本次循环要代表本次循环要求的是求的是i!； 循环条件：循环条件：ip；S4：使：使i的值加的值加1，即，即i+1=i；S5：如果：如果i=10，返回重新执行步骤，返回重新执行步骤S3以及其后的以及其后的步骤步骤S4和和S5；否则，算法结束。；否则，算法结束。 最后得到最后得到p的值就是的值就是10！的值。！的值。 求求12910算法思路：算法思路：“迭代和迭代和“循环循环” ：在程序设计

10、中，重复执行同样操：在程序设计中，重复执行同样操作的过程称为作的过程称为“迭代迭代”。程序中被重复执行的程序段。程序中被重复执行的程序段称为称为“循环循环”。 14例例1源程序源程序#include main() int n, i, p; /n：存储要求阶乘的数；：存储要求阶乘的数；p：存储求得的阶乘；：存储求得的阶乘； printf(input n:n);scanf(%d,&n);i=2; p=1; while (i = n) p=i*p; i=i+1; printf(%d!=%d,n,p); system(pause); return 0; 15 练习练习1：输入十个整数，求出最大

11、值、最小值：输入十个整数，求出最大值、最小值。 算法思路：采用迭代计算的方法算法思路：采用迭代计算的方法 以求最大值为例，即：以求最大值为例，即： Max(N1)=N1 Max(N2,N1)= N1 if N2=N1 Max(N3,N2,N1)= Max( N3, Max(N2,N1) ) . Max(Nn , Nn-1 ,N2,N1) Max(Nn ,Max(Nn-1 ,N2,N1)定义变量定义变量max来存储前来存储前n-1个整数的最大值。个整数的最大值。第第n个数将和个数将和max比比较，决定前较，决定前n个数的个数的最大值。最大值。整个问题就被转变为求整个问题就被转变为求9次两个次两个

12、数的最大值。数的最大值。每一次都是读入一个数，和之每一次都是读入一个数，和之前求得的最大数再去比较。前求得的最大数再去比较。 16循环条件：循环条件：imax,则则max=n； 否则，如果否则，如果nmin,则则min=n； i=i+1;循环初始化：循环初始化：读入一整数读入一整数n;minn; max=n;i2；请写出本题源程序请写出本题源程序 17源程序：输入十个整数，求出最大值、最小值源程序：输入十个整数，求出最大值、最小值#include#define COUNT 10 main() int i, n, max, min;/i:循环计数；循环计数；n:读取的数；读取的数； /max:当

13、前最大值当前最大值; min:当前最小值当前最小值 scanf(%d, &n); max=n; /将第一个数作为最大值和最小值将第一个数作为最大值和最小值 min=n; i=2; /代表接下去要读取的是第代表接下去要读取的是第2个数个数 18源程序：输入十个整数，求出最大值、最小值源程序：输入十个整数，求出最大值、最小值(续续) while (i max) /求最大数求最大数 max = n; else if (n i；问题分析：就是反复输入处理每一个学生的信息，处理问题分析：就是反复输入处理每一个学生的信息，处理120次。次。 20输入输入120个学生的学号和成绩，要求将他们之中个学

14、生的学号和成绩，要求将他们之中成绩在成绩在60分以上者的学号和成绩打印出来。分以上者的学号和成绩打印出来。S1S1：1=i1=i；S2S2：读入第：读入第i i个学生的学号和成绩分别到变量个学生的学号和成绩分别到变量numnum和和scorescore中；中；S3S3：如果：如果score 60score 60，则打印，则打印numnum和和score score ；S4S4：i+1=ii+1=i；S5S5：如果：如果i120i120，则返回，则返回S2S2，继续执行；否则，算法结束。，继续执行；否则，算法结束。循环处理模式：循环处理模式：处理本次循环要做的任务；处理本次循环要做的任务；为下一

15、次循环做准备；为下一次循环做准备； 214.1 算法的概念算法的概念练习练习2：请写出本题对应的程序：请写出本题对应的程序 224.1 算法的概念算法的概念#include main() int no,total,count;/no:学号。学号。total:总学生数。总学生数。count：计数：计数 float score;/成果成果 printf(how many int numbers do you want to input:n);scanf(%d,&total); count=1;while(count60) printf(no:%dtscore:%fn,no,score);

16、count=count+1; system(pause); return 0； 23例例3 一个大于或等于一个大于或等于3的正整数，判断它是否为一的正整数，判断它是否为一个素数质数）个素数质数） 。所谓质数，是指除了所谓质数，是指除了1和该数本身外，不能被其和该数本身外，不能被其他任何整数整除的数。例如，他任何整数整除的数。例如，13是素数质数）。是素数质数）。因为它不能被因为它不能被2，3，4，12整除。整除。由于素数在当代的密码学中扮演了中心的作用，由于素数在当代的密码学中扮演了中心的作用，所以该问题具有重要意义。所以该问题具有重要意义。判断一个数判断一个数nn3是否为质数：将是否为质数：

17、将n作为被除作为被除数，将数，将2到到n-1各个整数依次作为除数，如果各个整数依次作为除数，如果都不能被整除，则都不能被整除，则n为素数。为素数。4.1 算法的概念算法的概念 24判断质数看看n能否被能否被2到到n-1之间的各个整数整除：之间的各个整数整除： 变量抽象：变量抽象：n：存放被判断的整数；：存放被判断的整数；i：存放除：存放除 数，取值为数，取值为2,n-1；r：存放：存放n/i得到的余数得到的余数循环体：循环体：n被被i除，得余数除，得余数r；即；即n mod i=r；如果如果r=0，表示，表示n能被能被i整除，则打印整除，则打印n“不是素数不是素数”，算法结束；否则算法结束；否

18、则i+1=i；循环条件：循环条件： ir；如果如果r=0，表示，表示n能被能被i整除，则打印整除，则打印n“不是素数不是素数”，令令isPrim=1；否则；否则i+1=i；循环条件：循环条件： irn mod i=rS4S4：如果：如果r=0r=0，表示，表示n n能被能被i i整除，则打印整除，则打印n“n“不是素数不是素数”，算法结束；否则执行，算法结束；否则执行S5S5；S5S5：i+1=ii+1=i；S6S6：如果：如果in-1in-1，返回，返回S3S3；否则，打印；否则，打印n“n“是素数是素数”，算法结束。，算法结束。 n：被判断的整数；：被判断的整数；i：被除数；：被除数；r：

19、存放：存放n/i得到的余数得到的余数事实上，事实上，i只需只需2到到 之间的整数整除即可。之间的整数整除即可。n 274.1 算法的概念算法的概念4.2 算法的三种基本结构算法的三种基本结构4.3 算法的描述方法算法的描述方法4.4 结构化程序设计方法结构化程序设计方法4.5 算法设计实例研究算法设计实例研究提纲提纲 284.2 算法的三种基本结构算法的三种基本结构 三种控制结构三种控制结构(Bohra和和Jacopini )顺序结构、顺序结构、 选择结构、循环结构选择结构、循环结构 顺序结构顺序结构 按书写顺序执行的语句构按书写顺序执行的语句构成的程序段。成的程序段。 29选择结构选择结构u

20、 根据给定的表达式是否成立而选择执行操作根据给定的表达式是否成立而选择执行操作A A或操或操作作B B。如果表达式成立，则执行操作。如果表达式成立，则执行操作A A；如果表达式不；如果表达式不成立，则执行操作成立，则执行操作B B。u操作操作B B可以为空。可以为空。4.2 算法的三种基本结构算法的三种基本结构 30 当型循环结构当型循环结构4.2 算法的三种基本结构算法的三种基本结构C语言无直到型循环结构。语言无直到型循环结构。比较：直到型循环结构和比较：直到型循环结构和C语言中的语言中的do-while结构？结构？ 直到型循环结构直到型循环结构 31三种控制结构的共同点三种控制结构的共同点

21、 只有一个入口只有一个入口a a处）处） 只有一个出口只有一个出口b b处）处） 结构内的每一个部分都有机会被执行到结构内的每一个部分都有机会被执行到 结构内不存在结构内不存在“死循环死循环”（无终止的循环）（无终止的循环）4.2 算法的三种基本结构算法的三种基本结构由这三种基本结构顺序组成的算法结构，可由这三种基本结构顺序组成的算法结构，可以解决任何复杂问题！以解决任何复杂问题！ 324.1 算法的概念算法的概念4.2 算法的三种基本结构算法的三种基本结构4.3 算法的描述方法算法的描述方法4.4 结构化程序设计方法结构化程序设计方法4.5 算法设计实例研究算法设计实例研究提纲提纲 334.

22、3 算法的描述方法算法的描述方法 用自然语言描述 用流程图描述 用N-S流程图描述 用伪码描述 用计算机语言描述 344.3 算法的描述方法自然语言算法的描述方法自然语言文字冗长；文字冗长； 不严格，易产生歧义二义性）；不严格，易产生歧义二义性）； 不方便描述分支和循环结构；不方便描述分支和循环结构； 354.3 算法的描述方法流程图算法的描述方法流程图 流程图的基本元素流程图的基本元素ANSIANSI规定）规定） 起止框输入/出框判断框处理框流程线 连接点 注释框 364.3 算法的描述方法流程图算法的描述方法流程图流程图描述的选择结构流程图描述的选择结构 37 当型循环结构当型循环结构 直

23、到型循环结构直到型循环结构流程图描述的循环结构流程图描述的循环结构4.3 算法的描述方法流程图算法的描述方法流程图 38连接点小圆圈）：用于将画在不同地方的流程线连连接点小圆圈）：用于将画在不同地方的流程线连接起来接起来 39求求10！流程图！流程图使用当型循使用当型循环结构描述环结构描述 40打印学生序号打印学生序号及成绩流程图及成绩流程图 41判断质判断质数的流数的流程图程图使用直到型循使用直到型循环结构描述环结构描述判断判断r是否是否为为0条件成立则条件成立则跳出循环跳出循环 42练习：将以上流程图改成用当型循环结构表示。练习：将以上流程图改成用当型循环结构表示。该流程图中循该流程图中循

24、环结构有两个环结构有两个出口！违反单出口！违反单入单出原则！入单出原则！如何改进？如何改进？ 43改进后的流程图：改进后的流程图：单入单出单入单出 设置标志设置标志位位isPrim 44 传统流程图的弊端传统流程图的弊端 对流程线的使用没有严格限制，阅读困难；对流程线的使用没有严格限制，阅读困难； 不能保证算法结构的单入单出特性；不能保证算法结构的单入单出特性； 占用篇幅较多占用篇幅较多 ； 4.3 算法的描述方法算法的描述方法N-S流程图流程图必须限制箭头的滥用，让流程只能顺序执必须限制箭头的滥用，让流程只能顺序执行下去！行下去！保证结构化原则的流程描述工具保证结构化原则的流程描述工具N-S

25、图图 45 基本结构4.3 算法的描述方法算法的描述方法N-S流程图流程图p、p1表示的是表示的是判断条件；判断条件；A、B框是操作；框是操作；留意：留意：A、B框可框可以是一个简单以是一个简单的操作如读的操作如读入数据或打印入数据或打印输出等），也输出等），也可以是三种基可以是三种基本结构之一本结构之一顺序结构顺序结构选择结构选择结构当型循环结构当型循环结构直到型循环结构直到型循环结构 46例例1 求求10!的的N-S流程图流程图4.3 算法的描述方法算法的描述方法N-S流程图流程图 47例例2 打印学生成绩打印学生成绩N-S流程图流程图4.3 算法的描述方法算法的描述方法N-S流程图流程图

26、 48例例3 判断质数的判断质数的N-S流程图流程图4.3 算法的描述方法算法的描述方法N-S流程图流程图 494.3 算法的描述方法伪码描述算法的描述方法伪码描述 流程图和流程图和N-S图画起来比较费事，适合于表示图画起来比较费事，适合于表示算法，而在算法设计中使用不是很理想。算法，而在算法设计中使用不是很理想。 伪码伪码 用介于自然语言和程序设计语言之间的文用介于自然语言和程序设计语言之间的文字和符号来描述算法。字和符号来描述算法。【前往】 IF x is positive THEN print x ELSE print yWHILE i60 THEN print score i加加1 5

27、04.3 算法的描述方法算法的描述方法例例4：利用泰勒级数：利用泰勒级数：- -LLLLLLLL+ +- - -+ + +- -+ +- -= =+ +)!12() 1(! 7! 5! 3sin121753nxxxxxxnn计算正弦的值，直到最后一项绝对值小于计算正弦的值，直到最后一项绝对值小于10-6 时为止。时为止。被除被除数数除数除数符号符号n1 n2 n3分析：求分析：求n项和的算法思路项和的算法思路Sum(a1)=a1Sum(a1,a2)=Sum(a1)+a2 =a1+a2Sum(a1,a2, a3)=Sum(a1,a2)+a3Sum(a1,a2,an)=Sum(a1,a2,an-1

28、)+an 514.3 算法的描述方法算法的描述方法 算法的核心操作是求两数之和，其中第一个操算法的核心操作是求两数之和，其中第一个操作数是前一次求得的和。如何求第二个操作数作数是前一次求得的和。如何求第二个操作数？ 算法算法1：n决定了第决定了第n项因子的值，即第二个操项因子的值，即第二个操作数；因此每一次可根据当前作数；因此每一次可根据当前n的值计算出第的值计算出第二个操作数。二个操作数。 请用请用NS图描述出算法图描述出算法1。 52求求sin(x)算法算法1i代表下一个代表下一个p是第几项，是第几项，因此初值是因此初值是1变量抽象：变量抽象： x：存储未知数：存储未知数x的的值；值； s

29、um：存储和：存储和 ； p：存储当前待加的：存储当前待加的因子；因子；i：当前待加：当前待加的是第几个因子的是第几个因子 53问题：任何数据类型只能表示一定范围内的数，问题：任何数据类型只能表示一定范围内的数，当试图往变量中存储在范围之外的数，数据无当试图往变量中存储在范围之外的数，数据无法正确存储。求法正确存储。求x的的n次方和次方和(2n-1)!时可能会导时可能会导致结果太大而溢出。致结果太大而溢出。解决方法：解决方法：1.用浮点型变量来保存用浮点型变量来保存(2n-1)!的结果的结果2.改进算法改进算法算法算法2 544.3 算法的描述方法算法的描述方法=pi 1- - - -)!32

30、() 1(32ixii=Pi- - - -+ +)!12() 1(121ixiiPiPipi 1- -LLLLLLLL+ +- - -+ + +- -+ +- -= =+ +)!12() 1(! 7! 5! 3sin121753nxxxxxxnn算法算法2：设第：设第i项因子表示为项因子表示为 ，调查，调查 和和 的关系。的关系。 = = * *(-1)(-1)* * x2 /(2i-1) x2 /(2i-1)* *(2i-(2i-2)2)Pipi 1- 55请用请用NS图描述算法图描述算法2。4.3 算法的描述方法算法的描述方法 【源程序演示】i代表下一个代表下一个p是第几项，是第几项，因此

31、初值是因此初值是1 56#include#includemain()int i;float x; double sum,p; /p用于存放待加的那一项用于存放待加的那一项printf(input x:);scanf(%f,&x);/*变量初始化变量初始化*/sum=0.0;i=1;p=x;/*求解求解*/while(fabs(p)1e-8) sum=sum+p; i=i+1; p=-p*x*x/(2*i-2)*(2*i-1); printf(sin(%f) = %lfn,x,sum); system(pause); return 0; 574.1 算法的概念算法的概念4.2 算法的三种

32、基本结构算法的三种基本结构4.3 算法的描述方法算法的描述方法4.4 结构化程序设计方法结构化程序设计方法4.5 算法设计实例研究算法设计实例研究提纲提纲 58 源自于对源自于对goto语句的争论语句的争论 goto语句详见语句详见436页页4.4 结构化程序设计方法结构化程序设计方法 59#include main() int count=1; start: /标号标号,是跟有冒号的标识符是跟有冒号的标识符 if (count10) goto end; printf(%d ,count); count=count+1; goto start; end: printf(n); system(p

33、ause); return 0; 1 2 3 4 5 6 7 8 9 10请按任意键继续. . .运行效果：运行效果： 604.4 结构化程序设计方法结构化程序设计方法 用三种基本结构组成的程序必然是结构化的程序，这用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、阅读、修改和维护种程序便于编写、阅读、修改和维护 。 结构化程序设计强调程序设计风格和程序结构的规范结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构化，提倡清晰的结构 。 结构化程序设计方法的基本思想：采用分而治之的方结构化程序设计方法的基本思想：采用分而治之的方法，将一个复杂问题分解为相对简单的一些子问

34、题，法，将一个复杂问题分解为相对简单的一些子问题，然后针对这些子问题进行求解。如果某个子问题仍然然后针对这些子问题进行求解。如果某个子问题仍然是比较复杂的，再进一步分解为子是比较复杂的，再进一步分解为子-子问题，直到所有子问题，直到所有问题都能够求解。求解问题的过程是分阶段进行的，问题都能够求解。求解问题的过程是分阶段进行的，每个阶段处理的问题都控制在人们容易理解和处理的每个阶段处理的问题都控制在人们容易理解和处理的范围内范围内67个之内）。个之内）。 614.4 结构化程序设计方法结构化程序设计方法结构化程序设计方法结构化程序设计方法自顶向下；自顶向下；逐步细化；逐步细化；模块化设计函数）；

35、模块化设计函数）；结构化编码三种基本结构）。结构化编码三种基本结构）。 62例例4.13 利用辗转相除法求两个正整数的最大公约数。利用辗转相除法求两个正整数的最大公约数。辗转相除法求最大公约数的数学定义如下：辗转相除法求最大公约数的数学定义如下：GCDx,y）= y | xy and x MOD y = 0 GCDy, x MOD y）| xy and x MOD y 0; 阐明：先判断阐明：先判断x能否被能否被y整除，若可以，则最大公约数就整除，若可以，则最大公约数就是除数是除数y；否则，则将；否则，则将y 作为被除数，作为被除数，x MOD y 作为作为除数继续上面的操作，直到除数继续上面

36、的操作，直到x能否被能否被y整除为止。整除为止。 GCD(6,4)GCD(4,2)= 2=GCD(124,6)最大公约数为最大公约数为2例如：求例如：求GCD(124,6)的过程为：的过程为： 63算法算法1xyr231交换变量交换变量x和和y的值：的值：自顶向下，逐步细化自顶向下，逐步细化 64最终算法1 算法设计任务结算法设计任务结束的标准是各步束的标准是各步骤已精细到能用骤已精细到能用语句描述，即满语句描述，即满足算法的足算法的5大特大特征标志算法设计征标志算法设计任务结束任务结束 。 65算法算法2思索：能否不借助于变量思索：能否不借助于变量r，而是而是xy; y x%y？ 或者或者y

37、 x%y；x y 66 练习练习3：设计算法，求一个正整数的长度。：设计算法，求一个正整数的长度。 算法算法1：例如：例如num=12345，求，求num的长度的长度 第第1步：去掉最低位，步：去掉最低位，num=1234，长度，长度len=1 第第2步：去掉最低位，步：去掉最低位，num=123，长度，长度len=2 第第3步：去掉最低位，步：去掉最低位，num=12，长度，长度len=3 第第4步：去掉最低位，步：去掉最低位，num=1，长度，长度len=4 第第5步：去掉最低位，步：去掉最低位，num=0，长度，长度len=5算法中每一步的核心操作是从算法中每一步的核心操作是从num中去

38、掉最低中去掉最低位，长度位，长度len加加1 67 68 假设假设num长度不超过长度不超过8，例如，例如num=12345，求，求num的长度的长度 算法算法2：试探能被：试探能被10的几次方除后商不为的几次方除后商不为0 第第1步：步： num /107=0 第第2步：步： num /106=0 第第3步：步： num /105=0 第第4步：步： num /104!=0,说明长度为说明长度为4+15算法中每一步的核心操作是试探：算法中每一步的核心操作是试探：num除除10i后商是否后商是否0 69 增加对输增加对输入为入为0的的判断判断进一步细化进一步细化 70 练习练习4：输入一个不超

39、过：输入一个不超过8位的正整数，要求把位的正整数，要求把这个整数分解为单个数字，然后打印出每一个这个整数分解为单个数字，然后打印出每一个数字每一个数字之间用两个空格分开）。例数字每一个数字之间用两个空格分开）。例如用户输入了如用户输入了4200，程序打印结果为：，程序打印结果为：4 2 0 0。设计算法。设计算法。 第第1步：得到步：得到num最高位最高位4并输出，并输出，num=200 第第2步：得到步：得到num最高位最高位2并输出，并输出，num=0 第第3步：得到步：得到num最高位最高位0并输出，并输出，num=9 第第4步：得到步：得到num最高位最高位0并输出，并输出，num=0

40、 71 72 练习练习5：设计算法，判断一个正整数是否是回：设计算法，判断一个正整数是否是回文数。回文数是指正读和反读都一样的数。文数。回文数是指正读和反读都一样的数。 算法算法1： 比较第比较第1位和倒数第位和倒数第1位位 比较第比较第2位和倒数第位和倒数第2位位 算法算法2：反着读，假设读得的数为：反着读，假设读得的数为reverseNum，判断，判断num和和reverseNum是否相等是否相等 73以求以求a0a1a2a3的逆数为例，假设的逆数为例，假设reverse实现逆着实现逆着读读reverse(a3)=a3reverse(a2a3)=a3a2=a3*10 + a2= rever

41、se(a3)*10+a2reverse(a1a2a3)=a3a2a1=a3a2*10 + a1 =reverse(a2a3)*10+ a1reverse(a0a1a2a3)=a3a2a1a0 =a3a2a1*10+a0 =reverse(a1a2a3)*10+a0 74判断回文数判断回文数-算法算法1 75判断回文数判断回文数-算法算法2 76#includemain() int num;/存放输入的整数 int num1; /*循环中处理的数,每循环一次,右边少一位,假设num为1234,则num1初始值为1234,然后是123,然后是12.;*/ int reverse;/*是用分解出来的

42、数字组成的新数*/ int m;/*m:存放每一个分解出来的数字;*/ printf(请输入一个小于8位的正整数:); /读取要判断的整数 scanf(%d,&num); /*从右到左依次取出各个数字组装成一个新的整数保持到reverse中*/ num1=num; reverse=0; while(num1!=0) m=num1%10; /*取出num1的最低位*/ reverse=reverse*10+m; /*将最低位组装到reverse中*/ num1=num1/10; /*去掉num1的最低位*/ if (num=reverse) printf(%d 是回文数n,num); e

43、lse printf(%d 不是回文数n,num); system(PAUSE); return 0; 77总结：循环结构解题总结：循环结构解题 很多题目都需要循环结构进行求解。很多题目都需要循环结构进行求解。 当一时难以整理出每次循环迭代所做的事当一时难以整理出每次循环迭代所做的事情时，可以先看一下如果这件事情交给人做的情时，可以先看一下如果这件事情交给人做的话，一步一步是怎么做的。话，一步一步是怎么做的。 在上一步基础上抽象出循环结构的四个方面。在上一步基础上抽象出循环结构的四个方面。 78总结：循环结构解题总结：循环结构解题 2和和3一般没有绝对的先后顺序。一般没有绝对的先后顺序。 在分

44、析清楚在分析清楚2和和3后，才分析后，才分析4为什么？）。为什么？）。 一般将一般将1放在最后分析放在最后分析在在4中，要对出现在中，要对出现在2和和3中的某些变量进行修改，为中的某些变量进行修改，为下次循环做好准备，并使得循环能最终结束。下次循环做好准备，并使得循环能最终结束。思考上述四项工作有无先后顺序？应该是什么顺序？思考上述四项工作有无先后顺序？应该是什么顺序？ 79总结：对一批数进行处理的模式总结：对一批数进行处理的模式循环次数未知循环次数未知循环次数已知循环次数已知 804.1 算法的概念算法的概念4.2 算法的三种基本结构算法的三种基本结构4.3 算法的描述方法算法的描述方法4.

45、4 结构化程序设计方法结构化程序设计方法4.5 算法设计实例研究算法设计实例研究提纲提纲 81例例4.14 设计交通车辆观测统计算法。设计交通车辆观测统计算法。 问题描述：在一个路口设置一个探测器，通过通问题描述：在一个路口设置一个探测器，通过通信线路连接到后台的计算机。路口每通过一辆信线路连接到后台的计算机。路口每通过一辆汽车，探测器向计算机发出一个车辆信号汽车，探测器向计算机发出一个车辆信号1，探测器每隔探测器每隔1秒钟向计算机发出一个时钟信号秒钟向计算机发出一个时钟信号0，观测结束向计算机发出结束信号，观测结束向计算机发出结束信号。 要求在计算机上设计一个程序，能够接收探测器要求在计算机

46、上设计一个程序，能够接收探测器发出的信号，统计出观测的时长、在观测时长发出的信号，统计出观测的时长、在观测时长内通过的车辆总数、以及两辆车之间最大的时内通过的车辆总数、以及两辆车之间最大的时间间隔。间间隔。 问题分析：探测器向计算机发出的信号可以认为是一个问题分析：探测器向计算机发出的信号可以认为是一个任意长的字符序列以任意长的字符序列以#终了），比如：终了），比如：“011011000111101#”，这样设计程序实际上演变为读取，这样设计程序实际上演变为读取该字符序列，然后进行相关的操作。该字符序列，然后进行相关的操作。 1 4.5 算法设计实例研究算法设计实例研究观测时长：字符序列中观测

47、时长：字符序列中0的个数的个数(6秒秒)；车辆总数：字符序列中车辆总数：字符序列中1的个数的个数(9辆辆)；两车间最大时间间隔：两个两车间最大时间间隔：两个1之间的最大连续之间的最大连续0的个数的个数(3秒秒)；探测器探测器 82 计算观测时长（计算观测时长（0的个数和车辆总数（的个数和车辆总数（1的的个数是容易实现的，但是如何计算最大时间个数是容易实现的，但是如何计算最大时间间隔需要进一步考虑。在对一个比较复杂的问间隔需要进一步考虑。在对一个比较复杂的问题进行分析时，我们应该采用分而治之的方法题进行分析时，我们应该采用分而治之的方法，将复杂的问题分解为相对比较简单的问题，将复杂的问题分解为相

48、对比较简单的问题，再针对该较简单问题进行求解。再针对该较简单问题进行求解。 我们首先设计算法主体框架。我们首先设计算法主体框架。“0000110100011010#0000110100011010#”！留意：！留意：2019年年9月出版的教材假设接收到的信月出版的教材假设接收到的信号总是以号总是以1开场，因此算法会有所简化开场，因此算法会有所简化 83“0000110100011010#0000110100011010#”signal!=#待细化待细化 84 85Level 1层算法设计层算法设计第0层算法第1层算法 86“0000110100011010#0000110100011010#”

49、 分析：处理时钟信号分析：处理时钟信号0 观测时长观测时长seconds加加1； 两种情况。如果此两种情况。如果此前已接收到车辆信前已接收到车辆信号号1 (如何判断？如何判断？)，则间隔时长则间隔时长interval加加1；否则不做任何；否则不做任何处理。处理。 87“0000110100011010#0000110100011010#” 分析：处理车辆信号分析：处理车辆信号1 第一种：第一种： “0000110100011010#”（这是第一个（这是第一个1） 车辆总数车辆总数vehicles加加1 第二种：第二种： “0000110100011010#”（不是第一个（不是第一个1，且，且前

50、一个信号也是前一个信号也是1 ） 车辆总数车辆总数vehicles加加1 第三种：第三种： “0000110100011010#”（不是第一个（不是第一个1，且，且前一个信号是前一个信号是0 ） 车辆总数车辆总数vehicles加加1 处理是否要更新最长时间间隔（处理是否要更新最长时间间隔（ interval：两车之间：两车之间的时间间隔，的时间间隔，longest：两车之间的最长时间间隔）：两车之间的最长时间间隔） 88“0000110100011010#0000110100011010#” 分析：处理车辆信号分析：处理车辆信号1vehicles vehicles +1；情况情况1：第一个：

51、第一个1 判断式：判断式： vehicles =1情况情况2：不是第一个：不是第一个1，且前，且前一个信号也是一个信号也是1 判断式：判断式： vehicles1 & interval=0情况情况3：不是第一个：不是第一个1，且前，且前一个信号是一个信号是0 : 判断式：判断式： vehicles1 & interval0 处置：处置：1若若intervallongest 那么那么 longest interval。 2） interval0。情况情况1情况情况3情况情况2 89“0000110100011010#”验证算法验证算法【程序演示】 90#includemain()

52、 int vehicles; /记录车辆信号总数记录车辆信号总数 int seconds; /记录时钟信号总数记录时钟信号总数 int longest; /记录最长时间间隔记录最长时间间隔 int interval; /记录时间间隔记录时间间隔 char signal; /存放读取的信号存放读取的信号 /* 初始化设置初始化设置 */ vehicles=0; seconds=0; longest=0; interval=0; printf(please input signal: n); scanf(%c,&signal);/* 读入第一个信号读入第一个信号 */ 91 /* 循环结构

53、处理输入信号的字符序列循环结构处理输入信号的字符序列,边读取边处理边读取边处理 */ while (signal!=#) if (signal=1) /* 处理车辆信号处理车辆信号*/ vehicles=vehicles+1; if (vehicles1 & interval0) if (intervallongest) longest=interval; interval=0; else/* 处理时钟信号处理时钟信号*/ seconds=seconds+1; if (vehicles0) interval=interval+1; scanf(%c,&signal); 92/*

54、 输出结果输出结果 */ printf(%d vehicles passed in %d secondsn,vehicles,seconds); printf(the longest gap was %d secondsn,longest); system(PAUSE); return 0; 93 练习：将一个由数字字符组成的字符串转换为练习：将一个由数字字符组成的字符串转换为整数或者小数并输出。如：整数或者小数并输出。如：输入输入:134.567# 输出输出:134.567 94 #includemain() char ch; int num; /存放小数点前面的字符转换后得到的整数存放小数

55、点前面的字符转换后得到的整数 float fnum; /存放小数点后面的字符转换后得到的浮点数存放小数点后面的字符转换后得到的浮点数 int n; /存放字符对应的数字存放字符对应的数字 int p; / 存放小数点后面的字符转换后得到的数字对应的基数存放小数点后面的字符转换后得到的数字对应的基数1/p。小数点后第一位数的。小数点后第一位数的基数是基数是1/10 int flag;/用于表示输入的字符中是否有小数点。若有，则用于表示输入的字符中是否有小数点。若有，则flag值为值为1；否则为；否则为0 num = 0; fnum = 0; p = 10; flag = 0; printf(pl

56、ease input the string:); 算法算法1：读情况对字符进行处理：读情况对字符进行处理 95 scanf(%c,&ch); while( ch != #) if (ch=.) flag = 1;/flag为为1，表示输入了小数点，表示输入了小数点 else /处理小数点之前的字符处理小数点之前的字符 n = ch - 0; if (flag = 0)/若输入的是小数点之前的数若输入的是小数点之前的数 num = num * 10 + n; else/处理小数点之后的字符处理小数点之后的字符 fnum = fnum + (float)n / p; /必须进行强制类型转换

57、，否则必须进行强制类型转换，否则n/p结果为结果为0 p = p * 10; scanf(%c,&ch); 96 if (flag = 0) printf(the result is:%dn,num); else printf(the result is:%fn,num+fnum); system(pause); return 0; 97 #includemain() char ch; int num; float fnum; int n; int p; printf(please input the string:); /处理整数部分 num = 0; scanf(%c,&c

58、h); while(ch != . & ch != #) n = ch - 0; num = num * 10 + n; scanf(%c,&ch); 算法算法2：先循环处理小数点前面：先循环处理小数点前面的字符，再循环处理小数点的字符，再循环处理小数点后面的字符后面的字符 98 if (ch=.) /处理小数部分处理小数部分 p = 10; scanf(%c,&ch); while(ch != #) n = ch - 0; fnum = fnum + (float)n / p; /必须进行强制类型转换，否则必须进行强制类型转换，否则n/p结果为结果为0 scanf(%

59、c,&ch); p = p * 10; if (fnum 0) printf(the result is:%dn,num); else printf(the result is:%fn,num+fnum); system(pause); return 0; 99迭代算法迭代算法迭代算法是用计算机解决问题的一种基本方法。它利用计算机迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令运算速度快、适合做重复性操作的特点，让计算机对一组指令或一定步骤进行重复执行，在每次执行这组指令或这些或一定步骤进行重复执行，在每次执行这组指令或这些步

60、骤时，都从变量的原值推出它的一个新值。步骤时，都从变量的原值推出它的一个新值。利用迭代算法解决问题，需要做好以下三个方面的工作利用迭代算法解决问题，需要做好以下三个方面的工作 确定迭代变量确定迭代变量ai。在可以用迭代算法解决的问题中，至少存。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。就是迭代变量。 建立迭代关系式，即建立迭代关系式，即aif(ai-1)对迭代过程进行控制对迭代过程进行控制 。迭代过程的控制通常可分为两种情况。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种