1、第十一模块 算法初步 数系的扩充与复数的引入 第五十一讲 算法与程序框图 基本算法语句 共 124 页1 回归课本 共 124 页2 1.算法概念 算法通常是指可以用计算机来解决的某一类问题的程序或步 骤,这些程序或步骤必须是明确和有效的,而且能够在有限 步之内完成. 注意:算法与一般意义上具体问题的解法既有区别又有联系, 它们之间是一般和特殊的关系,算法一方面具有具体化 程 序化 机械化的特点,同时又有高度抽象性 概括性 精确性 的特点,所以算法在解决问题中更具条理性 逻辑性. 共 124 页3 2.程序框图的概念 表示及功能 (1)程序框图又称流程图,是一种用规定的图形 流程线及文字 说明
2、来准确 直观地表示算法的图形. 共 124 页4 (2)程序框图基本图形及功能: 共 124 页5 共 124 页6 注意:画程序框图的规则:使用标准的框图的符号;框图一般按 从上到下,从左到右的方向画;除判断框外,大多数流程图符 号只有一个进入点和一个退出点,而判断框是具有超过一 个退出点的唯一符号;在图形符号内描述的语言要非常简 练清楚. 共 124 页7 3.算法的逻辑结构 算法的三种基本逻辑结构是顺序结构 条件结构和循环结构. 其中循环结构又分为当型(WHILE型)循环和直到型(UNTIL 型)循环. 注意:顺序结构为最简单的算法结构,语句与语句之间 框与框 之间按从上至下的顺序进行;
3、条件结构中必含有判断框;循 环结构一定包含条件结构. 共 124 页8 4.基本算法语句 (1)输入 输出语句分别用来实现算法的输入和输出功能.其一 般格式为: 输入语句:INPUT“提示内容”;变量. 输出语句:PRINT“提示内容”;表达式. 注意:“提示内容”与变量之间必须用分号“;”隔开,“提 示内容”的主要作用是能够让程序运行者更清楚地在计算 机屏幕上看到程序指令,以便更方便 精确地输入相应的变 量值.提示内容也可省略不写. 共 124 页9 输入语句可以给多个变量赋值.其格式:INPUT“提示内容1, 提示内容2,提示内容3,”;变量1,变量2,变量3,特别注 意的是各提示信息之间
4、以及各变量之间必须用逗号“,” 隔开. 输出语句可以在计算机屏幕上输出常量 变量的值和表达 式的值以及系统信息. 共 124 页10 (2)赋值语句的功能是给变量赋值,其一般格式是:变量=表达 式. 注意:赋值语句一般格式中的“=”不同于等式中的“=”,其 实质是先计算“=”右边表达式的值,并将该值赋给“=” 左边的变量,若该变量已有值,该值将被当前值覆盖,即变量 只取当前表达式的值. 共 124 页11 (3)条件语句表达算法中条件结构.其一般格式为: 格式1: IF条件 THEN 语句 END IF 共 124 页12 格式2: IF条件 THEN 语句1 ELSE 语句2 END IF
5、共 124 页13 (4)循环语句有两种类型,即当型和直到型,其一般格式是: 格式1: DO 循环体 LOOP UNTIL条件 共 124 页14 格式2: WHILE条件 循环体 WEND 共 124 页15 5.常用符号 运算符号:加+,减-,乘*,除/,乘方,整除取商/,求余数MOD. 逻辑符号:且AND,或OR,大于,等于=,小于=,小 于等于=,不等于. 常用函数:绝对值ABS,平方根SQR,取整INT. 共 124 页16 6.算法案例 (1)辗转相除法 辗转相除法是用于求两数的最大公约数的一种方法,这种算 法是由欧几里得在公元前300年左右首先提出的,因而又叫 欧几里得算法. (
6、2)秦九韶算法 秦九韶算法是我国南宋数学家秦九韶在他的代表作数书九 章中提出的一种用于计算多项式的值的方法. 共 124 页17 (3)进位制 进位制是人们为了计数和运算方便而约定的记数系统,“满k 进一”就是k进制,k进制的基数为k,k进制数是0k-1之间 的数字构成的. 注意:(1)k进制化为十进制公式: a a a a =a kn+a kn-1+a k+a (其中0a k- n n-11 0(k)nn-110i 1,i=0,1,2,n-1;0a k-1). n 共 124 页18 (2)十进制化为k进制数用“除k求余法”,即把所给十进制数 除以k,得到商和余数,再对商除以k,得到商和余数
7、,以此类 推,直到商为0,把各步余数从下到上排列,即得k进制数. 共 124 页19 考点陪练 共 124 页20 1.任何一个算法都必须有的基本结构是( ) A.顺序结构 C.循环结构 B.条件分支结构 D.三个都有 解析:任何一个算法都不离开顺序结构,它是最简单的逻辑结 构. 答案:A 共 124 页21 2.条件分支结构不同于顺序结构的明显特征是含有( ) A.处理框 C.起止框 B.判断框 D.输入 输出框 解析:由条件分支结构与顺序结构定义可知,条件分支结构有 判断框,而顺序结构中无判断框. 答案:B 共 124 页22 3.下面的程序框图能判断任意输入的数x的奇偶性.其中判断 框内
8、的条件是( ) 共 124 页23 A.m=0 C.x=0 答案:B B.m=1 D.x=1 共 124 页24 4.用秦九韶算法计算多项式 f(x)=3x6+4x5+5x4+6x3+7x2+8x+1,当x=0.4时的值时,需要 做乘法和加法的次数分别是( ) A.6,6 C.5,5 B.5,6 D.6,5 解析:f(x)=(3x+4)x+5)x+6)x+7)x+8)x+1, 共需乘法6次,加法6次. 答案:A 共 124 页25 5.用辗转相除法求294和84的最大公约数时,需要做除法的次 数是( ) A.1 C.3 B.2 D.4 解析:294=843+42,84=422.至此最大公约数便
9、已求出. 答案:B 共 124 页26 类型一算法的设计及算法的顺序结构 解题准备:1.算法必须能解决一类问题(例如解任意一个二元 一次方程组),并且能重复使用. 2.算法过程要简练,而且经过有限步后能得出结果. 3.顺序结果是由若干个依次执行的步骤组成的,这是任何一个 算法都离不开的基本结构.顺序结构可以用如图所示的程 序框图表示. 共 124 页27 共 124 页28 【典例1】 已知一球的内接正方体表面积为S,画出求球体积 的程序框图. 分析 先求球的半径,再求球的体积;先写出算法,再画出框图. 共 124 页29 解 算法: S1 输入S; S a ; 6 S2 计算正方体的边长 2
10、 2 2 S3 计算正方体的体对角线长 b a a a ; 3 4 b 3 2 S4 计算球的体积 V ; S5 输出V. 共 124 页30 程序框图: 共 124 页31 反思感悟 给出一个问题,设计算法应注意: (1)认真分析问题,联系解决此问题的一般数学方法; (2)综合考虑此类问题中可能涉及的各种情况; (3)将解决问题的过程划分为若干个步骤; (4)用简练的语言将各个步骤表示出来. 共 124 页32 探究1 求两底面半径分别为1和4且高为4的圆台的表面积 及体积,写出该问题的一个算法,并画出程序框图. 分析 采用顺序结构,并结合圆台的表面积及体积公式按照 一定逻辑顺序分步写出.
11、共 124 页33 解 算法设计如下: 第一步:r =1,r =4,h=4; 12 第二步: l (r r ) h 22 ; 21 第三步:S =r2 ,S =r2 ,S =(r +r )l; 11 22 31 2 1 3 第四步:S=S +S +S ,V=(S + +S )h; S S 12312 1 2 第五步:输出S和V. 共 124 页34 该算法的程序框图如图: 共 124 页35 反思感悟 不明确圆台表面积,体积公式或逻辑顺序不清. 利用公式求解问题,先写出公式,看公式中的条件是否满足,若 不满足先求出需要的量,看要求的量需根据哪些条件求解, 需要的条件必须先输入,或将已知条件全部
12、输入,求出未知 的量,然后将公式中涉及的量全部代入求值即可. 共 124 页36 类型二算法的条件结构及算法的循环结构 解题准备:1.在一个算法中,经常会遇到一些条件的判断,算法 的流程要根据条件是否成立有不同的流向,条件结构就是 处理这种过程的结构. 共 124 页37 2.常见的条件结构可以用程序框图表示为如图(1)(2)所示的 两种形式. 共 124 页38 3.根据指定条件决定是否重复执行一条或多条指令的控制结 构称为循环结构,反复执行的处理步骤称为循环体.显然,循 环结构中有关于条件的判断,这个条件我们称为循环结束 条件.因此,循环结构中必包含条件分支结构. 共 124 页39 4.
13、常见的循环结构有当型循环和直到型循环,如图(1)(2)所示. 共 124 页40 【典例2】 到银行办理个人异地汇款(不超过100万)时,银行 要收取一定的手续费.汇款额不超过100元,收取1 元手续费;超过100元但不超过5000元,按汇款额的1%收取;超 过5000元,一律收取50元手续.设计算法求汇款额为x元时, 银行收取的手续费y元,只画出流程图. 共 124 页41 分析 先由题意写出函数解析式,对分段函数,因变量在不同 范围内函数的关系式不同,因而当给出一个自变量x的值求 它对应的函数值时,应先判断x满足的条件,因此需用条件结 构来解决. 共 124 页42 解 要计算手续费,首先
14、要建立汇款额与手续费之间的函数 关系式,依题意知 1(0 x 100), y x0.01(100 x5000), 50(5000 x 1000000). 共 124 页43 流程图如图所示. 共 124 页44 反思感悟 不理解“否”的含义,误将第二个判断框中的 “x5000”写成“100 x5000”,将第三个判断框中的 “x1000000”写成“5000100”,但“是”与“否”也应相应换位. 共 124 页45 探究2 某企业2008年的生产总值为200万元,技术创新后预 计以后每年的生产总值将比上一年增加5%,问最早哪一年 的生产总值将超过300万元?试写出解决该问题的一个算 法,并画
15、出相应的程序框图. 共 124 页46 分析 设第n年后该企业生产总值为a, 则a=200(1+0.05)n,此时为2008+n年. 解 算法设计如下: S1 n=0,a=200,r=0.05. S2 T=ar(计算年增量). S3 a=a+T(计算年产量). S4 如果a300,那么n=n+1,重复执行S2; 否则执行S5. 共 124 页47 S5 N=2008+n. S6 输出N. 共 124 页48 程序框图如下: 解法一:解法二: 共 124 页49 反思感悟 注意直到型循环结构和当型循环结构的本质区 别,直到型循环结构先执行a=a+T,再判断a300,若不满足, 则执行循环体,直到
16、满足才输出N;而当型循环结构先判断 a300,若成立,则执行循环体,直到a300不成立才结束循 环,输出N. 共 124 页50 类型三输入 输出语句 赋值语句 解题准备:1.将表达式所代表的值赋给变量的语句叫做赋值语 句.变量指的是计算机内存中的一块区域,用来存储数值,一 般用英文字母a,b,c或者单词(中间不能加空格)来表示. 在应用变量之前,我们必须事先利用赋值语句,将变量赋为 确定的值(这是因为变量在应用之前可能存储着某些值,我 们称这个过程为“清零”). 它的一般格式为:变量=表达式,赋值语句中的“=”称作赋值 号. 共 124 页51 2.在很多算法中,变量需要接受我们从键盘输入的
17、数据,完成 这个功能的语句叫做输入语句.在这里我们只研究INPUT 输入语句. INPUT输入语句的一般格式是: INPUT“提示内容”;变量. 共 124 页52 3.任何求解的算法,都要把求解的结果“输出”来,具有这种 功能的语句称为输出语句.在这里只研究常用的输出语句 PRINT. PRINT输出语句的一般格式是: PRINT“提示内容”;表达式. 共 124 页53 【典例3】 画出程序框图并编写一个程序,求用长度为l的细 铁丝分别围成一个正方形和一个圆时所围成的正方形和圆 的面积.要求输入l的值,输出正方形和圆的面积(取3.14). 共 124 页54 l 分析设围成的正方形的边长为
18、a,依题意4a l, a , 4 2 l l 2 所以正方形的面积为S ;同理若设围成的圆的 1 4 16 l 半径为R,则2R l, R ,所以圆的面积为 2 2 l l 2 S R 2 . 因此可以用顺序结构实现这 2 2 4 一算法,采用INPUT语句输入l的值,利用赋值语句得到面积, 最后输出两个面积. 共 124 页55 解 程序框图: 56 程序如下: INPUT“l=”;l S1=(l*l)/16 S2=(l*l)/(4*3.14) PRINT“正方形面积为”;S1 PRINT“圆面积为”;S2 END 共 124 页57 反思感悟 注意程序语言中运算符号的书写格式,如:乘号为
19、“*”平方为“2”,除号为“/”,这与平时运算符号有所 区别,其运算规则为先乘除,后加减,幂优于乘除,同级运算先 左后右,括号内最优先. 编写程序的关键在于搞清问题的算法,特别是算法的结构,然 后确定采取哪一种算法语句.本题中要用到相关的平面几 何的知识来寻求正方形和圆的面积的计算公式,在此基础 上确定利用顺序结构实现算法. 共 124 页58 类型四条件语句和循环语句 解题准备:1.IFTHENELSE格式的条件语句 IFTHENELSE格式的条件语句的一般格式如下: IF 条件THEN 语句序列1 ELSE 语句序列2 END IF 共 124 页59 程序框图如图所示: 共 124 页6
20、0 计算机执行这种格式的条件语句时,如果表达式结果为真,则 执行表达式后面的语句序列1;如果表达式结果为假,则执 行ELSE后面的语句序列2,然后结束这一条件语句. 共 124 页61 2.IFTHEN格式的条件语句 IFTHEN格式的条件语句的一般格式如下: IF 条件 THEN 语句序列1 END IF 共 124 页62 程序框图如下图所示: 共 124 页63 计算机要执行这种格式的条件语句时,先对表达式的结果进 行判断,若表达式结果为真,则执行表达式后面的语句序列1, 否则直接跳过语句序列1,执行其他语句. 共 124 页64 3.循环语句主要用来处理算法中的循环结构,即处理一些有规
21、 律的重复计算问题,如累加求和,累乘求积等问题.循环语句 包含两种常见的语句:UNTIL循环语句和WHILE循环语句. 共 124 页65 (1)UNTIL循环语句的格式如下: DO 循环体 LOOP UNTIL 条件 共 124 页66 UNTIL语句对应的基本框图(直到型)如下图(1). 共 124 页67 (2)WHILE循环语句的格式如下: WHILE 条件 循环体 WENDWHILE语句对应的基本框图(当型)如图(2). 共 124 页68 4.两个循环含有循环变量 终止条件和循环体三个要素,当型 循环先判断后执行,直到型循环先执行后判断. 共 124 页69 【典例4】 国庆期间,
22、某超市对顾客实行购物优惠活动,规定 一次购物付款总额:若不超过200元,则不予优惠;若超 过200元,但不超过500元,则按标价价格给予9折优惠;如 果超过500元,500元的部分按条优惠,超过500元的部分 给予7折优惠,编写一个收款程序. 分析 先根据题意,确定分段函数,再利用条件语句写出程序. 共 124 页70 解 依题意,付款总额y与标价x之间的关系式为(单位为元) x (x200) y 0.9x(200 x500) 0.9500 0.7(x 500)(x 500) 共 124 页71 算法分析: 第一步,输入x值. 第二步,判断,如果x200,则输出x,否则执行第三步. 第三步,判
23、断,如果x500成立,则计算y=0.9x,并输出y,否则 执行第四步. 第四步,计算y=0.9500+0.7(x-500),并输出y. 共 124 页72 程序框图: 共 124 页73 程序: INPUT x IF x=200 THEN PRINT x ELSE IF x=500 THEN y=0.9*x PRINT y ELSE y=0.9*500+0.7*(x-500) 共 124 页74 PRINT y END IF END IF END 共 124 页75 反思感悟 条件语句必须以IF语句开始,以END IF语句结束, 一个IF语句必须和一个END IF对应,尤其对条件语句的嵌 套编
24、程时,往往漏掉END IF. (1)要区别好条件语句的两种格式:IF-THEN-ELSE格式和IF- THEN格式,理解它们的区别与联系,以及在实际编写程序 中各自的特点. (2)求分段函数的函数值往往要用条件语句编写程序,有时还 要用到多个条件语句的嵌套,这时为防止漏掉相应的END IF,书写时成对的IF和END IF要上下对齐(内嵌的IF依次往 右错开),这样不仅层次清楚,而且形式美观. 共 124 页76 探究3 高一(2)班共有54名同学参加数学竞赛,现已有这54 名同学的竞赛分数,请设计一个将竞赛成绩优秀同学的平 均分输出的算法(规定90分以上为优秀),画出程序框图,并 设计程序.
25、共 124 页77 分析 由于涉及到54名同学的分数,因此可以使用循环结构 控制输入分数,用条件分支结构来判断分数是否高于90分, 同时统计高于90分的成绩的总和和人数,从而求平均分. 共 124 页78 解 程序框图: 共 124 页79 程序: S=0; M=0; i=1; WHILE i90 S=S+x; 共 124 页80 M=M+1; END i=i+1; WEND P=S/M; P 共 124 页81 反思感悟 在解决实际问题时,要正确理解其中的算法思想, 根据题目写出其关系式,再写出相应的算法.在循环语句中, 也可以嵌套条件语句,甚至是循环语句,此时需要注意嵌套 这些语句需要保证
26、语句的完整性,否则就会造成无法执行. 共 124 页82 类型五 算法语句的实际应用与算法案例的有关计算 解题准备:(1)辗转相除法和更相减损术都是求两个正整数最 大公约数的算法,区别在于辗转相除法进行的是除法运算, 而更相减损术是减法运算.它们都很方便地在计算机上通 过循环语句来实现. (2)秦九韶算法是求多项式值的算法,能方便地在计算机上实 现,且运算次数大大减少. 共 124 页83 【典例5】 填空: (1)779与209的最大公约数是_. (2)在计算多项式f(x)=5x5+4x4+3x3+2x2+ 1 2 x 在x=5处的 2 3 值时,用一般算法共进行了_次加法和乘法运算,用 秦
27、九韶算法,共进行了_次加法和乘法运算. (3)1011101 =_ 2008 =_ . (2)(10)(10)(5) 共 124 页84 分析 (1)利用辗转相除法或利用更相减损术求最大公约 数.(2)根据秦九韶算法列式,数出加法与乘法运算次数.(3) 二进制化十进制即将该二进制数展成基数为2的幂的运算, 十进制化为五进制即将该十进制数连除以5并求各次余数, 将各余数反序排列即为五进制数. 共 124 页85 解析 (1)解法一:(辗转相除法) 779=2093+152 209=1521+57 152=572+38 57=381+19 38=192 所以779和209的最大公约数为19. 共
28、124 页86 解法二:(更相减损术) 779-209=570 570-209=361 361-209=152 209-152=57 152-57=95 95-57=38 共 124 页87 57-38=19 38-19=19 所以779和209的最大公约数为19. 共 124 页88 (2)用一般算法共进行了5+4+3+2+1=15次乘法运算进行了5 次加法运算,进行加法和乘法共15+5=20次. 用秦九韶算法: 1 2 2 3 f (x) 5x 4 x 3 x 2 x x 共 124 页89 按从内向外的顺序,依次计算多项式当x=5时的值; v =5 0 v =v x+4 10 v =v
29、x+3 21 v =v x+2 32 1 2 v =v x+ 43 2 v =v x+ 54 3 由上式易知:共进行了5次加法和5次乘法运算,共进行了 5+5=10次加法和乘法运算. 共 124 页90 共 124 页91 (3)1011101 =126+025+124+123+122+021+1 (2) 20=93 所以1011101 =93 (2)(10) 所以2008 =31013 (10)(5) 答案 (1)19 (2)20 10 (3)93 31013 共 124 页92 错源一循环结构中的常见错误分析 【典例1】 下列三图是三位同学为计算22+42+62+1002而 绘制的算法程序
30、框图,根据程序框图回答后面的问题. 共 124 页93 94 其中正确的程序框图有哪几个?错误的程序框图有哪几个?错 误的要指出错在哪里. 共 124 页95 正解 以上三个程序框图都不正确. 图1所示的程序框图中,计数变量是i.22,42,62,1002中,指数 都是2,而底数是变化的,相邻两项底数相差2,因此计数变量 要加2. 共 124 页96 故图1有三处错误: 第一处错误,第二个处理框中的“i=42”应该是“i=4”; 第二处错误,第三个处理框中累加的是“i2”而不是“i”,即 p=p+i2; 第三处错误,第四个处理框中内容应是“i=i+2”,而不是 “i=i+1”; 共 124 页
31、97 图2所示的程序框图中共有四处错误: 第一处错误,流程线没有箭头显示程序的执行顺序; 第二处错误,第三个处理框中的内容应是“p=p+i2”,而不是 “p=p+i”; 第三处错误,判断框的流程线没有标明“是”和“否”; 共 124 页98 第四处错误,在第三个处理框和判断中漏掉了在循环中起主 要作用的框图,内容为i=i+2,否则程序无法退出循环. 图3所示的程序框图中有一处错误,判断框中的循环条件错误, 导致无法执行循环体,判断框中的内容应是“i100?”. 共 124 页99 错源二 对循环语句中的循环终止条件把握不准 1 1 11 【典例2】写出计算 的一个算法程序. 2222 1 2
32、3100 共 124 页100 错解 程序如下: S=0 i=1 1 1002 WHILE i 1 S=S+ i2 i=i+1 END WHILE PRINT S 共 124 页101 剖析 此解法的错误就在于循环起始终止条件不正确,实际 上,在循环结构中,引入循环变量i,一是为了计数,二是为了 控制循环,使程序执行后输出结果与实际结果一致.本题中, 循环条件应为i100,一般地,写完一个算法程序后,应执行 一遍循环体,检验一下自己的算法是否符合格式要求和题 目要求. 共 124 页102 正解 程序如下: S=0 i=1 WHILE i100 1 S=S+ i 2 i=i+1 WEND PR
33、INT S END 共 124 页103 技法一三种语句和框图的对应转化 【典例1】 以下是一个用基本算法语句编写的程序,根据程 序画出其相应的程序框图. 共 124 页104 INPUT“x,y=”;x,y x=x/2 y=3*y PRINT x,y x=x-y y=y-1 PRINT x,y END 共 124 页105 解题切入点 该程序主要利用了输入语句 赋值语句和输出 语句进行算法描述,只要按顺序从上到下将输入语句 赋值 语句 输出语句表达的内容填入相应的图框即可. 共 124 页106 解 程序框图如下所示. 共 124 页107 技法二三种语句的理解 【典例2】 写出下列语句描述
34、的算法的输出结果. (1) a=5 b=3 a b c 2 d=c*c PRINT“d=”;d 共 124 页108 (2) a=1 b=2 c=a+b b=a+c-b PRINT“a=,b=,c=”;a,b,c 共 124 页109 (3) a=10 b=20 c=30 a=b b=c c=a PRINT“a=,b=,c=”;a,b,c 共 124 页110 解题切入点 此题主要考查对三种语句的理解,只要对三种 语句理解透彻,不难得到答案. 共 124 页111 a b c 4,解 (1)a=5,b=3, d=c2=16. 2 (2)a=1,b=2,c=a+b, c=3. 又b=a+c-b,
35、 b=1+3-2=2. (3)由b=20及a=b,知a=20;由c=30及b=c,知b=30;由c=a及 a=20,知c=20. 共 124 页112 技法三辗转相除法 【典例3】 用辗转相除法求840与1764的最大公约数. 解 因为1764=8402+84,840=8410+0, 所以840与1764的最大公约数是84. 共 124 页113 方法与技巧 辗转相除法的操作方法: (1)算法步骤:(以求a,b两正整数的最大公约数为例) 第一步:输入两个正整数a,b(ab); 第二步:把ab的余数赋予r; 第三步:如果r0,那么把b赋予a,把r赋予b,转到第二步;否则转 到第四步; 第四步:输
36、出最大公约数b. 共 124 页114 (2)程序框图如图所示: 共 124 页115 (3)程序如下: INPUT“a,b=”;a,b DO r=a MOD b a=b b=r LOOP UNTIL r=0 PRINT b END 共 124 页116 (4)辗转相除法的理论依据是:由a=nb+rr=a-nb得a,b与b,r 有相同的公约数. 共 124 页117 技法四更相减损术 【典例4】 用更相减损术求440与556的最大公约数. 共 124 页118 解 因为556-440=116, 440-116=324, 324-116=208,208-116=92, 116-92=24,92-
37、24=68, 68-24=44,44-24=20, 24-20=4,20-4=16, 16-4=12,12-4=8, 8-4=4, 所以440与556的最大公约数为4. 共 124 页119 方法与技巧 更相减损术的操作方法: (1)算法步骤:(以求a,b两正整数的最大公约数为例) 第一步:输入两个正整数a,b(ab); 第二步:若a不等于b,则执行第三步,否则执行第五步; 第三步:把a-b的差赋予r; 第四步:如果br,则把b赋予a,把r赋予b;否则把r赋予a,执行第 二步; 第五步:输出最大公约数b. 共 124 页120 (2)程序框图如图所示: 共 124 页121 (3)程序如下: INPUT a,b, WHILE a=b r=a-b IF br THEN a=b b=r 共 124 页122 ELSE a=r END IF WEND PRINT b END 共 124 页123 (4)更相减损术的理论依据是: 由a-b=ra=b+r得a,b与b,r有相同的公约数.所以,辗转相除 法和更相减损术有相同的理论依据,只不过一个用除法,一 个用减法而已. 共 124 页124
