算法案例优秀教案

2024-04-20

算法案例优秀教案（精选6篇）

篇1：算法案例优秀教案

秦九韶算法

学习目标

1.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质。

2.掌握数据排序的原理能使用直接排序法与冒泡排序法给一组数据排序，进而能设计冒泡排序法的程序框图及程序，理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用。学习重难点

重点：1.秦九韶算法的特点

2.两种排序法的排序步骤及计算机程序设计难点：1.秦九韶算法的先进性理解

2.排序法的计算机程序设计

学法与学习用具

学法：1.探究秦九韶算法对比一般计算方法中计算次数的改变，体会科学的计算。

2.模仿排序法中数字排序的步骤，理解计算机计算的一般步骤，领会数学计算在计算机上实施的要求。

学习用具：电脑，计算器，图形计算器学习设想

（一）创设情景，揭示课题

我们已经学过了多项式的计算，下面我们计算一下多项式

f(x)x5x4x3x2x1当x5时的值，并统计所做的计算的种类及计算次数。

根据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算。我们把多项式变形为：f(x)x2(1x(1x(1x)))x1再统计一下计算当x5时的值时需要的计算次数，可以得出仅需4次乘法和5次加法运算即可得出结果。显然少了6次乘法运算。这种算法就叫秦九韶算法。

（二）研探新知

/ 4

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)a0例1 已知一个5次多项式为f(x)5x52x43.5x32.6x21.7x0.8 用秦九韶算法求这个多项式当x5时的值。解：略

思考：（1）例1计算时需要多少次乘法计算？多少次加法计算？

（2）在利用秦九韶算法计算n次多项式当xx0时需要多少次乘法计算和多少次加法计算？

练习：利用秦九韶算法计算f(x)0.83x50.41x40.16x30.33x20.5x1 当x5时的值，并统计需要多少次乘法计算和多少次加法计算？例2 设计利用秦九韶算法计算5次多项式

f(x)a5x5a4x4a3x3a2x2a1xa0当xx0时的值的程序框图。解：程序框图如下：

/ 4

开始输入f(x)的系数：a1,a2,a3,a4,a5输入x0n=1v=a5 n=n+1v=v x0+a5-nn≤5是否输出v结束

练习：利用程序框图试编写BASIC程序并在计算机上测试自己的程序。

2.排序

在信息技术课中我们学习过电子表格,电子表格对分数的排序非常简单,那么电子计算机是怎么对数据进行排序的呢? 阅读课本P30—P31面的内容,回答下面的问题:(1)排序法中的直接插入排序法与冒泡排序法的步骤有什么区别?(2)冒泡法排序中对5个数字进行排序最多需要多少趟?(3)在冒泡法排序对5个数字进行排序的每一趟中需要比较大小几次? 游戏:5位同学每人拿一个数字牌在讲台上演示冒泡排序法对5个数据4,11,7,9,6排序的过程,让学生通过观察叙述冒泡排序法的主要步骤.并结合步骤解决例3的问题.例3 用冒泡排序法对数据7,5,3,9,1从小到大进行排序

/ 4

练习:写出用冒泡排序法对5个数据4,11,7,9,6排序的过程中每一趟排序的结果.例4 设计冒泡排序法对5个数据进行排序的程序框图.解: 程序框图如下:

开始输入a1,a2,a3,a4,a5r=1i=1ai>ai+1是否x=aiai=ai+1ai+1=xi=i+1r=r+1i=5否是r=5否是输出a1,a2,a3,a4,a5结束思考:直接排序法的程序框图如何设计?可否把上述程序框图转化为程序? 练习:用直接排序法对例3中的数据从小到大排序 3.小结:(1)秦九韶算法计算多项式的值及程序设计

(2)数字排序法中的常见的两种排序法直接插入排序法与冒泡排序法(3)冒泡法排序的计算机程序框图设计

/ 4

篇2：算法案例优秀教案

第1课时辗转相除法与更相减损术、秦九韶算法

一、教学目标：

根据课标要求：在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序三种不同方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力。制定以下三维目标：

1、知识与技能

理解算法案例的算法步骤和程序框图.2、过程与方法：

引导学生得出自己设计的算法程序.3、情感态度与价值观：

体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.二、重点与难点：

重点：引导学生得出自己设计的算法步骤、程序框图和算法程序.解决策略：通过分析解决具体问题的算法步骤来引导学生写出算法，根据算法画出程序框图，再根据框图用规范的语言写出程序。

难点：体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.解决策略：让学生能严谨地按照自己是程序框图写出程序。

三、学法与教学用具：

1、学法：直观感知、操作确认。

