课件23张PPT。第一章 算法初步
1．3 算法案例
1．3.1 辗转相除法与更相减损术理解辗转相除法与更相减损术的含义和运算．基础梳理1．我们求最大公约数的方法就是辗转相除法，也叫欧几里得算法，它是由欧几里得在公元前300年左右首先提出的．利用辗转相除法求最大公约数的步骤如下：
第一步，用较大的数m除以较小的数n得到一个商q0和一个余数r0.
第二步，若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1.第三步，若r1＝0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2.
……
依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数．
例如：12与18的最大公约数为多少？
解析：18＝12×1＋6；12＝6×2；所以12与18的最大公约数6.2．更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之．
翻译成现代语言为：
第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
3．语句“r＝m MOD n”表示m除以n余数为r，则：“14 MOD 3”等于________．
2自测自评1．下列各组关于最大公约数的说法中不正确的是( )
A．16和12的最大公约数是4
B．78和36的最大公约数是6
C．85和340的最大公约数是17
D．105和315的最大公约数是105
2．在对16和12求最大公约数时，整个操作如下：(16,12)→(4,12)→(4,8)→(4,4)，由此可以看出12和16的最大公约数是( )
A．4 B．12 C．16 D．8CA3．今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何( )
A．2 323 B．23 C．46 D．69
4．284和1 024的最小公倍数是( )
A．1 024 B．142 C．72 704 D．568BC题型一 辗转相除法求最大公约数例1 用辗转相除法求820与500的最大公约数．解析：820＝500×1＋320；500＝320×1＋180；320＝180×1＋140；180＝140×1＋40；140＝40×3＋20；40＝20×2；所以820与500的最大公约数为20.
点评：辗转相除法是求两个数的最大公约数的方法，如果求三个或更多个数的最大公约数，可以先求两个数的最大公约数，把求得的最大公约数与第三个数再求最大公约数，这样依次下去，直到最后一个数为止，最后所得的一个最大公约数，就是所求这几个数的最大公约数．跟 踪训 练1．用辗转相除法求得459和357的最大公约数是( )
A．3 B．9 C．17 D．51D题型二 更相减损术求最大公约数例2 用更相减损术求98与63的最大公约数．解析：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：
98－63＝35
63－35＝28
35－28＝7
28－7＝21
21－7＝14
14－7＝7
所以，98与63的最大公约数是7.跟 踪训 练2．用更相减损术求225与135的最大公约数为( )
A．45 B．5 C．9 D．15A题型三 比较辗转相除法与更相减损术例3 用辗转相除法求下面两数的最大公约数，并用更相减损术检验你的结果：
(1)80,36； (2)294,84.分析：使用辗转相除法，我们可依据a＝nb＋r这个式子，反复执行，直到r＝0为止．用更相减损术就是根据r＝a－b这个式子，反复执行．
解析：(1)80＝36×2＋8，
36＝8×4＋4，
8＝4×2＋0，即80与36的最大公约数是4.
验证：80－36＝44，
44－36＝8,36－8＝28,28－8＝20，
20－8＝12,12－8＝4,8－4＝4.
∴80与36的最大公约数为4.
(2)294＝84×3＋42，
84＝42×2，
即294与84的最大公约数是42.
验证：∵294与84都是偶数可同时除以2，即取147与42的最大公约数后再乘2.
147－42＝105，
105－42＝63，
63－42＝21，
42－21＝21，
∴294与84的最大公约数为21×2＝42.
点评：由该题可以看出，辗转相除法求最大公约数步骤较少，而更相减损术运算简易，解题时要灵活运用．跟 踪训 练3．用更相减损术求98与64的最大公约数．解析：由于64是偶数，减半为32，把98和32以大数减小数，并辗转相减，即：98－32＝66；66－32＝34；34－32＝2；32－2＝30；30－2＝28；…；4－2＝2；
所以，98与64的最大公约数是2.题型四 辗转相除法的程序框图与程序例4 写出辗转相除法的程序框图及程序．解析：r＝m MOD n表示m除以n的余数为r，例如：3＝15 MOD 6.
程序框图： 程序：点评：借助程序框图准确理解程序的本质．跟 踪训 练4．下边程序运行后输出的结果为( )
A．50 B. 5 C. 25 D. 0D数学·必修3(人教A版)
1.3 算法案例
1．3.1 辗转相除法与更相减损术
1．用辗转相除法求得168与486的最大公约数( )
A．3 B．4 C．6 D．16
答案：C
2．阅读下面语句：
赋值语句表示的结果为________．
答案：p＝83
3．阅读下面语句：
输入－4，输出结果为________．
输入9，输出结果为________．
答案： negative 3
4．阅读下面语句：
语句计算结果为________．
答案：
5．下列所画程序框图是已知直角三角形两条直角边a，b，求斜边的算法，其中正确的是( )
答案：A
6．阅读下列语句，
语句计算结果为________．
答案：
7．用辗转相除法求得78和36的最大公约数是 ( )
A．3 B．6 C．9 D．12
答案：B
8．利用辗转相除法求3 869与6 497的最大公约数与最小公倍数．
解析：6 497＝3 869×1＋2 628，
3 869＝2 628×1＋1 241，
2 628＝1 241×2＋146，
1 241＝146×8＋73，
146＝73×2＋0，
所以3 869与6 497的最大公约数为73.
最小公倍数为3 869×6 497/73＝344 341.
9．用辗转相除法或者更相减损术求三个数324,243,135的最大公约数．
解析：324－243＝81,243－81＝162,162－81＝81；
135－81＝54,81－54＝27,54－27＝27.
故324,243,135最大公约数是27.
1．求最大公约数的方法要熟练使用，但一般不要求会编写相应的程序．
2．三个数的最大公约数求法一般是只求第一与第二个数的最大公约数，然后求这个最大公约数与第三个数的最大公约数．
课件24张PPT。第一章 算法初步
1．3 算法案例
1．3.2 秦九韶算法和进位制理解秦九韶算法与进位制的含义和运算．基础梳理1．秦九韶计算多项式的方法
f(x)＝anxn＋an－1xn－1＋an－2xn－2＋…＋a1x＋a0
＝(anxn－1＋an－1xn－2＋an－2xn－3＋…＋a1)x＋a0
＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0
＝…
＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0.
例如：已知一个3次多项式为f(x)＝x3－2x2＋x－1，用秦九韶算法求这个多项式当x＝2时的值．解析：f(x)＝x3－2x2＋x－1＝(((x－2)x＋1)x－1)＝1.2．进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值．可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制．现在最常用的是十进制，通常使用10个阿拉伯数字0～9进行记数．
对于任何一个数，我们可以用不同的进位制来表示．比如：十进数57，可以用二进制表示为111 001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的．表示各种进位制数一般在数字右下角加注来表示，如111001(2)表示二进制数，34(5)表示5进制数．
电子计算机一般都使用二进制，下面我们来进行二进制与十进制之间的转化．
例如：十进制3的二进制表示方法为________．
3．二进制数111(2)在十进制中表示哪个数？11(2)答案：7 4．十进制数是满十进一的原则，同理二进制数是满二进一的原则，要把十进制数9转化为二进制数，常常用如下方式：9＝1×23＋0×22＋0×21＋1×20，因此十进制数9的二进制表示法为1 001(2)．把十进制数20化为二进制数为( )
A．10 000 (2) B．10 100(2)
C．11 001(2) D．10 001(2)
5．二进制数10 0001(2)等于十进制数________．B33自测评价1．关于进位制说法错误的是( )
A．进位制是人们为了计数和运算方便而约定的记数系统
B．二进制就是满二进一，十进制就是满十进一
C．满几进一，就是几进制，几进制的基数就是几
D．为了区分不同的进位制，必须在数的右下角标明基数D2．在求高次代数方程根的完整算法时，秦九韶算法要比西方同样的算法( )
A．晚五六百年 B．早五六百年
C．早七八百年 D．晚七八百年
3．下列各数中最小的一个是( )
A．111 111(2) B．210(6)
C．1 000(4) D．81(8)B A4．用秦九韶算法计算多项式f(x)＝12＋35x－8x2＋6x4＋5x5＋3x6在x＝－4时的值时，V3的值为( )
A．－144 B．－136
C．－57 D．34B题型一 用秦九韶算法求函数值例1 用秦九韶算法求多项式f(x)＝2x6－3x5＋4x4－x3＋2x2＋x－3，当x＝2时的值．解析：f(x)＝((((((2x－3)x＋4)x－1)x＋2)x＋1)x－3)
因为V0＝2，V1＝1，V2＝6，V3＝11，V4＝24，V5＝49，V6＝95，
所以f(2)＝95.点评：当多项式函数中间出现空项时，利用秦九韶算法求函数值，要补上系数为0的相应项．当然当一个多项式函数空项很多时，用一般的计算方法可能更简单一些．如对于f(x)＝x6－2x2＋5，求，f(2)的值，就没有必要再利用秦九韶算法了，直接将x＝2代入计算即可．跟 踪训 练1．用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别为( )
A．6,6 B．5,6 C．5,5 D．6,5A题型二 秦九韶算法的程序框图与程序例2 设计利用秦九韶算法计算5次多项式f(x)＝a5x5＋a4x4＋a3x3＋a2x2＋a1x＋a0当x＝x0时的值的程序框图．解析：程序框图如下：点评：秦九韶算法的步骤：题型三 十进制数与二进制数的互化例3 把十进制数53化为二进制数为( )
A．101 101(2) B．110 101(2)
C．110 001(2) D．100 001(2)解析：方法一(除二取余法)
53＝2×26＋1，26＝2×13＋0,13＝2×6＋1,6＝2×3＋0,3＝2×1＋1，1＝2×0＋1；余数由后往前写得110 101.方法二
答案：B跟 踪训 练2．写出将k进制数a转换为十进制数(共有n位)：a＝anan－1…a3a2a1(k)＝ank(n－1)＋an－1k(n－2)＋…＋a3k2＋a2k1＋a1k0的算法步骤．解析：算法步骤：
第一步，输入a，k和n的值．
第二步，将b的值初始化为0，i的值初始化为1.
第三步，b＝b＋ai·ki－1，i＝i＋1.
第四步，判断i>n是否成立．若是，则执行第五步；否则返回第三步．
第五步，输出b的值．题型四 十进制数与其他进制数的互化例4 把十进制数53化为八进制数为_____________．答案：65(8)
点评：把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数．而在使用除k取余法时要注意三点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数．跟 踪训 练3．把十进制数53化为五进制数为________．解析：
答案：203(5)数学·必修3(人教A版)
1．3.2 秦九韶算法和进位制
1．将二进制数110(2)化为十进制结果为________．
答案：6
2．把十进制数20化为八进制数为________．
答案：24(8)
3．把八进制数20化为十进制数为________．
答案：16
4．已知一个3次多项式为f(x)＝x3－x2＋x－1，用秦九韶算法求这个多项式当x＝2时的值．
解析：f(x)＝x3－x2＋x－1＝(((x－1)x＋1)x－1)＝5.
5．用秦九韶算法计算多项式f(x)＝5x5＋4x4＋3x3＋2x2＋x＋1当x＝2时的值的过程中，要经过________次乘法运算和________次加法运算．
答案：5 5
6．11 211(4)化为六进制数结果为________．
答案：1 353(6)
7．二进制数111 101(2)等于十进制数________．
答案：61
8．把六进制数43(6)化为十进制数为________．
答案：27
9．已知175 (r)＝125(10)，求r的值．
解析：∵ 1×r2＋7×r1＋5×r0＝125，
∴r2＋7r－120＝0，
∴r＝8或r＝－15，
∴r＝8.
1．秦九韶算法的优点是能大量减少计算量，对相应的程序框图不作具体要求．
2．进位制是十分重要的知识点，要求掌握不同进位制的转换．
课件22张PPT。第一章 算法初步
1．3 算法案例
1．3.3 算法综合问题(习题课)1．熟悉算法的三种基本结构：顺序、条件和循环，以及基本的算法语句．
2．能熟练运用辗转相除法与更相减损术、秦九韶算法、进位制等典型的算法知识解决同类问题．
3．在复习旧知识的过程中把知识系统化，通过模仿、操作、探索，经历设计程序框图表达解决问题的过程．在具体问题的解决过程中进一步理解程序框图的三种基本逻辑结构：顺序结构、条件结构、循环结构．基础梳理1．教材为我们介绍了四个著名的算法案例，它们既是算法初步知识的应用，又是古代数学中算法思想的体现，我们应把重点放在通过四个案例的算法分析、程序框图或程序语言设计上，加深对算法思想的理解，至于它们所含算法的应用应以简单题型训练为主．
2．辗转相除法与更相减损术本质是相同的，常用来求两个或多个整数的公约数；秦九韶算法用以解决多项式求解问题；各种进位制的转化基本方法是“除k取余法”．3．除这几类问题之外，我国古代以及生活中还有许多有名的算法案例，如：割圆术、韩信点兵、孙子问题等，同学们若有兴趣，可搜集相关资料，了解其算法思想．自测自评1．在赋值语句中，“N＝N＋1”的说法正确的是( )
A．没有意义的 B．N与N＋1相等
C．将N的原值加1再赋给N，N的值增加1
D．无法运行
2．在算法当中，有时需要进行判断，判断的结果决定后面的步骤，像这样的结构称为( )
A．顺序结构 B．条件结构
C．循环结构 D．以上都不对C B4．以下给出的各数中不可能是八进制数的是( )
A．312 B．1 010 C．82 D．74BC题型一 多层条件结构的嵌套例1 设计一个计算方程ax2＋bx＋c＝0解的程序框图．跟 踪训 练解析：流程图如下：题型二 确定循环的控制条件例2 某篮球队6名主力队员在最近三场比赛中投进三分球个数如下表所示：上图是统计该6名队员在最近三场比赛中投进的三分球总数的程序框图，则图中判断框应填________，输出的s＝________(注：框图中的赋值等号“＝”也可以写成“←”或“：＝”)．跟 踪训 练2．请将下边算法流程框图填写完整：设计计算y＝x2的算法流程图，其中x＝－10，－9，…，0,1，…，9,10.
①________；
②________.x≤10？x＝x＋1题型三 算法案例的分析应用例3 用算法语句描述：把k进制数a(共有n位)转换为十进制数b的过程．解析：语句为：跟 踪训 练3．三个数72,120,168的最大公约数是________．24题型四 误用循环语句的错解分析例4 编写程序求12＋22＋…＋992＋1002的值．错解：错解分析：这是直到型循环，直到条件“i>＝100”成立时，执行循环．由程序可知，执行第一次循环时，sum＝0＋12，随着循环的继续，当i的值增加到100时结束循环，但此时sum＝0＋12＋22＋…＋992，显然少执行了一次循环．
正解：把条件“i>＝100”修改为“i>100”．点评：避免以上错误的关键是对循环控制条件进行检验．对一个循环语句的检验，不可能像执行循环体那样一次一次地去检验．如例4，循环次数达100次，若检验循环100次是不可取的．对循环的检验可分为两步进行：首先，检验第一次循环能否执行，既然是一个循环，那么它至少得循环一次，所以第一次循环必定能执行，这样就可避免类似的错误；其次，检验最后一次循环，如例4中，若条件为“i>＝100”，则执行最后一次循环时语句“sum＝sum＋i∧2”中i的值是99，显然少执行了一次循环．跟 踪训 练4．用循环语句写出求1＋2＋22＋23＋…＋263的值的程序．解析：程序如下：数学·必修3(人教A版)
1．3.3 算法综合问题(习题课)
1．下列说法错误的是( )
A．一个算法应包含有限的操作步骤，而不能是无限的
B．有的算法执行完后，可能有无数个结果
C．一个算法可以有0个或多个输入
D．算法中的每一步骤都是确定的，算法的含义是唯一的
答案：B
2．已知程序如下：
若输入x＝－5，运行结果是( )
A．x＝－5 y＝10 B．x＝－5 y＝0
C．y＝100 D．y＝0
答案：D
3．如下图，算法流程图的输出结果是( )
A．20 B．2 C．102 D．10
答案：A
4．计算机中常用的十六进制是逢16进1的计数制，采用数字0～9和字母A～F共16个计数符号，这些符号与十进制数的对应关系如下表：
十六进制
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
十进制
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
例如，用十六进制表示：E＋D＝1B，则A×B等于________．
答案：6E
5．观察算法的流程图，循环体和终止条件分别是( )
A．③② B．②① C．②④ D．③④
答案：C
6．10化为二进制数为________．
答案：1 010(2)
7．将二进制数101 101(2)化为十进制结果为________．
答案：45
8．下面程序框图的运算结果为________．
答案：24
9．以下程序运行后的输出结果为( )
A．17 B．19 C．21 D．23
答案：C
10．分析下题的错误解法，并说明修改意见．
编写程序求2×4×6×…×100的值．
错解：
解析：这是当型循环，当条件“i＞＝100”成立时，执行循环．而由程序可知，i的初值为2，第一次执行循环时，i的值就不满足条件“i＞＝100”，故根本就不执行循环．而是直接执行语句“PRINT p”，程序的运行结果是输出的初值1.
正解：把条件“i＞＝100”改为“i＜100”．
1．算法目前的考试形式主要是选择与填空，但不排除在解答题中用到画框图和写算法语句．
2．编写程序要注意科学性与简洁性．
3．特别注意算法语言的标点使用，切不可随意添加或省略.
