第八课时算法案例.doc

第八课时 算法案例
教学目的:
本节通过算法案例的学习,进一步理解算法的含义，掌握算法设计的常用方法。
教学重点：
如何在伪代码中运用条件语句。
教学难点:
如何在伪代码中运用条件语句。
教学过程：
Ⅰ.课题导入
、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，b
20　r←mod（a，b）
30　If　r=0　then　Goto 80
40　Else
50　a←b
60　b←r
70　Goto 20
80　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只，，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←1
20　i←9
30　a0←2×（a1+1）
40　a1←a0.
50　i←i－1
60　If　i≥1 then Goto 30
70　Else
80　Print a0
流程图如下：
点评：这是一个从详细到抽象的过程，详细方法：
（1）弄清假设由人来做，应该采取哪些步骤;
(2）对这些步骤进展归纳整理,抽象出数学模型;
（3）对其中的重复步骤，通过使用一样变量等方式求得形式的统一，然后简练地用循环解决。
Ⅲ。课堂练习
课本P30 1，2.
Ⅳ。课时小结
，就是计算机解题的过程。
1。本节通过对解决详细问题过程和步骤的分析（如求两个数的最大公约数），体会算法的思想，进一步理解算法的含义.
2。本节通过阅读中国古代数学中的算法案例，如约分术，体会中国古代