数学3（必修）—— 算 法 ALGORITHM 苏州大学数学科学学院 徐稼红 uuxjh@public1.sz.js.cn.

Presentation on theme: "数学3（必修）—— 算 法 ALGORITHM 苏州大学数学科学学院 徐稼红 uuxjh@public1.sz.js.cn."— Presentation transcript:

1 数学3（必修）—— 算 法 ALGORITHM 苏州大学数学科学学院 徐稼红

2  内容  结构 一、《算法初步》主要内容与结构 算法的含义→流程图→基本算法语句→算法案例 流 程 图 算法的描述 算法 自然语言
顺序结构 选择结构 循环结构 输 语句 伪 代 码 循环语句 赋值语句 条件语句 入出

3  理解算法的含义；  掌握算法的三种基本结构；  会用算法语句解决简单的实际问题。
二、本章教学重点和难点  重点  理解算法的含义；  掌握算法的三种基本结构；  会用算法语句解决简单的实际问题。  难点  循环语句；  算法设计。

4  展开方式  特点 三、教材展开的方式和特点 自然语言 自然语言 流程图 自然语言 流程图 伪代码
自然语言 流程图 伪代码 Excel VBA  特点  螺旋上升、渐次递进  整合渗透、前引后连  三线合一、横向贯通  弹性处理、多样选择

5 第1节 算法的含义 四、内容解析  算法的含义  算法的特点 （广义）完成某项工作的方法和步骤
第1节 算法的含义  算法的含义 （广义）完成某项工作的方法和步骤 （教材）对一类问题的机械的、统一的求解方法 （计算科学）可以用计算机来解决的一类问题的程序和步骤  算法的特点 （教材）有限性、确定性 （其他）输入、输出、可行性、一般性

6 第1节 算法的含义  关于例1 例1 给出求1 + 2 +3 + 4 + 5的一个算法． 算法3？ 算法1 按照逐一相加的程序进行．
第1节 算法的含义  关于例1 例1 给出求 的一个算法． 算法1 按照逐一相加的程序进行． 第一步 计算1 + 2，得到3； 第二步 将第一步中的运算结果3与3相加，得到6； 第三步 将第二步中的运算结果6与4相加，得到10； 第四步 将第三步中的运算结果10与5相加，得到15． 算法2 可以运用公式 … + n = 直接计算。 第一步 取n = 5； 第二步 计算 ； 第三步 输出运算结果。 算法3？

7 第2节 流程图  四种图框类型 输入、输出框 处理框 判断框 起止框
第2节 流程图  四种图框类型 输入、输出框 处理框 判断框 起止框 ● N-S结构化流程图（1973年由美国学者I．Nassi和B．Shneiderman提出，N和S是这两位学者英文姓名的第一个字母）

8 第2节 流程图  三种基本算法结构 i) 顺序结构 ii) 选择结构 A B A B p Y N

9 第2节 流程图  三种基本算法结构 iii) 循环结构 A p Y N A Y N p （直到型） （当型）

10 第2节 流程图  循环结构示例 引例 N 开始 结束 输出该城市 投票 有一城市 得票超过总 票数一半 淘汰得票最少的城市 Y

11 第2节 流程图  循环结构 例4 （P12）求1×2×3×4×5。 开始 T←1 算法2 I←2 S1 T←1； S2 I←2；
第2节 流程图  循环结构 I > 5 N Y T←1 输出T I←2 T←T×I I←I + 1 开始 结束 例4 （P12）求1×2×3×4×5。 算法2 S1 T←1； S2 I←2； S3 T←T × I； S4 I←I + 1． S5 如果I不大于5，重新执行 S3、S4、S5；否则算法结束．

12 第2节 流程图  直到型与当型的转换 例4 I > 5 T←1 输出T I←2 T←T×I I←I + 1 I≤5 T←1 输出T
第2节 流程图  直到型与当型的转换 例4 I > 5 N Y T←1 输出T I←2 T←T×I I←I + 1 I≤5 Y N T←1 输出T I←2 T←T×I I←I + 1 辨别

13 第2节 流程图 学习流程图时学生可能出现的错误： n←3 p←x p←x，y←p，x←y x←y y←p （1）关于输入框 （2）关于处理框
第2节 流程图 学习流程图时学生可能出现的错误： （1）关于输入框 输入n  3 n←3 （2）关于处理框 p←x x←y y←p p←x，y←p，x←y （3）循环结构判断框中的条件