2、教学用具：多媒体。

四、教学过程

（一）引入课题

大家喜欢打乒乓球吧，由于东、西方文化及身体条件的不同，西方人喜欢横握拍打球，东方人喜欢直握拍打球，对于同一个问题，东、西方人处理问题方式是有所不同的.在小学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.当两个数公有的质因数较大

时（如与6 105），使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法——辗转相除法与更相减损术,由此可以体会东、西方文化的差异.（二）研探新知

（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 例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.前面我们学习了辗转相除法与更相减损术，现在我们来学习一种新的算法：秦九韶算法.（1）怎样求多项式f(x)=x+x+x+x+x+1当x=5时的值呢？

一个自然的做法就是把5代入多项式f(x)，计算各项的值，然后把它们加起来，这时，我们一共做了1+2+3+4=10次乘法运算，5次加法运算.另一种做法是先计算x的值，然后依次计算x·x，（x·x）·x，（（x·x）·x）·x的值，这样每次都可以利用上一次计算的结果，这时，我们一共做了4次乘法运算，5次加法运算.第二种做法与第一种做法相比，乘法的运算次数减少了，因而能够提高运算效率，对于计算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以采用第二种做法，计算机能更快地得到结果.（2）上面问题有没有更有效的算法呢？我国南宋时期的数学家秦九韶（约1202~1261）在他的著作《数书九章》中提出了下面的算法：

把一个n次多项式f(x)=anx+an-1x+„+a1x+a0改写成如下形式： f(x)=anx+an-1x+„+a1x+a0 =（anx+an-1x+„+a1）x+ a0 =（（anx+an-1x+„+a2）x+a1)x+a0 =„

=（„（（anx+an-1）x+an-2）x+„+a1）x+a0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1=anx+an-1，然后由内向外逐层计算一次多项式的值，即 v2=v1x+an-2，n-2n-3n-1n-2nn-1n

n-1

222

5432

v3=v2x+an-3，„

vn=vn-1x+a0，这样，求n次多项式f（x）的值就转化为求n个一次多项式的值.上述方法称为秦九韶算法.直到今天，这种算法仍是多项式求值比较先进的算法.（3）计算机的一个很重要的特点就是运算速度快，但即便如此，算法好坏的一个重要标志仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论的算法.例3 已知一个5次多项式为f（x）=5x+2x+3.5x-2.6x+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，我们可以得到下面的公式：

32v0an, vvxa(k1,2,,n).k1nkk这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现.算法步骤如下：

第一步，输入多项式次数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

（四）随堂练习P45 练习1、2

（五）归纳总结

（1）用辗转相除法求最大公约数.（2）用更相减损术求最大公约数.（3）.秦九韶算法的方法和步骤.以及计算机程序框图.（六）作业布置

1、P48习题1.3 A组1、2

2、完成课后巩固作业

（八）五、教学反思：

_________________________________________________________ ___________________________________________________________________________________________________________________________________________________________________________

_________________________________________________________

1.3 算法案例第2课时进位制

一、教学目标：

根据课标要求：掌握不同进制之间的相互转化，会用程序描述不同进制之间的转化，体会数学的转化思想，制定以下三维目标：

1、知识与技能

学生理解各种进位制与十进制之间转换的规律，会利用十进制与各种进制之间的联系进行各种进位制之间的转换。

2、过程与方法

学生经历得出各种进位制与十进制之间转换的规律的过程，进一步掌握进位制之间转换的方法。

3、情感、态度与价值观

学生通过合作完成任务后，领悟十进制，二进制的特点，了解计算机的电路与二进制的联系，进一步认识到计算机与数学的联系，培养他们的合作精神和严谨的态度。

二、教学重点、难点

重点：各进位制之间的转换。

解决策略：让学生弄懂各进位制的特点和联系，再搭配习题讲解。难点：“除k取余法”的理解。

解决策略：先给出具体的例子讲解，再延伸到一般的情况。

三、学法与教学用具

1、学法：讲授法、归纳法、讨论法。

2、教学用具：多媒体，投影仪

四、教学过程

（一）引入课题

在日常生活中，我们最熟悉、最常用的是十进制，据说这与古人曾以手指计数有关，爱好天文学的古人也曾经采用七进制、十二进制、六十进制，至今我们仍然使用一周七天、一

年十二个月、一小时六十分的历法.今天我们来学习一下进位制.（二）研探新知

