湖北省巴东一中高二数学教案-必修三：算法案例教学内容.doc

§1.3 算法案例
一、教材分析
在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序三种不同方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.
二、教学目标
1、知识与技能
（1）理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
（2）基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
（3）了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质。
（4）掌握数据排序的原理能使用直接排序法与冒泡排序法给一组数据排序，进而能设计冒泡排序法的程序框图及程序，理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用。
（5）了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换。
2、过程与方法
（1）在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。
（2）模仿秦九韶计算方法，体会古人计算构思的巧妙。能根据排序法中的直接插入排序法与冒泡排序法的步骤，了解数学计算转换为计算机计算的途径，从而探究计算机算法与数学算法的区别，体会计算机对数学学习的辅助作用。
（3）学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k去余法，并理解其中的数学规律。
3、情态与价值观
（1）通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。
（2）在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。
（3）通过对秦九韶算法的学习，了解中国古代数学家对数学的贡献，充分认识到我国文化历史的悠久。通过对排序法的学习，领会数学计算与计算机计算的区别，充分认识信息技术对数学的促进。
（4）领悟十进制，二进制的特点，了解计算机的电路与二进制的联系，进一步认识到计算机与数学的联系。
三、重点难点
教学重点：（1）引导学生得出自己设计的算法步骤、程序框图和算法程序.
（2）秦九韶算法的特点
（3）两种排序法的排序步骤及计算机程序设计
（4）各进位制表示数的方法及各进位制之间的转换
教学难点：（1）体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.
（2）秦九韶算法的先进性理解
（3）排序法的计算机程序设计
（4）除k去余法的理解以及各进位制之间转换的程序框图的设计
四、课时安排
3课时
五、教学设计

第1课时 案例1 辗转相除法与更相减损术
（一）导入新课
思路1（情境导入）
大家喜欢打乒乓球吧，由于东、西方文化及身体条件的不同，西方人喜欢横握拍打球，东方人喜欢直握拍打球，对于同一个问题，东、西方人处理问题方式是有所不同的.在小学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来. 当两个数公有的质因数较大时（如8 251与6 105），使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法——辗转相除法与更相减损术,由此可以体会东、西方文化的差异.
思路2（直接导入）
前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过辗转相除法与更相减损术来进一步体会算法的思想.

（二）推进新课、新知探究、提出问题
（1）怎样用短除法求最大公约数？
（2）怎样用穷举法（也叫枚举法）求最大公约数？
（3）怎样用辗转相除法求最大公约数？
（4）怎样用更相减损术求最大公约数？
讨论结果：
（1）短除法
求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来.
（2）穷举法（也叫枚举法）
穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数.
（3）辗转相除法
辗转相除法求两个数的最大公约数，其算法步骤可以描述如下：
第一步，给定两个正整数m，n.
第二步，求余数r：计算m除以n，将所得余数存放到变量r中.
第三步，更新被除数和余数：m=n，n=r.
第四步，判断余数r是否为0.若余数为0，则输出结果；否则转向第二步继续循环执行.
如此循环，直到得到结果为止. 这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法.
（4）更相减损术
我国早期也有解决求最大公约数问题的算法，就是更相减损术. 《九章算术》是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”翻译为现代语言如下：
第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用2约简；若不是，执行第二步.
第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.

（三）应用示例
例1 用辗转相除法求8 251与6 105的最大公约数,写出算法分析，画出程序框图，写出算法程序.
解：用两数中较大的数除以较小的数，求得商和余数：8 251=6 105×1+2 146.
由此可得，6 105与2 146的公约数也是8 251与6 105的公约数，反过来，8 251与6 105的公约数也是6 105与2 146的公约数，所以它们的最大公约数相等.
对6 105与2 146重复上述步骤：6 105=2 146×2+1 813.
同理，2 146与1 813的最大公约数也是6 105与2 146的最大公约数.继续重复上述步骤：
2 146=1 813×1+333，
1 813=333×5+148，
333=148×2+37，
148=37×4.
最后的除数37是148和37的最大公约数，也就是8 251与6 105的最大公约数.
这就是辗转相除法.由除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出两个正整数的最大公约数.
算法分析：从上面的例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环结构来构造算法.
算法步骤如下：
第一步，给定两个正整数m，n.
第二步，计算m除以n所得的余数为r.
第三步，m=n，n=r.
第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.
程序框图如下图：

