算法设计方法

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

2、助人们自动地完成所要处理的复杂任务；动地完成所要处理的复杂任务； 程序设计两个核心问题：程序设计两个核心问题：“做什么做什么”与与“怎怎么做么做” ；其中；其中解决解决“做什么做什么”，解决解决“怎么做怎么做” 。 54.1 算法的概念算法的概念二二. 程序设计两步走程序设计两步走对复杂问题，直接写出能解决该问题的计算机对复杂问题，直接写出能解决该问题的计算机程序是困难的，为此，人们在进行程序设计时程序是困难的，为此，人们在进行程序设计时分两步走：分两步走：1）算法设计：不使用程序设计语言，而使用）算法设计：不使用程序设计语言，而使用一种较简单明了的表达方式（例如自然语言）一种较简单明了的表达

3、方式（例如自然语言）设计出设计出求解问题求解问题的步骤序列的步骤序列-算法算法。2）程序编写：根据设计并描述好的算法，使）程序编写：根据设计并描述好的算法，使用某种程序设计语言编写对应于该算法的程用某种程序设计语言编写对应于该算法的程序序 。 4.1 算法的概念算法的概念n 算法代表了对问题的解，n 程序则是算法在计算机上的特定的实现。n 一个算法若用程序设计语言来描述，则它就是一个程序.6 7三三.算法算法(Algorithm)的概念的概念算法：算法：是解决问题的步骤序列（操作序列）。是解决问题的步骤序列（操作序列）。 4.1 算法的概念算法的概念71.起床起床2.穿衣、叠被穿衣、叠被3.去

4、水房洗漱去水房洗漱4.回宿舍放洗漱用品回宿舍放洗漱用品5.骑车去食堂骑车去食堂6.排队买饭排队买饭7.吃饭吃饭8.交回餐具交回餐具9.骑车去教室骑车去教室描述的是描述的是活动和过活动和过程程1.休息状态休息状态2.离开宿舍状态离开宿舍状态3.离开食堂状态离开食堂状态4.到达教室状态到达教室状态描述的是操作执行后描述的是操作执行后的状态，通过状态的的状态，通过状态的转移来描述所执行的转移来描述所执行的操作。操作。事件：闹钟响。事件：闹钟响。可能的活动：可能的活动：起床、穿衣叠起床、穿衣叠被、洗漱等被、洗漱等事件：肚子饿了。事件：肚子饿了。可能的活动：骑可能的活动：骑车到食堂、排队车到食堂、排队买

5、饭、吃饭、交买饭、吃饭、交回餐具回餐具 事件：上课。事件：上课。可能的活动：骑车去教室可能的活动：骑车去教室 4.1 算法的概念算法的概念 算法，是求解问题类的、机械的、统一的方法，常用于计算、数据处理（Data processing）和自动推理。可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤。 算法中的指令描述的是一个计算，当其运行时能从一个初始状态和(可能为空的)初始输入开始， 经过一系列有限 而清晰定义的状态最终产生输出 并停止于一个终态。8 94.1 算法的概念算法的概念四四. “计算机算法计算机算法”及其特性及其特性u什么是计算机可执行的操作；什么是计算机可执行的操作；u

6、要在要在进行算法设计；进行算法设计；u算法必须具备的五个特性：算法必须具备的五个特性：1.1. 可执行性：可执行性：算法中的每一个步骤都是计算机算法中的每一个步骤都是计算机可执行的（在计算机能力集范围内）可执行的（在计算机能力集范围内） ；2.2. 确定性：确定性：算法中的每一个步骤，必须是明确算法中的每一个步骤，必须是明确定义的，不得有任何歧义性定义的，不得有任何歧义性 ；3.3. 有穷性：有穷性：算法必须在执行有穷步之后结束；算法必须在执行有穷步之后结束； 4.4. 有输入信息的说明：对加工对象提要求；有输入信息的说明：对加工对象提要求；5.5. 有输出信息的步骤有输出信息的步骤 ：至少要

7、输出问题答案。：至少要输出问题答案。 10例例1 求求12910 ，即10！ 算法思路：算法思路： 假设计算机能力集只提供两数相乘的运算。假设计算机能力集只提供两数相乘的运算。计算计算 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 11例例1 求求12910 ，即10！第一种算法：第一种算法：S1(求求2!)：先求：先求21，得到结果，得到结果

