高中1.3 算法与案例教案设计

展开

这是一份高中1.3 算法与案例教案设计

算法案例教学目标：本节通过算法案例的学习，进一步理解算法的含义，掌握算法设计的常用方法.教学重点：如何在伪代码中运用条件语句.教学难点：如何在伪代码中运用条件语句.教学过程：Ⅰ.课题导入1.中国古代数学中算法的内容是非常丰富的，比如，中国古代数学著作《九章算术》中介绍了下述“约分术”：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”给出了求任意两个数的最大公约数的一种算法，被后人称为“更相减损术”.这种方法与欧氏的辗转相除法异曲同工，本质上是相同的.2.中国是研究不定方程最早的国家，公元初的五家共井问题就是一个不定方程组问题，公元5世纪的《张丘建算经》中的百鸡问题标志着中国对不定方程理论有了系统研究.秦九韶的大衍求一术将不定方程与同余理论联系起来.研究不定方程要解决三个问题：①判断何时有解；②有解时决定解的个数；③求出所有的解.二分法是用计算机求解多项式方程的一种常用方法.基本思想是：如果取［a，b］的中点x0=（a+b）/2；若f(x0)=0，则x0就是方程的根，若f(a)f(x0)>0，则解在（x0，b）上，以x0代替a，否则解在（a，x0）之间，以x0代替b，重复上述步骤，直到|a－b|b），求它们的最大公约数.解析：求两个正整数a、b（a>b）的最大公约数，可以归结为求一数列：a，b，r1，r2，…，rn－1，rn，rn+1，0此数列的首项与第二项是a和b，从第三项开始的各项，分别是前两项相除所得的余数，如果余数为0，它的前项rn+1即是a和b的最大公约数，这种方法叫做欧几里得辗转相除法，其算法如下：S1　输入a，b（a>b）；S2　求a/b的余数r；S3　如果r≠0，则将b→a，r→b，再次求a/b的余数r，转至S2；S4　输出最大公约数b.伪代码如下：10　Read a，b20　r←mod（a，b）30　If　r=0　then　Goto 8040　Else50　a←b60　b←r70　Goto 2080　Print b流程图如下：点评：算法的多样性：对于同一个问题，可以有不同的算法.例如求1+2+3+…+100的和，可以采用如下方法：先求1+2，再加3，再加4，一直加到100，最后得到结果5050.也可以采用这样的方法：1+2+3+…+100=（1+100）+（2+99）+（3+98）+…+（50+51）=50×101=5050.显然，对于算法来说，后一种方法更简便，而循环累加更适用于计算机解题.因此，为了有效地进行解题，不仅要保证算法正确，还要选择好的算法，即方法简单、运算步骤少，能迅速得出正确结果的算法.例5：求1734，816，1343的最大公约数.分析：三个数的最大公约数分别是每个数的约数，因此也是任意两个数的最大公约数的约数，也就是说三个数的最大公约数是其中任意两个数的最大公约数与第三个数的最大公约数.解：用“辗转相除法”.先求1734和816的最大公约数，1734=816×2+102；816=102×8；所以1734与816的最大公约数为102.再求102与1343的最大公约数，1343=102×13+17；102=17×6.所以1343与102的最大公约数为17，即1734，816，1343的最大公约数为17.例6：猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一只，第二天照此办法，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？解析：此题粗看起来有些无从着手的感觉，那么怎样开始呢？假设第一天开始时有a1只桃子，第二天有a2只……第9天有a9只，第10天有a10只.在a1，a2，…，a10中，只有a10=1是知道的，现要求a1，而我们可以看出a1，a2，…，a10之间存在一个简单的关系：a9=2×（a10+1），a8=2×（a9+1），a1=2×（a2+1）.也就是：ai=2×（ai+1+1）　i=9，8，7，6，…，1.这就是此题的数学模型.再考察上面从a9，a8直至a1的计算过程，这其实是一个递推过程，这种递推的方法在计算机解题中经常用到.另一方面，这九步运算从形式上完全一样，不同的只是ai的下标而已.由此，我们引入循环的处理方法，并统一用a0表示前一天的桃子数，a1表示后一天的桃子数，将算法改写如下：S1　a1←1；｛第10天的桃子数，a1的初值｝S2　i←9；｛计数器初值为9｝S3　a0←2×（a1+1）；｛计算当天的桃子数｝S4　a1←a0；｛将当天的桃子数作为下一次计算的初值｝S5　i←i－1；S6　若i≥1，转S3；S7　输出a0的值；伪代码如下：10　a1←120　i←930　a0←2×（a1+1）40　a1←a0.50　i←i－160　If　i≥1 then Goto 3070　Else80　Print a0流程图如下：点评：这是一个从具体到抽象的过程，具体方法：（1）弄清如果由人来做，应该采取哪些步骤；（2）对这些步骤进行归纳整理，抽象出数学模型；（3）对其中的重复步骤，通过使用相同变量等方式求得形式的统一，然后简练地用循环解决.Ⅲ.课堂练习课本P30 1，2.Ⅳ.课时小结算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说，就是计算机解题的过程.1.本节通过对解决具体问题过程与步骤的分析（如求两个数的最大公约数），体会算法的思想，进一步了解算法的含义.2.本节通过阅读中国古代数学中的算法案例，如约分术，体会中国古代数学对世界数学发展的贡献.通过学生自己的亲身实践，亲自去解决几个算法设计的问题，才能体会到算法的基本思想.数学的其他内容与算法密切相关，如函数、数列等.我们在学习这些内容时要和算法联系起来Ⅴ.课后作业课本P31 1，3.变式练习1.数4557、1953、5115的最大公约数是（　　）A.31　　 B.93　　 C.217　 D.651答案：B2.下面的伪代码的算法目的是（　　）10　Read x，y20　m←x30　n←y40　If m/n=int（m/n） then Goto 9050　c←m－int（m/n）×n60　m←n70　n←c80　Goto 4090　a←（x×y）/n100 Print aA.求x，y的最小公倍数B.求x，y的最大公约数C.求x被y整除的商D.求y除以x的余数答案：B3.下面的伪代码的算法目的是　　　　.Read　X，YIf X>Y thenPrint XElsePrint YEnd if答案：输出x，y两个值中较大的一个值4.下面的伪代码的算法目的是　　　　.Read　a，b，c，If a>b thent←aa←bb←tElse if a>c thent←aa←cc←tElse if b>c thent←bb←cc←bEnd ifPrint a，b，c答案：输入三个数，要求由小到大的顺序输出5.流程图填空：输入x的值，通过函数y=求出y的值.其算法流程图如下：答案：①x　②1≤x<10　③3x－116.根据下面的流程图写出其算法的伪代码.答案：解：这是计算2+4+6+…+200的一个算法，可以用循环语句表示为T←0For I from 2 to 200 step 2T←T+IEnd for7.输入一个华氏温度，要求输出摄氏温度.公式为C=（F－32）.写出其算法的伪代码.答案：解：这是顺序结构.其伪代码如下：Read FC←（F－32）Print C8.一个小球从100 m高度自由落下，每次落地后反跳回原高度的一半，再落下.设计一个算法，求它在第10次落地时共经过多少米？第10次反弹多高？画出流程图并用伪代码表示.答案：解：这是一个循环结构，可以用循环语句实现.伪代码：S←100H←S/2For n from 2 to10S←S+2×HH←H/2End forPrint S，H流程图：9.用秦九韶算法求多项式f(x)=3x6+12x5+8x4－3.5x3+7.2x2+5x－13当x=6时的值.答案：243168.2.10.区间二分法是求方程近似解的常用算法，其解法步骤为S1　取［a，b］的中点x0=（a+b）/2；S2　若f(x0)=0，则x0就是方程的根，否则若f(a)f(x0)>0，则a←x0；否则b←x0；S3　若|a－b|

相关教案更多