程序：
INPUT m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
点评：从教学实践看，有些学生不能理解算法中的转化过程，例如：求8 251与6 105的最大公约数,为什么可以转化为求6 105与2 146的公约数.因为8 251=6 105×1+2 146，
可以化为8 251-6 105×1=2 164，所以公约数能够整除等式两边的数，即6 105与2 146的公约数也是8 251与6 105的公约数.
变式训练
你能用当型循环结构构造算法，求两个正整数的最大公约数吗？试画出程序框图和程序.
解：当型循环结构的程序框图如下图：

程序：
INPUT m，n
r=1
WHILE r＞0
r=m MOD n
m=n
n=r
WEND
PRINT m
END

例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.
点评：更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代数学名著，但是二者的算理却是相似的，有异曲同工之妙．主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归过程．
变式训练
用辗转相除法或者更相减损术求三个数324,243,135的最大公约数.
解：324=243×1＋81，
243=81×3＋0，
则324与243的最大公约数为81.
又135=81×1＋54，81=54×1＋27，
54=27×2＋0，
则 81 与 135的最大公约数为27.
所以,三个数324、243、135的最大公约数为27.
另法：324－243=81,243－81=162,162－81=81，则324与243的最大公约数为81.
135－81=54,81－54=27,54－27=27，则81与135的最大公约数为27.
所以，三个数324、243.135的最大公约数为27.

例3 （1）用辗转相除法求123和48的最大公约数.
（2）用更相减损术求80和36的最大公约数.
解：（1）辗转相除法求最大公约数的过程如下：
123＝2×48＋27，
48＝1×27＋21，
27＝1×21＋6，
21＝3×6＋3，
6＝2×3+0，
最后6能被3整除，得123和48的最大公约数为3.
（2）我们将80作为大数，36作为小数，因为80和36都是偶数，要除公因数2.
80÷2=40，36÷2=18.
40和18都是偶数，要除公因数2.
40÷2=20，18÷2=9.
下面来求20与9的最大公约数，
20－9=11，
11－9=2，
9－2=7，
7－2=5，
5－2=3，
3－2=1，
2－1=1，
可得80和36的最大公约数为22×1=4.
点评：对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等.
变式训练
分别用辗转相除法和更相减损术求1 734，816的最大公约数．
解：辗转相除法：
1 734=816×2+102，816=102×8（余0），
∴1 734与816的最大公约数是102．
更相减损术：因为两数皆为偶数，首先除以2得到867，408，再求867与408的最大公约数．
867-408=459，
459-408=51，
408-51=357，
357-51=306，
306-51=255，
255-51=204，
204-51=153，
153-51=102，
102-51=51.
∴1 734与816的最大公约数是51×2=102．
利用更相减损术可另解：
1 734－816＝918，
918－816＝102，
816－102＝714，
714－102＝612，
612－102＝510，
510－102＝408，
408－102＝306，
306－102＝204，
204－102＝102.
∴1 734与816的最大公约数是102．

（四）知能训练
求319，377，116的最大公约数．
解：377=319×1+58，
319=58×5+29，
58=29×2.
∴377与319的最大公约数为29，再求29与116的最大公约数．
116=29×4.
∴29与116的最大公约数为29.
∴377，319，116的最大公约数为29.

（五）拓展提升
试写出利用更相减损术求两个正整数的最大公约数的程序．
解：更相减损术程序：
INPUT “m，n=”；m，n
WHILE m<>n
IF m>n THEN
ｍ＝m-n
ELSE
m=n-m
END IF
WEND
PRINT m
END

（六）课堂小结
（1）用辗转相除法求最大公约数.
（2）用更相减损术求最大公约数.
思想方法：递归思想.

