高中数学必修3第一章算法初步

高中数学必修3第一章算法初步第一页，共45页。算法知识结构：基本概念算法基本结构表示方法应用自然语言程序框图基本算法语句顺序结构条件结构循环结构辗转相除法和更相减损数秦九韶算法进位制赋值语句条件语句循环语句输入、输出语句第一页第二页，共45页。算法的定义：

通常指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成。算法最重要的特征：1.有序性2.确定性3.有限性第二页第三页，共45页。算法的基本特点1、有限性一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。2、确定性算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。3、有序性算法中的每一个步骤都是有顺序的,前一步是后一步的前提,只有执行完前一步后,才能执行后一步,有着很强逻辑性的步骤序列。第三页第四页，共45页。

用程序框、流程线及文字说明来表示算法的图形称为程序框图，它使算法步骤显得直观、清晰、简明.终端框(起止框)

输入、输出框

处理框(执行框)

判断框

流程线○连接点二、程序框图第四页第五页，共45页。程序框图又称流程图，是一种用规定的图形，指向线及文字说明来准确、直观地表示算法的图形。程序框名称功能终端框（起止框）表示一个算法的起始和结束输入、输出框表示算法的输入和输出的信息处理框（执行框）赋值、计算判断框判断一个条件是否成立，用“是”、“否”或“Y”、“N”标明第五页第六页，共45页。二、程序框图1、顺序结构

2、条件结构

3、循环结构步骤n步骤n+1满足条件？步骤A步骤B是否满足条件？步骤A是否循环体满足条件?否是循环体满足条件?是否先做后判，否去循环先判后做，是去循环第六页第七页，共45页。二、程序框图1、顺序结构设计一算法,求和1+2+3+…+100，并画出程序框图。算法：第一步：取n=100；第二步：计算；第三步：输出结果。开始结束输入n=100s=(n+1)n/2输出s第七页第八页，共45页。二、程序框图2、条件结构算法：第一步：输入x;第二步：如果x≥0；则输出x；否则输出－x。设计一个算法，求数x的绝对值，并画出程序框图。YN结束x≥0输入x开始输出x输出-x算法分析：实数X的绝对值第八页第九页，共45页。二、程序框图3、循环结构AP是否否

是AP（A）AP否是（C）是

否AP（B）（D）直到型循环结构对应的程序框图是当型循环结构对应的程序框图是直到型循环结构当型循环结构

AD第九页第十页，共45页。

设计一个计算1+2+3+……+100的值的算法，并画出程序框图。算法：第一步：令i=1,s=0;第二步：s=s+i第三步：i=i+1；第四步：直到i＞100时,输出S，结束算法，否则返回第二步。程序框图如下：i>100?i=1开始输出s结束否是s=0i=i+1s=s+i否

是循环体条件循环结构直到型循环结构第十页第十一页，共45页。

设计一个计算1+2+3+……+100的值的算法，并画出程序框图。算法：第一步：令i=1,s=0;第二步：若i<=100成立，则执行第三步；否则，输出s，结束算法；第三步：s=s+i；第四步：i=i+1,返回第二步。i<=100?i=1开始输出s结束否是s=0i=i+1s=s+i当型循环结构程序框图如下：循环体条件是否第十一页第十二页，共45页。语句一般格式主要功能说明1.输入语句2.输出语句3.赋值语句INPUT“提示内容”;变量PRINT“提示内容”;表达式变量＝表达式可对程序中的变量赋值可输出表达式的值，计算可对程序中的变量赋值，计算（1）提示内容和它后面的“；”可以省略（2）一个语句可以给多个变量赋值，中间用“，”分隔（3）无计算功能（1）表达式可以是变量，计算公式，或系统信息（2）一个语句可以输入多个表达式，中间用“，”分隔（3）有计算功能（1）“=”的右侧必须是表达式，左侧必须是变量（2）一个语句只能给一个变量赋（3）有计算功能三．五种基本算法语句第十二页第十三页，共45页。（4）条件语句IF-THEN-ELSE格式

IF-THEN格式

IF

条件THEN语句1ELSE语句2ENDIF满足条件？语句1语句2是否IF

条件THEN语句ENDIF满足条件？语句是否第十三页第十四页，共45页。（5）循环语句①WHILE语句②UNTIL语句WHILE

条件循环体WEND满足条件？循环体是否DO循环体LOOPUNTIL条件满足条件？循环体是否第十四页第十五页，共45页。

成立AP不成立AP成立不成立While（当型）循环Until（直到型）循环两种循环结构有什么差别？先执行循环体，然后再检查条件是否成立，如果不成立就重复执行循环体，直到条件成立退出循环。先判断指定的条件是否为真，若条件为真，执行循环条件，条件为假时退出循环。先执行后判断先判断后执行第十五页第十六页，共45页。编写程序,求和1+2+3+…+n。开始结束输入ns=(n+1)n/2输出sINPUTns=(n+1)n/2*PRINT“S=”;S程序语句：输入语句赋值语句输出语句顺序结构：END变量=表达式第十六页第十七页，共45页。练：编写一程序，求实数X的绝对值。条件结构：开始输入XX≥0输出X输出－X结束YNIFX>=0THENPRINTXELSEPRINT-XENDIF程序:INPUTXEND条件语句：第十七页第十八页，共45页。i=1S=0WHILEi<=100S=S+ii=i+1WENDPRINTSEND当型循环语句当型循环语句练：设计一算法,求和1+2+3+…+100。循环体条件是否WHILE条件循环体WEND开始

