第11课时5.4 算法案例
重点难点
重点：通过案例分析，体会算法思想，熟练算法设计，进一步理解算法的基本思想，发展有条理的思考和表达能力，提高逻辑思维能力。
难点：在分析案例的过程中设计规范合理的算法
学习要求
1．理解剩余定理的内涵
2．能利用剩余定理解决“韩信点兵—孙子问题”
【课堂互动】
历史背景：
韩信是秦末汉初的著名军事家，据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数。
韩信先令士兵排成3列纵队，结果有2人多余；接着他立刻下令将队形改为5列纵队，这一改，又多出3人；随后他又下令改为7列纵队，这一次又剩下2人无法成整行。韩信看此情形，立刻报告共有士兵2 333人。
众人都愣了，不知韩信用什么办法清点出准确人数的。
这个故事是否属实，已无从查考，但这个故事却引出一个著名的数学问题，即闻名世界的“孙子问题”。
这种神机妙算，最早出现在我国《算经十书》之一的《孙子算经》中，原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。”
所以人们将这种问题的通用解法称为“孙子剩余定理”。
【分析】
“孙子问题”相当于求关于x，y，z的不定方程组
的正整数解。
根据题意，m应该满足三个条件：
（1）m被3除后余2，即
（2）m被5除后余3，即
（3）m被7除后余2，即
在自然数中可能存在满足条件的数，首先让m=2开始检验条件，若三个条件中有任何一个不满足，则检验下一个数，即m递增1，如此循环下去，一直到m满足三个条件为止。
这种解决问题的方法也称为“穷举法”，这种方法在利用计算机解决问题时非常有效，因为计算机最擅长重复机械的操作。
【流程图】
【伪代码】
【思考】
上述算法只能求出最小的满足条件的数，如果要求出10个满足条件的数，程序要做何修改？
你能否用数学上最小公倍数的知识分析出解决该问题的方法吗？
可以这样考虑：5和7的公倍数中能被3除余2的最小的公倍数是35；3和7的公倍数中能被5除余3的最小的公倍数是63；3和5的公倍数中能被7除余2的最小的公倍数是30；因此满足条件的其中的一个数就应是35+63+30，为128，若减去3,5,7的最小公倍数105得23，23就是满足题目要求的最小的数。
你能画出这种算法的流程图吗？
【解】算法流程图如下:
经典范例
例1 古今中外，许多人致力于圆周率的研究与计算。我国东汉的数学家刘徽利用“割圆术”计算圆的面积及圆周率。“割圆术”被称为千古绝技，它的原理是用圆内接正多边形的面积去逼近圆的面积。具体计算如下：
在单位圆内作正六边形，其面积记为A1，边长为a1，在此基础上作圆内接十二边形，面积记为A2，边长为a2,……，一直做下去，记该圆的内接正边形面积为，边长为。由于所考虑的是单位圆，计算出的的值即是圆周率的一个近似值，且越大，与圆周率越接近。你能否设计一个算法，计算圆周率的近似值？
思路点拨:画图可知，，.
【解】算法步骤如下：
Read n
a←1
For I From 2 To n
A←
a←sqrt
Print I,A,a
End For
【追踪训练】
1. 是一正整数,对两个正整数,若是的倍数,则称模同余,用符号表示.则中,的取值可能为 ( D )
A.11 B.22 C.27 D.32
2.有一堆围棋子,五个五个地数,最后余下2个；七个七个地数,最后余下3个；九个九个地数,最后余下4个.请设计一种算法,求出这堆棋子至少有多少个.
【解】 算法如下:
m←2
While Mod(m,5)≠2或 Mod(m,7)≠3
或 Mod(m,9)≠4
m←m+1
End While
Print m
3.（李白买酒)无事街上走，提壶去买酒，遇店加一倍，见花喝一斗，三遇店和花，喝光壶中酒．设计求酒壶中原有多少酒的一个算法并写出伪代码．
【解】 算法如下:
x←0
For i from 1 to 3
x←x+1
x←x/2
End for
Print x
4.求方程(其中为自然数)的所有小于100的的正整数解.
【解】 算法如下:
y←0
x←0
While x<100
x←5y+3
Print x
y←y+1
End While
第10课时算法案例（1）
分层训练
1、阅读下列代码，写出该代码的运行结果
t←0
s←0
For i From -5 To 5
t←t+1
s=s+t+i
End For
Print s
答：
2. 用二分法求方程的近似根，精确度为，若用当型循环结构，则终止条件是（ ）
A． B．
C． D．
3、如果以下程序运行后s值是336，
么在程序中until后面的条件应为（ ）
i=8
s=1
Do
s←s×i
i = i -1
Loop Until
A. B.
C. D.
4. 一种放射性物质不断变化为其他物质，每经过一年剩留下来的物质的质量约为原来84%，那么，约经过多少年，剩留的质量是原来的一半？试写出运用二分法计算这个近似值的语句。
5.设计计算两个正整数a，b的最小公倍数的算法。（可以先求出a，b的最大公约数c，那么就是它们的最小公倍数）
6. 已知⊙O，写出求作⊙O的圆心的一个算法。
7. 已知，且，设计一个算法，求出使取最大值时的值。
8. 已知函数，设计一个算法，分别对，时计算的值。
w.w.w.k.s.5.u.c.o.m
【点此下载】