进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制等等.也就是说：“满几进一”就是几进制，几进制的基数（都是大于1的整数）就是几.在日常生活中，我们最熟悉、最常用的是十进制，据说这与古人曾以手指计数有关，爱好天文学的古人也曾经采用七进制、十二进制、六十进制，至今我们仍然使用一周七天、一年十二个月、一小时六十分的历法.十进制使用0 ~9十个数字.计数时，几个数字排成一行，从右起，第一位是个位，个位上的数字是几，就表示几个一；第二位是十位，十位上的数字是几，就表示几个十；接着依次是百位、千位、万位„„

例如：十进制数3 721中的3表示3个千，7表示7个百，2表示2个十，1表示1个一.于是，我们得到下面的式子： 3 721=3×10+7×10+2×10+1×10.与十进制类似，其他的进位制也可以按照位置原则计数.由于每一种进位制的基数不同，所用的数字个数也不同.如二进制用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×2+1×2+0×2+0×2+1×2+1×2，7 342（8）=7×8+3×8+4×8+2×8.非十进制数转换为十进制数比较简单，只要计算下面的式子值即可： anan-1„a1a0(k)=an×k+an-1×k+„+a1×k+a0.第一步：从左到右依次取出k进制数anan-1„a1a0(k)各位上的数字，乘以相应的k的幂，k的幂从n开始取值，每次递减1，递减到0，即an×k,an-1×k,„,a1×k,a0×k；第二步：把所得到的乘积加起来，所得的结果就是相应的十进制数.关于进位制的转换，教科书上以十进制和二进制之间的转换为例讲解，并推广到十进制和

10nn-1321

543210321

其他进制之间的转换.这样做的原因是，计算机是以二进制的形式进行存储和计算数据的，而一般我们传输给计算机的数据是十进制数据，因此计算机必须先将十进制数转换为二进制数，再处理，显然运算后首次得到的结果为二进制数，同时计算机又把运算结果由二进制数转换成十进制数输出.1°十进制数转换成非十进制数

把十进制数转换为二进制数，教科书上提供了“除2取余法”，我们可以类比得到十进制数转换成k进制数的算法“除k取余法”.2°非十进制之间的转换

一个自然的想法是利用十进制作为桥梁.教科书上提供了一个二进制数据与16进制数据之间的互化的方法，也就是先由二进制数转化为十进制数，再由十进制数转化成为16进制数.（三）范例分析

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

i-1i-1

i-154

程序：

INPUT “a,k，n=”；a，k，n b=0 i=1 t=a MOD 10 DO b=b+t*k^（i-1）a=a10 t=a MOD 10 i=i+1 LOOP UNTIL i＞n PRINT b END 例3 把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×（2+1）+1）+0）+0）+1 =„=1×2+0×2+1×2+1×2+0×2+0×2+1×2 =1 011 001(2).这种算法叫做除2取余法，还可以用右边的除法算式表示：

把上式中各步所得的余数从下到上排列，得到89=1 011 001(2).上述方法也可以推广为把十进制数化为k进制数的算法，称为除k取余法.6543

例4 设计一个程序，实现“除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=ak r=a MOD k b=b+r*10^i i=i+1 a=q LOOP UNTIL q=0 PRINT b END

（四）随堂练习

1、将十进制数34转化为二进制数．解：

即34(10)=100 010(2)

2、把1 234(5)分别转化为十进制数和八进制数．解：1 234(5)=1×5+2×5+3×5+4＝194．则1 234(5)=302(8)

所以，1 234(5)=194＝302(8)

点评：本题主要考查进位制以及不同进位制数的互化．五进制数直接利用公式就可以转化为十进制数；五进制数和八进制数之间需要借助于十进制数来转化．

32（五）归纳总结

（1）理解算法与进位制的关系.（2）熟练掌握各种进位制之间转化.（六）作业布置

1、习题1.3A组3、4.2、完成课后巩固作业

（九）五、教学反思：

篇3：算法案例优秀教案

本节教学内容选自广东教育出版社信息技术选修模块教材《算法与程序设计》。面对初学程序和算法的高中二年级学生而言, 本节内容偏理论、较抽象。如果直接讲算法, 学生很难建立新旧知识的联系, 更难真正理解算法的含义。笔者遵循认知规律, 从学生的感性认识入手, 从他们的兴趣出发, 通过对现实生活具体问题的讨论, 使他们明白解决任何问题都需要有清晰的解决思路和步骤, 很自然地引入了算法的概念;学生独立进行算法设计的实践环节, 有利于学生从生活算法设计中的思维模式向计算机算法设计 (描述) 的转变, 更有利于学生接受和理解下一节的“计算机解决问题的过程”和“程序设计语言”。

一、教学目标

知识与技能:理解算法的概念及其特征;能够理论联系实际, 初步利用算法解决简单的问题;培养自我探索信息、高效获取信息、分析评价信息、处理运用信息、表达呈现信息的能力, 进一步提高信息素养。