（七）作业
分别用辗转相除法和更相减损术求261，319的最大公约数.
分析：本题主要考查辗转相除法和更相减损术及其应用．使用辗转相除法可依据m=nq+r，反复执行，直到r=0为止；用更相减损术就是根据m-n=r，反复执行，直到n=r为止．
解：辗转相除法：
319=261×1+58,
261=58×4+29,
58=29×2.
∴319与261的最大公约数是29．
更相减损术：
319-261=58,
261-58=203,
203-58=145,
145-58=87,
87-58=29,
58-29=29,
∴319与261的最大公约数是29．

第2课时 案例2 秦九韶算法
（一）导入新课
思路1（情境导入）
大家都喜欢吃苹果吧，我们吃苹果都是从外到里一口一口的吃，而虫子却是先钻到苹果里面从里到外一口一口的吃，由此看来处理同一个问题的方法多种多样.怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？方法也是多种多样的，今天我们开始学习秦九韶算法.
思路2（直接导入）
前面我们学习了辗转相除法与更相减损术， 今天我们开始学习秦九韶算法.

（二）推进新课、新知探究、提出问题
（1）求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值有哪些方法？比较它们的特点.
（2）什么是秦九韶算法？
（3）怎样评价一个算法的好坏？
讨论结果：
（1）怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？
一个自然的做法就是把5代入多项式f(x)，计算各项的值，然后把它们加起来，这时，我们一共做了1+2+3+4=10次乘法运算，5次加法运算.
另一种做法是先计算x2的值，然后依次计算x2·x，（x2·x）·x，（（x2·x）·x）·x的值，这样每次都可以利用上一次计算的结果，这时，我们一共做了4次乘法运算，5次加法运算.
第二种做法与第一种做法相比，乘法的运算次数减少了，因而能够提高运算效率，对于计算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以采用第二种做法，计算机能更快地得到结果.
（2）上面问题有没有更有效的算法呢？我国南宋时期的数学家秦九韶（约1202~1261）在他的著作《数书九章》中提出了下面的算法：
把一个n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0改写成如下形式：
f(x)=anxn+an-1xn-1+…+a1x+a0
=（anxn-1+an-1xn-2+…+a1）x+ a0
=（（anxn-2+an-1xn-3+…+a2）x+a1)x+a0
=…
=（…（（anx+an-1）x+an-2）x+…+a1）x+a0.
求多项式的值时，首先计算最内层括号内一次多项式的值，即
v1=anx+an-1，
然后由内向外逐层计算一次多项式的值，即
v2=v1x+an-2，
v3=v2x+an-3，
…
vn=vn-1x+a0，
这样，求n次多项式f（x）的值就转化为求n个一次多项式的值.
上述方法称为秦九韶算法.直到今天，这种算法仍是多项式求值比较先进的算法.
（3）计算机的一个很重要的特点就是运算速度快，但即便如此，算法好坏的一个重要标志仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论的算法.

（三）应用示例
例1 已知一个5次多项式为f（x）=5x5+2x4+3.5x3-2.6x2+1.7x-0.8，
用秦九韶算法求这个多项式当x=5时的值.
解：根据秦九韶算法，把多项式改写成如下形式：
f(x)=（(((5x+2)x+3.5)x-2.6)x+1.7)x-0.8，
按照从内到外的顺序，依次计算一次多项式当x=5时的值：
v0=5；
v1=5×5+2=27;
v2=27×5+3.5=138.5;
v3=138.5×5-2.6=689.9;
v4=689.9×5+1.7=3 451.2;
v5=3 415.2×5-0.8=17 255.2;
所以，当x=5时，多项式的值等于17 255.2.
算法分析：观察上述秦九韶算法中的n个一次式，可见vk的计算要用到vk-1的值，若令v0=an，我们可以得到下面的公式：

这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现.
算法步骤如下：
第一步，输入多项式次数n、最高次的系数an和x的值.
第二步，将v的值初始化为an，将i的值初始化为n-1.
第三步，输入i次项的系数ai.
第四步，v=vx+ai,i=i-1.
第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.
程序框图如下图：