14 第3节 基本算法语句  伪代码  Excel VBA p ← x x ← y y ← p p = x x = y y = p
 赋值语句 第3节 基本算法语句 例1 交换两个变量 x、y 的值  伪代码  Excel VBA p ← x x ← y y ← p p = x x = y y = p  赋值号  x、y、p的值各是多少？

15 第3节 基本算法语句  伪代码  Excel VBA  输入输出语句 例2 输入一个数，输出这个数的绝对值。
第3节 基本算法语句 例2 输入一个数，输出这个数的绝对值。  伪代码  Excel VBA Read a x ← | a | Print x a = Inputbox("请输入一个数") x = Abs(a) Msgbox x  其他输入、输出语句——input，output  英语单词的处理

16 第3节 基本算法语句  伪代码  Excel VBA  条件语句——单行 例3 输入三个数，输出最大数。
第3节 基本算法语句 例3 输入三个数，输出最大数。  伪代码  Excel VBA Read a, b, c x ← a If b > x Then x ← b If c > x Then x ← c Print x a = InputBox("输入a") b = InputBox("输入b") c = InputBox("输入c") x = a If b > x Then x = b If c > x Then x = c MsgBox "最大数" & x

17  算法的实现——条理化、逻辑化、精微化的过程
a = InputBox("输入a"): b = InputBox("输入b") c = InputBox("输入c") x = a If b > x Then x = b: If c > x Then x = c MsgBox "最大数为" & x  分别输入a = 12，b = 9，c = 5时，为什么输出最大数为9？

18 第3节 基本算法语句  伪代码  Excel VBA  条件语句——块 例4 输入x，计算 y = 的值。
第3节 基本算法语句 例4 输入x，计算 y = 的值。  伪代码  Excel VBA Read x If x≥0 Then y ← x2 Else y ← sin x End If Print y x = InputBox("输入一个数") If x >=0 Then y = x^2 Else y = sin(x) End If MsgBox y

19 第3节 基本算法语句  伪代码  Excel VBA  条件语句——嵌套 例5（P19）输入x，计算 y = 的值。
第3节 基本算法语句 例5（P19）输入x，计算 y = 的值。  伪代码  Excel VBA Read x If x > 0 Then y ← 1 Else If x = 0 Then y ← 0 Else y ← -1 End If Print y x = InputBox("输入一个数") If x > 0 Then y = 1 ElseIf x = 0 Then y = 0 Else y = -1 End If MsgBox y

20 第3节 基本算法语句  伪代码  Excel VBA  循环语句——For
第3节 基本算法语句 例6（P21）计算1  3  5  7  …  99。  伪代码  Excel VBA S ← 1 For I From 3 To 99 Step S ← S  I End For Print S S = 1 For I = 3 To 99 Step S = S*I Next I MsgBox S

21 第3节 基本算法语句  伪代码1  伪代码2  循环语句——While
第3节 基本算法语句 例7（P21）求最小的奇数I，使  3  5  7  …  I > 。  伪代码1  伪代码2 S ← 1 I ← 3 While S≤ S ← S  I I ← I End While Print I S ← 1 I ← 1 While S≤ I ← I S ← S  I End While Print I

22 第3节 基本算法语句  Excel VBA-1  Excel VBA-2  循环语句——While
第3节 基本算法语句 例7（P21）求最小的奇数I，使  3  5  7  …  I > 。  Excel VBA-1  Excel VBA-2 S = 1 I = 1 While S <= I = I S = S*I Wend MsgBox I S = 1 I = 1 Do I = I S = S*I Loop Until S> MsgBox I

23 例8（P22、例4）抛硬币试验。  伪代码 s ← 0 Read n For i From 1 To n If Rnd > 0.5 Then s ← s + 1 End For Print 出现正面的频率为s/n

24  Excel VBA s = 0 n = InputBox("输入试验次数") For i = 1 To n If Rnd > 0.5 Then s = s + 1 Next i MsgBox "出现正面的频率为" & s/n

25 第4节 算法案例  问题背景与分析 例1（P25、例1）孙子问题：“今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二．问物几何？答曰：二十三．” 分析 “孙子问题”相当于求关于x，y，z的 不定方程组 的正整数解．