过程与方法:培养发现旧知识的规律、方法和解决问题的思路, 并把它运用到新知识中去。

情感、态度与价值观:通过算法与算法设计在日常生活中的实际应用, 启发思维, 养成主动探究问题、解决问题的思维习惯, 从而解决生活中的现实问题。

二、教学重点、难点

重点:理解算法的概念及其特征。

难点:算法设计思想及实践。

三、教学过程

1. 创设情境

师:大家在生活中会碰到许多困难和问题。当遇到问题时, 你会怎么办?

生:解决问题。

师:对。从遇到问题到解决问题, 中间要经历哪些步骤?

生:分析问题→找出解决问题的方法→解决问题。

师:很好。比如说, 早上谁叫你起床?

生:闹钟、别人或生物钟。

师:这些都是解决“早上起床”这个问题的方法。培根的《论读书》说:“读史使人明智。”就让我们来看看古人在遇到实际问题时是怎样解决的。思考一下, 我们能从中受到怎样的启发。

问题一:曹冲称象 (略)

问题二:田忌赛马 (略)

2. 得出算法概念

师:通过对上述问题的分析, 我们对算法有了一个初步的了解。在解决某些问题时, 需要设计出一系列可操作或可计算的步骤, 通过实施这些步骤来解决问题, 通常把这些方法和步骤称为解决问题的算法。

师生得出概念:为了解决某一问题而采取的方法和步骤, 就称之为算法。算法设计分两部分内容:一是找方法;二是描述实现方法的步骤。

师:做任何事情都有一定的步骤。例如刚才我们提到的“早上起床”的问题, 如果采用的方法是闹钟, 那么步骤是先调好时间, 再打开开关。等时间到了, 闹钟就响。又如描述太极拳动作的图解, 就是太极拳的算法。再如一首歌的乐谱, 也可以称之为该歌曲的算法。推而广之, 厨师的菜谱实际上也是一个算法。

3. 师生探讨

问题三:数学问题

问题详述:使用一根长度为L厘米的铁丝, 制作一个面积为S平方厘米的矩形框, 要求计算该矩形框的高h和宽w。

【解题方法】

【步骤】

第一步:输入数据L、S;

第二步:判断d=L 2-1 6 S;

第三步:根据d的取值范围, 计算公式;

第四步:输出运算结果。

4. 算法的特征

根据问题三, 师生归纳算法的特征如下:

有穷性:一个算法必须保证它的执行步骤是有限的、能终止的。

确定性:算法中的每个步骤必须有确切的含义, 不应该是含糊的、模棱两可的。

可行性:算法的每一步都应当能有效地执行, 并得到确定的结果。

输入:有0个或多个输入。

输出:有1个或多个输出。

5. 分组活动

问题四:过河游戏

问题详述：有三个牧师和三个野人过河，牧师和野人都会撑船，他们都要到河的对岸。只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有被吃掉的危险。你能不能找出一种安全的渡河方法呢?请写一写你的渡河方案(如图 1 )。

学生分组讨论回答, 并上讲台演示。

【方法】:确保在河的任意一边 (包括船上和岸上) 的牧师人数大于或等于野人的人数。

【步骤】

第一步:两个野人先过河, 一个野人回来;

第二步:再两个野人过河, 一个野人回来;

第三步:两个牧师过河, 一个野人和一个牧师回来;

第四步:两个牧师过河, 一个野人回来;

第五步:两个野人过河, 一个野人回来;

第六步:两个野人过河。

师:从事各种工作和活动, 都要事先想好解决问题的方法和工作的步骤, 然后按部就班地进行, 这样就可以避免产生错误。

问题五:“烧水泡茶”的算法

【方法与步骤】

师:在数学、物理、化学的各种习题中, 我们经常遇到一题多解的现象。在处理此类问题时, 要注意从多种正确解法中寻找最简单、最快捷的解法, 这就是我们算法中的最优算法了。

6. 巩固运用

练习:货场上堆放着直径为d厘米的钢管, 请设计一个算法, 根据这堆钢管的层数n, 计算并输出这堆钢管的高度h (如图2) 。

教师让学生在黑板上写出自己的解题答案, 并在讲台上说出自己的解题思路:如何分析问题, 得出解决问题的方法, 并描述如何实现方法的步骤。

学生根据题意, 找出方法:

【步骤】

第一步:输入数据n、d;

第二步:计算

第三步:输出运算结果。

7. 回顾小结思考拓展

师生共同回顾算法的概念以及特征, 教师留下问题让学生进行拓展思考。

