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

1、第一章第一章 算法初步算法初步算法知识结构：算法知识结构：基本概念基本概念算法算法基本结构基本结构表示方法表示方法应用应用自然语言自然语言程序框图程序框图基本算法语句基本算法语句顺序结构顺序结构条件结构条件结构循环结构循环结构辗转相除法和更相减损数辗转相除法和更相减损数秦九韶算法秦九韶算法进位制进位制赋值语句赋值语句条件语句条件语句循环语句循环语句输入、输出语句输入、输出语句算法的定义：算法的定义： 通常指可以用计算机来解决的某一类通常指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步须是明确和有效的，而且能够在有

2、限步之内完成。之内完成。算法最重要的特征：算法最重要的特征：1.有序性有序性 2.确定性确定性 3.有限性有限性算法的基本特点1、有限性一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。2、确定性算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。3、有序性算法中的每一个步骤都是有顺序的,前一步是后一步的前提,只有执行完前一步后,才能执行后一步,有着很强逻辑性的步骤序列。 用用程序框、流程线程序框、流程线及及文字说明文字说明来表示算来表示算法的图形称为程序框图，它使算法步骤显得法的图形称为程序框图，它使算法步骤显得直观、清晰、简明直观、清晰、简明. .终

3、端框终端框 (起止框起止框) 输入、输入、输出框输出框 处理框处理框 (执行框执行框) 判断框判断框 流程线流程线 连接点连接点 二、程序框图二、程序框图程序框图又称流程图，是一种用规定的图形，指向线及程序框图又称流程图，是一种用规定的图形，指向线及文字说明来准确、直观地表示算法的图形。文字说明来准确、直观地表示算法的图形。程序框名称功能终端框（起止框）表示一个算法的起始和结束输入、输出框表示算法的输入和输出的信息处理框（执行框）赋值、计算判断框判断一个条件是否成立，用“是”、“否”或“Y”、“N”标明二、程序框图二、程序框图l1、顺序结构l 2、条件结构l 3、循环结构步骤步骤n步骤步骤n+

4、1满足条件？满足条件？步骤步骤A步骤步骤B是是否否满足条件？满足条件？步骤步骤A是是否否循环体循环体满足条件满足条件?否否是是循环体循环体满足条件满足条件?是是否否先做后判，先做后判，否去循环否去循环先判后做，先判后做，是去循环是去循环二、程序框图二、程序框图l1、顺序结构设计一算法,求和1+2+3+ +100，并画出程序框图。算法：算法：第一步：取第一步：取n=100；第二步：计算第二步：计算 ；(1 )2nn 第三步：输出结果。第三步：输出结果。开始开始结束结束输入输入n=100s=(n+1)n/2输出输出s二、程序框图二、程序框图l2、条件结构算法：算法：第一步：输入第一步：输入x;第二

5、步：如果第二步：如果x0；则输出则输出x；否则输出；否则输出x。设计一个算法，求数x的绝对值，并画出程序框图。YN结束x0输入x开始输出x输出-x算法分析：实数算法分析：实数X的绝对值的绝对值(0)(0)xxxxx二、程序框图二、程序框图l3、循环结构AP是是否否否否 是是AP（A）AP否否是是（C）是是 否否AP（B）（D）直到型循环结构对应的程序框图是 当型循环结构对应的程序框图是 直到型循环结构直到型循环结构 当型循环结构当型循环结构 AD 设计一个计算1+2+3+100的值的算法，并画出程序框图。算法：算法：第一步：令第一步：令i=1,s=0;第二步：第二步：s=s+i第三步：第三步：

6、i=i+1；第四步：第四步： 直到直到i100时时,输出输出S，结束算法，否则返回第二步。结束算法，否则返回第二步。程序框图如下：程序框图如下：i100?i=1开始输出s结束否是s=0i=i+1s=s+i否否 是是循环体循环体条件条件循环结构循环结构直到型循环结构直到型循环结构 设计一个计算设计一个计算1+2+3+100的值的算法，并画出程序框图。的值的算法，并画出程序框图。算法：算法：第一步：令第一步：令i=1,s=0;第二步：若第二步：若i=100成立，则执行第三步；否则，输出成立，则执行第三步；否则，输出s，结束算法；，结束算法；第三步：第三步：s=s+i；第四步：第四步：i=i+1,返

