人教版高中数学必修三专题讲义基本算法语句及算法案例

进位制学习目标1.了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换。

2.学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k去余法，并理解其中的数学规律。

学习重难点重点：各进位制表示数的方法及各进位制之间的转换难点：除k去余法的理解以及各进位制之间转换的程序框图的设计学法与学习用具学法：在学习各种进位制特点的同时探讨进位制表示数与十进制表示数的区别与联系，熟悉各种进位制表示数的方法，从而理解十进制转换为各种进位制的除k去余法。

学习用具：电脑，计算器，图形计算器学习设想（一）创设情景，揭示课题我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进制.那么什么是进位制?不同的进位制之间又又什么联系呢?（二）研探新知进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。

可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。

现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数。

对于任何一个数，我们可以用不同的进位制来表示。

比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的。

表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.电子计算机一般都使用二进制,下面我们来进行二进制与十进制之间的转化例1 把二进制数110011(2)化为十进制数.解:110011=1*25+1*24+0*23+1*24+0*22+1*21+1*20=32+16+2+1=51例2 把89化为二进制数.解:根据二进制数满二进一的原则,可以用2连续去除89或所得商,然后去余数. 具体的计算方法如下:89=2*44+144=2*22+022=2*11+011=2*5+15=2*2+1所以:89=2*(2*(2*(2*(2*2+1)+1)+0)+0)+1=1*26+0*25+1*24+1*23+0*22+0*21+1*20=1011001(2)这种算法叫做除2取余法,还可以用下面的除法算式表示:把上式中的各步所得的余数从下到上排列即可得到89=1011001(2) 89 44 22 11 5 21222222 2 0 余数 1 0 0 1 1 01。

基本算法语句与算法案例主讲教师：熊丹 北京五中数学教师开篇语算法是实践性很强的内容，只有通过自身的实践解决几个算法设计问题，才能体会到算法思想，学会一些基本逻辑结构和语句．因此尽可能地通过实例体会和理解算法的含义，通过模仿、操作、探索，经历通过设计程序框图表达解决问题的过程，了解算法语言的基本构成，理解几种基本算法语句．但并非必须使用信息技术才能学习算法，在数学中的算法更注重设计算法的过程，体验算法的思想，培养有条理地思考表达能力，提高逻辑思维能力．本节课我们来复习几种基本的算法语句——赋值语句、输入和输出语句、条件语句、循环语句，在此基础上再了解几个算法案例，进一步体会算法的思想．重难点易错点解析题一：运行下面程序，输出结果为( )．a ＝3b ＝5a ＝a ＋bb ＝a \bPRINT a ，bA ．3，5B ．8，53C ．8，1D ．8，85题二：运行下列程序，当输入数值－2时，输出结果是( )．A．7 B．-3 C．0D．-16题三：下边程序运行后输出的结果分别是___________，____________．金题精讲题一：已知函数f(x)＝x2－1，g(x)＝2x＋3，下面程序是求f(g(0))＋g(f(0))的值的算法语句：x＝0g＝2* x +3f =①y1＝ff＝x*x－1g＝____②____y2＝gy＝y1＋y2PRINT yEND则①、②处应填入的表达式为()．A．①x*x-1 ②2*x+3 B．①g*g-1 ②2*f +3 C．①2*g+3 ②f*f-1 D．①f*f-1 ②2*g+3题二：若运行如下程序，最后输出y的值为－20，那么输入的t值为()．A．10或-6 B．10或-2C．-6 D．10或-2或-6题三：有如下两个程序()．A．两个程序输出结果相同B．程序(1)输出的结果比程序(2)输出的结果大C．程序(2)输出的结果比程序(1)输出的结果大D．两个程序输出结果的大小不能确定，谁大谁小都有可能题四：分析下面程序的算法功能，画出其算法的程序框图．题五：下列程序运行后的输出结果为()．INPUT“输入正整数a，b＝”；a，bm＝a*bWHILE a<>bIF a>b THENa＝a－bELSE b＝b－aEND IFWENDPRINT m＝m/aEND运行时，从键盘输入48,36．A．36 B．12 C．144 D．48题六：用秦九韶算法求多项式f(x)＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6的值，当x＝－4时，f (x)＝_____．基本算法语句与算法案例讲义参考答案重难点易错点解析题一：C 题二：D 题三：0；0金题精讲题一：B 题二：A 题三：B题四：题五：C题六：3392。