师:你还有别的称大象的方法吗, 你的方法比曹冲的好吗?这节课, 我们学了如何进行算法设计 (方法和步骤) , 那么计算机是怎样解决问题的呢?

四、教学反思

篇4：算法案例

1. 二分法

从循环结构的角度来看，二分法是通过精确度来控制循环体，只有达到所规定的精确度之后才结束循环，否则就继续下去.

例1 写出用“二分法”求方程[x2-2=0]（[x>0]）的近似解的算法.

解析算法步骤：

第一步，令[f(x)=x2-2]，给定精度[d].

第二步，确定区间[[a,b]]，满足[f(a)f(b)<0].

第三步，取区间中点[m=a+b2].

第四步，若[f(a)f(m)<0]，则含零点的区间为[[a,m]]；否则，含零点的区间为[[m,b]]，将新得到的含零点的区间仍记为[[a,b]].

第五步，判断[[a,b]]的长度是否小于[d]或[f(m)]是否等于0. 若是，则[m]为方程的近似解；否则，返回第三步.

点拨二分法是求解方程近似解的经典算法，其实质就是通过选取区间的中点，利用逼近思想不断缩小方程的解所在的区间，直到符合给定精度为止. 要弄清二分法的思想，就必须明确二分法算法的原理，二分法的原理可以理解为两点. 第一，已知函数[f(x)]，其区间是[[a,b]]，若[f(a)f(b)<0]，则函数[f(x)]在区间[[a,b]]上至少存在一个零点；第二，就是利用精度[d]来控制循环体，当[a-bd]时，整个循环结束，得到方程的近似解. 只有明确这样的原理之后，才能更好地理解、掌握、使用二分法.

2. 辗转相除法

辗转相除法最早出现在公元前300年的古希腊作家欧几里得的《几何原本》中，也称为欧几里得算法，是算法中出现最早的. 最初它只用于求两个正整数的最大公约数，后来被推广到数学的其它领域.

例2 利用辗转相除法求两个正整数的最大公约数.

解析算法步骤：

第一步，给定两个正整数[m，n].

第二步，计算[m]除以[n]所得余数[r].

第三步，[m=n，n=r].

第四步，若[r=0]，则[m，n]的最大公约数等于[m]；否则返回第二步.

点拨辗转相除法的原理是：对于给定的整数[a]和[b]，若[ab]，则[a=qb+r]，此时[(a，b)=(b，r)]，即[a]和[b]的最大公约数与[b]和[r]（[r]为[a]除以[b]的余数）的最大公约数是相等的.辗转相除法渗透着算法中变量赋值与循环结构中对循环体的控制两大难点.

3. 更相减损术

更相减损术是《九章算术》的一种求两个整数最大公约数的算法，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”更相减损术本来是用于分数约分的，但是也用其求两个整数的最大公约数.

例3 利用更相减损术求两个正整数的最大公约数.

解析算法步骤：

第一步，任意给定两个正整数，判断他们是否都是偶数. 若是，用2约简；若不是，执行第二步.

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以较大的数减较小的数.继续这个操作，直到所得的数相等为止，则这个数或这个数与约简数的乘积就是所求的最大公约数.

点拨更相减损术与辗转相除法，从算法思想的角度看，两者在本质上是一致的；从运算形式的角度看，辗转相除法所采用的运算是“除”，而“更相减损术”所采用的运算是“减”；从结果形式的角度看，辗转相除法的最终结果以余数为0来体现，而更相减损术以减数与差相等来体现.虽然更相减损术和辗转相除法在原理上是一致的，对于这两种算法，程序都是通过循环结构来实现的，但是若考虑计算效率，二者却各有利弊.

4. 秦九韶算法

秦九韶算法是我国南宋时期的数学家秦九韶提出的，它是一种多项式求值的计算方法，通过递推变换，将一元[n]次多项式的求值问题转化成[n]个一次式加法运算，从而简化计算难度的算法. 即便是计算机飞速发展的现在，在利用计算机对多项式求值时，秦九韶算法仍不失为一种最优算法.

例4 用秦九韶算法求[n]次多项式[f(x)=anxn+][an-1xn-1+]…[+a1x+a0]，当[x=x0]（[x0]是任意实数）时的值.

解析算法步骤：

第一步，输入多项式次数[n]、最高次项的系数[an]和[x]的值.

第二步，将[v]的值初始化为[an]，将[i]的值初始化为[n-1].

第三步，输入[i]次项的系数[ai].

第四步，[v=vx+ai]， [i=i-1].

第五步，判断[i]是否大于或等于0，若是，则返回第三步；否则，输出多项式的值[v].