程序：
INPUT “n=”；n
INPUT “an=”；a
INPUT “x=”；x
v=a
i=n-1
WHILE i＞=0
PRINT “i=”；i
INPUT “ai=”；a
v=v*x+a
i=i-1
WEND
PRINT v
END
点评：本题是古老算法与现代计算机语言的完美结合，详尽介绍了思想方法、算法步骤、程序框图和算法语句,是一个典型的算法案例.
变式训练
请以5次多项式函数为例说明秦九韶算法，并画出程序框图.
解：设f（x）=a5x5+a4x4+a3x3+a2x2+a1x+a0
首先，让我们以5次多项式一步步地进行改写：
f（x）=（a5x4+a4x3+a3x2+a2x+a1）x+a0
=（（a5x3+a4x2+ a3x+a2）x+a1）x+a0
=（（（a5x2+a4x+ a3）x+a2）x+a1）x+a0
=（（（（a5x+a4）x+ a3）x+a2）x+a1）x+a0.
上面的分层计算,只用了小括号，计算时，首先计算最内层的括号，然后由里向外逐层计算，直到最外层的括号，然后加上常数项即可.
程序框图如下图：

例2 已知n次多项式Pn(x)=a0xn+a1xn-1+…+an-1x+an，如果在一种算法中，计算（k=2，3，4，…，n）的值需要k－1次乘法，计算P3(x0)的值共需要9次运算（6次乘法，3次加法），那么计算P10(x0)的值共需要__________次运算.下面给出一种减少运算次数的算法：P0(x)=a0,Pk+1(x)=xPk(x)+ak+1（k＝0，1，2，…，n－1）．利用该算法，计算P3(x0)的值共需要6次运算，计算P10(x0)的值共需要___________次运算.
答案：65 20
点评：秦九韶算法适用一般的多项式f(x)=anxn+an-1xn-1+…+a1x+a0的求值问题.直接法乘法运算的次数最多可到达，加法最多n次.秦九韶算法通过转化把乘法运算的次数减少到最多n次，加法最多n次.

例3 已知多项式函数f(x)=2x5－5x4－4x3+3x2－6x+7，求当x=5时的函数的值.
解析：把多项式变形为：f(x)=2x5－5x4－4x3+3x2－6x+7
=((((2x－5)x－4)x+3)x－6)x+7.
计算的过程可以列表表示为：

最后的系数2 677即为所求的值.
算法过程：
v0=2；
v1=2×5－5=5；
v2=5×5－4=21；
v3=21×5+3=108；
v4=108×5－6=534；
v5=534×5+7=2 677.
点评：如果多项式函数中有缺项的话，要以系数为0的项补齐后再计算.