8、2并赋值给变量并赋值给变量p；即：；即：21p；S2 (求求3!) ：将步骤：将步骤S1得到的乘积得到的乘积p（p=2）再乘以）再乘以3，得结果，得结果6并并 赋值给变量赋值给变量p；即：；即： 3 pp；S3(求求4!)：将：将p（p=6）再乘以）再乘以4，得，得24并赋值给变量并赋值给变量p；即：；即： 4pp；S4(求求5！)：将：将p（p=24）再乘以）再乘以5，得，得120并赋值给变量并赋值给变量p；即：；即： 5pp；S9(求求10!)：将：将p（p=362880)乘以乘以10，得，得3628800，10pp； 12#includemain() int p; p=2*1; /求求2

9、!赋值给赋值给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*p; /求求10!赋值给赋值给p printf(%d,p); system(pause); return 0; 评价：求评价：求10!需要写需要写9个赋值操作，算法个赋值操作，算法过于繁琐！试想：过于繁琐！试想：求求1000！的算法！的算法 13 对算法进行抽象对算法进行抽象:核心操作就是两数相乘核心操作就是两数相乘ipp ，反复相乘，反复相乘10-1=9次，次，i初始值为初始值为2，p初始值为初始值为1，每相乘一次，每相乘一次i的值加的值加1

10、。 根据上述分析，本题可利用循环结构求解：根据上述分析，本题可利用循环结构求解：第第1次循环用于求次循环用于求2！，第！，第2次循环在第次循环在第1次循环基次循环基础上求础上求3！，！，,第第9次循环在第次循环在第8次循环基础上求次循环基础上求10！例例1 求求12910 ，即10！ 14定义两个变量定义两个变量p和和i，p代表阶乘结果代表阶乘结果,i代表本次循环要代表本次循环要求的是求的是i!； 循环条件：循环条件：ip；S4：使使i的值加的值加1，即，即i+1=i；S5：如果如果i=10，返回重新执行步骤，返回重新执行步骤S3以及其后的以及其后的步骤步骤S4和和S5；否则，算法结束。否则，

11、算法结束。 最后得到最后得到p的值就是的值就是10！的值。！的值。 求求12910算法思路：算法思路：“迭代迭代”和和“循环循环” ：在程序设计中，重复执行同：在程序设计中，重复执行同样操作的过程称为样操作的过程称为“迭代迭代”。程序中被重复执行的。程序中被重复执行的程序段称为程序段称为“循环循环”。 16例例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+

12、1; printf(%d!=%d,n,p); system(pause); return 0; 17 练习练习1：输入十个整数，求出最大值、最小值。：输入十个整数，求出最大值、最小值。 算法思路：采用迭代计算的方法算法思路：采用迭代计算的方法 以求最大值为例，即：以求最大值为例，即： 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个整数的最大值。个整数的最大值。

13、第第n个数将和个数将和max比比较，决定前较，决定前n个数的个数的最大值。最大值。整个问题就被转变为求整个问题就被转变为求9次两个次两个数的最大值。数的最大值。每一次都是读入一个数，和之每一次都是读入一个数，和之前求得的最大数再去比较。前求得的最大数再去比较。 18循环条件循环条件：imax,则则max=n； 否则，如果否则，如果nmin,则则min=n； i=i+1;循环初始化：循环初始化：读入一整数读入一整数n;minn; max=n;i2；请写出本题源程序请写出本题源程序变量定义：变量定义：n, i, max, min 19源程序：源程序：输入十个整数，求出最大值、最小值输入十个整数，求

14、出最大值、最小值#include#define COUNT 10 main() int i, n, max, min;/i:循环计数；循环计数；n:读取的数；读取的数； /max:当前最大值当前最大值; min:当前最小值当前最小值 scanf(%d, &n); max=n; /将第一个数作为最大值和最小值将第一个数作为最大值和最小值 min=n; i=2; /代表接下去要读取的是第代表接下去要读取的是第2个数个数 20源程序：源程序：输入十个整数，求出最大值、最小值输入十个整数，求出最大值、最小值(续续) while (i max) /求最大数求最大数 max = n; else if (n