结束

输出S是否程序框图：程序语句：当型循环结构第十八页第十九页，共45页。i=1S=0DOS=S+ii=i+1LOOPUNTIL

i>100PRINTSEND开始结束

输出S直到型循环语句直到型循环语句否是否

是循环体条件DO循环体LOOPUNTIL

条件直到型循环结构第十九页第二十页，共45页。一、辗转相除法（欧几里得算法）1、定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。第二十页第二十一页，共45页。(1)、算法步骤：第一步：输入两个正整数

m,n(m>n).第二步：计算m除以n所得的余数r.第三步：m=n,n=r.第四步：若r＝0,则m,n的最大公约数等于m；否则转到第二步.第五步：输出最大公约数m.第二十一页第二十二页，共45页。以求8251和6105的最大公约数的过程为例步骤：8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0显然37是148和37的最大公约数，也就是8251和6105的最大公约数第二十二页第二十三页，共45页。更相减损术

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。（1）、《九章算术》中的更相减损术：1、背景介绍：（2）、现代数学中的更相减损术：第二十三页第二十四页，共45页。2、定义：

所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。第二十四页第二十五页，共45页。例:用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减98－63＝35

63－35＝28

35－28＝7

28－7＝2121－7＝2114－7＝7所以，98和63的最大公约数等于73、方法：第二十五页第二十六页，共45页。比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。第二十六页第二十七页，共45页。1、用更相减损术求两个正数84与72的最大公约数．

练习：思路分析：先约简，再求21与18的最大公约数,然后乘以两次约简的质因数4。2、求324、243、135这三个数的最大公约数。思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。第二十七页第二十八页，共45页。《数书九章》——秦九韶算法设是一个n次的多项式对该多项式按下面的方式进行改写：第二十八页第二十九页，共45页。要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦九韶算法。思考：在求多项式的值上，这是怎样的一个转化？第二十九页第三十页，共45页。

通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。秦九韶算法的特点：在秦九韶算法中反复执行的步骤，可用循环结构来实现。第三十页第三十一页，共45页。例:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.解法一:首先将原多项式改写成如下形式: f(x)=((((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所以,当x=5时,多项式的值是2677.然后由内向外逐层计算一次多项式的值,即第三十一页第三十二页，共45页。2-5-43-67x=5105252110510854053426702677所以,当x=5时,多项式的值是2677.原多项式的系数多项式的值.例.用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.解法二:列表2第三十二页第三十三页，共45页。一、进位制进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。“满几进一”就是几进制，几进制的基数就是几.基数：二进制、七进制、八进制、十二进制、六十进制等二进制只有0和1两个数字，七进制用0~6七个数字十六进制有0~9十个数字及ABCDEF六个字母.第三十三页第三十四页，共45页。

式中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第三十四页第三十五页，共45页。

为了区分不同的进位制，常在数的右下角标明基数，十进制一般不标注基数.例如十进制的133.59，写成133.59(10)七进制的13，写成13(7)；二进制的10，写成10(2)

一般地，若k是一个大于1的整数，那么以k为基数的k进制可以表示为一串数字连写在一起的形式：第三十五页第三十六页，共45页。二进制与十进制的转换1、二进制数转化为十进制数例1：将二进制数110011(2)化成十进制数。解：根据进位制的定义可知所以，110011（2）=51．把其他进位制的数化为十进制数的公式是什么？第三十六页第三十七页，共45页。方法：除2取余法，即用2连续去除89或所得的商，然后取余数。例、把89化为二进制数解：根据“逢二进一”的原则，有89＝2×44＋1＝2×

(2×22＋0)+1＝2×(2×(2×11＋0)+0)+1＝2×(2×(2×

(2×5＋1)+0)+0)+15＝2×2＋1＝2×（2×（2×（2×（22＋1）＋1）＋0）＋0）＋189＝1×26＋0×25＋1×24＋1×23＋0×22＋0×21＋1×20所以：89=1011001（2）＝2×（2×（2×（23＋2＋1）＋0）＋0）＋1＝2×（2×（24＋22＋2＋0）＋0）＋1＝2×（25＋23+22＋0＋0）＋1＝26＋24+23＋0＋0＋2089＝2×44＋144＝2×22＋022＝2×11＋011＝2×

5＋1＝2×(2×(2×(2×

(2×2＋1)+1)+0)+0)+1所以89＝2×（2×（2×（2×（2×2＋1）＋1）＋0）＋0）＋1十进制转换为二进制第三十七页第三十八页，共45页。注意：1.最后一步商为0，2.将上式各步所得的余数从下到上排列，得到：

89=1011001（2）另解（除2取余法的另一直观写法）：522212010余数11224489222201101练习将下面的十进制数化为二进制数？（1）10（2）20第三十八页第三十九页，共45页。例：把89化为五进制数。解：根据除k取余法以5作为除数，相应的除法算式为：所以，89=324（5）895175350423余数除k取余法：十进制数转化为k进制数的方法

用k连续去除该