《算法初步课件》由会员分享，可在线阅读，更多相关《算法初步课件（100页珍藏版）》请在金锄头文库上搜索。
1、1a2a先先去括号去括号再再乘除乘除后后加减加减1、什么是算法呢？什么是算法呢？3a 要把大象装冰箱，分几步？要把大象装冰箱，分几步？答：分三步：答：分三步：第一步：翻开冰箱第一步：翻开冰箱门第二步：把大象装冰箱第二步：把大象装冰箱第三步：关上冰箱第三步：关上冰箱门问：2问题4a 简单地说，算法就是解决问题的程序或步骤。什么是算法呢？什么是算法呢？5a第一步第一步, ,第二步第二步, ,第三步第三步, ,消元消元解一元一次方程解一元一次方程+2+2，得，得 解解得得代入求解代入求解将将 代入代入, ,得得 写一写写一写解方程解方程组写出写出的步的步骤6a写出解第二个方程写出解第二个方程组的算法
2、：的算法：第一步第一步, ,第二步第二步, ,第三步第三步, ,解，得 将代入得 得变一一变7a 在数学上，通常是按照一定在数学上，通常是按照一定规那那么解决某一么解决某一类问题的明确有限的步的明确有限的步骤。算法的定义：8a例例1 (1)设计一个算法一个算法,判断判断7是是否否为质数数;(1)(1)第一步第一步, ,用2除7,得到余数1.因为余数不为0,所以2不能整除7.第二步第二步, ,用3除7,得到余数1.因为余数不为0,所以3不能整除7.第三步第三步, ,用4除7,得到余数3.因为余数不为0,所以4不能整除7.第四步第四步, ,用5除7,得到余数2.因为余数不为0,所以5不能整除7.第
3、五步第五步, ,用6除7,得到余数1.因为余数不为0,所以6不能整除7.因此,7是质数.9a(2)设计一个算法一个算法,判断判断35是否是否为质数数.算法: 第一步第一步, ,用2除35,得到余数1.因为余数不为0,所以2不能整除35.第二步第二步, ,用3除35,得到余数2.因为余数不为0,所以3不能整除35.第三步第三步, ,用4除35,得到余数3.因为余数不为0,所以4不能整除35.第四步第四步, ,用5除35,得到余数0.因为余数为0,所以5能整除35.因此,35不是质数.10a探究你能写出判断整数n(n2)是否为质数的算法吗? 第一步第一步, ,给定大于2的整数n. 第二步第二步,
4、,令i=2. 第三步第三步, ,用i除n,得到余数r. 第四步第四步, ,判断”r=0”是否成立.若是,则n不是质数,结束算法;否则,将i的值增加1,仍用i表示. 第五步第五步, ,判断”i(n-1)”是否成立.若是,则n是质数,结束算法;否则,返回第三步.11a算法的根本特点算法的根本特点1、有、有穷性性一个算法一个算法应包括有限的操作步包括有限的操作步骤，能在，能在执行有行有穷的操作步的操作步骤之后之后结束。束。2、确定性、确定性算法的算法的计算算规那么及相那么及相应的的计算步算步骤必必须是唯一是唯一确定的，既不能模糊其确定的，既不能模糊其词，也不能有二，也不能有二义性。性。3、逻辑性性算
5、法中从开始的算法中从开始的“第一步到第一步到“最后一步之最后一步之间做到做到环环相扣，分工明确，相扣，分工明确，“前一步是前一步是“后一步后一步的前提，的前提，“后一步是后一步是“前一步的前一步的继续。12a算法算法1 1：第二步第二步：计算算1015010150；第三步第三步：写出运算：写出运算结果果算法算法2 2：第一步第一步：取：取n=100n=100；第二步第二步：计算算第三步第三步：写出运算：写出运算结果果写出求写出求1+2+3+ +1001+2+3+ +100的一个算法的一个算法(1+100)+(2+99)+ +(50+51)(1+100)+(2+99)+ +(50+51)；第一步
6、第一步：将原式：将原式变形形为你会了你会了吗？13a2.2.任意任意给定一个正定一个正实数数, ,设计一个算法求以一个算法求以这个个数数为半径的半径的圆的面的面积. .第一步第一步:输入任意一个正入任意一个正实数数r0；第二步第二步:计算算圆的面的面积: S=r2;第三步第三步:输出出圆的面的面积S.14a15a程序框程序框图程序框程序框图又称流程又称流程图，是一种用程，是一种用程序框、流程序框、流程线及文字及文字说明来表示算法明来表示算法的的图形。形。 在程序框在程序框图中，一个或几个程序框的中，一个或几个程序框的组合表示算合表示算法中的一个步法中的一个步骤；带有方向箭有方向箭头的流程的流程
7、线将程序框将程序框连接起来，表示算法步接起来，表示算法步骤的的执行行顺序。序。16a图形符号图形符号名称名称功能功能终端框（起止终端框（起止框）框） 表示一个算法的起始和结束表示一个算法的起始和结束 输入、输出框输入、输出框 表示一个算法输入和输出的信息表示一个算法输入和输出的信息 处理框处理框 赋值、计算赋值、计算判断框判断框 判断某一条件是否成立，成立时在判断某一条件是否成立，成立时在出口处标明出口处标明“是是”或或“Y”；不成立时；不成立时标明标明“否否”或或“N”。 流程线流程线 连接程序框连接程序框 连接点连接点 连接程序框图的两部分连接程序框图的两部分 17a例例用程序框用程序框图
8、表示表示“判断整数判断整数n nn2n2是否是否为质数的算法数的算法18a开始开始输入入ni=2求求n除以除以i的余数的余数ri的的值增加增加1仍用仍用i表示表示in-1或或r=0?输出出“n不是不是质质数数”结束束是是否否是是输出出“n是是质质数数”否否r=0?设n是一个大是一个大于于2的整数的整数.一般用一般用i=i+1表示表示. i=i+1说明明:i表示从表示从2(n-1)的所有正整数的所有正整数,用以用以判断例判断例1步步骤2是否是否终止止,i是一个是一个计数数变量量,有了有了这个个变量量,算法算法才能依次才能依次执行行.逐步逐步考察从考察从2(n-1)的所的所有正整数中是否有有正整数
9、中是否有n的因数存在的因数存在.19a1 1使用使用标准的准的图形符号。形符号。2 2框框图一般按从上到下，从左到右的方向画。一般按从上到下，从左到右的方向画。 3 3除判断框外，大多数流程除判断框外，大多数流程图符号只有一个符号只有一个进入点和一个退出点。判断框具有超入点和一个退出点。判断框具有超过一个退出一个退出点的唯一符号。点的唯一符号。 4 4判断框分两大判断框分两大类，一，一类判断框判断框“是与是与“否否两分支的判断，而且又且两分支的判断，而且又且仅有两个有两个结果；另一果；另一类是多分支判断，有几种不同的是多分支判断，有几种不同的结果。果。 5 5在在图形符号内描述的形符号内描述的
10、语言要非常言要非常简练清楚。清楚。 20a21a开始开始输入入ni=2求求n除以除以i的余数的余数ri=i+1in或或r=0?n不是不是质数数结束束是是否否是是n是是质数数否否r=0?顺序序结构构用程序框用程序框图来表示算法，有来表示算法，有三种不同的根本三种不同的根本逻辑结构：构：条件条件结构构循循环结构构22a三种根本三种根本结构表示一个良好算法的根本构表示一个良好算法的根本单元元顺序序结构构条件条件结构构选择结构构循循环结构构ABPAB成立成立不成立不成立 成立成立AP不成立不成立AP成立成立不成立不成立While 当型当型 循循环环Until 直到型直到型 循循环环23a顺序序结构构
11、顺序结构是由假设干个依次执行的步骤组成的。这是任何一个算法都离不开的根本结构AB24a例1 一个三角形的三边边长分别为a、b、c，利用海伦-秦九韶公式设计一个算法，求出它的面积，画出它的程序框图.第一步：输入三角形三条边的边长 a，b，c；第二步：计算 ；第三步：计算 ；第四步：输出s。算法分析：算法分析：25a开始输入a，b，c输出S结束程序框程序框图26a习题1 设计一算法：输入圆的半径,输出圆的面积，并画出流程图算法分析：第一步：输入入圆的半径的半径第二步：利用公式“圆的面积=圆周率半径的平方计算圆的面积；第三步：输出出圆的面的面积。开始结束输入半径R计算S=Pi*R*R输出面积S定义P
12、i=3.14思考：整个程序框图有什么特点？27a条件条件结构构选择结构构 算法的流程根据条件是否成立有不同的算法的流程根据条件是否成立有不同的流向。条件流向。条件结构就是构就是处理理这种种过程的程的结构。构。PAB成立成立不成立不成立PA不成立不成立成立成立28a例2 任意给定3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在.画出这个算法的程序框图.开始输入a、b、ca+bc,a+cb,b+ca是否同时成立存在这样的三角形结束否是不存在这样的三角形29a解：算法如下。S1 输入xS2 假设x为奇数，那么输出A=3x+2；否那么输出A=5x S3 算法结束。习题2 设x为一
13、个正整数，规定如下运算：假设x为奇数，那么求3x+2；假设x为偶数，那么为5x，写出算法，并画出程序框图。 x为奇数？开始输入xA=3x+2结束否是A=5x30a循循环结构构AP成立成立不成立不成立While（当型）循）循环 成立成立AP不成立不成立Until（直到型）循）循环在一些算法中，从否在一些算法中，从否处开始，按照一定条件，反复开始，按照一定条件，反复执行行某一某一处理步理步骤的情况，的情况，这就是循就是循环结构。反复构。反复执行的行的处理步理步骤称称为循循环体。体。在循在循环结构中，通常都有一个起到循构中，通常都有一个起到循环计数作用的数作用的变量，量，这个个变量的取量的取值一般都
14、含在一般都含在执行或中止循行或中止循环体的条件中。体的条件中。31a例3 设计一个计算1+2+3+100的值的算法，并画出程序框图。算法分析：需要一个累加变量和一个计数变量，将累加变量的初始值设为0，计数变量的值可以从1到100.i=100?i=1开始输出sum结束否是sum=0i=i+1sum=sum+132a根本算法根本算法语句句第一章第一章 算法初步算法初步33a【探究新知】【探究新知】我我们们知道，知道，顺顺序序结结构是任何一个算法都离不开构是任何一个算法都离不开的根本的根本结结构。构。语句句n+1语句句n 输入、入、输出出语句和句和赋值语句根本上句根本上对应于算法中的于算法中的顺序序
15、结构构. .计算机从上而下按照算机从上而下按照语句排列句排列的的顺序序执行行这些些语句句. .输入入语句和句和输出出语句分句分别用来用来实现算法的算法的输入信息入信息, ,输出出结果的功果的功能能. .( (如右如右图) )34a输入入语句和句和输出出语句分句分别用来用来实现算法的算法的输入信息，入信息，输出出结果的功能。果的功能。 例例1 1 用描点法作函数用描点法作函数yx3 33 3x2 22424x3030的的图象象时, ,需要需要求出自求出自变量和函数的一量和函数的一组对应值. .编写程序写程序, ,分分别计算当算当 x5 5，4 4，3 3，2 2，1 1，0 0，1 1，2 2，
16、3 3，4 4，5 5时的函数的函数值. . INPUT “x=;x y=x3+3*x2-24*x+30PRINT xPRINT yEND程序程序: : -输入入语句句 -赋值语句句-打印打印语句句-打印打印语句句-表示表示结束束输出出语句句输出出语句句35a一一. .输入入语句句 INPUT “INPUT “提示内容；提示内容；变变量量输入入语句的一般格式句的一般格式 说明明: :(1)(1)输入入语句的作用是句的作用是实现算法的算法的输入信息功能；入信息功能；(2)“(2)“提示内容提示用提示内容提示用户输入什么入什么样的信息，的信息，变量是指程序在运行量是指程序在运行时其其值是可以是可以
17、变化的量；化的量；(3)(3)输入入语句要求句要求输入的入的值只能是具体的常数，只能是具体的常数，不能是函数、不能是函数、变量或表达式；量或表达式；(4)(4)提示内容与提示内容与变量之量之间用分号用分号“；隔开，；隔开，假假设输入多个入多个变量，量，变量与量与变量之量之间用逗号用逗号“，隔开，隔开. .36a例如例如, ,输入一个学生数学入一个学生数学, ,语文文, ,英英语三三门课的成的成绩, ,可以写成：可以写成：INPUT “数学，数学，语语文，英文，英语语；a，b，c注意注意: :INPUTINPUT语句不但可以句不但可以给单个个变量量赋值, ,还可以可以给多个多个变量量赋值, ,其
18、格式其格式为：INPUT “INPUT “提示内容提示内容1 1，提示内容，提示内容2 2，提示内容，提示内容3 3，；变变量量1 1，变变量量2 2，变变量量3 3，练一一练:请你用你用输入入语句表达句表达课本本P5和和P9页程序框程序框图中中输入框中的内容入框中的内容.P7页: INPUT “n=; n P9页: INPUT a, b, c 37a二二. .输出出语句句 PRINT “提示内容；表达式提示内容；表达式说明明: :(1)“(1)“提示内容提示用提示内容提示用户输出什么出什么样的信息的信息, ,表表达式是指程序要达式是指程序要输出的数据；出的数据；输出常量，出常量，变量的量的值
19、和字符串等系和字符串等系统信息。信息。输出数出数值计算的算的结果。果。(2)(2)输出出语句的用途：句的用途： 输出出语句的一般格式句的一般格式38a(3)同同输输入入语语句一句一样样，表达式前也可以有，表达式前也可以有“提示内容提示内容. 思考思考 : :在在课本本P7P7页图程序框程序框图中的中的输出框的内出框的内容怎容怎样用用输出出语句来表达？句来表达？ 参考答案：参考答案：输出框：出框： PRINT “n is a prime number PRINT “n is a prime number . . PRINT “n is not a prime PRINT “n is not a
20、prime number.number.如如P9页的的输出框出框 可以可以转化化为输出出语句句:输出出SPRINT “S=; S 39a三三. .赋值语句句(1)赋值语句的一般格式句的一般格式:变量表达式量表达式(2)(2)赋值语赋值语句的作用是句的作用是: :先先计计算出算出赋值赋值号右号右边边表达表达式的式的值值, ,然后把然后把这这个个值赋给值赋给左左边边的的变变量量, ,使使该变该变量的量的值值等于表达式的等于表达式的值值。(3)(3)赋值语赋值语句中的句中的“称作称作赋值赋值号号, ,与数学中的等与数学中的等号的意号的意义义是不同的是不同的. .赋值赋值号的左右两号的左右两边边不能不
21、能对换对换. .(4)(4)赋值语赋值语句左句左边边只能是只能是变变量名字而不是表达式量名字而不是表达式, ,如如:2=x:2=x是是错误错误的的; ;右右边边表达式可以是一个数据、表达式可以是一个数据、常量或算式；不能利用常量或算式；不能利用赋值语赋值语句句进进行代数式的行代数式的演算。演算。 如化如化简简、因式分解、解方程等、因式分解、解方程等 5 5 对对于一个于一个变变量可以屡次量可以屡次赋值赋值。40a【例例题解析解析】 例例2 2 ：编写程序，写程序，计算一个学生数学、算一个学生数学、语文、文、英英语三三门课的平均成的平均成绩。分析分析：先写出算法，画出程序框：先写出算法，画出程序
22、框图，再，再进行行编程。程。结束束开始开始输入入a,b,c输出出y程序框程序框图INPUT “Maths,Chinese,English；a,b,cy=(a+b+c)/3PRINT “y=；y END程序程序: :41a 例例3 3 ：给一个一个变量重复量重复赋值。程序程序: :A=10A=A+15PRINT AENDA的的输出出值是多少是多少?分析分析:此程序此程序给变量量A赋了两次了两次值.A的初的初值为10,第二次第二次赋值后后,初初值被被“覆覆盖盖,A的的值变为25,因此因此输出出值是是25.42a 变变式引申式引申:在此程序的根底上，在此程序的根底上，设计设计一个程序，一个程序，要求
23、最后要求最后A A的的输输出出值值是是30.30.A=10A=A+15PRINT AA=A+5PRINT AEND程序程序: : 例例3 3 ：给一个一个变量重复量重复赋值。程序程序: :A=10A=A+15PRINT AEND43a 例例4 4 交交换两个两个变量量A A和和B B的的值, ,并并输出交出交换前后前后 的的值。分析：引入一个中分析：引入一个中间变量量X,X,将将A A的的值赋予予X,X,又将又将B B的的值赋予予A A，再将，再将X X的的值赋予予B B，从而到达交，从而到达交换A A，B B的的值. .比方交比方交换装装满水的两个水桶里的水需要水的两个水桶里的水需要再找一个
24、空桶再找一个空桶INPUT AINPUT BPRINT A，BX=AA=BB=XPRINT A，BEND程序程序: :问题:能否用下列能否用下列赋值语句交句交换A,B的的值?A=BB=A不能不能!44a 练习练习1 1 : :编编写一个程序写一个程序, ,要求要求输输入一个入一个圆圆的半径的半径, ,便能便能输输出出该圆该圆的周的周长长和面和面积积. . 取取 分析分析: :设圆的半径的半径为R,R,那么那么圆的周的周长C=2R,C=2R,面面积S=R2,S=R2,可以利用可以利用顺序序结构中的构中的INPUTINPUT语句句,PRINT,PRINT语句和句和赋值语句句设计程序。程序。INPU
25、T “R=；RC=2*R*R2PRINT “C=；CPRINT “S=； S END45a算法中的条件算法中的条件结构是由条件构是由条件语句来表达的句来表达的, ,条件条件语句是句是处理条件分支理条件分支逻辑结构的算法构的算法语句句 . .条件条件语句的一般格式句的一般格式 满足条件？足条件？语句句是是否否只含一个只含一个“分支的条件分支的条件结构构写成条件写成条件语句句为IFIF 条件条件 THENTHEN 语句体句体END IFEND IF当当计算机算机执行行这种形式的条件种形式的条件语句句时，首先，首先对IFIF后的条件后的条件进行判断，如果条件符合，就行判断，如果条件符合，就执行行TH
26、ENTHEN后的后的语句体，否那么句体，否那么执行行END IFEND IF之后的之后的语句句. . 46a满足条件？足条件？语句句1 1语句句2 2是是否否含两个含两个“分支的条件分支的条件结构构写成条件写成条件语句句为IFIF 条件条件 THENTHEN 语句体句体1 1ELSEELSE 语句体句体2 2END IFEND IF当当计算机算机执行上述行上述语句句时，首先，首先对IFIF后的后的条件条件进行判断，如果条件符合，就行判断，如果条件符合，就执行行THENTHEN后后的的语句体句体1 1，否那么，否那么执行行ELSEELSE后的后的语句体句体2. 2. 47a 条件条件语句的作用句
27、的作用 在程序在程序执行行过程中，根据判断是程中，根据判断是否否满足足约定的条件而决定是否需要定的条件而决定是否需要转换到何到何处去。需要去。需要计算机按条件算机按条件进行行分析、比分析、比较、判断，并按判断后的不、判断，并按判断后的不同情况同情况进行不同的行不同的处理。理。48a1、编写一个程序，求任意写一个程序，求任意实数的数的绝对值。INPUT “x=”；xIF x0 THEN y=-xELSEy=xEND IFPRINT “x=”；yEND程序如下：程序如下：程序框程序框图：开始开始输入入 xy=-xy=x输出出 y结束束x0时,一元二次方程有两个不等的一元二次方程有两个不等的实数根数
28、根.(2)当当=0时,一元二次方程有两个相等的一元二次方程有两个相等的实数根数根.(3)当当=0 THEN p=-b/(2*a) q=SQR(d)/(2*a)IF d=0 THEN PRINT “One real root:；pELSE x1=p+q x2=p-q PRINT “Two real roots:“；x1,x2 END IFELSE PRINT “No real root!END IFEND51a 例例7 7 ：编写程序，使得任意写程序，使得任意输入的入的3 3个整数个整数按从大到小的按从大到小的顺序序输出。出。算法分析：用算法分析：用a a，b b，c c表示表示输入的入的3 3
29、个整数；个整数；为了了节约变量，把它量，把它们重新排列后，仍用重新排列后，仍用a a，b b，c c表示，表示，并使并使abc.abc.具体操作步具体操作步骤如下。如下。第一步：第一步：输入入3 3个整数个整数a a，b b，c.c.第二步：将第二步：将a a与与b b比比较，并把小者，并把小者赋给b b，大者，大者赋给a.a.第三步：将第三步：将a a与与c c比比较. . 并把小者并把小者赋给c c，大者，大者赋给a a，此，此时a a已是三者中最大的。已是三者中最大的。第四步：将第四步：将b b与与c c比比较，并把小者，并把小者赋给c c，大者，大者赋给b b，此，此时a a，b b，
30、c c已按从大到小的已按从大到小的顺序排列好。序排列好。第五步：按第五步：按顺序序输出出a a，b b，c.c.52a【程序程序】INPUT “a，b，c =;a，b，cIF ba THEN t=a a=b b=tEND IFIF ca THEN t=a a=c c=tEND IFIF cb THEN t=b b=c c=tEND IF END IF PRINT a，b，cENDEND53a算法中的循算法中的循环结构是由循构是由循环语句来句来实现的的 . .循循环结构有两种构有两种-当型与直到型当型与直到型.满足条件？足条件？循循环体体是是否否当型循当型循环结构构(当条件当条件满足足时反复反复
31、执行循行循环体体)直到型循直到型循环结构构(反复反复执行循行循环体直到条件体直到条件满足足)循循环体体是是否否满足条件？足条件？对应于程序框于程序框图中的两种循中的两种循环结构，一般构，一般程序程序设计语言中也有当型言中也有当型WHILEWHILE型和直到型型和直到型UNTILUNTIL型两种型两种语句句结构。构。 54a即即WHILEWHILE语句和句和UNTILUNTIL语句。句。 (1)WHILE(1)WHILE语句的一般格式是句的一般格式是: :WHILE WHILE 条件条件 循循环体体WENDWEND其中循其中循环体是由体是由计算机反复算机反复执行的一行的一组语句句构成的。构成的。
32、WHLIEWHLIE后面的后面的“条件是用于控制条件是用于控制计算机算机执行循行循环体或跳出循体或跳出循环体的。体的。WHILEWHILE当当 时候候WENDWEND朝朝方向方向 行走行走55a(1)WHILE(1)WHILE语句的一般格式是句的一般格式是 WHILE 条件条件 循循环体体WEND 当当计算机遇到算机遇到WHILEWHILE语句句时, ,先判断条件的真假先判断条件的真假, ,如果条件如果条件符合符合, ,就就执行行WHILEWHILE与与WENDWEND之之间的循的循环体体; ;然后再然后再检查上述条上述条件件, ,如果条件仍符合如果条件仍符合, ,再次再次执行行循循环体体,
33、,这个个过程反复程反复进行行, ,直直到某一次条件不符合到某一次条件不符合为止止. .这时, ,计算机将不算机将不执行循行循环体体, ,直直接跳到接跳到WENDWEND语句后句后, ,接着接着执行行WENDWEND之后的之后的语句句. . 满足条件？足条件？循循环体体是是否否当型循当型循环结构构56a(2)UNTIL(2)UNTIL语句的一般格式是句的一般格式是: :DODO 循循环体体LOOP UNTIL LOOP UNTIL 条件条件循循环体体是是否否满足条件？足条件？直到型循直到型循环结构构DODO做什么做什么LOOP UNTILLOOP UNTIL绕环绕环回回线线走走, ,直到到达某种
34、直到到达某种 条件条件为为止止思考思考: :参照其直到型循参照其直到型循环结构构对应的程序框的程序框图, ,说说计算机是按怎算机是按怎样的的顺序序执行行UNTILUNTIL语句的？句的？ 57a(2)UNTIL(2)UNTIL语句的一般格式是句的一般格式是: :DODO 循循环体体LOOP UNTIL LOOP UNTIL 条件条件循循环体体是是否否满足条件？足条件？直到型循直到型循环结构构从从UNTILUNTIL型循型循环结构分析构分析, ,计算机算机执行行该语句句时, ,先先执行一次循行一次循环体体, ,然后然后进行条件的判断行条件的判断, ,如果条件不如果条件不满足足, ,继续返回返回执
35、行循行循环体体, ,然后再然后再进行条件的判断行条件的判断, ,这个个过程反复程反复进行行, ,直到某一次条件直到某一次条件满足足时, ,不再不再执行循行循环体体, ,跳到跳到LOOP UNTILLOOP UNTIL语句后句后执行其他行其他语句句, ,是先是先执行循行循环体后体后进行条件判断的循行条件判断的循环语句句. .58a提提问: :通通过对照照, ,大家大家觉得得WHILEWHILE型型语句与句与UNTILUNTIL型型语句之句之间有什么区有什么区别呢？呢？ 区区别：在：在WHILEWHILE语句中句中, ,是当条件是当条件满足足时执行循行循环体体, ,而在而在UNTILUNTIL语句
36、中句中, ,是当条件是当条件不不满足足时执行循行循环体。体。WHILEWHILE语句的一般格式句的一般格式WHILE WHILE 条件条件 循循环体体WENDWENDUNTILUNTIL语句的一般格式句的一般格式DODO 循循环体体LOOP UNTIL LOOP UNTIL 条件条件59a例例1.1.编写程序写程序, ,计算自然数算自然数1+2+3+1+2+3+99+100+99+100的和的和. .分析分析: :这是一个累加是一个累加问题. .我我们可可以用以用WHILEWHILE型型语句句, ,也可以用也可以用UNTILUNTIL型型语句。句。60aWHILEWHILE语句句开始开始结束束
37、i=1S=0i=i+1S=S+i输出出Si100?是是否否当型循当型循环结构构i=1S=0WHLIE i100?否否是是直到型直到型i=1S=0DOS=S+ii=i+1LOOP UNTIL i100PRINT SEND62a开始开始i=1S=0i100?是是S=S+ii=i+1否否输出出S结束束当型循当型循环结构构变式式训练(1):(1):编写程序求写程序求:n!=12345n:n!=12345n的的值. .如何修改如何修改? ?输入入nWHILEWHILE语句句i=1S=0WHLIE i100PRINT SENDS=1101S=Sii=i+2是是开始开始结束束i=1S=0i=i+1S=S+i
38、输出出Si100?否否直到型直到型S=1S=Si i=i+2i101?64a算法案例算法案例65a辗转相除法相除法更相减更相减损术66a1、求两个正整数的最大公、求两个正整数的最大公约数数1求求25和和35的最大公的最大公约数数2求求225和和135的最大公的最大公约数数2、求、求8251和和6105的最大公的最大公约数数 25（1） 55357所以，所以，25和和35的最大公的最大公约数数为5所以，所以，225和和135的最大公的最大公约数数为533=45课前复习225（2） 545135273159知知识回回忆：先用：先用两个数公有的两个数公有的质因数因数连续去除，去除，一直除到所得的一直
39、除到所得的商是互商是互质数数为止，止，然后把所有的除然后把所有的除数数连乘起来乘起来33567a辗转相除法欧几里得算法相除法欧几里得算法观察用察用辗转相除法求相除法求8251和和6105的最大公的最大公约数的数的过程程 第一步第一步 用两数中用两数中较大的数除以大的数除以较小的数，求得小的数，求得商商和和余数余数8251=61051+2146结论： 8251和和6105的公的公约数就是数就是6105和和2146的公的公约数，求数，求8251和和6105的最大公的最大公约数，只要求出数，只要求出6105和和2146的公的公约数数就可以了。就可以了。第二步第二步 对6105和和2146重复第一步的
40、做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公的最大公约数也是数也是2146和和1813的最大的最大公公约数。数。 68a完整的完整的过程程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例2 用用辗转相除法求相除法求225和和135的最大公的最大公约数数225=1351+90135=901+4590=452显然然37是是148和和37的最大公的最大公约数，也就是数，也就是8251和和6105的最的最大公大公约数数 显然然45是是90和和45的
41、最大公的最大公约数，也就是数，也就是225和和135的最大公的最大公约数数 思考思考1：从上面的两个例子可以看出：从上面的两个例子可以看出计算的算的规律是什么？律是什么？ S1：用大数除以小数：用大数除以小数S2：除数：除数变成被除数，余数成被除数，余数变成除数成除数S3：重复：重复S1，直到余数，直到余数为069a第一步第一步, ,给定两个正数定两个正数m m、n n第二步第二步, ,计算算m m除以除以n n所得到余数所得到余数r r第三步第三步,m=n,m=n；n=rn=r第四步第四步, ,假假设r=0,r=0,那么那么m m、n n的最大公的最大公约数等数等于于m;m;否那么返回第二步
42、否那么返回第二步辗转相除法求最大公相除法求最大公约数算法：数算法： 辗转相除法是一个反复相除法是一个反复执行直到余数等于行直到余数等于0 0停止停止的步的步骤，这实际上是一个循上是一个循环结构。构。70a否否开始开始 输入两个正数入两个正数m,nmn?r=m MOD nr0?输出出n结束束m=xm=nn=r否否是是是是INPUT m,nIF mn THEN x=n n=m m=xEND IFr=m MOD nWHILE r0 m=nn=rr=m MOD n WENDPRINT nENDx=nn=m71a更相减更相减损术算理算理：可半者半之，不可半者，副置分母、子之数，以少可半者半之，不可半者，
43、副置分母、子之数，以少减多，更相减减多，更相减损，求其等也，以等数，求其等也，以等数约之。之。第一步：任意第一步：任意给定两个正整数；判断他定两个正整数；判断他们是否都是是否都是偶数。假偶数。假设是，那么用是，那么用2 2约简；假；假设不是，那么不是，那么执行行第二步。第二步。第二步：以第二步：以较大的数减大的数减较小的数，接着把所得的差与小的数，接着把所得的差与较小的数比小的数比较，并以大数减小数。，并以大数减小数。继续这个操作，直个操作，直到所得的减数和差相等到所得的减数和差相等为止，那么止，那么这个等数或个等数或这个等个等数与数与约简的数的乘的数的乘积就是所求的最大公就是所求的最大公约数
44、。数。72a例例1 1、用更相减、用更相减损术求求9898与与6363的最大公的最大公约数数. .解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数以大数减小数，并减小数，并辗转相减，相减， 即：即：986335; 633528; 35287; 28721; 21714; 1477.所以，所以，9898与与6363的最大公的最大公约数是数是7 7。73a二者算理相似，有异曲同工之妙二者算理相似，有异曲同工之妙1 1、都是求最大公、都是求最大公约数的方法，数的方法，计算上算上辗转相除相除法以除法法以除法为主，更相减主，更相减损术以减法以减法为主，主，计算算次数上次数上辗转
45、相除法相除法计算次数相算次数相对较少，特少，特别当当两个数字大小区两个数字大小区别较大大时计算次数的区算次数的区别较明明显。2 2、从、从结果表达形式来看，果表达形式来看，辗转相除法表达相除法表达结果果是以相除余数是以相除余数为0 0那么得到，而更相减那么得到，而更相减损术那么那么以减数与差相等而得到差以减数与差相等而得到差为0 0辗转相除法与更相减相除法与更相减损术的区的区别74a秦九韶算法秦九韶算法75a问题1设计求多求多项式式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的的值的算法的算法,并写出程序并写出程序.x=5f=2*x5-5*x4-4*x3+3*x2-6*x+7
46、PRINT fEND程序程序点点评:上述算法一共做了上述算法一共做了15次乘法运算次乘法运算,5次加法运算次加法运算.优点是点是简单,易懂易懂;缺点是不通用缺点是不通用,不能解决任意多不能解决任意多项多求多求值问题,而且而且计算效率不高算效率不高.76a 这析析计算上述多算上述多项式的式的值,一共需要一共需要9次乘次乘法运算法运算,5次加法运算次加法运算.问题2有没有更高效的算法有没有更高效的算法?分析分析:计算算x的的幂时,可以利用前面的可以利用前面的计算算结果果,以减少以减少计算量算量,即先即先计算算x2,然后依次然后依次计算算的的值.第二种做法与第一种做法相比第二种做法与第一种做法相比,
47、乘法的运算次数乘法的运算次数减少了减少了,因而能提高运算效率因而能提高运算效率.而且而且对于于计算机来算机来说,做做一次乘法所需的运算一次乘法所需的运算时间比做一次加法要比做一次加法要长得多得多,因此因此第二种做法能更快地得到第二种做法能更快地得到结果果.77a问题3能否探索更好的算法能否探索更好的算法,来解决任意多来解决任意多项式的求式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0x-
48、5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677这种求多种求多项式式值的方法就叫的方法就叫秦九韶算法秦九韶算法.78af(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我我们可以改写成如下形式可以改写成如下形式:求多求多项式的式的值时,首先首先计算最内算最内层括号内一括号内一次多次多项式的式的值,即即 v1=anx+an-1,然后由内向外逐然后由内向外逐层计算一次多算一次多项式的式的值,即即一般地一般地,对于一个于一个n次多次多项式式v2=v1x+an-2, v
49、3=v2x+an-3, ,vn=vn-1x+a0.这样,求求n次多次多项式式f(x)的的值就就转化化为求求n个个一次多一次多项式的式的值.这种算法称种算法称为秦九韶算法秦九韶算法.f(x)=(anx+an-1)x+an-2)x+a1)x+a0.秦九韶算法秦九韶算法79a点点评:秦九韶算法是求一元多秦九韶算法是求一元多项式的式的值的一种方法的一种方法.它的特点是它的特点是:把求一个把求一个n次多次多项式的式的值转化化为求求n个一次多个一次多项式的式的值,通通过这种种转化化,把运算的次数由至多把运算的次数由至多n(n+1)/2次乘法运次乘法运算和算和n次加法运算次加法运算,减少减少为n次乘法运算和
50、次乘法运算和n次加法运算次加法运算,大大提高了运算效率大大提高了运算效率.80av1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.观察上述秦九韶算法中的察上述秦九韶算法中的n个一次式个一次式,可可见vk的的计算要用到算要用到vk-1的的值. 假假设令令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n)这是一个在秦九韶算法中反复是一个在秦九韶算法中反复执行的步行的步骤,因此可用循因此可用循环结构来构来实现.81a问题画出程序框画出程序框图,表示用秦九韶算法求表示用秦九韶算法求5次多次多项式式f(x)=a5x5+a4x4+a3
51、x3+a2x2+a1x+a0当当x=x0 (x0是是任意任意实数数)时的的值的的过程程,然后写出程序然后写出程序.算法步算法步骤如下：如下：第一步，第一步，输入多入多项式次数式次数n n、最高次、最高次项的系数的系数anan和和x x的的值. .第二步，将第二步，将v v的的值初始化初始化为anan，将，将i i的的值初始化初始化为n-1.n-1.第三步，第三步，输入入i i次次项的系数的系数ai.ai.第四步，第四步，v=vx+aiv=vx+ai，i=i-1.i=i-1.第五步，判断第五步，判断i i是否大于或等于是否大于或等于0 0，假，假设是，那么返回第三是，那么返回第三步；否那么，步；
52、否那么，输出多出多项式的式的值v.v.82a否否程序框程序框图开始开始输入入n,an,x的的值i0?i=n-1v=anv=vx+aii=i-1输出出v结束束是是INPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE i=0 PRINT “i=”; IINPUT “ai=”; a v=v*x+a i=i-1WENDPRINT vEND输入入ai83a进位制位制84a 问题问题11我我们们常常见见的数字都是十的数字都是十进进制的制的, ,但是并不是生但是并不是生活中的每一种数字都是十活中的每一种数字都是十进进制的制的. .比方比方时间时间和角度的和角度
53、的单单位用六十位用六十进进位制位制, ,电电子子计计算机用的是二算机用的是二进进制制. .那么什那么什么是么是进进位制位制? ?不同的不同的进进位制之位制之间间又有什么又有什么联联系呢系呢? ?进位制是人位制是人们为了了计数和运算的方便而数和运算的方便而约定的一种定的一种记数系数系统，约定定满二二进一一, ,就是二就是二进制制; ;满十十进一一, ,就就是十是十进制制; ;满十六十六进一一, ,就是十六就是十六进制制; ;等等等等. . “满几几进一一,就是几就是几进制制,几几进制的基数就是制的基数就是几几.可使用数字符号的个数称可使用数字符号的个数称为基数基数. .基数基数都是大于都是大于1
54、 1的整数的整数. . 85a例如：二例如：二进制可使用的数字有制可使用的数字有0和和1,基数是基数是2; 十十进制可使用的数字有制可使用的数字有0,1,2,8,9等十个数字等十个数字,基基数是数是10; 十六十六进制可使用的数字或符号有制可使用的数字或符号有09等等10个数字个数字以及以及AF等等6个字母个字母(规定字母定字母AF对应1015),十六十六进制的基数是制的基数是16.注意注意: :为了区分不同的了区分不同的进位制位制, ,常在数字的右下常在数字的右下脚脚标明基数明基数,. ,. 如如111001111001(2)(2)表示二表示二进制数制数,34,34(5)(5)表示表示5 5
55、进制数制数. .十十进制数一般不制数一般不标注基数注基数.86a问题2十十进制数制数3721中的中的3表示表示3个千个千,7表示表示7个百个百,2表示表示2个十个十,1表示表示1个一个一,从而它可以写成下面的形式从而它可以写成下面的形式:3721=3103+7102+2101+1100.想一想二想一想二进制数制数1011(2)可以可以类似的写成什么形式似的写成什么形式?1011(2)=123+022+121+120.同理同理: 3421(5)=353+452+251+150.C7A16(16)=12164+7163+10162 +1161+6160.87a 一般地一般地,假假设k是一个大于是一
56、个大于1的整数的整数,那么以那么以k为基数基数的的k进制数可以表示制数可以表示为一串数字一串数字连写在一起的形式写在一起的形式anan-1a1a0(k) (0ank,0an-1,a1,a0n?输出出b结束束 否否是是INPUT a,k,ni=1b=0t=a MOD 10DO b=b+t*k(i-1) a=a10 t=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND程序程序: :程序框程序框图：输入入a,k,n92a例例2:把把89化化为二二进制的数制的数.分析分析:把把89化化为二二进制的数制的数,需将需将89先写成如下形式先写成如下形式89=an2n+an-12n-
57、1+a121+a020 .89=64+16+8+1=126+025+124 +123+022+021+120 =1011001(2).但如果数太大但如果数太大,我我们是无法是无法这样凑出来的凑出来的,怎么怎么办?89=442+1, 44=222+0, 22=112+0, 11=52+1, 5=22+1, 2=12+0, 1=02+1, 93a89=442+1, 44=222+0, 22=112+0, 11=52+1, 5=22+1, 89=442+1, =(222+0)2+1 =(112+0)2+0)2+1 =(52+1)2+0)2+0)2+1 =(22+1)2+1)2+0) 2+0)2+1
58、=(12)+0)2+1)2+1)2+0) 2+0)2+1=126+025+124 +123+022+021+120=1011001(2).可以用可以用2连续去除去除89或所或所得商得商(一直到商一直到商为0为止止),然后取余数然后取余数-除除2取余法取余法.2=12+0, 1=02+1, 94a44 1例例2:把把89化化为二二进制的数制的数.我我们可以用下面的除法算式表示除可以用下面的除法算式表示除2取余法取余法:289 余数余数222 0211 025 122 121 020 1把算式中各步所得的余数把算式中各步所得的余数从下到上排列从下到上排列,得到得到89=1011001(2).这种方
59、法也可以推广种方法也可以推广为把把十十进制数化制数化为k进制数的制数的算法算法,称称为除除k取余法取余法.95a解解:以以5作作为除数除数,相相应的除法算式的除法算式为:17 4589 余数余数53 250 3 89=324(5).例例3:把把89化化为五五进制的数制的数.96a问题5你会把三你会把三进制数制数10221(3)化化为二二进制数制数吗?解解:第一步第一步:先把三先把三进制数化制数化为十十进制数制数:10221(3)=134+033+232+231+130 =81+18+6+1=106. 第二步第二步:再把十再把十进制数化制数化为二二进制数制数: 106=1101010(2).10
60、221(3)=106= 1101010(2).97a例例 设计一个程序，一个程序，实现“除除k k取余法取余法kNkN，2k92k9第一步：第一步：给定的十定的十进制正整数制正整数a a和和转化后的数的基数化后的数的基数k k第二步：求出第二步：求出a a除以除以k k所得的商所得的商q q，余数，余数r.r.第三步：把得到的余数依次从右到左排列第三步：把得到的余数依次从右到左排列. .第四步：假第四步：假设q0q0，那么，那么a=qa=q，返回第二步；否那么，返回第二步；否那么，输出全部余数出全部余数r r排列得到的排列得到的k k进制数制数. .98a程序框程序框图：开始开始输入入a,k求求a除以除以k的商的商q求求a除以除以k的余数的余数ra=qq=0?输出全部余数出全部余数r排列得到的排列得到的k进制数制数结束束把得到的余数依次从把得到的余数依次从右到左排列右到左排列是是否否99aINPUT “a,k=;a,kb=0i=0DO q=ak r=a MOD k b=b+r*10i i=i+1 a=qLOOP UNTIL q=0PRINT bEND程序程序: :例例 设计一个程序一个程序, ,实现“除除k k取余法取余法. .100a