（四）知能训练
当x=2时，用秦九韶算法求多项式f(x)=3x5+8x4-3x3+5x2+12x-6的值．
解法一：根据秦九韶算法，把多项式改写成如下形式：
f(x)=((((3x+8)x-3)x+5)x+12）x-6.
按照从内到外的顺序，依次计算一次多项式当x=2时的值.
v0=3;
v1=v0×2+8=3×2+8=14;
v2=v1×2-3=14×2-3=25;
v3=v2×2+5=25×2+5=55;
v4=v3×2+12=55×2+12=122;
v5=v4×2-6=122×2-6=238.
∴当x=2时，多项式的值为238.
解法二：f(x)=((((3x+8)x-3)x+5)x+12）x-6，
则f(2)=((((3×2+8)×2－3)×2+5)×2+12)×2－6＝238．

（五）拓展提升
用秦九韶算法求多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x当x=3时的值.
解：f(x)=((((((7x+6)+5)x+4)x+3)x+2)x+1)x
v0=7；
v1=7×3+6=27；
v2=27×3+5=86；
v3=86×3+4=262；
v4=262×3+3=789；
v5=789×3+2=2 369；
v6=2 369×3+1=7 108；
v7=7 108×3+0=21 324.
∴f(3)=21 324.

（六）课堂小结
1.秦九韶算法的方法和步骤.
2.秦九韶算法的计算机程序框图.

（七）作业
已知函数f(x)=x3－2x2－5x+8,求f(9)的值.
解：f(x)=x3－2x2－5x+8=(x2－2x－5)x+8=((x－2)x－5)x+8
∴f(9)=((9－2)×9－5)×9+8=530.

第3课时 案例3 进位制
（一）导入新课
情境导入
在日常生活中，我们最熟悉、最常用的是十进制，据说这与古人曾以手指计数有关，爱好天文学的古人也曾经采用七进制、十二进制、六十进制，至今我们仍然使用一周七天、一年十二个月、一小时六十分的历法.今天我们来学习一下进位制.

（二）推进新课、新知探究、提出问题
（1）你都了解哪些进位制？
（2）举出常见的进位制.
（3）思考非十进制数转换为十进制数的转化方法.
（4）思考十进制数转换成非十进制数及非十进制之间的转换方法.
活动：先让学生思考或讨论后再回答，经教师提示、点拨，对回答正确的学生及时表扬，对回答不准确的学生提示引导考虑问题的思路．
讨论结果：
（1）进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制等等.也就是说：“满几进一”就是几进制，几进制的基数（都是大于1的整数）就是几.
（2）在日常生活中，我们最熟悉、最常用的是十进制，据说这与古人曾以手指计数有关，爱好天文学的古人也曾经采用七进制、十二进制、六十进制，至今我们仍然使用一周七天、一年十二个月、一小时六十分的历法.
（3）十进制使用0~9十个数字.计数时，几个数字排成一行，从右起，第一位是个位，个位上的数字是几，就表示几个一；第二位是十位，十位上的数字是几，就表示几个十；接着依次是百位、千位、万位……
例如：十进制数3 721中的3表示3个千，7表示7个百，2表示2个十，1表示1个一.于是，我们得到下面的式子：
3 721=3×103+7×102+2×101+1×100.
与十进制类似，其他的进位制也可以按照位置原则计数.由于每一种进位制的基数不同，所用的数字个数也不同.如二进制用0和1两个数字，七进制用0~6七个数字.
一般地，若k是一个大于1的整数，那么以k为基数的k进制数可以表示为一串数字连写在一起的形式
anan-1…a1a0（k）（0＜an＜k，0≤an-1，…，a1，a0＜k).
其他进位制的数也可以表示成不同位上数字与基数的幂的乘积之和的形式，如
110 011（2）=1×25+1×24+0×23+0×22+1×21+1×20，
7 342（8）=7×83+3×82+4×81+2×80.
非十进制数转换为十进制数比较简单，只要计算下面的式子值即可：
anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k+a0.
第一步：从左到右依次取出k进制数anan-1…a1a0(k)各位上的数字，乘以相应的k的幂，k的幂从n开始取值，每次递减1，递减到0，即an×kn,an-1×kn-1,…,a1×k,a0×k0；
第二步：把所得到的乘积加起来，所得的结果就是相应的十进制数.
（4）关于进位制的转换，教科书上以十进制和二进制之间的转换为例讲解，并推广到十进制和其他进制之间的转换.这样做的原因是，计算机是以二进制的形式进行存储和计算数据的，而一般我们传输给计算机的数据是十进制数据，因此计算机必须先将十进制数转换为二进制数，再处理，显然运算后首次得到的结果为二进制数，同时计算机又把运算结果由二进制数转换成十进制数输出.
1°十进制数转换成非十进制数
把十进制数转换为二进制数，教科书上提供了“除2取余法”，我们可以类比得到十进制数转换成k进制数的算法“除k取余法”.
2°非十进制之间的转换
一个自然的想法是利用十进制作为桥梁.教科书上提供了一个二进制数据与16进制数据之间的互化的方法，也就是先由二进制数转化为十进制数，再由十进制数转化成为16进制数.

（三）应用示例
思路1
例1 把二进制数110 011(2)化为十进制数.
解：110 011(2)=1×25+1×24+0×23+0×22+1×21+1×20=1×32+1×16+1×2+1=51.
点评：先把二进制数写成不同位上数字与2的幂的乘积之和的形式，再按照十进制的运算规则计算出结果.
变式训练
设计一个算法，把k进制数a（共有n位）化为十进制数b.
算法分析：从例1的计算过程可以看出，计算k进制数a的右数第i位数字ai与ki-1的乘积ai·ki-1，再将其累加，这是一个重复操作的步骤.所以，可以用循环结构来构造算法.
算法步骤如下：
第一步，输入a，k和n的值.
第二步，将b的值初始化为0，i的值初始化为1.
第三步，b=b+ai·ki-1，i=i+1.
第四步，判断i＞n是否成立.若是，则执行第五步；否则，返回第三步.
第五步，输出b的值.
程序框图如下图：

程序：
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

例2 把89化为二进制数.
解：根据二进制数“满二进一”的原则，可以用2连续去除89或所得商，然后取余数.具体计算方法如下：
因为89=2×44+1，44=2×22+0，
22=2×11+0，
11=2×5+1，
5=2×2+1，
2=2×1+0，
1=2×0+1，
所以
89=2×（2×（2×（2×（2×2+1）+1）+0）+0）+1
=2×（2×（2×（2×（22+1）+1）+0）+0）+1
=…=1×26+0×25+1×24+1×23+0×22+0×21+1×20
=1 011 001(2).
这种算法叫做除2取余法，还可以用下面的除法算式表示：

把上式中各步所得的余数从下到上排列，得到89=1 011 001(2).
上述方法也可以推广为把十进制数化为k进制数的算法，称为除k取余法.
变式训练
设计一个程序，实现“除k取余法”.
算法分析：从例2的计算过程可以看出如下的规律：
若十制数a除以k所得商是q0，余数是r0，即a=k·q0+r0，则r0是a的k进制数的右数第1位数.
若q0除以k所得的商是q1，余数是r1，即q0=k·q1+r1，则r1是a的k进制数的左数第2位数.
……
若qn-1除以k所得的商是0，余数是rn，即qn-1=rn，则rn是a的k进制数的左数第1位数.
这样，我们可以得到算法步骤如下：
第一步，给定十进制正整数a和转化后的数的基数k.
第二步，求出a除以k所得的商q，余数r.
第三步，把得到的余数依次从右到左排列.
第四步，若q≠0，则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=q
LOOP UNTIL q=0
PRINT b
END

思路2
例1 将8进制数314 706(8)化为十进制数，并编写出一个实现算法的程序.
解：314 706(8)=3×85+1×84+4×83+7×82+0×81+6×80=104 902.
所以，化为十进制数是104 902.
点评：利用把k进制数转化为十进制数的一般方法就可以把8进制数314 706(8)化为十进制数.

例2 把十进制数89化为三进制数，并写出程序语句.
解：具体的计算方法如下：
89=3×29+2，
29=3×9+2，
9=3×3+0，
3=3×1+0，
1=3×0+1，
所以:89(10)=10 022(3).
点评：根据三进制数满三进一的原则，可以用3连续去除89及其所得的商，然后按倒序的顺序取出余数组成数据即可.

（四）知能训练
将十进制数34转化为二进制数．
分析：把一个十进制数转换成二进制数，用2反复去除这个十进制数，直到商为0，所得余数（从下往上读）就是所求．
解：

即34(10)=100 010(2)

（五）拓展提升
把1 234(5)分别转化为十进制数和八进制数．
解：1 234(5)=1×53+2×52+3×5+4＝194．

则1 234(5)=302(8)
所以，1 234(5)=194＝302(8)
点评：本题主要考查进位制以及不同进位制数的互化．五进制数直接利用公式就可以转化为十进制数；五进制数和八进制数之间需要借助于十进制数来转化．

（六）课堂小结
（1）理解算法与进位制的关系.
（2）熟练掌握各种进位制之间转化.

（七）作业
习题1.3A组3、4.

算法初步 复习课
一、教学目标
1、知识与技能
（1）明确算法的含义，熟悉算法的三种基本结构：顺序、条件和循环，以及基本的算法语句。
（2）能熟练运用辗转相除法与更相减损术、秦九韶算法、排序、进位制等典型的算法知识解决同类问题。
2、过程与方法
在复习旧知识的过程中把知识系统化，通过模仿、操作、探索，经历设计程序框图表达解决问题的过程。在具体问题的解决过程中进一步理解程序框图的三种基本逻辑结构：顺序、条件分支、循环。
3、情态与价值观
算法内容反映了时代的特点，同时也是中国数学课程内容的新特色。中国古代数学以算法为主要特征，取得了举世公认的伟大成就。现代信息技术的发展使算法重新焕发了前所未有的生机和活力，算法进入中学数学课程，既反映了时代的要求，也是中国古代数学思想在一个新的层次上的复兴，也就成为了中国数学课程的一个新的特色。
二、教学重难点
重点：算法的基本知识与算法对应的程序框图的设计
难点：与算法对应的程序框图的设计及算法程序的编写
三、学法与教学用具
学法：利用实例让学生体会基本的算法思想，提高逻辑思维能力，对比信息技术课程中的程序语言的学习和程序设计，了解数学算法与信息技术上的区别。通过案例的运用，引导学生体会算法的核心是一般意义上的解决问题策略的具体化。面临一个问题时，在分析、思考后获得了解决它的基本思路（解题策略），将这种思路具体化、条理化，用适当的方式表达出来（画出程序框图，转化为程序语句）。
教学用具：电脑，计算器，图形计算器
四、教学设计
（一）、本章的知识结构

（二）、知识梳理
(1)四种基本的程序框

(2)三种基本逻辑结构

顺序结构 条件结构 循环结构

(3)基本算法语句
（一）输入语句
单个变量
INPUT “提示内容”；变量

多个变量
INPUT “提示内容1，提示内容2，提示内容3，…”；变量1，变量2，变量3，…

（二）输出语句
PRINT “提示内容”；表达式

（三）赋值语句
变量=表达式

（四）条件语句
IF-THEN-ELSE格式满足条件？

语句1
语句2
是
否

IF 条件 THEN
语句1
ELSE
语句2
END IF

当计算机执行上述语句时，首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句1，否则执行ELSE后的语句2。其对应的程序框图为：（如上右图）
IF-THEN格式
满足条件？

语句
是
否

IF 条件 THEN
语句
END IF

计算机执行这种形式的条件语句时，也是首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句，如果条件不符合，则直接结束该条件语句，转而执行其他语句。其对应的程序框图为：（如上右图）
（五）循环语句
满足条件？

循环体
是
否
（1）WHILE语句

WHILE 条件
循环体
WEND

其中循环体是由计算机反复执行的一组语句构成的。WHLIE后面的“条件”是用于控制计算机执行循环体或跳出循环体的。
当计算机遇到WHILE语句时，先判断条件的真假，如果条件符合，就执行WHILE与WEND之间的循环体；然后再检查上述条件，如果条件仍符合，再次执行循环体，这个过程反复进行，直到某一次条件不符合为止。这时，计算机将不执行循环体，直接跳到WEND语句后，接着执行WEND之后的语句。因此，当型循环有时也称为“前测试型”循环。其对应的程序结构框图为：（如上右图）
满足条件？

循环体
是
否
（2）UNTIL语句

DO
循环体
LOOP UNTIL 条件

其对应的程序结构框图为：（如上右图）

(4)算法案例
案例1 辗转相除法与更相减损术
案例2 秦九韶算法
案例3 排序法：直接插入排序法与冒泡排序法
案例4 进位制

（三）、典型例题
例1 写一个算法程序,计算1+2+3+…+n的值(要求可以输入任意大于1的正自然数)
解：INPUT “n=”;n
i=1
sum=0
WHILE i<=n
sum=sum+i
i=i+1