15、 i；问题分析：就是反复输入处理每一个学生的信息，处理问题分析：就是反复输入处理每一个学生的信息，处理120次。次。 22输入输入120个学生的学号和成绩，要求将他们之中个学生的学号和成绩，要求将他们之中成绩在成绩在60分以上者的学号和成绩打印出来。分以上者的学号和成绩打印出来。S1S1：1=i1=i；S2S2：读入第读入第i i个学生的学号和成绩分别到变量个学生的学号和成绩分别到变量numnum和和scorescore中；中；S3S3：如果如果score 60score 60，则打印则打印num和和score ；S4S4：i+1=ii+1=i；S5：如果如果i120i120，则返回则返回S2

16、S2，继续执行；否则，算法结束。继续执行；否则，算法结束。循环处理模式：循环处理模式：处理本次循环要做的任务；处理本次循环要做的任务；为下一次循环做准备；为下一次循环做准备； 234.1 算法的概念算法的概念练习练习2：请写出本题对应的程序：请写出本题对应的程序 244.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,

17、&total); count=1;while(count60) printf(no:%dtscore:%fn,no,score); count=count+1; system(pause); return 0； 25例例3 一个大于或等于一个大于或等于3的正整数，判断它是否为一的正整数，判断它是否为一个素数（质数）个素数（质数） 。u所谓质数，比所谓质数，比1大的自然数中，除了大的自然数中，除了1和该数本和该数本身外，不能被其他任何自然数整除的数。例如，身外，不能被其他任何自然数整除的数。例如，13是素数（质数）。因为它不能被是素数（质数）。因为它不能被2，3，4，12整除。整除。u由于素数在

18、当代的密码学中扮演了中心的作用，由于素数在当代的密码学中扮演了中心的作用，所以该问题具有重要意义。所以该问题具有重要意义。u判断一个数判断一个数n（n3）是否为质数：将）是否为质数：将n作为被作为被除数，将除数，将2到（到（n-1）各个整数依次作为除数，如）各个整数依次作为除数，如果都不能被整除，则果都不能被整除，则n为素数。为素数。4.1 算法的概念算法的概念 26判断质数看看n能否被能否被2到（到（n-1）之间的各个整数整除：）之间的各个整数整除： 变量抽象：变量抽象：n：存放被判断的整数；：存放被判断的整数；i：存放除：存放除 数，取值为数，取值为2,n-1；r：存放存放n/i得到的余数

19、得到的余数循环体：循环体：n被被i除，得余数除，得余数r；即即n mod i=r；如果如果r=0，表示表示n能被能被i整除，则打印整除，则打印n“不是不是素数素数”，算法结束；否则，算法结束；否则i+1=i；循环条件：循环条件： ir；如果如果r=0，表示表示n能被能被i整除，则打印整除，则打印n“不是不是素数素数”，令，令isPrim=0；否则；否则i+1=i；循环条件：循环条件： irn mod i=rS4S4：如果如果r=0r=0，表示表示n n能被能被i i整除，则打印整除，则打印n n“不是素数不是素数”，算法结束；否则执行，算法结束；否则执行S5S5；S5S5：i+1=ii+1=i

20、；S6S6：如果如果in-1in-1，返回返回S3S3；否则，打印否则，打印n n“是是素数素数”，算法结束。，算法结束。 n：被判断的整数；：被判断的整数；i：被除数：被除数；r：存放存放n/i得到的余数得到的余数事实上，事实上，i只需只需2到到 之间的整数整除即可。之间的整数整除即可。n 294.1 算法的概念算法的概念4.2 算法的三种基本结构算法的三种基本结构4.3 算法的描述方法算法的描述方法4.4 结构化程序设计方法结构化程序设计方法4.5 算法设计实例研究算法设计实例研究提纲提纲 304.2 算法的三种基本结构算法的三种基本结构 三种控制结构三种控制结构(Bohra和和Jacop

21、ini )顺序结构、顺序结构、 选择结构、循环结构选择结构、循环结构 顺序结构顺序结构 按书写顺序执行的语句构按书写顺序执行的语句构成的程序段。成的程序段。 31选择结构选择结构u 根据给定的表达式是否成立而选择执行操作根据给定的表达式是否成立而选择执行操作A A或操或操作作B B。如果表达式成立，则执行。如果表达式成立，则执行操作操作A A；如果表达式不；如果表达式不成立，则执行成立，则执行操作操作B B。u操作操作B B可以为空。可以为空。4.2 算法的三种基本结构算法的三种基本结构 32 当型循环结构当型循环结构4.2 算法的三种基本结构算法的三种基本结构C语言无直到型循环结构。语言无直