26  流程图  伪代码 m←2 While Mod(m, 3)≠2 或 Mod(m, 5)≠3 或 Mod(m, 7)≠2 m←m + 1
 流程图  伪代码 N Y 输出m Mod(m, 3)≠2 m←m + 1 m←2 或Mod(m, 5)≠3 或Mod(m, 7)≠2 m←2 While Mod(m, 3)≠2 或 Mod(m, 5)≠3 或 Mod(m, 7)≠2 m←m + 1 End While Print m

27  Excel VBA-1 m = 2 While m Mod 3 < > 2 Or m Mod 5 < > Or m Mod 7 < > 2 m = m + 1 Wend MsgBox "不定方程的一个解为" & m

28  Excel VBA-2 m = 1 Do m = m + 1 Loop Until m Mod 3 = 2 And m Mod 5 = 3 _ And m Mod 7 = 2 MsgBox "不定方程的一个解为" & m

29 第4节 算法案例  问题背景与分析 例2（P26）求两个整数a和b的最大公约数——欧几里得辗转相除法。 分析 求出列数：
第4节 算法案例  问题背景与分析 例2（P26）求两个整数a和b的最大公约数——欧几里得辗转相除法。 分析 求出列数： a，b，r1，r2，…，rn – 1，rn，0． 这列数从第三项开始，每项都是前两项相除所得的余数，余数为0的前一项rn即是a和b的最大公约数．这种方法称为“欧几里得辗转相除法”．

30  流程图  伪代码 Read a, b While Mod(a，b)≠0 r←Mod(a，b) a←b b←r End While
 流程图  伪代码 输出b a←b Y N 输入a,b r←Mod(a,b) b←r Mod(a,b)≠0 Read a, b While Mod(a，b)≠0 r←Mod(a，b) a←b b←r End While Print b

31  Excel VBA-1 a = InputBox("输入第一个自然数") b = InputBox("输入第二个自然数") Do
r = a Mod b a = b b = r Loop Until r = 0 MsgBox "最大公约数为" & a

32  Excel VBA-2 a = InputBox("输入第一个自然数") b = InputBox("输入第二个自然数")
While a Mod b < > 0 r = a Mod b a = b b = r Wend MsgBox "最大公约数为" & a

33 第4节 算法案例  问题背景与分析 例3 用二分法求方程x3 - x - 1 = 0在区间 [1,1.5] 内的一个近似解（误差不超过0.001）。 第一步 确定有解区间[a, b] 第二步 取[a, b]的中点 第三步 计算函数在中点处的函数值 第四步 判断中点处函数值是否为0 第五步 判断新的有解区间的长度是否小于 给定的误差

34  流程图  伪代码 10 Read a, b, c 20 x0←(a + b)/2 30 f(a)←a3 – a – 1
 流程图  伪代码 N 输出x0 x0←(a+b) f(x0)=0 输入a,b,c b←x0 f(a)f(x0)<0 |a – b| < c a←x0 f(a)←a3 - a - 1 f(x0)←x03 – x0 – 1 Y 10 Read 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 b←x0 80 Else a←x0 100 End If 110 If |a – b|≥c Then Goto 20 120 Print x0

35  Excel VBA-1 10 a = Val(InputBox("输入区间左端点值"))
20 b = Val(InputBox("输入区间右端点值")) 30 c = Val(InputBox("输入误差点限制")) 40 x0 = (a + b) / 2 50 f1 = a^3 - a - 1 60 f2 = x0^3 - x0 - 1 70 If f2 = 0 Then Goto 140 80 If f1*f2 < 0 Then b = x0 100 Else a = x0 120 End If 130 If Abs(a – b) >= c Then Goto 40 140 MsgBox "方程的近似解为" & x0  Excel VBA-1

36  Excel VBA-2 a = Val(InputBox("输入区间左端点值"))
b = Val(InputBox("输入区间右端点值")) c = Val(InputBox("输入误差限制")) Do x0 = (a + b) / 2 f1 = a^3 - a - 1 f2 = x0^3 - x0 - 1 If f2 = 0 Then Exit do If f1*f2 < 0 Then b = x0 Else a = x0 End If Loop Until Abs(a – b) < c MsgBox "方程的近似解为" & x0  Excel VBA-2

37  Excel VBA-3 a = Val(InputBox("输入区间左端点值"))
b = Val(InputBox("输入区间右端点值")) c = Val(InputBox("输入误差限制")) Do x = (a + b) / 2 If f(x) = 0 Then Exit do If f(a)*f(x) < 0 Then b = x Else a = x End If Loop Until Abs(a – b) < c MsgBox "方程的近似解为" & x  Excel VBA-3

38 谢谢！