算法初步课件

算法初步课件第一页，共101页。1.1算法与程序框图第二页，共101页。1.1.1算法的概念第三页，共101页。先去括号再乘除后加减1、什么是算法呢？第四页，共101页。要把大象装冰箱，分几步？答：分三步：第一步：打开冰箱门第二步：把大象装冰箱第三步：关上冰箱门问：2问题第五页，共101页。简单地说，算法就是解决问题的程序或步骤。什么是算法呢？第六页，共101页。第一步,第二步,第三步,（消元）（解一元一次方程）①+②×2，得③解③得（代入求解）将代入①,得写一写解方程组①②写出的步骤第七页，共101页。写出解第二个方程组的算法：第一步,第二步,第三步,③解③，得④将④代入①得①×－②×得变一变①②第八页，共101页。

在数学上，通常是按照一定规则解决某一类问题的明确有限的步骤。算法的定义：第九页，共101页。例1

(1)设计一个算法,判断7是否为质数;(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.第五步,用6除7,得到余数1.因为余数不为0,所以6不能整除7.因此,7是质数.第十页，共101页。(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不是质数.第十一页，共101页。探究你能写出”判断整数n(n>2)是否为质数”的算法吗?第一步,给定大于2的整数n.第二步,令i=2.第三步,用i除n,得到余数r.第四步,判断”r=0”是否成立.若是,则n不是质数,结束算法;否则,将i的值增加1,仍用i表示.第五步,判断”i>(n-1)”是否成立.若是,则n是质数,结束算法;否则,返回第三步.第十二页，共101页。算法的基本特点1、有穷性一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。2、确定性算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。3、逻辑性算法中从开始的“第一步”到“最后一步”之间做到环环相扣，分工明确，“前一步”是“后一步”的前提，“后一步”是“前一步”的继续。第十三页，共101页。算法1：第二步：计算101×50；第三步：写出运算结果算法2：第一步：取n=100；第二步：计算第三步：写出运算结果写出求1+2+3++100的一个算法(1+100)+(2+99)++(50+51)；第一步：将原式变形为你会了吗？第十四页，共101页。2.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.第一步:输入任意一个正实数r>0；第二步:计算圆的面积:S=πr2;第三步:输出圆的面积S.第十五页，共101页。1.1.2程序框图第十六页，共101页。程序框图

程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形。

在程序框图中，一个或几个程序框的组合表示算法中的一个步骤；带有方向箭头的流程线将程序框连接起来，表示算法步骤的执行顺序。第十七页，共101页。图形符号名称功能终端框（起止框）表示一个算法的起始和结束输入、输出框表示一个算法输入和输出的信息处理框赋值、计算判断框判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N”。流程线连接程序框连接点连接程序框图的两部分第十八页，共101页。例用程序框图表示“判断整数n（n>2）是否为质数”的算法第十九页，共101页。开始输入ni=2求n除以i的余数ri的值增加1仍用i表示i≥n-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)的所有正整数中是否有n的因数存在.第二十页，共101页。画程序框图的规则（1）使用标准的图形符号。（2）框图一般按从上到下，从左到右的方向画。（3）除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符号。（4）判断框分两大类，一类判断框“是”与“否”两分支的判断，而且又且仅有两个结果；另一类是多分支判断，有几种不同的结果。（5）在图形符号内描述的语言要非常简练清楚。第二十一页，共101页。算法的基本逻辑结构第二十二页，共101页。开始输入ni=2求n除以i的余数ri=i+1i≥n或r=0?n不是质数结束是否是n是质数否r=0?顺序结构用程序框图来表示算法，有三种不同的基本逻辑结构：条件结构循环结构第二十三页，共101页。三种基本结构（表示一个良好算法的基本单元）①顺序结构②条件结构（选择结构）③循环结构ABPAB成立不成立成立AP不成立AP成立不成立While（当型）循环Until（直到型）循环第二十四页，共101页。①顺序结构

顺序结构是由若干个依次执行的步骤组成的。这是任何一个算法都离不开的基本结构AB第二十五页，共101页。例1已知一个三角形的三边边长分别为a、b、c，利用海伦-秦九韶公式设计一个算法，求出它的面积，画出它的程序框图.第一步：输入三角形三条边的边长a，b，c；第二步：计算；第三步：计算；第四步：输出s。算法分析：第二十六页，共101页。开始输入a，b，c输出S结束程序框图第二十七页，共101页。习题1设计一算法：输入圆的半径,输出圆的面积，并画出流程图算法分析：第一步：输入圆的半径第二步：利用公式“圆的面积=圆周率×（半径的平方）”计算圆的面积；第三步：输出圆的面积。开始结束输入半径R计算S=Pi*R*R输出面积S定义Pi=3.14思考：整个程序框图有什么特点？第二十八页，共101页。②条件结构（选择结构）

算法的流程根据条件是否成立有不同的流向。条件结构就是处理这种过程的结构。PAB成立不成立PA不成立成立第二十九页，共101页。例2任意给定3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在.画出这个算法的程序框图.开始输入a、b、ca+b>c,a+c>b,b+c>a是否同时成立存在这样的三角形结束否是不存在这样的三角形第三十页，共101页。解：算法如下。S1输入xS2若x为奇数，则输出A=3x+2；否则输出A=5xS3算法结束。习题2设x为一个正整数，规定如下运算：若x为奇数，则求3x+2；若x为偶数，则为5x，写出算法，并画出程序框图。

x为奇数？开始输入xA=3x+2结束否是A=5x第三十一页，共101页。③循环结构AP成立不成立While（当型）循环成立AP不成立Until（直到型）循环在一些算法中，从否处开始，按照一定条件，反复执行某一处理步骤的情况，这就是循环结构。反复执行的处理步骤称为循环体。在循环结构中，通常都有一个起到循环计数作用的变量，这个变量的取值一般都含在执行或中止循环体的条件中。第三十二页，共101页。例3设计一个计算1+2+3+……+100的值的算法，并画出程序框图。算法分析：需要一个累加变量和一个计数变量，将累加变量的初始值设为0，计数变量的值可以从1到100.i<=100?i=1开始输出sum结束否是sum=0i=i+1sum=sum+1第三十三页，共101页。1.2基本算法语句第一章算法初步第三十四页，共101页。【探究新知】

我们知道，顺序结构是任何一个算法都离不开的基本结构。语句n+1语句n 输入、输出语句和赋值语句基本上对应于算法中的顺序结构. 计算机从上而下按照语句排列的顺序执行这些语句. 输入语句和输出语句分别用来实现算法的输入信息,输出结果的功能.(如右图)第三十五页，共101页。 输入语句和输出语句分别用来实现算法的输入信息，输出结果的功能。例1用描点法作函数y＝x3＋3x2－24x＋30的图象时,需要求出自变量和函数的一组对应值.编写程序,分别计算当

x＝－5，－4，－3，－2，－1，0，1，2，3，4，5时的函数值.INPUT

“x=”;xy=x^3+3*x^2-24*x+30PRINT

xPRINT

yEND程序:

-----------------输入语句

---------赋值语句-------------------------打印语句-------------------------打印语句-------------------------表示结束输出语句输出语句第三十六页，共101页。一.输入语句

INPUT“提示内容”；变量输入语句的一般格式说明:(1)输入语句的作用是实现算法的输入信息功能；(2)“提示内容”提示用户输入什么样的信息，变量是指程序在运行时其值是可以变化的量；(3)输入语句要求输入的值只能是具体的常数，不能是函数、变量或表达式；(4)提示内容与变量之间用分号“；”隔开，若输入多个变量，变量与变量之间用逗号“，”隔开.第三十七页，共101页。例如,输入一个学生数学,语文,英语三门课的成绩,可以写成：INPUT“数学，语文，英语”；a，b，c注意: INPUT语句不但可以给单个变量赋值,还可以给多个变量赋值,其格式为：INPUT“提示内容1，提示内容2，提示内容3，…”；变量1，变量2，变量3，… 练一练:请你用输入语句表达课本P5和P9页程序框图中输入框中的内容.P7页:INPUT“n=”;nP9页:INPUTa,b,c第三十八页，共101页。二.输出语句

PRINT“提示内容”；表达式说明:(1)“提示内容”提示用户输出什么样的信息,表达式是指程序要输出的数据；①输出常量，变量的值和字符串等系统信息。②输出数值计算的结果。(2)输出语句的用途：输出语句的一般格式第三十九页，共101页。(3)同输入语句一样，表达式前也可以有“提示内容”.〖思考〗:在课本P7页图1.1-2程序框图中的输出框的内容怎样用输出语句来表达？参考答案：输出框：

PRINT“nisaprimenumber.”PRINT“nisnotaprimenumber.”如P9页的输出框可以转化为输出语句:输出SPRINT“S=”;S第四十页，共101页。三.赋值语句(1)赋值语句的一般格式:变量＝表达式(2)赋值语句的作用是:先计算出赋值号右边表达式的值,然后把这个值赋给左边的变量,使该变量的值等于表达式的值。(3)赋值语句中的“＝”称作赋值号,与数学中的等号的意义是不同的.赋值号的左右两边不能对换.(4)赋值语句左边只能是变量名字而不是表达式,如:2=x是错误的;右边表达式可以是一个数据、常量或算式；不能利用赋值语句进行代数式的演算。（如化简、因式分解、解方程等）（5）对于一个变量可以多次赋值。第四十一页，共101页。【例题解析】〖例2〗：编写程序，计算一个学生数学、语文、英语三门课的平均成绩。分析：先写出算法，画出程序框图，再进行编程。结束开始输入a,b,c输出y程序框图INPUT“Maths,Chinese,English”；a,b,cy=(a+b+c)/3PRINT“y=”；yEND程序:第四十二页，共101页。〖例3〗：给一个变量重复赋值。程序:A=10A=A+15PRINT

AENDA的输出值是多少? 分析:此程序给变量A赋了两次值.A的初值为10,第二次赋值后,初值被“覆盖”,A的值变为25,因此输出值是25.第四十三页，共101页。[变式引申]:在此程序的基础上，设计一个程序，要求最后A的输出值是30.A=10A=A+15PRINT

AA=A+5PRINT

AEND程序:〖例3〗：给一个变量重复赋值。程序:A=10A=A+15PRINT

AEND第四十四页，共101页。〖例4〗交换两个变量A和B的值,并输出交换前后的值。分析：引入一个中间变量X,将A的值赋予X,又将B的值赋予A，再将X的值赋予B，从而达到交换A，B的值.（比如交换装满水的两个水桶里的水需要再找一个空桶）INPUT

AINPUT

BPRINT

A，BX=AA=BB=XPRINT

A，BEND程序:问题:能否用下列赋值语句交换A,B的值?A=BB=A不能!!!!!!第四十五页，共101页。〖练习1〗:编写一个程序,要求输入一个圆的半径,便能输出该圆的周长和面积.（π取3.14）分析:设圆的半径为R,则圆的周长C=2πR,面积S=πR2,可以利用顺序结构中的INPUT语句,PRINT语句和赋值语句设计程序。INPUT“R=”；RC=2*3.14*RS=3.14*R^2PRINT“C=”；CPRINT“S=”；SEND第四十六页，共101页。 算法中的条件结构是由条件语句来表达的,条件语句是处理条件分支逻辑结构的算法语句.条件语句的一般格式满足条件？语句是否只含一个“分支”的条件结构写成条件语句为IF

条件THEN

语句体ENDIF当计算机执行这种形式的条件语句时，首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句体，否则执行ENDIF之后的语句.第四十七页，共101页。满足条件？语句1语句2是否含两个“分支”的条件结构写成条件语句为IF

条件THEN

语句体1ELSE

语句体2ENDIF 当计算机执行上述语句时，首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句体1，否则执行ELSE后的语句体2.第四十八页，共101页。条件语句的作用 在程序执行过程中，根据判断是否满足约定的条件而决定是否需要转换到何处去。需要计算机按条件进行分析、比较、判断，并按判断后的不同情况进行不同的处理。第四十九页，共101页。1、编写一个程序，求任意实数的绝对值。INPUT“x=”；xIFx<0THEN

y=-xELSEy=xENDIFPRINT“︱x︱=”；yEND程序如下：程序框图：开始输入xy=-xy=x输出y结束x<0?是否【例题解析】第五十页，共101页。【例题解析】〖例6〗：编写程序，输入一元二次方程ax2+bx+c=0的系数，输出它的实数根。算法分析:一元二次方程的根有三种不同情况:设判别式△=b2-4ac(1)当△>0时,一元二次方程有两个不等的实数根.(2)当△=0时,一元二次方程有两个相等的实数根.(3)当△<0时,一元二次方程没有实数根.第五十一页，共101页。【程序】INPUT

“a，b，c=”;a，b，cd=b*b-4*a*c

IFd>=0THENp=-b/(2*a)q=SQR(d)/(2*a)IFd=0THENPRINT“Onerealroot:”；pELSEx1=p+qx2=p-qPRINT“Tworealroots:“；x1,x2ENDIFELSEPRINT“Norealroot!”ENDIFEND第五十二页，共101页。〖例7〗：编写程序，使得任意输入的3个整数按从大到小的顺序输出。 算法分析：用a，b，c表示输入的3个整数；为了节约变量，把它们重新排列后，仍用a，b，c表示，并使a≥b≥c.具体操作步骤如下。 第一步：输入3个整数a，b，c.

第二步：将a与b比较，并把小者赋给b，大者赋给a.

第三步：将a与c比较.并把小者赋给c，大者赋给a，此时a已是三者中最大的。 第四步：将b与c比较，并把小者赋给c，大者赋给b，此时a，b，c已按从大到小的顺序排列好。 第五步：按顺序输出a，b，c.第五十三页，共101页。【程序】INPUT

“a，b，c=”;a，b，cIFb>aTHENt=aa=bb=tENDIFIFc>aTHENt=aa=cc=tENDIFIFc>bTHENt=bb=cc=tENDIFPRINTa，b，cEND第五十四页，共101页。算法中的循环结构是由循环语句来实现的.循环结构有两种-----当型与直到型.满足条件？循环体是否当型循环结构(当条件满足时反复执行循环体)直到型循环结构(反复执行循环体直到条件满足)循环体是否满足条件？ 对应于程序框图中的两种循环结构，一般程序设计语言中也有当型（WHILE型）和直到型（UNTIL型）两种语句结构。第五十五页，共101页。即WHILE语句和UNTIL语句。(1)WHILE语句的一般格式是:WHILE

条件循环体WEND 其中循环体是由计算机反复执行的一组语句构成的。WHLIE后面的“条件”是用于控制计算机执行循环体或跳出循环体的。WHILE——当……

时候WEND——朝……方向行走第五十六页，共101页。(1)WHILE语句的一般格式是WHILE

条件循环体WEND当计算机遇到WHILE语句时,先判断条件的真假,如果条件符合,就执行WHILE与WEND之间的循环体;然后再检查上述条件,如果条件仍符合,再次执行循环体,这个过程反复进行,直到某一次条件不符合为止.这时,计算机将不执行循环体,直接跳到WEND语句后,接着执行WEND之后的语句.满足条件？循环体是否当型循环结构第五十七页，共101页。(2)UNTIL语句的一般格式是:DO

循环体LOOPUNTIL条件循环体是否满足条件？直到型循环结构DO——做什么LOOPUNTIL——绕环回线走,直到达到某种条件为止思考:参照其直到型循环结构对应的程序框图,说说计算机是按怎样的顺序执行UNTIL语句的？第五十八页，共101页。(2)UNTIL语句的一般格式是:DO

循环体LOOPUNTIL条件循环体是否满足条件？直到型循环结构从UNTIL型循环结构分析,计算机执行该语句时,先执行一次循环体,然后进行条件的判断,如果条件不满足,继续返回执行循环体,然后再进行条件的判断,这个过程反复进行,直到某一次条件满足时,不再执行循环体,跳到LOOPUNTIL语句后执行其他语句,是先执行循环体后进行条件判断的循环语句.第五十九页，共101页。提问:通过对照,大家觉得WHILE型语句与UNTIL型语句之间有什么区别呢？区别：在WHILE语句中,是当条件满足时执行循环体,而在UNTIL语句中,是当条件不满足时执行循环体。WHILE语句的一般格式WHILE

条件循环体WENDUNTIL语句的一般格式DO

循环体LOOPUNTIL条件第六十页，共101页。例1.编写程序,计算自然数1+2+3+…+99+100的和. 分析:这是一个累加问题.我们可以用WHILE型语句,也可以用UNTIL型语句。第六十一页，共101页。WHILE语句开始结束i=1S=0i=i+1S=S+i输出Si≤100?是否当型循环结构i=1S=0WHLIEi<=100S=S+ii=i+1WENDPRINTSEND第六十二页，共101页。UNTIL语句开始结束i=1S=0i=i+1S=S+i输出Si>100?否是直到型i=1S=0DOS=S+ii=i+1LOOPUNTILi>100PRINTSEND第六十三页，共101页。开始i=1S=0i≤100?是S=S+ii=i+1否输出S结束当型循环结构变式训练(1):编写程序求:n!=1×2×3×4×5×……×n的值.如何修改?输入nWHILE语句i=1S=0WHLIEi<=100S=S+ii=i+1WENDPRINTSENDINPUT“n=”;nS=1S=S＊ii≤n?S=1nS=S＊i第六十四页，共101页。变式训练(2):编写程序求:1×3×5×7×……×101的值.如何修改?UNITL语句i=1S=0DOS=S+ii=i+1LOOPUNTILi>100PRINTSENDS=1101S=S＊ii=i+2是开始结束i=1S=0i=i+1S=S+i输出Si>100?否直到型S=1S=S＊i

i=i+2i>101?第六十五页，共101页。算法案例1.3第六十六页，共101页。辗转相除法

更相减损术第六十七页，共101页。1、求两个正整数的最大公约数（1）求25和35的最大公约数（2）求225和135的最大公约数2、求8251和6105的最大公约数25（1）55357所以，25和35的最大公约数为5所以，225和135的最大公约数为5×3×3=45课前复习225（2）545135273159知识回顾：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来335第六十八页，共101页。辗转相除法（欧几里得算法）观察用辗转相除法求8251和6105的最大公约数的过程第一步用两数中较大的数除以较小的数，求得商和余数

8251=6105×1+2146结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。第二步对6105和2146重复第一步的做法

6105=2146×2+1813

同理6105和2146的最大公约数也是2146和1813的最大公约数。思考：从上述的过程你体会到了什么？第六十九页，共101页。完整的过程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2用辗转相除法求225和135的最大公约数225=135×1+90135=90×1+4590=45×2显然37是148和37的最大公约数，也就是8251和6105的最大公约数显然45是90和45的最大公约数，也就是225和135的最大公约数思考1：从上面的两个例子可以看出计算的规律是什么？S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0第七十页，共101页。第一步,给定两个正数m、n第二步,计算m除以n所得到余数r第三步,m=n；n=r第四步,若r=0,则m、n的最大公约数等于m;否则返回第二步辗转相除法求最大公约数算法：

辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。第七十一页，共101页。否开始输入两个正数m,nm<n?r=mMODnr≠0?输出n结束m=xm=nn=r否是是INPUTm,nIFm<nTHENx=nn=mm=xENDIFr=mMODnWHILEr<>0m=nn=rr=mMODnWENDPRINTnENDx=nn=m第七十二页，共101页。更相减损术算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是，则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。第七十三页，共101页。例1、用更相减损术求98与63的最大公约数. 解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝35;63－35＝28;35－28＝7;28－7＝21;21－7＝14;14－7＝7.所以，98与63的最大公约数是7。第七十四页，共101页。二者算理相似，有异曲同工之妙1、都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。2、从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到（差为0）辗转相除法与更相减损术的区别第七十五页，共101页。秦九韶算法第七十六页，共101页。[问题1]设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值的算法,并写出程序.x=5f=2*x^5-5*x^4-4*x^3+3*x^2-6*x+7PRINTfEND程序点评:上述算法一共做了15次乘法运算,5次加法运算.优点是简单,易懂;缺点是不通用,不能解决任意多项多求值问题,而且计算效率不高.第七十七页，共101页。 这析计算上述多项式的值,一共需要9次乘法运算,5次加法运算.[问题2]有没有更高效的算法? 分析:计算x的幂时,可以利用前面的计算结果,以减少计算量, 即先计算x2,然后依次计算的值.

第二种做法与第一种做法相比,乘法的运算次数减少了,因而能提高运算效率.而且对于计算机来说,做一次乘法所需的运算时间比做一次加法要长得多,因此第二种做法能更快地得到结果.第七十八页，共101页。

[问题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=2×5-5=5v2=v1x-4=5×5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677这种求多项式值的方法就叫秦九韶算法.第七十九页，共101页。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)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法.f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0.秦九韶算法第八十页，共101页。 点评:秦九韶算法是求一元多项式的值的一种方法.

它的特点是:把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数由至多n(n+1)/2次乘法运算和n次加法运算,减少为n次乘法运算和n次加法运算,大大提高了运算效率.第八十一页，共101页。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) 这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现.第八十二页，共101页。[问题]画出程序框图,表示用秦九韶算法求5次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0(x0是任意实数)时的值的过程,然后写出程序.算法步骤如下：第一步，输入多项式次数n、最高次项的系数an和x的值.第二步，将v的值初始化为an，将i的值初始化为n-1.第三步，输入i次项的系数ai.第四步，v=vx+ai，i=i-1.第五步，判断i是否大于或等于0，若是，则返回第三步；否则，输出多项式的值v.第八十三页，共101页。否程序框图开始输入n,an,x的值i≥0?i=n-1v=anv=vx+aii=i-1输出v结束是INPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILEi>=0PRINT“i=”;IINPUT“ai=”;av=v*x+ai=i-1WENDPRINTvEND输入ai第八十四页，共101页。进位制第八十五页，共101页。[问题1]我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进制.那么什么是进位制?不同的进位制之间又有什么联系呢?进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一,就是二进制;满十进一,就是十进制;满十六进一,就是十六进制;等等.“满几进一”,就是几进制,几进制的基数就是几. 可使用数字符号的个数称为基数.基数都是大于1的整数.第八十六页，共101页。例如：二进制可使用的数字有0和1,基数是2;