22、到型循环结构。比较：直到型循环结构和比较：直到型循环结构和C语言中的语言中的do-while结构？结构？ 直到型循环结构直到型循环结构 33三种控制结构的共同点三种控制结构的共同点 只有一个入口（只有一个入口（a处）处） 只有一个出口（只有一个出口（b处）处） 结构内的每一个部分都有机会被执行到结构内的每一个部分都有机会被执行到 结构内不存在结构内不存在“死循环死循环”（无终止的循环）（无终止的循环）4.2 算法的三种基本结构算法的三种基本结构由这三种基本结构顺序组成的算法结构，可由这三种基本结构顺序组成的算法结构，可以解决任何复杂问题！以解决任何复杂问题！ 344.1 算法的概念算法的概念4

23、.2 算法的三种基本结构算法的三种基本结构4.3 算法的描述方法算法的描述方法4.4 结构化程序设计方法结构化程序设计方法4.5 算法设计实例研究算法设计实例研究提纲提纲 354.3 算法的描述方法算法的描述方法 用自然语言描述用自然语言描述 用流程图描述用流程图描述 用用N-SN-S流程图描述流程图描述 用伪码描述用伪码描述 用计算机语言描述用计算机语言描述 364.3 算法的描述方法算法的描述方法自然语言自然语言 文字冗长；文字冗长； 不严格，易产生歧义（二义性）；不严格，易产生歧义（二义性）； 不方便描述分支和循环结构；不方便描述分支和循环结构； 374.3 算法的描述方法算法的描述方法

24、流程图流程图 流程图的基本元素（流程图的基本元素（ANSIANSI规定）规定） 起止框输入/出框判断框处理框流程线 连接点 注释框 384.3 算法的描述方法算法的描述方法流程图流程图流程图描述的选择结构流程图描述的选择结构 39 当型循环结构当型循环结构 直到型循环结构直到型循环结构流程图描述的循环结构流程图描述的循环结构4.3 算法的描述方法流程图算法的描述方法流程图 40连接点（小圆圈）：用于将画在不同地方的流程线连连接点（小圆圈）：用于将画在不同地方的流程线连接起来接起来 41求求10！流程图！流程图使用当型循使用当型循环结构描述环结构描述 42打印学生序号打印学生序号及成绩流程图及成

25、绩流程图 43判断质判断质数的流数的流程图程图使用直到型循使用直到型循环结构描述环结构描述判断判断r是否是否为为0条件成立则条件成立则跳出循环跳出循环 44练习：将以上流程图改成用当型循环结构表示。练习：将以上流程图改成用当型循环结构表示。该流程图中循该流程图中循环结构有两个环结构有两个出口！违反单出口！违反单入单出原则！入单出原则！如何改进？如何改进？ 45改进后的流程图：改进后的流程图：单入单出单入单出 设置标志设置标志位位isPrim 46 传统流程图的弊端传统流程图的弊端 对流程线的使用没有严格限制，阅读困难；对流程线的使用没有严格限制，阅读困难； 不能保证算法结构的单入单出特性；不能

26、保证算法结构的单入单出特性； 占用篇幅较多占用篇幅较多 ； 4.3 算法的描述方法算法的描述方法N-SN-S流程图流程图必须限制箭头的滥用，让流程只能顺序执必须限制箭头的滥用，让流程只能顺序执行下去！行下去！保证结构化原则的流程描述工具保证结构化原则的流程描述工具N-S图图 47 基本结构基本结构4.3 算法的描述方法算法的描述方法N-SN-S流程图流程图p、p1表示的是表示的是判断条件；判断条件；A、B框是操作；框是操作；注意：注意：A、B框可框可以是一个简单以是一个简单的操作（如读的操作（如读入数据或打印入数据或打印输出等），也输出等），也可以是三种基可以是三种基本结构之一本结构之一顺序结