点拨如果想计算[vk]的值，就必须先求出[vk-1]，因此秦九韶算法的核心思想就是一个递推关系，即[v0=an,vk=vk-1?x+an-k,]（其中[k=1，2，…，n]），通过这种递推关系，使高次多项式求值问题转化成一次多项式求值问题，体现了数学的化归思想，而在算法中要实现递推关系的表达，就要依靠循环结构.秦九韶算法减少了乘法的运算次数，大大提高了运算速度.

5. 进位制

进位制是人们为了计数和运算方便而约定的计数系统.常用的进制有二进制、八进制、十进制、十二进制、十六进制等. 简单地说，几进制就是满几进一，几进制的基数就是几. 进制的基数不同，不同进制之间就可以相互转化.

例5 设计一个算法，把[k]进制数[a]（共有[n]位）化成十进制数[b].

解析算法步骤：

第一步，输入[a，k]和[n]的值.

第二步，将[b]的值初始化为0，[i]的值初始化为1.

第三步，[b=b+aiki-1,i=i+1].

第四步，判断[i>n]是否成立，若成立，则执行第五步；否则，返回第三步.

第五步，输出[b]的值.

篇5：算法案例优秀教案

一、教案背景

1，面向学生：高中

2，学科：数学

3，课时：1 4，学生课前准备：通过阅读课本找出中国古代数学中的算法案例，结合案例，了解一下中国古代主要的数学家和数学著作。

二、教学课题１．知识与技能目标：

（１）了解中国古代数学中求两个正整数最大公约数的算法以及割圆术的算法；

（２）通过对“更相减损之术”及“割圆术”的学习，更好的理解将要解决的问题“算法化”的思维方法，并注意理解推导“割圆术”的操作步骤。２．过程与方法目标：

（１）改变解决问题的思路，要将抽象的数学思维转变为具体的步骤化的思维方法，提高逻辑思维能力；（２）学会借助实例分析，探究数学问题。３．情感与价值目标：

（１）通过学生的主动参与，师生，生生的合作交流，提高学生兴趣，激发其求知欲，培养探索精神；（２）体会中国古代数学对世界数学发展的贡献，增强爱国主义情怀。

三、教材分析

本节为为高中数学人教B版必修三中第一章第三节课，本节课的重点是理解书中介绍的中国古代的三个问题的算法，难点是为算法编写程序。

求最大公约数的更相减损之术

教材对这个算法编好了程序，可让学生通过执行程序来学习体会此算法，注意让学生自主解释此算法的有穷性。欧几里得的辗转相除法也是求最大公约数的有效算法，在实际问题中和抽象代数理论上都有重要应用，它的程序可参看本小节中的探索与研究，可鼓励学生自主编写程序。

割圆术

可以启发学生自己编写算法，和Scilab程序，试验证明，学生对此非常感兴趣秦九韶算法

一方面，这个算法是目前仍在广泛使用（很多文献中称之为霍纳法）；另一方面，秦九韶算法给我们提供了一个比较算法优劣的机会，一般地说，在中学生的程度上比较分析算法的优劣不是容易的事，所以要利用这个机会让学生对算法的优劣性有所体会。

四、教学方法

通过典型实例，使学生经历算法设计的全过程，在解决具体问题的过程中学习一些基本逻辑结构，学会有条理地思考问题、表达算法，并能将解决问题的过程整理成程序框图。

五、教学过程

说明如何导入该课程，主要教学点的设计，知识拓展等。

1、课前任务：

请同学们自己查一些资料或者上网搜索一些中国古代的数学家以及其主要成就：【百度知道】中国古代数学家

（提前认识一下中国古代的数学成就，激励同学们需要继续努力）

2、课上探讨：

同学们是否知道，我们在小学、初中学到的算术、代数，从记数到多元一次联立方程组以及方程的求根方法，都是我国古代数学家最先创造的，有的比其他国家早几百年甚至上千年，我们人民在长期的生活、生产和劳动过程中，创造了整数、分数、小数、正负数及其计算，以及无限逼近任意实数的方法，在代数学、几何学方面，我国在宋、元之前也都处于世界前列，更为重要的是我国古代数学的发展有着自己鲜明的特色，走着与西方完全不同的道路，在今天看来这条道路仍然有很大的优越性。这条道路的一个重要特色就是“寓理于算”，也就是本节中所讲的要把解决问题“算法化”。下面我们举一些我国古代数学中算法的例子，让同学们更进一步体会“算法”的概念，看一看中国古代数学家的伟大成就和显著特色。

下面就中国古代的数学成就，结合算法的知识，主要了解一下下面三个方面的内容：求两个正整数最大公约数的算法、割圆术和秦九韶算法。