1.2基本算法语句1.2.1输入、输出语句和赋值语句1.输入语句在该程序中的第1行中的INPUT语句就是输入语句.这个语句的一般格式是：其中，“提示内容”一般是提示用户输入什么样的信息.如每次运行上述程序时，依次输入-5，-4，-3，-2，-1，0，1，2，3，4，5，计算机每次都把新输入的值赋给变量“x”,并按“x”新获得的值执行下面的语句.2.输出语句在该程序中，第3行和第4行中的PRINT语句是输出语句.它的一般格式是：3.赋值语句用来表明赋给某一个变量一个具体的确定值的语句.除了输入语句，在该程序中第2行的赋值语句也可以给变量提供初值.它的一般格式是：4.INPUT语句不但可以给单个变量赋值，还可以给多个变量赋值，其格式为：5.（1）赋值语句中的“=”叫做赋值号.（2）赋值语句的作用：先计算出赋值号右边表达式的值，然后把这个值赋给赋值号左边的变量，使该变量的值等于表达式的值.（3）赋值号左边只能是变量名字，而不能是表达式.如：2=X是错误的.（4）赋值号左右不能对换.如“A=B”“B=A”的含义运行结果是不同的.（5）不能利用赋值语句进行代数式的演算.（如化简、因式分解、解方程等）（6）赋值号“=”与数学中的等号意义不同.1.3算法案例1.利用辗转相除法求最大公约数的步骤如下：（1）用较大的数m 除以较小的数n 得到一个商0S 和一个余数0R ；（2）：若0R ＝0，则n 为m ，n 的最大公约数；若0R ≠0，则用除数n 除以余数0R 得到一个商1S 和一个余数1R ；（3）：若1R ＝0，则1R 为m ，n 的最大公约数；若1R ≠0，则用除数0R 除以余数1R 得到一个商2S 和一个余数2R ；……依次计算直至n R ＝0，此时所得到的1n R 即为所求的最大公约数.2.直接插入排序的基本思想：插入排序的思想就是读一个，排一个.将第１个数放入数组的第１个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置．将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中．（由于算法简单，可以举例说明）3.冒泡排序的基本思想：依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数......直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数...... 由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.4.进位制是一种记数方式用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为n ，即可称n 进位制，简称n 进制.现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数.对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的.5.辗转相除法与更相减损术的区别：（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到6. 一般地，若k 是一个大于一的整数，那么以k 为基数的k 进制可以表示为： 110()110...(0,0,...,,)n n k n n a a a a a k a a a k --<<≤<，而表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.。

