天天练 §1.3.1算法案例1
1、下列各组关于最大公约数的说法中不正确的是 （ ）
A、16和12的最大公约数是4
B、78和36的最大公约数是6
C、85和357的最大公约数是34
D、105和315的最大公约数是105
2、用更相减损术求567和405的最大公约数，需要做减法的次数是 ( )
A、1 B、2 C、3 D、4
3、用辗转相除法求295和85的最大公约数时，需要做出除法的次数是 ( )
A、1 B、2 C、3 D、 4
4、整数143和65的最大公约数为 ( )
A、13 B、11 C、5 D、9
5、在对16和12求最大公约数时，整个操作如下：
（16，12）→（4，12）→（4，8）→（4，4），
由此可以看出12和16的最大公约数是 （ ）
A、 4 B、 12 C、 16 D、 8
6、我国古代数学发展一直处于世界领先水平，特别是宋、元时期的“算法”，其中可以同欧几里德辗转相除法相媲美的是 ( )
A、割圆术 B、更相减损术
C、秦九韶算法 D、孙子乘余定理
7、如果a, b是正整数，且a>b，r=a mod b，则a与b的最大公约数为 ( )
A、r B、b C、b－r D、b与r的最大公约数
8、用辗转相除法或更相减损术求168与93的最大公约数：
9、数4557，1953，5115的最大公约数为 （ ）
A、93 B、31 C、651 D、217
10、算法
S1 输入 x，y
S2 m=max{x，y}
S3 n=min{x，y}
S4 若m/n=[m/n] ([x]表示x的整数部分)
则输出n，否则执行S5
S5 r=m－[m/n]*n
S6 m=n
S7 n=r
S8 执行S4
S9 输出n
上述算法的含义是
11、有一堆火柴棒，三根三根的数，最后余下两根；五根五根的数，最后余下三根；七根七根的数，最后余下两根。那么这对火柴棒最少是多少根？写出解决此问题的算法或程序框图或程序.
-----------------------------------------------------------------------------------------------------------------------------------
小结与反思：天天练 §1.3.1算法案例3
1、把七进制数235化为十进制数为（ ）
A、124 B、126 C、128 D、130
2、三位七进制的数表示的最大的十进制的数是( )
A、322 B、402 C、342 D、365
3、把88化为五进制数是（ ）
A、324(5) B、323(5) C、233(5) D、332(5)
4、下列给出的数中不可能是八进数的是（ ）
A、312 B、10110 C、82 D、7456
5、下列各数中最小的数是（ ）
A、111111(2) B、210(6) C、1000(4) D、81(9)
6、若六进数化为十进数为12710，则，把12710化为八进数为____________.
7、下图是把二进制数111（2）化成十进制数的一个程序框图，则判断框内应填入的条件是 .
8、以下程序：
INPUT x
If x<=2 Then
F(x)=2x－3
Else
F(x)=log2x
End If
Print y
则F(－3)+F(2)= ．
9、（1）把八进位制数706（8）化为十进制数
（2）把十进位制数706化为八进制数
10、已知=,求r.
11、二进制数10111转化为五进制数是 （ ）
A、41 B、25
C、21 D、43
12、在右图给出的程序中，若输入a=333，k=5，
则输出的b为 ．
13、如左上图，是一程序框图，则输出结果为 ．
14、我市某机构为调查2008年下半年落实中学生“阳光体育”活动的情况，设平均每人每天参加体育锻炼时间（单位：分钟），按锻炼时间分下列四种情况统计：
0～10分钟；②11～20分钟；
③21～30分钟；④30分钟以上，
有10000名中学生参加了此项活动，右图是此次调查中某一项的流程图，其输出的结果是6200，则平均每天参加体育锻炼时间在0～20分钟内的学生的频率是
A、0.62 B、0.38 C、6200 D、3800
？
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=q
LOOP UNTIL q=0
PRINT b
END
T=1
开始
S=0
S=S+1
T=T+1
结束
输入X
X≤20
是
否
输出S
T≤10000
否
是
-----------------------------------------------------------------------------------------------------------------------------------
小结与反思：导学案 §1.3.1算法案例3（进位制）
【学习目标】
1、了解各种进位制与十进制之间转化的规律，用类比的思想方法掌握将k进制转化为十进制的算法。
2、掌握用“除k取余法”将十进制转化成k进制，各种进制间的转化。
3、发展学生有条理的思维能力。
【重点】
用类比的思想方法掌握将k进制转化为十进制的算法，十进制转化成k进制的算法“除k取余法”。
【难点】
将k进制转化为十进制的算法步骤，十进制转化成k进制的算法步骤。
【新知探究】
进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。现在最常用的是十进制 ( http: / / www.21cnjy.com / " \o "十进制 )，通常使用10个阿拉伯数字0-9进行记数。
十进制使用0～9十个数字，类似的二进制使用0和1 两个数，七进制使用0～6七个数字，想一下五进制与八进制分别使用哪些数呢？
_________________ _______________
对于任何一个数，我们可以用不同的进位制来表示。比如：十进数 ( http: / / www.21cnjy.com / " \o "十进制 )57，可以用二进制表示为111001，也可以用八进制 ( http: / / www.21cnjy.com / " \o "八进制 )表示为71、用十六进制表示为39，它们所代表的数值都是一样的。
表示各种进位制数一般在数字右下脚加注来表示,
如111001(2)表示二进制数,34(5)表示5进制数.
【范例研讨】
把k进制转化为十进制
1、十进制3721写成：
3721=3×10+7×10+2×10+1×10
与十进制类似，二进制11001可以写成：
11001= 1×2 +1×2+0×2+0×2+1×2
试想一下，五进制432132可以写成：
__________________________________
2、把其他进制转化为十进制
11001= 1×2 +1×2+0×2+0×2+1×2
= 1×16+1×8+1
= 25
例1、将五进制4321转化为十进制
把十进制转化成k进制
例2、把十进制数191化成五进制数。
例3、已知10b1（2）=a02（3）,求数字a，b的值.
【课堂练习1】
1、将389化成四进位制数的末位是 ( )
A、 1 B、 2 C、 3 D、0
2、把67化为二进制数为 （ ）
A、1100001（2） B、1000011（2） C、110000（2） D、1000111（2）
3、二进制算式1010（2）+10（2）的值是 （ ）
A、1011（2） B、1100（2） C、1101（2） D、1000（2）
4、四位二进制能表示的最大十进制数是（ ）
A、4 B、15 C、64 D、127
6、完成下列进位制之间的转化.
=_____________=_____________
=_________=_____________
=_________ =_________
【算法设计】
把进制数a（共有n位）化为十进制数b的算法
将十进制数a化为k进制数的算法步骤：
小结:
(1)进位制的概念及表示方法
(2)十进制与二进制之间转换的方法及计算机程序
INPUT “a,k,n=”;a,k,n
b=0
i=1
t=a MOD 10
DO
b=b+t*k^(i-1)
a=a\10
t=a MOD 10
i=i+1
LOOP UNTIL i>n
PRINT b
END
INPUT “a,k=”;a,k
b=0
i=1
DO
q=a\k
r=a MOD k
b=b+r*10^i
i=i+1
a=q
LOOP UNTIL q=0
PRINT b
END导学案 §1.3.1算法案例2（秦九韶算法）
学习目标：
1. 用转化的数学思想方法理解秦九韶算法。
2. 掌握用秦九韶算法计算高次多项式的值。
重点：掌握秦九韶算法思想、特点，及其程序设计
难点：秦九韶算法的步骤，用循环结构表示算法
一、自主探究：
探究：秦九韶算法
对于多项式f(x)=2x5-5x4-4x3+3x2-6x+7，求f(5)的值.
问题1：若先计算各项的值，然后再相加，那么一共要做_____次乘法运算和____次加法运算
问题2：在上述问题中，，将多项式变形为：
f(x)=2x5-5x4-4x3+3x2-6x+7=((((2x-5)x-4)x+3)x-6)x+7，
依次计算2ⅹ5-5=5，
5ⅹ5-4=21，
21ⅹ5+3=108，
108ⅹ5-6=534，
534ⅹ5+7=2677
故f(5)= 2677.
那么一共做了_____次乘法运算和_____次加法运算
比较两种算法：
二、新知学习
新知1：上述求多项式的值的方法叫做__________，其基本思路是：
将多项式f(x)=anxn+an-1xn-1+…+a1x+a0先写成
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.
思考：在利用秦九韶算法计算n次多项式当时需要______次乘法计算和______次加法计算
新知2：算法设计
上述个一次式，可发现的计算要用到的值，若令，可得到下列递推公式：.
这是一个反复执行的步骤，因此可用循环结构来实现.算法步骤如下：
第一步，输入多项式的次数___，最高次项的系数____和____的值.
第二步，令v=____，i=________.
第三步，输入i次项的系数____.
第四步，v=________，i=________.
第五步，判断________是否成立.
若是，返回第三步；否则，输出多项式值____.
框图： 程序：
三、例题分析：
例1、已知一个5次多项式为 f(x)=5x5+2x4+3.5x3－2.6x2+1.7x－0.8 用秦九韶算法求f(5)的值.
四、课堂练习
1、用秦九韶算法计算多项式f(x)=3x+4x+5x+6x+7x+8x+1，当x=4时，需要做乘法和加法的次数分别是（ ）
A、6，6 B、5，6 C、5，5 D、6，5
2、用秦九韶算法计算多项式f(x)= x+4x+3x+1，当x=1.3时的值需要将多项
式改写为＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
3、用秦九韶算法求多项式f(x)=5x+7x+6x+3x+x+1,当x=3的值。
4、f(x)=3x+2x+x+4，则f(10)等于（ ）
A、3214 B、3210 C、2214 D 90
5、用秦九韶算法计算多项式在时的值时,的值为 ( )
A. －845 B. 220 C. －57 D. 34
课堂小结：
1、掌握用秦九韶算法计算高次多项式的值。
2、掌握秦九韶算法的特点，及其程序设计
六、学习反思
否
是
结束
输出v
输入ai
i≥0
v=vx+ai
i=i-1
i=n-1
v=an
输入n,an,x的值
开始天天练 §1.3.1算法案例2
1、用秦九韶算法和直接算法求当时
的值，做的乘法次数分别为（ ）
A、6，20 B、7，20
C、7，21 D、6，21
2、用秦九韶算法求多项式在的值时，
其中的值为（ ）．
A、－57 B、124 C、－845 D、220
3、秦九韶算法与直接计算相比较，下列说法错误的是（ ）
A、秦九韶算法与直接计算相比，大大节省了乘法得次数，使计算量减小，并且逻辑结构简单
B、秦九韶算法减少做乘法的次数，在计算机上也就加快了计算的速度
C、秦九韶算法减少做乘法的次数，在计算机上也就降低了计算的速度
D、秦九韶算法避免对自变量x单独作幂的计算，而是与系数一起逐次增长幂次，从而可提高计算的精度
4、用秦九韶算法求ｎ次多项式ｆ（ｘ）＝，当ｘ＝时，求需要算乘方、乘法、加法的次数分别为（ ）
A、 B、 n，，n
C、0，，n D、 0，n，n
5、利用秦九韶算法求多项式在的值时，在运算中下列哪个值用不到（ ）
A、164 B、3767 C、86652 D、85169
6、下图的框图是一古代数学家的一个算法的程序框图，它输出的结果s表示（ ）
A、的值
B、的值
C、的值
D、以上都不对
7、利用秦九韶算法求多项式在的值，写出详细步骤，并统计需要多少次乘法计算和多少次加法计算？
试写出程序框图或程序。
8、执行如图的程序框图，如果输入，则输出的（ ）
A、 B、 C、 D、
9、按如图所示的程序框图运算．
(1) 若输入，则输出 ；
(2) 若输出，则输入的取值范围是 ．
S=S*x0+ak
K>0
开始
K=3
K=K-1
输入
输出S
结束
开始
结束
输入x
是
否
输出k
-----------------------------------------------------------------------------------------------------------------------------------
小结与反思：导学案 §1.3.1算法案例1(辗转相除法与更相减损术)
学习目标：
1、理解辗转相除法与更相减损术的数学原理，会用辗转相除法与更相减损术求最大公约数；
2、基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.
重点：理解辗转相除法与更相减损术求最大公约数的方法.
难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.
一、复习回顾：
用小学的方法求下列三组正整数的最大公约数：
(1)72和168 (2) 98和63 (3) 8251和6105
二、新知探究
1、辗转相除法：
例1、求8251和6105的最大公约数
以上我们求最大公约数的方法就是辗转相除法．也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的．
思考：你能把辗转相除法编成一个计算机程序吗？
辗转相除法程序框图 根据左图写出程序
思考：你能用当型循环结构构造算法，求两个正整数的最大公约数吗？
2、更相减损术
例2、 用更相减损术求98与63的最大公约数.
．
更相减损术程序框图： 程序
注：辗转相除法与更相减损术的区别:
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到；而更相减损术则以减数与差相等而得到。
思考：利用辗转相除法是否可以求两数的最大公倍数？
三、课堂练习
1、用辗转相除法求294和84的最大公约数时，需要做除法的次数是（ ）
A、2 B、3 C、4 D、5
2、用辗转相除法求567和405的最大公约数是 ( )
A、81 B、7 C、 5 D、35
用更相减损术求587和405的最大公约数，需要做减法的次数是 ( )
A、12 B、13 C、14 D、15
4、145与232的最大公约数为 ( )
A、45 B、19 C、29. D、32
5、用更相减损术求612与468的最大公约数：
6、用辗转相除法求下列两数的的最大公约数，并用更相减损术检验你的结果：
280，124
四、课堂小结
1、理解辗转相除法与更相减损术求最大公约数的方法。
2、辗转相除法与更相减损术求最大公约数的方法的区别。
五、学习反思
用辗转相除法求最大公约数的方法如下：
S1：用较__的数m除以较__的数n得到一个____q0和一个_______r0；
S2：若______，则___为m，n的最大公约数；
若______，则用___________除以_______得到又一个商q1和一个余数r1；
S3：若r1=0，则r1为的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；
……
依次计算直至rn≠0， rn-1即为所求的最大公约数
8251＝6105×1＋2146
6105＝2146×2＋1813
2146＝1813×1＋333
1813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
则37为8251与6105的最大公约数
开始
INPUT m，n
m>n
r=m MOD n
PRINT
结束
r=0
S1：给定两个正整数m，n(m>n).
S2：计算m－n所得的差k.
S3：若n≠k，则其中大者用m表示，小者用n表示，返回第二步
S4：若n=k，则m，n的最大公约数为n
∵63不是偶数
98－63＝35
63－35＝28
35－28＝7
28－7＝21
21－7＝14
14－7＝7
∴98与63的最大公约数是7
输出m
开始
输入m,n
k=m-n
否
是
否
是
结束
m=k
n=k
m=n
