《算法案例》学案
- 资源简介:
约1720字。
总 课 题 算法案例 总课时 第 9 课时
分 课 题 算法案例 分课时 第 1 课时
教学目标 通过了解中国古代算法案例,体会中国古代数学对世界数学发展的贡献.
重点难点 通过案例分析,体会算法思想,熟练算法设计.
例题剖析
【案例1】
韩信是秦末汉初的著名军事家,据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什么办法,不要逐个报数,就能知道场上士兵的人数.
韩信先令士兵排成3列纵队,结果有2人多余;接着他立刻下令将队形改为5列纵队,这一改,又多出3人;随后他又下令改为7列纵队,这一次又剩下2人无法成整行.韩信看此情形,立刻报告共有士兵2333人.
众人都愣了,不知韩信用什么办法清点出准确人数的.
这个故事是否属实,已无从查考,但这个故事却引出一个著名的数学问题,即闻名世界的“孙子问题”.
这种神机妙算,最早出现在我国《算经十书》之一的《孙子算经》中,原文是:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?答曰:二十三.”
所以人们将这种问题的通用解法称为“孙子剩余定理”或“中国剩余定理”.
【算法设计思想】
“孙子问题”相当于求关于 的不定方程组 的整数解.
设所求的数为 ,根据题意, 应同时满足下列三个条件:
(1) 被 除后余 ,即 ;
(2) 被 除后余 ,即 ;
(3) 被 除后余 ,即 ;
首先,从 开始检验条件,若 个条件中有任何一个不满足,则 递增 ,当 同时满足 个条件时,输出 .
【流程图】 【伪代码】
【案例2】
写出求两个正整数 的最大公约数的一个算法.
公元前3世纪,欧几里得介绍了求两个正整数 的最大公约数的方法,即求出一列数: ,这列数从第三项开始,每一项都是前两项相除所得的余数(即 ),余数等于 的前一项 ,即是 和 的最大公约数,这种方法称为“欧几里得辗转相除法”.
【算法设计思想】
欧几里得展转相除法求两个正整数 的最大公约数的步骤是:计算出 的余数 ,若 ,则 即为 的最大公约数;若 ,则把前面的除数 作为新的被除数,把余数 作为新的除数,继续运算,直到余数为 ,此时的除数即为 的最大公约数.
求 的最大公约数的算法为:
输入两个正整数 ;
如果 ,那么转 ,否则转 ;
;
;
,转 ;
输出 .
【流程图】 【伪代码】
资源评论
共有 0位用户发表了评论 查看完整内容我要评价此资源