7、回第二步。返回第二步。i=0 THEN PRINT XELSE PRINT -XEND IF程序程序:INPUT XEND条件语句：条件语句：练：设计一算法练：设计一算法,求和求和1+2+3+ +100。循环体循环体条件条件是是否否1i 0S 1i i S S i 100?i 是是否否1i 0S 1ii SSi 100?i 直到型循环语句否否是是否否 是是循环体循环体条件条件一、辗转相除法（欧几里得算法）一、辗转相除法（欧几里得算法）1、定义：、定义： 所谓辗转相除法，就是对于给定的两个所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为数，用较大的数除以较小的数。若余数不

8、为零，则将余数和较小的数构成新的一对数，零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。这时较小的数就是原来两个数的最大公约数。(1)(1)、算法步骤：、算法步骤：第一步：输入两个正整数第一步：输入两个正整数 m,n(mn).第二步：计算第二步：计算m除以除以n所得的余所得的余 数数r.第三步：第三步：m=n,n=r.第四步：若第四步：若r0,则则m,n的最大的最大 公约数等于公约数等于m；否则；否则 转到第二步转到第二步. 第五步：输出最大公约数第五步：输出最大公约数m.以求以求8251

9、和和6105的最大公约数的过程为例的最大公约数的过程为例步骤：步骤：8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最大公约数，的最大公约数，也就是也就是8251和和6105的最大公约的最大公约数数 更相减损术更相减损术 可半者半之，不可半者，副置分母、子之数，以少减多，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。第一步：任意给定两个正

10、整数；判断他们是否都是偶数。若是，则用若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。减数和差相等为止，则这个等数就是所求的最大公约数。（1）、九章算术中的更相减损术：1、背景介绍：（2）、现代数学中的更相减损术：2、定义：、定义： 所谓更相减损术，就是对于给定的两个所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后

11、将差和数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个小的数相等，此时相等的两数便为原来两个数的最大公约数。数的最大公约数。例例: : 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数. .解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，以大数减小数，并辗转相减并辗转相减 989863633535636335352828353528287 728287 721

12、2121217 7212114147 77 7所以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7 3、方法：比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。大小区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体现结果）从结果体现形式来看，辗

13、转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数与则得到，而更相减损术则以减数与差相等而得到。差相等而得到。1、用更相减损术求两个正数、用更相减损术求两个正数84与与72的最大公约数的最大公约数 练习：练习：思路分析：先约简，再求思路分析：先约简，再求21与与18的最大公约数的最大公约数,然后乘以两次约简的质因数然后乘以两次约简的质因数4。2、求、求324、243、135这三个数的最大公约数。这三个数的最大公约数。思路分析：求三个数的最大公约数可以先求出两个思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数，第三