一、求两个正整数最大公约数的算法：更相减损之术

我们知道，如果整数a能被整数b整除，则b称为a的一个约数，一个整数可能有好几个约数。例如，12能被1,2,3,4,6,12整除，这6个数都是12的约数。16的有1,2,4,8,16这5个约数。我们看到2和4，既是12的约数，又是16的约数，2和4叫做12和16的公约数，公约数2和4中，4最大，4称作12和16的最大公约数。如何找到一种算法，对任意两个正整数都能求出它们的最大公约数呢？下面给出我国古代数学家的一个算法，这个算法被称做“更相减损之术”。

【百度百科】更相减损之术

http://baike.baidu.com/view/1431259.htm（了解更相减损之术的出处，开拓知识容量）

我们以求16,12这两个数的最大公约数为例加以说明。用两个数中较大的数减去较小的数，即16-12=4，用差数4和最小的数12构成新的一对数，对这一对数再用大数减小数，以同样的操作一直做下去，知道产生一对相等的数，这个数就是最大公约数。整个操作如下： 4是12和16的最大公约数。

这种算法的道理何在？不难看出，对任意两个数，每次操作后所得的两个数与前两数具有相同的最大公约数，而两数的值逐渐减少，经过有限步地操作后，总能得到相等的两个数，即求得两数的最大公约数。例1：求78和36的最大公约数。解：

这种算法，只做简单的减法，操作方便、易懂，也完全符合算法的要求，它完全是机械的运算，据此很容易编出程序，在计算机上运算，把这个算法与我们下面探索与研究中介绍的欧几里德算法比较，看看这个算法的优越性。下面是我们用Scilab编出的程序，供大家参考。实际上，你可用你在信息技术课上学到的任一种程序设计语言编出程序，从中体会一下这个算法的优越性。为了方便叙述，我们称这种算法为“等值算法” 用等值算法求最大公约数的程序： a=input(“please give the first number”);b=input(“please give the second number”);while a<>b

if a>b

a=a-b

else

b=b-a

end end print(%io2(2),a,b)

把这个程序保存成文件，可随时调入Scilab界面运行，求任意两个正整数的最大公约数。课后任务：

【百度百科】九章算术

【百度百科】刘徽

【百度百科】辗转相除法

（增加知识容量）

二、割圆术

我国魏晋时期的数学家刘徽，他在注《九章算术》中采用正多边形面积逐渐逼近圆面积的算法计算圆周率，用刘徽自己的原话就是“割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体而无所失矣。”他的思想后来又得到祖冲之的推进和发展，计算出圆周率的近似值在世界上很长时间里处于领先地位。

刘徽从圆内接正六边形开始，让边数逐次加倍，逐个算出这些圆内接正多边形的面积，从而得到一系列逐渐递增的数值，来一步一步地逼近圆面积，最后求出圆周率的近似值。可以想象在当时需要付出多么艰辛的劳动，现在让我们用刘徽的思想，使用计算机求圆周率的近似值，计算机最大的特点是运算速度快，只要我们将运算规律告诉计算机，计算机会迅速得到所求的答案。

我们先对单位圆内接正六边形、正十二边形、正二十四边形„„的面积之间的关系进行分析，找出它们之间的递增规律。

【百度图片】刘徽割圆的弧田图

如上图所示，假设圆的半径为1，面积为S，圆内接正n边形面积为，边长为，边心距为，根据勾股定理。

正2n边形的面积为正n边形的面积再加上n个等腰三角形的面积和，即 ①

正2n边形的边长为。

刘徽割圆术还注意到，如果在内接n边形的每一边上，做一高为CD的矩形，就可得到

这样我们就不仅可计算出圆周率的不足近似值，还可计算出圆周率的过剩近似值。

正六边形的面积开始计算，即n=6，则正六边形的面积。用上面的公式①重复计算，就可得到正十二边形、正二十四边形„„的面积。因为圆的半径为1，所以随着n的增大，的值不断趋近于圆周率，这样不断计算下去，就可以得到越来越精密的圆周率近似值。下面我们根据刘徽割圆术的算法思想，用Scilsb语言写出求的不足近似值程序： n=6 x=1 s=6*sqrt(3)/4 for i=1:1:5

h=sqrt(1-(x/2)^2)

s=s+n*x*(1-h)/2

n=2*n

x=sqrt((x/2)^2+(1-h)^2)end print(%io(2),n,s)