知识1．求两个正整数的最大公约数的算法 （1）辗转相除法①定义：辗转相除法是用于求_____________的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，则这时较小的数就是原来两个数的最大公约数． ②算法步骤用辗转相除法求两个正整数的最大公约数，其算法步骤如下： 第一步，给定两个正整数,m n ． 第二步，计算m 除以n 所得的余数r ． 第三步，,m n n r ==．第四步，若0r =，则,m n 的最大公约数等于m ；否则，返回第二步． ③程序框图如图所示：④程序如下：INPUT m ，n DOr=m MOD n m=n n=rPRINT m END或INPUT m ，nr=1 While r>0 r=m MOD n m=n n=rPRINT m END（2）更相减损术①定义：中国古代的数学专著《九章算术》中记载着“更相减损术”，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也．以等数约之．” ②算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步． 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． ③程序框图④程序如下：INPUT “a ，b=”;a ，b WHILE a≠b r=a-bIF b>r THEN a=b b=r ELSE a=r END IF WEND PRINT b END2．秦九韶算法（1）定义及原理：把一个n 次多项式1110()n n n n f a x a x x a x a --=++⋅⋅⋅++改写成如下形式：2110()((()))n n n f a x a x x a x a x a --=⋅⋅⋅+++⋅⋅+⋅+．求多项式的值时，首先计算最内层括号内一次多项式的值，即11n n v a x a -=+，然后由内向外逐层计算一次多项式的值，即212323,n n v v x a v v x a --=+=+，…，10n n v v x a -=+，这种求n 次多项式()f x 的值的方法叫做秦九韶算法．（2）秦九韶算法程序化的可行性探讨：观察秦九韶算法中的n 个一次式，可见计算k v 时要用到1k v -的值，若令0n v a =，我们可以得到下面的递推公式：0____________(1,2,,)n k v a v k n =⎧⎨==⋅⋅⋅⎩．这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现． （3）算法步骤第一步，输入多项式次数n 、最高次项的系数n a 和x 的值． 第二步，将v 的值初始化为n a ，将i 的值初始化为n －1． 第三步，输入i 次项的系数i a ． 第四步，,1i v vx a i i =+=-．第五步，判断i是否大于或等于0．若是，则返回第三步；否则，输出多项式的值v．（4）程序框图如图所示：（5）程序如下：INPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE i>=0PRINT “i=”；iINPUT “ai=”；av=v*x+ai=i-1WENDPRINT vEND3．进位制（1）定义：进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满六十进一，就是六十进制；等等．也就是说，“满几进一”就是几进制，几进制的基数就是几．一般地，若k 是一个大于1的整数，那么以k 为基数的k 进制数可以表示为一串数字连写在一起的形式：1210()110110(,,,,,0<,0,,,)n n n k n n n n a a a a a a a a a a k a a a k ----⋅⋅⋅⋅⋅⋅∈<≤⋅⋅⋅<N ．说明：①若一个数为十进制数，其基数可以省略不写．②若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数． （2）将k 进制数转化为十进制数 ①算法步骤：计算k 进制数a 的右数第i 位数字i a 与1i k -的乘积1i i a k -⋅，再将其累加，这是一个重复操作的步骤．所以，可以用循环结构来构造算法，算法步骤如下： 第一步，输入,a k 和n 的值．第二步，将b 的值初始化为0，i 的值初始化为1． 第三步，1,1i i b b a k i i -=+⋅=+．第四步，判断i n >是否成立．若是，则执行第五步；否则，返回第三步． 第五步，输出b 的值． ②程序框图如图所示：③程序如下：INPUT “a ，k ，n=”；a ，k ，n b=0 i=1 t=a MOD 10 DOb=b+t*k^(i-1) a=a\10 t=a MOD 10 i=i+1LOOP UNTIL i>n PRINT b END（3）将十进制数转化为k 进制数 ①转化方法：十进制数化为k 进制数用____________，即先把十进制数a 除以k ，商为0q ，余数为0r ，再把0q 除以k ，商为1q ，余数为1r ，…，反复进行这种除法，直到商1n q -除以k 所得的商为0，余数是n r ，即1n n q r -=为止，此时将所有余数按从右到左排列就得到所要求的k 进制数10()n n k r r r -⋅⋅⋅． ②算法步骤：第一步，给定十进制正整数a 和转化后的数的基数k ． 第二步，求出a 除以k 所得的商q ，余数r ． 第三步，把得到的余数依次从右到左排列．第四步，若0q ≠，则a q =，返回第二步；否则，输出全部余数r 排列得到的k 进制数． ③程序框图如图所示：④程序如下：INPUT “a ，k=”；a ，k b=0 i=0 DO q=a\k r=a MOD k b=b+r*10^i i=i+1 a=qLOOP UNTIL q=0 PRINT b END知识参考答案： 1．（1）两个正整数2．（2）1k n k v x a --+3．（3）①除k 取余法重点重点辗转相除法、更相减损术、秦九韶算法、进位制难点用秦九韶算法求多项式的值，进位制间的转换易错易对秦九韶算法中的运算次数理解错误1．辗转相除法与更相减损术辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别．两者的区别是：（1）辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递推过程．（2）辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可．而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数．注意：用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2，这时莫忘记求得的相等两数乘以约简的数才是所求的最大公约数．【例1】用辗转相除法和更相减损术求840与1764的最大公约数．【答案】840与1764的最大公约数是84．【解析】辗转相除法：1764=840×2+84，840=84×10+0，∴840与1764的最大公约数是84．更相减损术：1764–840=924，924–840=84，840–84=756，756–84=672，672–84=588，588–84=504， 504–84=420， 420–84=336， 336–84=252， 252–84=168， 168–84=84，∴840与1764的最大公约数是84．【例2】利用辗转相除法求3869与6497的最大公约数． 【答案】3869与6497的最大公约数为73．【名师点睛】辗转相除法计算次数少，而更相减损术计算次数多，但是更相减损术每一步的计算都是减法，比做除法运算要简单一些，所以一般当数较小时考虑用更相减损术，当数较大时考虑用辗转相除法． 2．秦九韶算法秦九韶算法的实质是：求多项式1110()n n n n f a x a x x a x a --=++⋅⋅⋅++的值时，转化为求n 个一次多项式的值，共进行n 次乘法运算和n 次加法运算．这种算法的运算次数较少，是多项式求值比较先进的算法． 【例3】 用秦九韶算法计算多项式f （x ）=12+35x –8x 2+79x 3+6x 4+5x 5+3x 6在x =–4时的值时，V 3的值为A ．–845B ．220C ．–57D ．34【答案】C【解析】∵多项式f （x ）=12+35x –8x 2+79x 3+6x 4+5x 5+3x 6=（（（（（3x +5）x +6）x +79）x –8）x +35）x +12， 当x =–4时，∴v 0=3，v 1=3×（–4）+5=–7，v 2=–7×（–4）+6=34，v 3=34×（–4）+79=–57．故选C ．【例4】用秦九韶算法计算函数f （x ）=2x 4+3x 3+5x –4在x =2时的函数值．【答案】62【名师点睛】利用秦九韶算法计算多项式的值的策略：（1）正确地将多项式改写，若在多项式中有几项不存在，可将这些项的系数看成0，即把这些项看做0n x ⨯． （2）由内向外逐次计算．（3）每一步计算结果准确，由于下一次计算用到上一次计算的结果，应认真、细致地计算每一步． 3．进位制把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k 取余法，把十进制数转化为k 进制数． 【例5】将八进制数127（8）化为十进制数． 【答案】87【解析】()21081271828786416787=⨯+⨯+⨯=++=．【例6】已知一个k 进制的数123（k ）与十进制的数38相等，求k 的值． 【答案】5【解析】将转化为十进制，()210212312323k k k k k k =⨯+⨯+⨯=++， 由题意，得k 2+2k +3=38， 所以k 2+2k –35=0， 所以k =5或k =–7（舍） 所以k =5．【名师点睛】除k 取余法的两个关注点：①要连续除：用k 连续去除十进制数或所得的商，直到商为零为止． ②若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数．基础训练1．秦九韶算法的先进性主要体现在减少运算次数，下列说法正确的是A ．可以减少加法运算次数B ．可以减少乘法运算次数C ．同时减少加法和乘法的运算次数D ．加法次数和乘法次数都有可能减少2．用秦九韶算法求多项式652()7632f x x x x =+++，当4x =时的值，先算的是A ．4×4=16B ．7×4=28C ．4×4×4=64D ．7×4+6=343．把十进制的23化成二进制数是A ．00 110（2）B ．10 111（2）C ．10 1111（2）D ．11 101（2）4．若十进制数26等于k 进制数32，则k 等于A ．4B ．5C ．6D ．85．用更相减损术求294和84的最大公约数时，需要做减法的次数是A ．3B ．4C ．5D ．66．1 037和425的最大公约数是A ．51B ．17C ．9D ．37．已知多项式54321()4322f x x x x x x =++---，用秦九韶算法求(2)f -等于 A ．1972-B ．1972C ．1832D ．1832-8．用更相减损术求156与91的最大公约数时，需要做减法的次数是__________． 9．将45（6）改写成十进制数为__________．10．用秦九韶算法计算多项式5432()54321f x x x x x x =+++++当4x =时的值时，乘法运算的次数为__________．11．用更相减损术求288与153的最大公约数．12．用秦九韶算法求多项式5432()3532f x x x x x x =-+-+当2x =时的值．能力提升13．在下列四个数中，最小的数是A ．(9)85B ．(6)210C ．(4)1000D ．(2)11111114．用秦九韶算法计算多项式65432()256238103f x x x x x x x =+++-+-当4x =-时的值时，3v 的值为A ．742-B ．49-C ．18D ．18815．若98与63的最大公约数为a ，二进制数(2)110011化为十进制数为b ，则a b +=A ．53B ．54C ．58D ．6016．用更相减损术求123和48的最大公约数是A ．3B ．7C ．9D ．1217．计算机是将信息转换成二进制处理，二进制即“逢二进一”，如(2)1101表示二进制数．将它转化成十进制形式是32101212021213⨯+⨯+⨯+⨯=，那么将二进制数1611111个（2）转换成十进制形式是A ．217-2B ．216-2C ．216-1D ．215-118．在下列各数中，最大的数是A ．(9)85B ．(6)210C ．(4)1000D ．(2)1111119．完成进位制之间的转化：(5)413=__________(7)． 20．（1）把八进制数()87341化为十进制数；（2）把1285化为16进制数．21．先将412（5）化成十进制的数，然后用“除k取余法”再化成七进制的数．22．用辗转相除法和更相减损术求261与319的最大公约数．参考答案1 2 3 4 5 6 7 13 14 15 16 17 18B D B D B B A D BC A C B 1．【答案】B【解析】通过对秦九韶算法的理解，可知它的主要作用是减少乘法的次数，将原来的乘法次数由(1)2n n减少到n，而对加法没有影响．故选B．2．【答案】D3．【答案】B【解析】23÷2=11…1，11÷2=5…1，5÷2=2…1，2÷2=1…0，1÷2=0…1，故23（10）=10111（2）．故选B．4．【答案】D【解析】由题意知，10 2632k k =⨯+⨯，解得8k =．故选D ． 5．【答案】B【解析】()()()()()294,84210,84126,8484,4242,42→→→→． 6．【答案】B【解析】∵1 037＝425×2＋187，425＝187×2＋51，187＝51×3＋34，51＝34×1＋17，34＝17×2，即1 037和425的最大公约数是17． 7．【答案】A【解析】∵1()((((43)2)1)1)2f x x x x x x =++---，∴197(2)2f -=-．8．【答案】5【解析】求最大公约数的过程如下：1569165-=，916526-=，652639-=，392613-=，261313-=．故13是最大公约数，共进行了5次减法运算． 9．【答案】29（10）【解析】由于45（6）=4×61+5×60=29（10）．故答案为：29（10）． 10．【答案】5【解析】5432((((54)3)2)1()54321)1f x x x x x x x x x x x =++++++++++=，不难发现要经过5次乘法，5次加法运算． 11．【答案】详见解析．【解析】288－153＝135，153－135＝18，135－18＝117，117－18＝99，99－18＝81，81－18＝63，63－18＝45，45－18＝27，27－18＝9，18－9＝9． 因此288与153的最大公约数为9． 12．【答案】详见解析．13．【答案】D【解析】因为(9)8589577=⨯+=，2(6)210261678=⨯+⨯=，3(4)10001464=⨯=，543210(2)11111122222263=+++++=，所以最小的数是(2)111111．故选D ．14．【答案】B【解析】65432()256238103f x x x x x x x =+++-+- (((((25)6)23)8)10)3x x x x x x =+++-+-，则010212,52(4)53,63(4)618v v v x v v x ==+=⨯-+=-=+=-⨯-+=，322318(4)v v x =+=⨯-2349+=-，故选B ． 15．【答案】C【解析】∵9816335=⨯+，6313528=⨯+，351287=⨯+，2874=⨯，∴98和63的最大公约数是7，即7a =．二进制数(2)110011化为十进制数为54321012120202121251⨯+⨯+⨯+⨯+⨯+⨯=，即51b =，则58a b +=．故选C ． 16．【答案】A【解析】123-48=75，75-48=27，48-27=21，27-21=6，21-6=15，15-6=9，9-6=3，6-3=3，所以123和48的最大公约数是3． 17．【答案】C【解析】161111个（2）1514016=12+12++12=21⨯⨯⨯-．18．【答案】B19．【答案】213【解析】∵012(5)41335154535425108=⨯+⨯+⨯=++⨯=，012108371727=⨯+⨯+⨯，∴(7)(5)421313=．20．【答案】（1）3809；（2）()16505．【解析】（1）()87341=3210783848183809⨯+⨯+⨯+⨯=；（2）用16连续去除1285，直到商为0为止，所得到的余数依次从右向左排列，就得到()161285505=． 21．【答案】详见解析．【解析】412（5）=2×50+1×51+4×52=2+5+4×25=107， ∵107=7×15+2， 15=7×2+1， 2=7×0+2．∴把5进制的数412（5）化为7进制是212（7）． 22．【答案】详见解析．【解析】辗转相除法： 319＝261×1＋58， 261＝58×4＋29， 58=29×2，所以261与319的最大公约数为29．。