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