高二数学下学期讲解

《高二数学下学期讲解》由会员分享，可在线阅读，更多相关《高二数学下学期讲解（69页珍藏版）》请在金锄头文库上搜索。

1、1.3 算法案例 1.3.4 十进制化K进制 1.3.1 辗转相除法和更相减损术 1.3.2 秦九韶算法 1.3.3 K进制化十进制 1.3 算法案例 1.3.1 辗转相除法 和更相减损术 复习 1.研究一个实际问题的算法，主要从哪几方面展开？ 2.在程序框图中算法的基本逻辑结构有哪几种？ 3.在程序设计中基本的算法语句有哪几种？ 算法步骤、程序框图和编写程序三方面展开. 顺序结构、条件结构、循环结构 输入语句、输出语句、赋值语句、条件语句、循环语句 情境创设 韩信是秦末汉初的著名军事家.据说有一次汉高祖 刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什 么方法,不要逐个报数,就能知道场上的士兵的

2、人数 ,韩信先令士兵排成3列纵队,结果有2人多余,接着 下令排成5列纵队,结果又多出3人,随后他又下令 改为7列纵队,这次又剩下2人无法成整行.在场的 人都哈哈大笑,以为韩信不能清点出准确的人数,不 料笑声刚落,韩信高声报告共有士兵2333人.众人 听了一楞,不知道韩信用什么方法这么快就能得到 正确的结果的.今天,我们将以这些古典案例的思想 ,设计出适宜计算机的运行程序,提高我们对基本算 法结构和算法语句在实际中的运用能力. 探究一,辗转相除法 思考1:在小学中我们是如何求出两个正整数 的最大公约数的呢? 算法案例之求最大公约数 求以下几组正整数的最大公约数。 (注：若整数m和n满足n整除m，

3、则（m,n）=n。用（m,n）来表示 m和n的最大公约数。) （1）（18，30） （2）（24，16） （3）（63，63） （4）（72，8） （5）（301，133 ） 解：2 1 8 2 4 用公有质因数2除， 3 9 1 2 用公有质因数3除， 3 4 3和4互质不除了。 得：18和24最大公约数是：236 例、求18与24的最大公约数： 6； 8； 63； 8； 7； 短除法 想一想，如何求8251与6105的最大公约数？ 思考2:对于8251与6105这两个数，它们的最大公 约数是多少？你是怎样得到的？ 由于它们公有的质因数较大，利用上述方法求最 大公约数就比较困难.有没有其它的

4、方法可以较简单 的找出它们的最大公约数呢？ 思考3：注意到8251=61051+2146，那么8251与 6105这两个数的公约数和6105与2146的公约数有什么 关系？ 我们发现6105=21462+1813，同理，6105与 2146的公约数和2146与1813的公约数相等. 思考4：重复上述操作，你能得到8251与6105这 两个数的最大公约数吗？ 2146=18131+333，148=374+0. 333=1482+37， 1813=3335+148， 8251=61051+2146， 6105=21462+1813， 定义:所谓的辗转相除法,就是对于给定的两个数, 用较大的数除以较

5、小的数,若余数不为零,则将余数 和较小的数构成新的数对,继续上面的除法, 直到大数 被小数除尽,则这是较小的数就是原来两个数的最大公约数 辗转相除法求两个数的最大公约数，其算法可以描述如下： 辗转相除法是一个反复执行直到余数等于0停止的步骤， 这实际上是一个循环结构 思考4：辗转相除直到何时结束？ 主要运用的是哪种算法结构？ 如此循环，直到得到结果。 输入两个正整数m和n； 求余数r：计算m除以n，将所得余数存放到变量r中； 更新被除数和余数：m=n，n=r。 判断余数r是否为0：若余数为0则输出结果，否则转 向第步继续循环执行。 第一步，给定两个正整数m，n(mn). 第二步，计算m除以n所

6、得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等于m； 否则，返回第二步. 思考5:你能把辗转相除法编成一个计算机程序吗？ 程序框图 开始 输入m，n 求m除以n的余数r m=n n=r r=0？ 是 输出m 结束 否 INPUT m，n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 思考6:如果用当型循环结构构造算法，则用辗 转相除法求两个正整数m、n的最大公约数的程序框 图和程序分别如何表示？ 开始 输入m，n 求m除以n的余数r m=n r0 ？否 输出m 结束 是 n=r INPUT m，n WHILE

7、r0 r=m MOD n m=n n=r WEND PRINT m END 练习：用辗转相除法求下列两数的最大公约数： （1）（225，135） （2）（98，196） （3）（72，168） （4）（153，119） 4598 2417 二、更相减损术 九章算术是中国古代的数学专著，其中的 “更相减损术”也可以用来求两个数的最大公约数， 即“可半者半之，不可半者，副置分母、子之数， 以少减多，更相减损，求其等也.以等数约之.” 意思是： 第一步：任意给定两个正整数，判断它们是否 都是偶数. 若是，用2约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把差 与较小的数比较，并以大

8、数减小数.继续这个操作， 直到所得的数相等为止，则这个等数或这个数与约 简的数的乘积就是所求的最大公约数. 例1：用更相减损术求98与63的最大公约数. 98-63=35， 14-7=7. 21-7=14， 28-7=21， 35-28=7， 63-35=28， 因为63不是偶数，所以 所以最大公约数是7. 例2 分别用辗转相除法和更相减损术求168与93 的最大公约数. 168=931+75， 93=751+18， 75=184+3， 18=36. 辗转相除法： 更相减损术: 168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3