27、构顺序结构选择结构选择结构当型循环结构当型循环结构直到型循环结构直到型循环结构 48例例1 求求10!的的N-S流程图流程图4.3 算法的描述方法算法的描述方法N-SN-S流程图流程图 49例例2 打印学生成绩打印学生成绩N-S流程图流程图4.3 算法的描述方法算法的描述方法N-SN-S流程图流程图 50例例3 判断质数的判断质数的N-S流程图流程图4.3 算法的描述方法算法的描述方法N-SN-S流程图流程图 514.3 算法的描述方法算法的描述方法伪码描述伪码描述 流程图和流程图和N-S图画起来比较费事，适合于表示图画起来比较费事，适合于表示算法，而在算法设计中使用不是很理想。算法，而在算法

28、设计中使用不是很理想。 伪码伪码 用介于自然语言和程序设计语言之间的文介于自然语言和程序设计语言之间的文字和符号来描述算法。字和符号来描述算法。【返回】 IF x is positive THEN print x ELSE print yWHILE i60 THEN print score i加加1 524.3 算法的描述方法算法的描述方法例例4：利用泰勒级数：利用泰勒级数：- -LLLLLLLL+ +- - -+ + +- -+ +- -= =+ +)!12() 1(! 7! 5! 3sin121753nxxxxxxnn计算正弦的值，直到最后一项绝对值小于计算正弦的值，直到最后一项绝对值小于

29、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)+an 534.3 算法的描述方法算法的描述方法 算法的核心操作是求两数之和，其中第一个操算法的核心操作是求两数之和，其中第一个操作数是前一次求得的和。如何求第二个操作数？作数是前一次求得的和。如何求第二个操作数？ 算法算法1：n决定了第决定了第n项因子的值，即第二个操项因子的值，即第二个操作

30、数；因此每一次可根据当前作数；因此每一次可根据当前n的值计算出第的值计算出第二个操作数。二个操作数。 请用请用NS图描述出算法图描述出算法1。 54求求sin(x)算法算法1i代表下一个代表下一个p是第几项，是第几项，因此初值是因此初值是1变量抽象：变量抽象： x：存储未知数：存储未知数x的的值；值； sum：存储和：存储和 ； p：存储当前待加的：存储当前待加的因子；因子；i：当前待加：当前待加的是第几个因子的是第几个因子 55问题：任何数据类型只能表示一定范围内的数，问题：任何数据类型只能表示一定范围内的数，当试图往变量中存储在范围之外的数，数据无当试图往变量中存储在范围之外的数，数据无法

