高二数学必修3 算法案例3 ppt.ppt

* ? 有助于我们全面地理解运算能力 给出一个问题的不同算法，比较这些算法的优劣并作出选择，从而提高效率——真正的运算过程 ? 有利于培养学生的思维能力 将解决具体问题的方法整理成算法的过程是一个条理化、精确化和逻辑化的过程 ? 算法思想是贯穿高中课程的基本思想 例1（第25页例1）孙子问题：“今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二．问物几何？答曰：二十三．” 分析 “孙子问题”相当于求关于x，y，z的 不定方程组 的正整数解． ? 问题背景与分析 第4节 算法案例 算法案例 10 m←2 20 If mod(m, 3)≠2 then 70 30 If mod(m, 5)≠3 then 70 40 If mod(m, 7)≠2 then 70 50 Print m 60 Goto 90 70 m←m + 1 80 Goto 20 90 End N Y 输出m mod(m, 3)≠2 m←m + 1 m←2 mod(m, 5)≠3 mod(m, 7)≠2 Y Y N N ? 流程图与伪代码 第4节 算法案例 算法案例 10 m = 2 20 If m Mod 3 2 then 70 30 If m Mod 5 3 then 70 40 If m Mod 7 2 then 70 50 MsgBox 不定方程的一个解为 m 60 Goto 90 70 m = m + 1 80 Goto 20 90 End ? Excel VBA-1 第4节 算法案例 例2 求两个整数a和b的最大公约数——欧几里得辗转相除法。 ? 问题背景与分析 分析 求出列数： a，b，r1，r2，…，rn – 1，rn，0． 这列数从第三项开始，每项都是前两项相除所得的余数，余数为0的前一项rn即是a和b的最大公约数．这种方法称为“欧几里得辗转相除法”． 第4节 算法案例 ? 流程图与伪代码 10 Read a, b 20 r←mod(a，b) 30 a←b 40 b←r 50 If r ? 0 then 20 60 Print a 70 End 输出a a←b N r = 0 Y 输入a,b r←mod(a,b) b←r 第4节 算法案例 算法案例 a = InputBox(输入第一个自然数) b = InputBox(“输入第二个自然数) Do r = a Mod b a = b b = r Loop until r = 0 MsgBox 最大公约数为 a ? Excel VBA 第4节 算法案例 例3 用二分法求方程x3 - x - 1 = 0在区间 [1,1.5] 内的一个近似解（误差不超过0.001）。 ? 问题背景与分析 第一步 确定有解区间[a, b] 第二步 取[a, b]的中点 第三步 计算函数在中点处的函数值 第四步 判断中点处函数值是否为0 第五步 判断新的有解区间的长度是否小于 给定的误差 第4节 算法案例 ? 流程图与伪代码 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 70 b←x0 80 Else 90 a←x0 100 End if 110 If |a – b|≥c then Goto 20 120 Print x0 N 输出x0 x0←(a+b)/2 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 N Y Y N 第4节 算法案例 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 90