9、， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3. 例3 用更相减损术求80与36的最大公 约数. 例4 求325，130，270三个数的最大公约数. 因为325=1302+65，130=652，所以325与130 的最大公约数是65. 因为270=654+10，65=106+5，10=52，所 以65与270最大公约数是5. 故325，130，270三个数的最大公约数是5. 练习:用更相减损术求两个正整数m，n的最大公 约数，可以用什么逻辑结构来构造算法？其算法步骤 如何设计？ 第一步，给定两个正整数m，n(mn). 第二步，计算m-n所得的差k. 第三步，比

10、较n与k的大小，其中大者用m表示 ，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于m； 否则，返回第二步. 讨论:该算法的程序框图如何表示？ 开始 输入m，n nk？ m=n 是 输出m 结束 mn？ k=m-n 是 否 n=k m=k 否 讨论:该程 序框图对应的程 序如何表述？ INPUT m，n WHILE mn k=m-n IF nk THEN m=n n=k ELSE m=k END IF WEND PRINT m END 开始 输入m，n nk？ m=n 是 输出m 结束 mn？ k=m-n 是 否 n=k m=k 否 1、辗转相除法. 小结 2、更相减损术. 布置作业

11、： P45练习：1. P48习题1.3A组：1. 1.3.2 秦九韶算法 1、什么是辗转相除法和更相减损术？ 2、辗转相除法和更相减损术，是求两个正整 数的最大公约数的优秀算法，我们将算法转化为程 序后，就可以由计算机来执行运算，实现了古代数 学与现代信息技术的完美结合. 复习 探究三、秦九昭算法 思考1,在初中,我们是如何求一个多项式的 值的? 思考2,已知一个n 次多项式 f(x)=anxn+an-1xn-1+a1x+a0当x=x0时，除 了用代入法求解外是否还有更好的方法呢 ？ 秦九韶算法的基本思想 思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求 f(5)的值. 4+3+

12、2+1=10次乘法运算，5次加法运算. 分析：把5代入多项式，若先计算各项的值， 然后再相加，那么一共要做： 思考2:另一种做法是先计算x2的值，然后依 次计算x2x，(x2x)x，(x2x)x)x的 值，这样每次都可以利用上一次计算的结果，这 时一共做了： 4次乘法运算，5次加法运算. 思考3:有没有更有效的算法呢？利用后一种算 法求多项式f(x)=anxn+an-1xn-1+a1x+a0的值，这 个多项式应写成哪种形式？ f(x)=anxn+an-1xn-1+a1x+a0 =(anxn-1+an-1xn-2+a2x+a1)x+a0 =(anxn-2+an-1xn-3+a2)x+a1)x+a

13、0 = =(anx+an-1)x+an-2)x+a1)x+a0. 这就是我国南宋时期数学家秦九韶在他的著作 数书九章中提出的算法. 思考4:对于f(x)=(anx+an-1)x+ an-2)x+a1)x+a0， 由内向外逐层计算一次多项式的值，其算法步骤如何？ 第一步，计算v1=anx+an-1. 第二步，计算v2=v1x+an-2. 第三步，计算v3=v2x+an-3. 第n步，计算vn=vn-1x+a0. 上述方法称为秦九韶算法. 思考5:在秦九韶算法中，记v0=an，那么第k步的 算式是什么？ vk=vk-1x+an-k (k=1，2，n) 解：f(x)=(4x+2)x+3.5)x-2.

14、6)x+1.7)x-0.8. v1=45+2=22； v2=225+3.5=113.5； v3=113.55-2.6=564.9； v4=564.95+1.7=2826.2； v5=2826.25-0.8=14130.2. 所以f(5)= =14130.2. 例1 已知一个5次多项式为 用秦九韶算法求f(5)的值. 练习：阅读下列程序，说明它解决的实际问题是什么？ INPUT “x=”；a n=0 y=0 WHLE n=0 INPUT “ai=”；a v=v*x+a i=i-1 WEND PRINT v END PRINT “i=”；i 小结 2.计算机的一个很重要的特点就是运算速度快 ，但评

15、价算法好坏的一个重要标志是运算的次数， 如果一个算法从理论上需要超出计算机允许范围内 的运算次数，那么这样的算法就只能是一个理论算 法.在多项式求值的各种算法中，秦九韶算法是一 个优秀算法. 1.秦九韶算法计算多项式的值及程序设计. 布置作业： P45练习：2. P48习题1.3A组：2. 1.3.3 K进制化十进制 1.简述辗转相除法和更相减损术的用途及内容. 2、秦九韶算法的用途及内容. 将这些算法转化为程序，就可以由计算机来完 成相关运算. 复习 进位制的概念 进位制是为了计数和运算方便而约定的记数系统 . 约定满二进一，就是二进制； 满十进一，就是十进制； 七天为一周，就是七进制； 十

16、二个月为一年，就是十二进制； 六十秒为一分钟，六十分钟为一个小时，就是六 十进制；等等. 一般地，“满几进一”就是几进制. 思考1:十进制使用09十个数字，那么二进制、 五进制、七进制分别使用哪些数字？ 在十进制中10表示十，在二进制中10表示2.一 般地，若k是一个大于1的整数，则以k为基数的k进制 数可以表示为一串数字连写在一起的形式： anan-1a1a0(k). “满K进一”就是K进制，其中k称为k进制的基数. 那么k是一个什么范围内的数？ 与十进制类似，其它的进位制也可以按照位置原 则计数. 思考2：其中各个数位上的数字an，an-1，a1 ，a0的取值范围如何？ 例如:十进制数3721表示的数可以写成： 110011（2）=125+124+023+0