31、正确存储。求法正确存储。求x的的n次方和次方和(2n-1)!时可能会导时可能会导致结果太大而溢出。致结果太大而溢出。解决方法：解决方法：改进算法改进算法算法算法2 564.3 算法的描述方法算法的描述方法=pi 1- - - -)!32() 1(32ixii=Pi- - - -+ +)!12() 1(121ixiiPiPipi 1- -LLLLLLLL+ +- - -+ + +- -+ +- -= =+ +)!12() 1(! 7! 5! 3sin121753nxxxxxxnn算法算法2：设第：设第i项因子表示为项因子表示为 ，考察，考察 和和 的关系。的关系。 = = * *(-1)(-1)

32、* * x2 /(2i-1)(2i-1)* *(2i-2)(2i-2)Pipi 1- 57请用请用NS图描述算法图描述算法2。4.3 算法的描述方法算法的描述方法i代表下一个代表下一个p是第几项，是第几项，因此初值是因此初值是1 58#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-6) sum=sum+p; i=i+1; p=-

33、p*x*x/(2*i-2)*(2*i-1); printf(sin(%f) = %lfn,x,sum); system(pause); return 0; 594.1 算法的概念算法的概念4.2 算法的三种基本结构算法的三种基本结构4.3 算法的描述方法算法的描述方法4.4 结构化程序设计方法结构化程序设计方法4.5 算法设计实例研究算法设计实例研究提纲提纲 60 源自于对源自于对goto语句的争论语句的争论 goto语句详见语句详见程序设计教程程序设计教程436页页4.4 结构化程序设计方法结构化程序设计方法 61#include #include main() int count=1; s

34、tart: /标号标号,是跟有冒号的标识符是跟有冒号的标识符 if (count10) goto end; printf(%d ,count); count=count+1; goto start; end: printf(n); system(pause); return 0; 1 2 3 4 5 6 7 8 9 10请按任意键继续. . .运行效果：运行效果： 624.4 结构化程序设计方法结构化程序设计方法 用三种基本结构组成的程序必然是用三种基本结构组成的程序必然是结构化结构化的程序，这的程序，这种程序便于编写、阅读、修改和维护种程序便于编写、阅读、修改和维护 。 结构化程序设计强调结

35、构化程序设计强调和和，提倡清晰的结构，提倡清晰的结构 。 结构化程序设计方法的基本思想：采用分而治之的方结构化程序设计方法的基本思想：采用分而治之的方法，将一个复杂问题分解为相对简单的一些子问题，法，将一个复杂问题分解为相对简单的一些子问题，然后针对这些子问题进行求解。如果某个子问题仍然然后针对这些子问题进行求解。如果某个子问题仍然是比较复杂的，再进一步分解为子是比较复杂的，再进一步分解为子-子问题，直到所有子问题，直到所有问题都能够求解。求解问题的过程是分阶段进行的，问题都能够求解。求解问题的过程是分阶段进行的，每个阶段处理的问题都控制在人们容易理解和处理的每个阶段处理的问题都控制在人们容易

36、理解和处理的范围内（范围内（67个之内）。个之内）。 634.4 结构化程序设计方法结构化程序设计方法结构化程序设计方法结构化程序设计方法自顶向下；自顶向下；逐步细化；逐步细化；模块化设计（函数）；模块化设计（函数）；结构化编码（三种基本结构）。结构化编码（三种基本结构）。 64例例4.13 利用辗转相除法求两个正整数的最大公约数。利用辗转相除法求两个正整数的最大公约数。辗转相除法求最大公约数的数学定义如下：辗转相除法求最大公约数的数学定义如下：GCD（x,y）= y | xy and x MOD y = 0; GCD（y, x MOD y）| xy and x MOD y 0 说明：先判断说

37、明：先判断x能否被能否被y整除，若可以，则最大公约数整除，若可以，则最大公约数就是除数就是除数y；否则，则将；否则，则将y 作为被除数，作为被除数，x MOD y 作为除数继续上面的操作，直到作为除数继续上面的操作，直到x能被能被y整除为止。整除为止。 GCD(6,4)GCD(4,2)= 2=GCD(124,6)最大公约数为最大公约数为2例如：求例如：求GCD(124,6)的过程为：的过程为： 65算法算法1xyr231交换变量交换变量x和和y的值：的值：自顶向下，逐步细化自顶向下，逐步细化 66最终算法1 算法设计任务结算法设计任务结束的标准是各步束的标准是各步骤已精细到能用骤已精细到能用语

38、句描述，即满语句描述，即满足算法的足算法的5大特大特征标志算法设计征标志算法设计任务结束任务结束 。 67算法算法2思考：能否不借助于变量思考：能否不借助于变量r，而是而是xy; y x%y？ 或者或者y x%y；x y 68 练习练习3：设计算法，求一个非负整数的长度。：设计算法，求一个非负整数的长度。 算法算法1：例如：例如num=12345，求，求num的长度的长度 第第1步：去掉最低位，步：去掉最低位，num=1234，长度，长度len=1 第第2步：去掉最低位，步：去掉最低位，num=123，长度，长度len=2 第第3步：去掉最低位，步：去掉最低位，num=12，长度，长度len=

39、3 第第4步：去掉最低位，步：去掉最低位，num=1，长度，长度len=4 第第5步：去掉最低位，步：去掉最低位，num=0，长度，长度len=5算法中每一步的核心操作是从算法中每一步的核心操作是从num中去掉最低中去掉最低位，长度位，长度len加加1 69 70求正整数的长度求正整数的长度-算法算法2 假设假设num长度不超过长度不超过8，例如，例如num=12345，求，求num的长度的长度 算法算法2：试探能被：试探能被10的几次方除后商不为的几次方除后商不为0 第第1步：步： num /107=0 第第2步：步： num /106=0 第第3步：步： num /105=0 第第4步：步

40、： num /104!=0,说明长度为说明长度为4+15算法中每一步的核心操作是试探：算法中每一步的核心操作是试探：num除除10i后商是否后商是否0 71 增加对输增加对输入为入为0的的判断判断进一步细化进一步细化 72练习4：分解数字 练习练习4：输入一个不超过：输入一个不超过8位的正整数，要求把位的正整数，要求把这个整数分解为单个数字，然后打印出每一个这个整数分解为单个数字，然后打印出每一个数字（每一个数字之间用两个空格分开）。例数字（每一个数字之间用两个空格分开）。例如用户输入了如用户输入了4231，程序打印结果为：，程序打印结果为：4 2 3 1。设计算法。设计算法。 第第1步：得到

41、步：得到num最高位最高位4并输出，并输出，num=231 第第2步：得到步：得到num最高位最高位2并输出，并输出，num=31 第第3步：得到步：得到num最高位最高位3并输出，并输出，num=1 第第4步：得到步：得到num最高位最高位1并输出，并输出，num=0 73求求num的长度的长度len，以及，以及p（p为为10的的len-1次方）次方）得到得到m最高位并输出：最高位并输出：m/p去掉去掉m最高位：最高位：m=m%pp=p/10; len=len-1细化细化练习4：分解数字 74练习5：判断回文数 练习练习5：设计算法，判断一个正整数是否是回：设计算法，判断一个正整数是否是回文

42、数。回文数是指正读和反读都一样的数。如文数。回文数是指正读和反读都一样的数。如121、1221就是回文数。就是回文数。 算法算法1：回文数的第：回文数的第i位和倒数第位和倒数第i位肯定相等位肯定相等 比较第比较第1位和倒数第位和倒数第1位位 比较第比较第2位和倒数第位和倒数第2位位 算法算法2：反着读，假设读得的数为：反着读，假设读得的数为reverseNum，判断判断num和和reverseNum是否相等是否相等 75判断回文数判断回文数-算法算法1left=num/10的的len-1次方次方right=num%10num= num%10的的len-1次方次方/10 76以求以求a0a1a2

43、a3的逆数为例，假设的逆数为例，假设reverse实现逆着实现逆着读读reverse(a3)=a3reverse(a2a3)=a3a2=a3*10 + a2= reverse(a3)*10+a2reverse(a1a2a3)=a3a2a1=a3a2*10 + a1 =reverse(a2a3)*10+ a1reverse(a0a1a2a3)=a3a2a1a0 =a3a2a1*10+a0 =reverse(a1a2a3)*10+a0判断回文数判断回文数-算法算法2 77判断回文数判断回文数-算法算法2 78判断回文数判断回文数-算法算法2#include#includemain() int nu

44、m;/存放输入的整数存放输入的整数 int num1; /*循环中处理的数循环中处理的数,每循环一次每循环一次,右边少一位右边少一位,假设假设num为为1234,则则 num1初始值为初始值为1234,然后是然后是123,然后是然后是12.;*/ int reverse;/*是用分解出来的数字组成的新数是用分解出来的数字组成的新数*/ int m;/*m:存放每一个分解出来的数字存放每一个分解出来的数字;*/ printf(请输入一个小于请输入一个小于8位的正整数位的正整数:); /读取要判断的整数读取要判断的整数 scanf(%d,&num); 79 /*从右到左依次取出各个数字组装成一个新

45、的整数保持到从右到左依次取出各个数字组装成一个新的整数保持到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); else printf(%d 不是回文数不是回文数n,num); system(PAUSE); return 0; 判断回文

46、数判断回文数-算法算法2 80总结：循环结构解题总结：循环结构解题 很多题目都需要循环结构进行求解。很多题目都需要循环结构进行求解。 当一时难以整理出每次循环（迭代）所做的事当一时难以整理出每次循环（迭代）所做的事情时，可以先看一下如果这件事情交给人做的情时，可以先看一下如果这件事情交给人做的话，一步一步是怎么做的。话，一步一步是怎么做的。 在上一步基础上抽象出循环结构的四个方面。在上一步基础上抽象出循环结构的四个方面。 81总结：循环结构解题总结：循环结构解题 2和和3一般没有绝对的先后顺序。一般没有绝对的先后顺序。 在分析清楚在分析清楚2和和3后，才分析后，才分析4（为什么？）。（为什么？

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

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

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

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

51、该较简单问题进行求解。 我们首先设计算法主体框架。我们首先设计算法主体框架。“0000110100011010#”！注意：！注意：2006年年9月出版的教材假设接收到的信月出版的教材假设接收到的信号总是以号总是以1开始，因此算法会有所简化开始，因此算法会有所简化 86“0000110100011010#”signal!=#待细化待细化 87设置观测变量：设置观测变量： int vehicles; /记录车辆信号总数记录车辆信号总数 int seconds; /记录时钟信号总数记录时钟信号总数 int interval; /记录时间间隔记录时间间隔 int longest; /记录最长时间间隔记

52、录最长时间间隔 88Level 1层算法设计层算法设计第0层算法第1层算法 89“0000110100011010#” 分析：分析：处理时钟信号处理时钟信号0 观测时长观测时长seconds加加1； 两车之间的间隔时两车之间的间隔时长长interval加加1。两。两种情况：如果此前种情况：如果此前已接收到车辆信号已接收到车辆信号1 (如何判断？如何判断？)，则间隔时长则间隔时长interval加加1；否则不做任何；否则不做任何处理。处理。 90“0000110100011010#” 分析：分析：处理车辆信号处理车辆信号1 第一种：第一种： “0000110100011010#”（这是第一个（这

53、是第一个1）n车辆总数车辆总数vehicles加加1 第二种：第二种： “0000110100011010#”（不是第一个（不是第一个1，且前一个信号也是且前一个信号也是1 ）n车辆总数车辆总数vehicles加加1 第三种：第三种： “0000110100011010#”（不是第一个（不是第一个1，且前一个信号是且前一个信号是0 ）n车辆总数车辆总数vehicles加加1n处理是否要更新最长时间间隔（处理是否要更新最长时间间隔（ interval：两车之：两车之间的时间间隔，间的时间间隔，longest：两车之间的最长时间间隔）：两车之间的最长时间间隔） 91“000011010001101

54、0#” 分析：处理车辆信号分析：处理车辆信号1vehicles vehicles +1； 情况情况1：第一个：第一个1 判断式：判断式： vehicles =1 情况情况2：不是第一个：不是第一个1，且，且前一个信号也是前一个信号也是1 判断式：判断式： vehicles1 & interval=0 情况情况3：不是第一个：不是第一个1，且，且前一个信号是前一个信号是0 : 判断式：判断式： vehicles1 & interval0 处理：处理：1）若）若intervallongest 则则 longest interval。 2） interval0。情况情况1情况情况3情况情况2 92“

55、0000110100011010#”验证算法验证算法【程序演示】 93#includemain() int vehicles; /记录车辆信号总数记录车辆信号总数 int seconds; /记录时钟信号总数记录时钟信号总数 int longest; /记录最长时间间隔记录最长时间间隔 int interval; /记录时间间隔记录时间间隔 char signal; /存放读取的信号存放读取的信号 /* 初始化设置初始化设置 */ vehicles=0; seconds=0; longest=0; interval=0; printf(please input signal: n); scan

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

57、l=interval+1; scanf(%c,&signal); 95/* 输出结果输出结果 */ printf(%d vehicles passed in %d secondsn,vehicles,seconds); printf(the longest gap was %d secondsn,longest); system(PAUSE); return 0; 96 练习：将一个由数字字符组成的字符串转换为练习：将一个由数字字符组成的字符串转换为整数或者小数并输出。如：整数或者小数并输出。如：输入输入:134.567# 输出输出:134.567 97 #includemain() char

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

59、fnum = 0; p = 10; flag = 0; printf(please input the string:); 算法算法1：逐情况对字符进行处理：逐情况对字符进行处理 98 scanf(%c,&ch); while( ch != #) if (ch=.) flag = 1;/flag为为1，表示输入了小数点，表示输入了小数点 else /处理小数点之前的字符处理小数点之前的字符 n = ch - 0; if (flag = 0)/若输入的是小数点之前的数若输入的是小数点之前的数 num = num * 10 + n; else/处理小数点之后的字符处理小数点之后的字符 fnum =

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