14、个数与前两个数的最大公约数的最大公约数即为所求。数的最大公约数即为所求。数书九章数书九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn设设)(xf是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn0121)()(axaxaxaxaxfnnn要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即11nnaxav然后，由内到外逐层计算一次多项

15、式的值，即然后，由内到外逐层计算一次多项式的值，即212naxvv323naxvv01axvvnn这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。 通过一次式的反复计算，逐步得出高次多通过一次式的反复计算，逐步得出高次多项式的值，对于一个项式的值，对于一个n次多项式，只需做次多项式，只需做n次乘次乘法和法和n次加法即可。次加法即可。秦九韶算法的特点：秦九韶算法的特点：),2 ,1(循环体：10nkaxvvavknkkn在在秦九韶算法中反复执行的步骤，可用循环结秦九韶算法中反复执行的步骤，可

16、用循环结构来实现。构来实现。例例:用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值.解法一解法一:首先将原多项式改写成如下形式首先将原多项式改写成如下形式 : 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所以所以,当当x=5时时,多多项式的值是项式的值是2677.然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即

17、2 -5 -4 3 -6 7x=5105252110510854053426702677所以所以,当当x=5时时,多项式的值是多项式的值是2677.原多项式原多项式的系数的系数多项式多项式的值的值.例例.用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值.解法二解法二:列表列表2进位制是人们为了计数和运算方便而约定的记数系统。进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式，用有限的进位制是一种记数方式，用有限的数字数字在不同的位在不同的位置表示不同的数值。可使用数字符号的个数称为基置表示不同的数值。可使用数字

18、符号的个数称为基数，基数为数，基数为n n，即可称，即可称n n进位制，简称进位制，简称n n进制。进制。“满几进一”就是几进制，几进制的基数就是几.基数：基数：二进制、七进制、八进制、十二进制、六十进制等二进制只有0和1两个数字，七进制用06七个数字十六进制有09十个数字及ABCDEF六个字母. 式中式中1 1处在百位，第一个处在百位，第一个3 3所在十位，第二个所在十位，第二个3 3所在所在个位，个位，5 5和和9 9分别处在十分位和百分位。十进制数是逢分别处在十分位和百分位。十进制数是逢十进一的。十进一的。 我们最常用最熟悉的就是十进制数，它的数值部分是十个不我们最常用最熟悉的就是十进制

19、数，它的数值部分是十个不同的数字符号同的数字符号0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8，9 9来表示的。来表示的。十进制：十进制：例如例如133.59133.59，它可用一个多项式来表示：，它可用一个多项式来表示：133.59=1133.59=1* *10102 2+3+3* *10101 1+3+3* *10100 0 +5+5* *1010-1-1+9+9* *1010-2-2 为了区分不同的进位制，常在数的右下角标明基数，为了区分不同的进位制，常在数的右下角标明基数，十进制一般不标注基数十进制一般不标注基数. .例如十进制的例如十进制的133.59133.

20、59，写成，写成133.59133.59(10)(10)七进制的七进制的1313，写成，写成1313(7)(7)；二进制的；二进制的1010，写成，写成1010(2) (2) 一般地，若一般地，若k是一个大于是一个大于1的整数，那么以的整数，那么以k为基数的为基数的k进制可以表示为一串数字连写在一起进制可以表示为一串数字连写在一起的形式：的形式：11 0( )110(0,0, , ,).n nknnaaaaakaa ak二进制与十进制的转换二进制与十进制的转换1 1、二进制数转化为十进制数、二进制数转化为十进制数例例1 1：将二进制数：将二进制数110011110011(2)(2)化成十进制数

21、。化成十进制数。解：解：根据进位制的定义可知根据进位制的定义可知012345)2(21212020212111001112116132151所以，所以，110011110011（2 2）=51=51110( )110110(10)nnknnnna aa aakakakak把其他进位制的数化为十进制数的公式是什么？把其他进位制的数化为十进制数的公式是什么？方法：除方法：除2取余法，即用取余法，即用2连续去除连续去除89或所得的商，然后取余数。或所得的商，然后取余数。例、例、 把把89化为二进制数化为二进制数解：解：根据根据“逢二进一逢二进一”的原则，有的原则，有892441 2 (2220)+1

22、 2( 2( 2110)+0)+1 2 (2 (2 (2 51)+0)+0)+15 2 212（2（2（2（221）1）0）0）189126025124123022021120所以：所以：89=1011001（2）2（2（2（2321）0）0）12（2（242220）0）12（2523+2200）12624+23002089244144 222022 211011 2 51 2 (2 (2 (2 (2 21)+1)+0)+0)+1所以所以892（2（2（2（2 2 1）1）0）0）1十进制转换为二进制十进制转换为二进制注意：注意：1. 1.最后一步商为最后一步商为0 0，2.2.将上式各步所得

23、的余数将上式各步所得的余数从下到上排列从下到上排列，得到：，得到： 89=101100189=1011001（2 2）另解（另解（除除2 2取余法的另一直观写法取余法的另一直观写法）：）：5 52 22 22 21 12 20 01 10 0余数余数11112222444489892 22 22 22 20 01 11 10 01 1练习练习将下面的十进制数化为二进制数？将下面的十进制数化为二进制数？（1 1）1010（2 2）2020例：把例：把8989化为五进制数。化为五进制数。解：解：根据根据除除k k取余法取余法以以5 5作为除数，相应的除法算式为：作为除数，相应的除法算式为：所以，所

24、以，89=32489=324（5 5）89895 517175 53 35 50 04 42 23 3余数余数除除k取余法取余法：十进制数转化为k进制数的方法 用用k连续去除该十进制数或所得的商，直连续去除该十进制数或所得的商，直到商为零为止，然后把每次所得的余数倒着到商为零为止，然后把每次所得的余数倒着排成一个数，就是相应的排成一个数，就是相应的k进制数。进制数。考题剖析考题剖析 点评点评本小题考查程序框图中的循环结构，主本小题考查程序框图中的循环结构，主要是根据框图，找到规律。要是根据框图，找到规律。解：解：由程序知由程序知s=21+22+250 =2550故选（故选（C） 1 502502 例、（例、（2