《必修3第一章算法初步复习课件讲课教案.ppt》由会员分享，可在线阅读，更多相关《必修3第一章算法初步复习课件讲课教案.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章第一章 算法算法(sun f)初步初步第一页，共30页。算法算法(sun f)知识结构：知识结构：基本概念基本概念算算法法(sun f)基本基本(jbn)结构结构表示方法表示方法应用应用自然语言自然语言程序框图程序框图基本算法语句基本算法语句顺序结构顺序结构条件结构条件结构循环结构循环结构辗转相除法和更相减损数辗转相除法和更相减损数秦九韶算法秦九韶算法进位制进位制赋值语句赋值语句条件语句条件语句循环语句循环语句输入、输出语句输入、输出语句第二页，共30页。算法的定义：算法的定义：通常指可以用计算机来解决的通常指可以用计算机来解决的某一类问题的程序或步骤，这些程某一类问题的程序或步骤，这些
2、程序或步骤必须是明确和有效的，而序或步骤必须是明确和有效的，而且且(r qi)能够在有限步之内完成。能够在有限步之内完成。算法最重要算法最重要(zhngyo)的特征：的特征：1.有序性有序性 2.确定性确定性 3.有限性有限性第三页，共30页。用程序框、流程用程序框、流程(lichng)(lichng)线及文字说明来线及文字说明来表示算法的图形称为程序框图，它使算法步骤显表示算法的图形称为程序框图，它使算法步骤显得直观、清晰、简明得直观、清晰、简明.终端终端(zhn dun)框框 (起止框起止框)输入输入(shr)、输出框输出框 处理框处理框(执执行框行框)判断框判断框 流程线流程线 连接点连
3、接点 二、程序框图二、程序框图第四页，共30页。程序框图又称流程图，是一种用规定的图形，指向程序框图又称流程图，是一种用规定的图形，指向(zh xin)线及文字说明来准确、直观地表示算法的图形。线及文字说明来准确、直观地表示算法的图形。程序框名称功能终端框（起止框）表示一个算法的起始和结束输入、输出框表示算法的输入和输出的信息处理框（执行框）赋值、计算判断框判断一个条件是否成立，用“是”、“否”或“Y”、“N”标明第五页，共30页。二、程序框图二、程序框图l1、顺序(shnx)结构l 2、条件(tiojin)结构l 3、循环(xnhun)结构步骤步骤n步骤步骤n+1满足条件？满足条件？步骤步骤
4、A步骤步骤B是是否否满足条件？满足条件？步骤步骤A是是否否循环体循环体满足条件满足条件?否否是是循环体循环体满足条件满足条件?是是否否先做后判，先做后判，否去循环否去循环先判后做，先判后做，是去循环是去循环第六页，共30页。二、程序框图二、程序框图l1、顺序(shnx)结构设计一算法(sun f),求和1+2+3+100，并画出程序框图。算法：算法：第一步：取第一步：取n=100；第二步：计算第二步：计算 ；第三步：输出结果。第三步：输出结果。开始开始结束结束输入输入n=100s=(n+1)n/2输出输出s第七页，共30页。二、程序框图二、程序框图l2、条件(tiojin)结构算法：算法：第一
5、步：输入第一步：输入x;第二步：如果第二步：如果(rgu)x0；则输；则输出出x；否则输出；否则输出x。设计一个(y)算法，求数x的绝对值，并画出程序框图。YN结束x0输入x开始输出x输出-x算法分析：实数算法分析：实数X的绝对值的绝对值第八页，共30页。二、程序框图二、程序框图l3、循环(xnhun)结构AP是是否否否否 是是AP（A）AP否否是是（C）是是 否否AP（B）（D）直到型循环结构对应的程序框图是 当型循环结构对应的程序框图是 直到型循环直到型循环(xnhun)结构结构 当型循当型循环环(xnhun)结构结构 AD第九页，共30页。设计(shj)一个计算1+2+3+100的值的算
6、法，并画出程序框图。算法：算法：第一步：令第一步：令i=1,s=0;第二步：第二步：s=s+i第三步：第三步：i=i+1；第四步：第四步：直到直到i100时时,输出输出S，结束算法，否则结束算法，否则(fuz)返回第二步。返回第二步。程序框图如下程序框图如下(rxi)：i100?i=1开始输出s结束否是s=0i=i+1s=s+i否否 是是循环体循环体条件条件循环结构循环结构直到型循环结构直到型循环结构第十页，共30页。设计一个设计一个(y)计算计算1+2+3+100的值的算法，并画出程序框图。的值的算法，并画出程序框图。算法：算法：第一步：令第一步：令i=1,s=0;第二步：若第二步：若i=1
7、00成立，则执行成立，则执行(zhxng)第三步；否则，输出第三步；否则，输出s，结束算法；，结束算法；第三步：第三步：s=s+i；第四步：第四步：i=i+1,返回第二步。返回第二步。i=0 THEN PRINT XELSE PRINT -XEND IF程序程序(chngx):INPUT XEND条件语句：条件语句：第十七页，共30页。i=1i=1S=0S=0WHILE WHILE i=100 i100i100PRINTPRINT S SENDEND开始开始开始开始(kish(kish)结束结束结束结束(jis(jish)h)输出输出输出输出(shch(shch)S)S直到型循环语句直到型循环
8、语句直到型循环语句直到型循环语句直到型循环语句否否是是否否 是是循环体循环体条件条件DODO循循循循环环体体体体LOOP UNTILLOOP UNTIL 条件条件条件条件 直到型循环结构直到型循环结构直到型循环结构直到型循环结构第十九页，共30页。辗转辗转(zhnzhun)相除法（欧几里得算法）相除法（欧几里得算法）1、定义：、定义：所谓辗转相除法，就是对于给定的两个数，所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数法
9、，直到大数被小数(xiosh)除尽，则这时较小除尽，则这时较小的数就是原来两个数的最大公约数。的数就是原来两个数的最大公约数。第二十页，共30页。2、定义、定义(dngy)：所谓更相减损术，就是对于给定的两个数，所谓更相减损术，就是对于给定的两个数，用较大用较大(jio d)的数减去较小的数，然后将差和的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大较小的数构成新的一对数，再用较大(jio d)的的数减去较小的数，反复执行此步骤直到差数和数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个较小的数相等，此时相等的两数便为原来两个数的最大公约数。数的最大公
10、约数。更相减损更相减损(jin sn)术术 第二十一页，共30页。用辗转相除法(chf)与更相减损术求161与253的最大公约数辗转辗转(zhnzhun)相除相除法：法：更相减损更相减损(jin sn)术：术：所以，所以，161和和253的最大公约数为的最大公约数为23第二十二页，共30页。数书九章数书九章(ji zhn)秦九秦九韶算法韶算法设设是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行对该多项式按下面的方式进行(jnxng)改写：改写：第二十三页，共30页。要求多项式的值，应该要求多项式的值，应该(ynggi)先算最内层的一次多项式的值，即先算最内层的一次多项式的值，即然
11、后然后(rnhu)，由内到外逐层计算一次多项式的值，即，由内到外逐层计算一次多项式的值，即这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为(chn wi)秦九韶秦九韶算法。算法。第二十四页，共30页。通过一次式的反复计算，逐步得出高次多项式的通过一次式的反复计算，逐步得出高次多项式的值，对于值，对于(duy)一个一个n次多项式，只需做次多项式，只需做n次乘法和次乘法和n次加法即可。次加法即可。秦九韶算法秦九韶算法(sun f)的特的特点：点：第二十五页，共30页。例例:用秦九韶算法用秦九韶算法(sun f)求多
12、项式求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值.解法一解法一:首先首先(shuxin)将原多项式改写成将原多项式改写成如下形式如下形式:f(x)=(2x-5)x-4)x+3)x-6)x+7v0=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所以所以(suy),当当x=5时时,多项式的值多项式的值是是2677.然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即第二十六页，共30页。一、进位制一、进位
13、制进位制是人们为了计数和运算方便进位制是人们为了计数和运算方便(fngbin)(fngbin)而约定的记数系而约定的记数系统。统。进位制是一种记数方式，用有限的数字在不同进位制是一种记数方式，用有限的数字在不同(b tn)(b tn)的位置表示不同的位置表示不同(b tn)(b tn)的数值。可使用数字符号的个的数值。可使用数字符号的个数称为基数，基数为数称为基数，基数为n n，即可称，即可称n n进位制，简称进位制，简称n n进制。进制。“满几进一”就是(jish)几进制，几进制的基数就是(jish)几.基数：基数：二进制、七进制、八进制、十二进制、六十进制等二进制只有0和1两个数字，七进制
14、用06七个数字十六进制有09十个数字及ABCDEF六个字母.第二十七页，共30页。二进制与十进制的转换二进制与十进制的转换(zhunhun)(zhunhun)1 1、二进制数转化、二进制数转化(zhunhu)(zhunhu)为十为十进制数进制数例例1 1：将二进制数：将二进制数110011(2)110011(2)化成化成(hu chn)(hu chn)十进制数。十进制数。解：解：根据进位制的定义可知根据进位制的定义可知所以，所以，110011110011（2 2）=51=51第二十八页，共30页。注意：注意：1.1.最后一步商为最后一步商为0 0，2.2.将上式各步所得的余数从下到上排列将上式
15、各步所得的余数从下到上排列(pili)(pili)，得到：，得到：89=1011001 89=1011001（2 2）5 52 22 22 21 12 20 01 10 0余数余数(ysh)(ysh)11112222444489892 22 22 22 20 01 11 10 01 1练习练习将下面的十进制数化为二进制数？将下面的十进制数化为二进制数？（1 1）1010（2 2）2020十进制转换十进制转换(zhunhun)为二进制为二进制例、例、把把89化为二进制数化为二进制数第二十九页，共30页。例：把例：把8989化为五进制数。化为五进制数。解：解：根据根据(gnj)(gnj)除除k k取余法取余法以以5 5作为除数，相应的除法作为除数，相应的除法(chf)(chf)算式为：算式为：所以所以(suy)(suy)，89=32489=324（5 5）89895 517175 53 35 50 04 42 23 3余数余数除除k取余法取余法：十进制数转化为k进制数的方法 用用k连续去除该十进制数或所得的商，直到商连续去除该十进制数或所得的商，直到商为零为止，然后把每次所得的余数倒着排成一个为零为止，然后把每次所得的余数倒着排成一个数，就是相应的数，就是相应的k进制数。进制数。第三十页，共30页。