高二新课程数学必修（Ⅲ）教案 算法小结复习[上学期]

高二新课程数学必修（Ⅲ）教案
算法小结复习
教学目的：总结算法解题的一般思路，即算法分析（提炼问题的数学本质）——画出程序框图——按框图编写伪代码；通过本章学习增强解题的规范性．
教学重点：在准确理解算法的基础上，掌握流程图的画法及判断；掌握伪代码的编写．
教学过程：
例1．阅读下列伪代码，并指出当时的计算结果：
（1）read a, b (2) read a, b (3) read a, b
X←a+b a←a+b a←a+b
y←a-b b←a-b b←a-b
a←(x+y)/2 a←(a+b)/2 a←(a-b)/2
b←(x-y)/2 b←(a-b)/2 b←(a+b)/2
Print a, b Print a, b Print a, b
a=____,b___ a=____,b___ a=____,b___
例2．写出用二分法求方程在区间内的一个近似解（误差不超过）的一个算法．
说明：此题主要再次强调算法的问题根本上是一个思维的问题以及算法语言的基本规则；如何通过语句的结构形式规范处理及简化问题，
从而增强解题的规范性．
流程图与伪代码
10 Rend a,b,c
20 x0 ←(a+b)/2
30 f(a) ←a3-a-1
40 f(x0) ←x03-x0-1
50 If f(x0)=0 then Goto 120
60 If f(a)f(x0)<0 then
70 b ←x0
80 Else
90 a ←x0
100 End if
110 If |a-b|≧c then Goto 20
120 Print x0
N
以上两例重点理解赋值语句，尤其是在循环结构中如何根据对变量的理解灵活赋值，从而用简炼的语句表示算法。
例3．满足方程的一组正整数称为勾股数或商高数，设计计算某一范围内的勾股数的算法．
For a from 3 to 30
For b from a+1 to 40
For c from b+1 to 50
If a2+b2=c2 then
P a, b, c
End if
End
End
End
例四．已知钱数（不足10元），要把它用于1元、5角、1角、1分的硬币表示，若要用尽量少的硬币个数表示，设计一个算法，求各硬币的个数．
分析：要用尽量少的硬币表示钱数，也就是要尽可能地用大面值的硬币．以1元钱的个数就是的整数部分，记为，则5角钱的个数就是（－）/0.5的整数部分,记为；1角钱的个数就是（－＊1－＊0.5）的整数部分，记为；1分钱的个数就是（－＊1－＊0.5－＊0.1）的整数部分．
解：Read
=int（）
=int（（－）/0.5）
= int（（－＊1－＊0.5）/0.1）
=int（（－＊1－＊0.5－＊0.1）/0.01）
Print ，，，
例五. 在日常生活中，人们经常要把一些记录中的数据排序，如招生录取中按照成绩对考生进行排序，汉字拼音检索中按照字母顺序对汉字进行排序等等。排序就是按照一定的规则，对数据加以排列整理，从而提高查找效率．
（1）直接插入排序法：
（2）冒泡排序法：
现用直接插入排序法对任意输入的n个数进行从小到大的排序，其伪代码程序如下：
Begin
Read n
For i=1 to n
Read a(i)
End For
For i=2 to n
For j=1 to i-1
If a(j)>a(i) Then
m=a(i)
a(i)=a(j)
a(j)=m
End if
End For
End For
For k=1 to n
Print a(k)
End For
End
再用直接冒泡排序法对任意输入的n个数进行从小到大的排序，其伪代码程序如下：
10 Begin
20 Read n
30 For i=1 to n
40 Read a(i)
50 End For
60 For j=1 to n-1
70 w=0
80 For i=1 to n-1
90 If a(i)>a(i+1) Then
100 m=a(i)
110 a(i)=a(i+1)
120 a(i+1)=m
130 w=w+1
140 end if
150 End For
160 If w=0 Then Goto 180
170 End For
180 For k=1 to n
190 Print a(k)
200 End For
210 End
用DO循环语句表示如下：
Begin
Read n
For i=1 to n
Read a(i)
End For
Do
w=0
For i=1 to n-1
If a(i)>a(i+1) Then
m=a(i)
a(i)=a(i+1)
a(i+1)=m
w=w+1
end if
Next i
Loop Until w=0
For k=1 to n
Print a(k)
End For
End
例三与例五及算经中的“百钱百鸡”问题均对循环语句的应用提出更高要求，在算法理解及流程图的设计上思路一定要清晰。
例六．（李白买酒)“无事街上走，提壶去买酒，遇店加一倍，见花喝一斗，三遇店和花，喝光壶中酒”．设计求酒壶中原有多少酒的一个算法并写出伪代码．
S=0
For I from 1 to 3
S←(S+1)/2
End For
Pint S
例七．一个三位数,如果每一位数字的立方和等于它本身,则称之为“水仙花数”．设计一个算法，找出所有的水仙花数，用伪代码表示．
For n from 100 to 999
←int(n/100)
←int((n-100x)/10)
z←n－100－10
If n=3+3+z3 then
Pint n
End If
Next n
End for
例八．一辆邮车依次前往城市Ａ１，Ａ２，Ａ３，…Am（），每到一个城市先卸下前面各城市发往该城市的邮袋1个，然后再装上该城市发往后面各城市的邮袋各1个，
设ｎ是邮车从第ｎ个（1≤n＜m，n∈N* ）城市出发时邮车上邮袋的个数，设计一个算法，对任给两个正数ｍ＞ｎ，求ｎ.
分析:到达第n个城市时,邮袋个数为前一个城市的邮袋个数减去前面城市发往该市的n-1个邮袋，再加上发往后面各城市的（m-n）个邮袋，可用循环计算I从1至ｎ时，ｎ的变化。
解：　伪代码为：
Read m,n
If m≤n then Print“错误！ｍ必须大于ｎ”
Else
S←0
For I from 1 to n
S←S+(m- I)-(I-1)
Next I
End For
End If
Print S
例九．进位制与秦九韶算法
1．用程序把进制数（共有位）转换为十进制数
2．把一个十进制数化为k进制数
Begin
Read a , k
i=1
Do
r=mod(a,k)
a(i)=r
a=(a-r)/k
i=i+1
Loop Until a=0
m=i-1
For j=m to 1 Step -1
Print a(j);
Next j
Prin “(”;k;”)”
End
3．求次多项式当（是任意实数）的值
解析：把次多项式改写如下形式：
发现规律结合所掌握算法，通过模仿，操作，探索，寻找解决问题的通法。]
例十．（焚塔传说）
解析：关键是理解问题发现规律
二、数学构建：
三、知识运用：
四、学力发展：
五、课堂小结：
六、课外作业：
输入a,b,c
输出x0
b←x0
a←x0
f(a)←a3-a-1
f(x0)←x03-x0-1
X0←(a+b)/2
|a-b|f(a)f(x0)<0
f(x0)=0
Y
N
Y
N
Y
结束
开始
Y
N
结束
b←a+1
输出a,b,c
a2+b2=c2
a←3
b←b+1
c←c+1
a←a+1
c←b+1
开始
Y
N
I=I+1
V=v×x0+an-i
V=v0
输出v
I≦n
I=1
输入x0
输入f(x)的系数：
a0 a1 a2 …an
Read a, k, n
I=1
b=0
while i<=n
t=get a(i)
b=b+t*k^(i-1)
i=i+1
end while
print b
a≦30
b≦40
c≦50
Y
Y
Y
N
N
N