专业C 9讲 变量设计ppt课件.pptVIP

本章通过几种不同类型的算法实现，着重讨论算法实现中的变量设计问题，包括函数的参数、局部变量、标志变量的设计与应用。 从本章起，将围绕所谓的“评委评分”程序的设计和优化、程序功能的扩充逐步展开讨论。 本章涉及一些基本算法，这些算法的设计思想是朴素的。 4.1~4.2 穷举、迭代计算 4.1 穷举计算 4.1.1 “百钱买百鸡”问题 4.1.2 判定素数 4.2 迭代计算 4.2.1 牛顿迭代法 4.2.2 级数计算（即：数列求和） 指数函数 正弦函数 4.2.3 最大公因数和最小公倍数 4.1.1 “百钱买百鸡”问题 例4.1 公元前5世纪，我国古代数学家张丘建在《算经》一书中提出了“百鸡问题”： 鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？ 【数学模型】 记x, y, z分别表示购买鸡翁、母、雏的数量，则有 这是一个不定方程，数学方法求解有较大难度。 4.1.1 “百钱买百鸡”问题 【算法设计】 显然有 即：将解集合投影到xoy平面上，将被包含在如下集合中 集合A共有 21×34＝714个元素 利用计算机的高速度，对上述714个元素逐个试算，判断是否满足题意，并输出满足题意者。 ———— 这就是穷举法、亦称为枚举法。 计算流程 程序编译、连接生成可执行文件可执行文件的运行结果 说明 多种有哪些信誉好的足球投注网站方案 考察(x,y)组合 有21×34＝714种情形 考察(y,z)组合 有34×101＝3434种情形 （3434/714 4.8倍） 考察(x,y,z)组合 有21×34×101＝7211种情形（72114/714＝101倍） 不同方案的计算量有巨大差别 穷举法成功的关键 ———— 裁剪有哪些信誉好的足球投注网站空间； 当有哪些信誉好的足球投注网站空间中的元素个数巨大时，穷举算法失效。 说明 关于条件判断 if(3*100 == 3*(5*cocks + 3*hens)+chicks) 写成如下形式 if(100 == 5*cocks + 3*hens + chicks/3) 将多出3组错误的解 鸡翁 3 只，鸡母 20 只，鸡雏 77 只。 鸡翁 7 只，鸡母 13 只，鸡雏 80 只。 鸡翁 11 只，鸡母 6 只，鸡雏 83 只。 建议将常量写在左侧，有利于减少将“==”误用成“=”的机会 因为 if(3=a) 为语法错，编译时被系统发现 而 if(a=3) 没有语法错，编译时只有警告 4.1.2 判定素数 例4.2 给定一个正整数n，判断其是否为素数(亦称为质数，即只有1及自身两个平凡因数的正整数。 整数1不是素数)。 【算法设计】穷举法 令k=2，3，…，n-1逐个试算，考察n%k是否为0 计算量约为n次除法及判断 令m=sqrt(n);考察k=2，3，…，m逐个试算即可 计算量约为m次除法及判断，约为前一种方法的1/m。 测试程序的运行结果 4.2.1 牛顿迭代法 算术平方根函数 对于给定的非负实数d，计算d的算术平方根有标准函数sqrt(d) 本小节给出一个自定义函数，仅用四则运算计算非负实数的算术平方根 为了与标准函数区别，自定义函数原型设计如下： double mysqrt(double x); 4.2.1 牛顿迭代法 原理 ———— 牛顿迭代法 时间顺序性：循环结构 空间复用性：覆盖存储（去掉公式中的下标） 精度控制法：前后两次迭代的误差充分小 y = 1;y = y + (d/y-y)/2; 前后两次迭代误差恰好为 (d/y-y)/2 的绝对值 4.2.2 级数计算 指数函数 分析 化成递推公式 4.2.2 级数计算 正弦函数（符号交错级数） 分析 化成递推公式 综合测试 综合测试函数（主函数）见教材 从测试结果可见，与标准函数计算结果的误差 小于自定义函数的控制误差 1e-8。 4.2.3 最大公因数和最小公倍数 例4.5 求两个整数m, n的最大公因数(m, n)和最小公倍数[m, n]. 【分析】 (m, n) = (|m|, |n|) [m, n] = [|m|, |n|] 若m, n均非负 欧几里得算法 若m,n均为整数，由带余除法 m = q1n + r1 (0≤r1n) 则 (m, n) = (n, r1) 同理 n = q2r1 + r2 (0≤r2r1) 则 (m, n) = (n, r1) = (r1, r2) 依次类推，由于 0 ≤ … ≤ r2r1n，则必有某rk=0， 从而 rk-1即为所求。 例如：若m=36, n=14 36 = 2×14 + 8 (36, 14) = (14, 8) 14 = 1×8 + 6 (14, 8) = (8, 6) 8