资源预览内容
第1页 / 共87页
第2页 / 共87页
第3页 / 共87页
第4页 / 共87页
第5页 / 共87页
第6页 / 共87页
第7页 / 共87页
第8页 / 共87页
第9页 / 共87页
第10页 / 共87页
亲,该文档总共87页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
,必修3全册课件,第一章 算法初步,算法知识结构:,基本概念,算法,基本结构,表示方法,应用,自然语言,程序框图,基本算法语句,顺序结构,条件结构,循环结构,辗转相除法和更相减损数,秦九韶算法,进位制,赋值语句,条件语句,循环语句,输入、输出语句,算法的定义: 通常指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成。,算法最重要的特征: 1.有序性 2.确定性 3.有限性,算法的基本特点,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 语句1 ELSE 语句2 END 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 X ELSE PRINT -X END 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、定义: 所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数。若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数。,(1)、算法步骤:,第一步:输入两个正整数 m,n(mn). 第二步:计算m除以n所得的余 数r. 第三步:m=n,n=r. 第四步:若r0,则m,n的最大 公约数等于m;否则 转到第二步. 第五步:输出最大公约数m.,以求8251和6105的最大公约数的过程为例 步骤:,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,显然37是148和37的最大公约数,也就是8251和6105的最大公约数,更相减损术,可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之。,第一步:任意给定两个正整数;判断他们是否都是偶数。若是,则用2约简;若不是则执行第二步。,第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止,则这个等数就是所求的最大公约数。,(1)、九章算术中的更相减损术:,1、背景介绍:,(2)、现代数学中的更相减损术:,2、定义:,所谓更相减损术,就是对于给定的两个数,用较大的数减去较小的数,然后将差和较小的数构成新的一对数,再用较大的数减去较小的数,反复执行此步骤直到差数和较小的数相等,此时相等的两数便为原来两个数的最大公约数。,例: 用更相减损术求98与63的最大公约数.,解:由于63不是偶数,把98和63以大数减小数,并辗转相减,986335 633528 35287 28721 21721 1477,所以,98和63的最大公约数等于7,3、方法:,比较辗转相除法与更相减损术的区别 (1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。 (2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到。,1、用更相减损术求两个正数84与72的最大公约数,练习:,思路分析:先约简,再求21与18的最大公约数,然后乘以两次约简的质因数4。,2、求324、243、135这三个数的最大公约数。,思路分析:求三个数的最大公约数可以先求出两个数的最大公约数,第三个数与前两个数的最大公约数的最大公约数即为所求。,数书九章秦九韶算法,对该多项式按下面的方式进行改写:,要求多项式的值,应该先算最内层的一次多项式的值,即,然后,由内到外逐层计算一次多项式的值,即,这种将求一个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=v0x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677,所以,当x=5时,多项式的值是2677.,然后由内向外逐层计算一次多项式的值,即,2 -5 -4 3 -6 7,x=5,10,5,25,21,105,108,540,534,2670,2677,所以,当x=5时,多项式的值是2677.,原多项式的系数,多项式的值.,例.用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.,解法二:列表,2,一、进位制,进位制是人们为了计数和运算方便而约定的记数系统。,进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数,基数为n,即可称n进位制,简称n进制。,“满几进一”就是几进制,几进制的基数就是几.,基数:,二进制、七进制、八进制、十二进制、六十进制等,二进制只有0和1两个数字,七进制用06七个数字,十六进制有09十个数字及ABCDEF六个字母.,式中1处在百位,第一个3所在十位,第二个3所在个位,5和9分别处在十分位和百分位。十进制数是逢十进一的。,我们最常用最熟悉的就是十进制数,它的数值部分是十个不同的数字符号0,1,2,3,4,5,6,7,8,9来表示的。,十进制:,例如133.59,它可用一个多项式来表示:,133.59=1*102+3*101+3*100 +5*10-1+9*10-2,为了区分不同的进位制,常在数的右下角标明基数,十进制一般不标注基数.,例如十进制的133.59,写成133.59(10),七进制的13,写成13(7);二进制的10,写成10(2),二进制与十进制的转换,1、二进制数转化为十进制数,例1:将二进制数110011(2)化成十进制数。,解:,根据进位制的定义可知,所以,110011(2)=51,把其他进位制的数化为十进制数的公式是什么?,方法:除2取余法,即用2连续去除89或所得的商,然后取余数。,例、 把89化为二进制数,解:,根据“逢二进一”的原则,有,892441, 2 (2220)+1, 2( 2( 2110)+0)+1, 2 (2 (2 (2 51)+0)+0)+1,5 2 21,2(2(2(2(221)1)0)0)1,89126025124123022021120,所以:89=1011001(2),2(2(2(2321)0)0)1,2(2(242220)0)1,2(2523+2200)1,2624+230020,892441,44 2220,22 2110,11 2 51, 2 (2 (2 (2 (2 21)+1)+0)+0)+1,所以892(2(2(2(2 2 1)1)0)0)1,十进制转换为二进制,注意: 1.最后一步商为0, 2.将上式各步所得的余数从下到上排列,得到: 89=1011001(2),另解(除2取余法的另一直观写法):,5,2,2,2,1,2,0,1,0,余数,11,22,44,89,2,2,2,2,0,1,1,0,1,例:把89化为五进制数。,解:,根据除k取余法,以5作为除数,相应的除法算
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号