必修3第一章算法初步复习ppt课件.ppt
第一章 算法初步,算法知识结构：,基本概念,算法,基本结构,表示方法,应用,自然语言,程序框图,基本算法语句,顺序结构,条件结构,循环结构,辗转相除法和更相减损数,秦九韶算法,进位制,赋值语句,条件语句,循环语句,输入、输出语句,算法的定义： 通常指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成。,算法最重要的特征：1.有序性 2.确定性 3.有限性,用程序框、流程线及文字说明来表示算法的图形称为程序框图，它使算法步骤显得直观、清晰、简明.,终端框 (起止框),输入、输出框,处理框 (执行框),判断框,流程线,连接点,二、程序框图,程序框图又称流程图，是一种用规定的图形，指向线及文字说明来准确、直观地表示算法的图形。,二、程序框图,1、顺序结构,2、条件结构,3、循环结构,先做后判，否去循环,先判后做，是去循环,二、程序框图,1、顺序结构,设计一算法,求和1+2+3+ +100，并画出程序框图。,二、程序框图,2、条件结构,算法：第一步：输入x;第二步：如果x0；则输出x；否则输出x。,设计一个算法，求数x的绝对值，并画出程序框图。,算法分析：实数X的绝对值,二、程序框图,3、循环结构,直到型循环结构 当型循环结构,A,D,设计一个计算1+2+3+100的值的算法，并画出程序框图。,算法：第一步：令i=1,s=0;第二步：s=s+i第三步：i=i+1；第四步： 直到i100时,输出S，结束算法，否则返回第二步。,程序框图如下：,循环结构,直到型循环结构,设计一个计算1+2+3+100的值的算法，并画出程序框图。,算法：第一步：令i=1,s=0;第二步：若i=100成立，则执行第三步；否则，输出s，结束算法；第三步：s=s+i；第四步：i=i+1,返回第二步。,当型循环结构,程序框图如下：,INPUT “提示内容”;变量,PRINT “提示内容”;表达式,变量表达式,可对程序中的变量赋值,可输出表达式的值，计算,可对程序中的变量赋值，计算,（1）提示内容和它后面 的“；”可以省略,（2）一个语句可以给多个变 量赋值，中间用“，”分隔,（3）无计算功能,（1）表达式可以是变量，计算公式，或系统信息,（2）一个语句可以输入多个表达式，中间用“，”分隔,（3）有计算功能,（1）“=”的右侧必须是表达式，左侧必须是变量,（2）一个语句只能给一个变量赋,（3）有计算功能,三五种基本算法语句,（4）条件语句,IF-THEN-ELSE格式,IF-THEN格式,IF 条件 THEN语句1ELSE语句2END IF,IF 条件 THEN语句END IF,（5）循环语句,WHILE语句,UNTIL语句,WHILE 条件循环体WEND,DO循环体LOOP UNTIL 条件,While（当型）循环,Until（直到型）循环,两种循环结构有什么差别？,先执行循环体，然后再检查条件是否成立，如果不成立就重复执行循环体，直到条件成立退出循环。,先判断指定的条件是否为真，若条件为真，执行循环条件，条件为假时退出循环。,先执行 后判断,先判断 后执行,编写程序,求和1+2+3+ +n。,INPUT n,PRINT “S=” ; S,程序语句：,输入语句,赋值语句,输出语句,顺序结构：,END,变量=表达式,练：编写一程序，求实数X的绝对值。,条件结构：,IF X=0 THEN PRINT XELSE PRINT -XEND IF,程序:,INPUT X,END,条件语句：,i=1,S=0,WHILE i=100,S=S+i,i=i+1,WEND,PRINT S,END,当型循环语句,当型循环语句,练：设计一算法,求和1+2+3+ +100。,WHILE,条件,循环体,WEND,程序框图：,程序语句：,当型循环结构,i=1,S=0,DO,S=S+i,i=i+1,LOOP UNTIL i100,PRINT S,END,开始,结束,输出S,直到型循环语句,直到型循环语句,否,是,DO循环体LOOP UNTIL 条件,直到型循环结构,辗转相除法（欧几里得算法）,1、定义： 所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。,2、定义：,所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。,更相减损术,用辗转相除法与更相减损术求161与253的最大公约数,辗转相除法：,更相减损术：,所以，161和253的最大公约数为23,数书九章秦九韶算法,对该多项式按下面的方式进行改写：,要求多项式的值，应该先算最内层的一次多项式的值，即,然后，由内到外逐层计算一次多项式的值，即,这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦九韶算法。,思考：在求多项式的值上，这是怎样的一个转化？,通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。,秦九韶算法的特点：,例:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.,解法一:首先将原多项式改写成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7,v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677,所以,当x=5时,多项式的值是2677.,然后由内向外逐层计算一次多项式的值,即,一、进位制,进位制是人们为了计数和运算方便而约定的记数系统。,进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。,“满几进一”就是几进制，几进制的基数就是几.,基数：,二进制、七进制、八进制、十二进制、六十进制等,二进制只有0和1两个数字，七进制用06七个数字,十六进制有09十个数字及ABCDEF六个字母.,二进制与十进制的转换,1、二进制数转化为十进制数,例1：将二进制数110011(2)化成十进制数。,解：,根据进位制的定义可知,所以，110011（2）=51,注意：1.最后一步商为0，2.将上式各步所得的余数从下到上排列，得到： 89=1011001（2）,5,2,2,2,1,2,0,1,0,余数,11,22,44,89,2,2,2,2,0,1,1,0,1,十进制转换为二进制,例、 把89化为二进制数,例：把89化为五进制数。,解：,根据除k取余法,以5作为除数，相应的除法算式为：,所以，89=324（5）,除k取余法：十进制数转化为k进制数的方法 用k连续去除该十进制数或所得的商，直到商为零为止，然后把每次所得的余数倒着排成一个数，就是相应的k进制数。,