十进制可使用的数字有0,1,2,…,8,9等十个数字,基数是10;

十六进制可使用的数字或符号有0~9等10个数字以及A~F等6个字母(规定字母A~F对应10~15),十六进制的基数是16. 注意:为了区分不同的进位制,常在数字的右下脚标明基数,.如111001(2)表示二进制数,34(5)表示5进制数.十进制数一般不标注基数.第八十七页，共101页。[问题2]十进制数3721中的3表示3个千,7表示7个百,2表示2个十,1表示1个一,从而它可以写成下面的形式:3721=3×103+7×102+2×101+1×100. 想一想二进制数1011(2)可以类似的写成什么形式?1011(2)=1×23+0×22+1×21+1×20.同理:3421(5)=3×53+4×52+2×51+1×50.C7A16(16)=12×164+7×163+10×162

+1×161+6×160.第八十八页，共101页。一般地,若k是一个大于1的整数,那么以k为基数的k进制数可以表示为一串数字连写在一起的形式anan-1…a1a0(k)(0<an<k,0≤an-1,…,a1,a0<k)意思是:(1)第一个数字an不能等于0;(2)每一个数字an,an-1,…,a1,a0都须小于k.k进制的数也可以表示成不同位上数字与基数k的幂的乘积之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1

+…+a1×k1+a0×k0.注意这是一个n+1位数.第八十九页，共101页。[问题3]二进制只用0和1两个数字,这正好与电路的通和断两种状态相对应,因此计算机内部都使用二进制.计算机在进行数的运算时,先把接受到的数转化成二进制数进行运算,再把运算结果转化为十进制数输出.那么二进制数与十进制数之间是如何转化的呢?例1:把二进制数110011(2)化为十进制数.分析:先把二进制数写成不同位上数字与2的幂的乘积之和的形式,再按照十进制数的运算规则计算出结果.解:110011(2)=1×25+1×24+0×23+0×22+1×21+1×20=1×32+1×16+1×2+1=51.

第九十页，共101页。[问题4]你会把三进制数10221(3)化为十进制数吗?解:10221(3)=1×34+0×33+2×32+2×31+1×30=81+18+6+1=106.

总结：

k进制数转化为十进制数的方法 先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.再按照十进制数的运算规则计算出结果.第九十一页，共101页。例

设计一个算法,把k进制数a(共有n位)化为十进制数b.算法步骤如下:第九十二页，共101页。开始输入a,k,nb=0i=1把a的右数第i位数字赋给ti=i+1i>n?输出b结束

①否是①②②INPUTa,k,ni