运行程序，当边数为192时，就可以得到刘徽求的的圆周率的近似值3.14，当边数为24576时，就得到了祖冲之计算的结果3.1415926.由于是用圆内接正多边形逼近圆，因而得到的圆周率总是小于的实际值。作为练习，请同学们编出程序求作为的过剩近似值。课后任务

【百度文库】祖冲之和圆周率 http://wenku.baidu.com/view/f5e8cfc789eb172ded63b7c7.html

三、秦九韶算法

【百度百科】秦九韶http://baike.baidu.com/view/18635.htm

已知一个一元n次多项式函数，当，我们可按顺序一项一项地计算，然后相加，求得。下面看看我们宋代（约13世纪）大数学家秦九韶是如何计算多项式函数值的。

让我们以5次多项式函数为例加以说明。设

首先，我们把这个多项式一步一步的进行改写：

上面的分层计算，只用了小括号，计算时，首先计算最内层的括号，然后由内向外逐层计算，知道最外层的一个括号，然后加上常数项。

这种算法与直接算法比较，有什么有什么优越性呢？首先，这种算法一共做了5次乘法，5次加法，与直接计算相比较大大节省了乘法的次数，是计算量减少，并且逻辑结构简单。

对任意一元n次多项式，类似的叙述如下：

上面的方法，现在大家称它为秦九韶方法。直到今天，这种算法仍是世界上多项式求值的最先进的算法。

这种方法的计算量仅为：乘法n次，加法n次。我们看看其他算法的计算量。

用直接求和法，直接计算多项式各项的值，然后把他们相加。可知乘法的次数为，加法次数为n。

逐项求和在直接求和法的基础上做了改进，先把多项式写成的形式，这样多项式的每一含x的幂的项都是与的乘积（k=1,2,3，„„，n），在计算

项时把的值保存在变量c中，求项时只须计算，同时把的值存入c中，继续下一项的运算，然后把这n+1项的值相加。

容易看出逐项求和法所用乘法的次数为2n-1，加法次数为n，当时，通过上面的比较，我们可看到秦九韶算法比其他算法优越得多。

3、课堂小结：

本节主要学习了中国古代的三个算法问题：更相减损之术求两个正整数的最大公约数、割圆术求圆周率和秦九韶求一元n次多项式的值，重点在于这三种方法的应用，难点就是如何去编制算法语言，主要以了解为主。

4、当堂练习：

⑴.下面各组关于最大公约数的说法中不正确的是（C）

A.80与36的最大公约数是4

B.294与84的最大公约数是42 C.85与357的最大公约数是34

D.228与741的最大公约数是57 ⑵.我国数学家刘徽采用正多边形面积逐渐逼近圆面积的计算方法来求圆周率，其算法的特点为（C）A.运算速率快

B.能计算出的精确值

C.“内外夹逼”

D.无限次地分割 ⑶.用秦九韶算法求多项式的值时，应把变形为（D）A.B.C.D.⑷.用更相减损之术求81与135的最大公约数时，要进行

次减法运算。

5、课后作业

⑴.145与232的最大公约数是（）A.145

B.19

C.29

D.32 ⑵.用秦九韶算法计算多项式在时的值时，的值为（）A.-845

B.220

C.-57

D.34 ⑶.用圆内接正多边形逼近圆，因而得到的圆周率总是（）的实际值 A.大于等于

B.小于等于

C.等于

D.小于

⑷.已知一个5次多项式，用秦九韶算法求当时，多项式的值，可把多项式写成如下的形式

。⑸求两个数51与85的最大公约数及最小公倍数。

⑹（创新应用）

《孙子算经》有这样一道题目：“今有百鹿入城，家取一鹿不尽，又三家共一鹿适尽，问城中家几何？”你能设计一个程序解决这个问题吗？

六、教学反思

算法是中国古代数学的优良传统.《九章算术》及其刘徽开创了中国传统数学构造性和机械化的算法模式.中国传统数学以算为主、以术为法的算法体系,同古希腊以《几何原本》为代表的逻辑演绎和公理化体系异其旨趣,在数学历史发展的进程中争雄媲美,交相辉映.吴文俊先生提出,数学机械化思想贯穿于中国传统数学,数学机械化思想是我国古代数学的精髓.他分析了中国传统数学的光辉成就在数学科学进步历程中的地位和作用.明确指出,源于西方的公理化思想和源于中国的机械化思想,对于数学的发展都发挥了巨大作用,理应兼收并蓄.现代计算机科学是算法的科学,它所需的数学方法,与《九章算术》中传统的方法体系若合符节.吴文俊先生正是吸取了中国古代数学的思想精华,创立几何定理的机器证明方法,用现代的算法理论,焕发了中国古代数学的算法传统,开创了数学机械化的新纪元。