《专业C9讲变量设计课件教案资料》由会员分享，可在线阅读，更多相关《专业C9讲变量设计课件教案资料（49页珍藏版）》请在金锄头文库上搜索。
1、本章通过几种不同类型的算法实现，着重讨论算法实现中的变量设计问题，包括函数的参数、局部变量、标志变量的设计与应用。 从本章起，将围绕所谓的“评委评分”程序的设计和优化、程序功能的扩充逐步展开讨论。 本章涉及一些基本算法，这些算法的设计思想是朴素的。,第九讲 变量设计,4.14.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世纪，我国古代数学家张丘建在算经一书中提出了
2、“百鸡问题”： 鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？ 【数学模型】 记x, y, z分别表示购买鸡翁、母、雏的数量，则有 这是一个不定方程，数学方法求解有较大难度。,计算流程,/ Hundredchicken.cpp源程序文件名 #include using namespace std; int chicken100();/ 函数原型用于函数声明 int main() chicken100();/ 函数调用 return 0; / 主函数起调度作用，尽可能地简单,int chicken100() int cocks, hens, chicks, n=0;
3、 for(cocks=0; cocks=20; cocks+) for(hens=0; hens=33; hens+) chicks = 100 cocks hens; if(3*100 = 3*(5*cocks+3*hens)+chicks) cout ”鸡翁 ” cocks ” 只，鸡母 ” hens ” 只，鸡雏 ” chicks ” 只。” endl; n+; return n; ,int chicken100() int cocks, hens, chicks, n=0; for(cocks=0; cocks=20; cocks+) for(hens=0; hens=33; hens
4、+) chicks = 100 cocks hens; if(3*100 = 3*(5*cocks+3*hens)+chicks) cout ”鸡翁 ” cocks ” 只，鸡母 ” hens ” 只，鸡雏 ” chicks ” 只。” endl; n+; return n; ,程序编译、连接生成可执行文件可执行文件的运行结果,说明,多种搜索方案 考察(x,y)组合 有2134714种情形 考察(y,z)组合 有341013434种情形 （3434/714 4.8倍） 考察(x,y,z)组合 有21341017211种情形（72114/714101倍） 不同方案的计算量有巨大差别 穷举法成功的
5、关键 裁剪搜索空间； 当搜索空间中的元素个数巨大时，穷举算法失效。,说明,关于条件判断 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 判定素数,
6、例4.2 给定一个正整数n，判断其是否为素数(亦称为质数，即只有1及自身两个平凡因数的正整数。 整数1不是素数)。 【算法设计】穷举法 令k=2，3，n-1逐个试算，考察n%k是否为0 计算量约为n次除法及判断 令m=sqrt(n);考察k=2，3，m逐个试算即可 计算量约为m次除法及判断，约为前一种方法的1/m。,#include int isprime(unsigned int n) if(n2) return 0; unsigned int k, m; m = (unsigned int)sqrt(double(n); for(k=2; k=m; k+) if(n%k = 0) retu
7、rn 0; return 1; 测试程序见教材 主函数中反复调用上述函数判断21000内的整数， 输出其中的素数，并统计其中素数的个数。 输出的每个素数占4个字符宽，显示器上每行输出 20个素数后自动换行。,测试程序的运行结果,#include int isprime(unsigned int n) unsigned int k, m; m = (unsigned int)sqrt(double(n); for(k=2; km时结束循环 if(n%k = 0) break; / 整除时提前结束循环 / 上述循环语句有两个出口 if(k=m) / 循环语句结束后，根据k值进行判断 return
8、0; else return 1; ,#include int isprime(unsigned int n) unsigned int m; m = (unsigned int)sqrt(double(n); for(int k=2; k=m; k+) if(n%k = 0) break; if(k=m) return 0; else return 1; ,但Visual C+未按标准C+实现，认为上述函数正确,int test() for(int i=0; i10; i+) cout i ; cout endl; for(int i=0; i10; i+) cout char(A+i) ;
9、 cout endl; ,该函数符合标准C+，在MinGW Developer Studio 系统下编译通过。 但Visual C+未按标准C+实现，认为上述函数中变量i重复定义而错。,4.2.1 牛顿迭代法,算术平方根函数 对于给定的非负实数d，计算d的算术平方根有标准函数sqrt(d) 本小节给出一个自定义函数，仅用四则运算计算非负实数的算术平方根 为了与标准函数区别，自定义函数原型设计如下： double mysqrt(double x);,4.2.1 牛顿迭代法,原理 牛顿迭代法 时间顺序性：循环结构 空间复用性：覆盖存储（去掉公式中的下标） 精度控制法：前后两次迭代的误差充分小 y
10、= 1;y = y + (d/y-y)/2; 前后两次迭代误差恰好为 (d/y-y)/2 的绝对值,double mysqrt(double x) double delta, y=1, epsilon=1e-8; do delta = (x/y y)/2; y += delta; while(delta=epsilon | delta 中声明的标准函数 double sqrt(double);的具体实现过程无法得知（是个黑箱），可能同上，不过精度控制可能更高，如 epsilon=1e-16。,4.2.2 级数计算,指数函数 分析 化成递推公式,double myexp(double x) in
11、t n; double s, p, epsilon=1e-8; s = p = n = 1; do p *= x/n;/ 这里有一个隐式类型转换 s += p; n+; while(p=epsilon | p=-epsilon); return s; 注意：切勿先计算 xn 及 n!，然后计算它们的商。因为它们均可能是非常大的数，尤其是整数n!可能溢出；再做除法，又可能出现更大的误差。,4.2.2 级数计算,正弦函数（符号交错级数） 分析 化成递推公式,double mysin(double x) int n; double s, p, epsilon=1e-8; s = p = x; n =
12、 3; do p *= -x*x/(n-1)*n); s += p; n += 2; while(p=epsilon | p=-epsilon); return s; ,综合测试,综合测试函数（主函数）见教材 从测试结果可见，与标准函数计算结果的误差 小于自定义函数的控制误差 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 (0r1n) 则 (m, n
13、) = (n, r1) 同理 n = q2r1 + r2 (0r2r1) 则 (m, n) = (n, r1) = (r1, r2) 依次类推，由于 0 r2r1n，则必有某rk=0， 从而 rk-1即为所求。 例如：若m=36, n=14 36 = 214 + 8(36, 14) = (14, 8) 14 = 18 + 6(14, 8) = (8, 6) 8 = 16 + 2(8, 6) = (6, 2) 6 = 32 + 0(6, 2) = (2, 0) = 2,/ 最大公因数 Greatest Common Divisor unsigned int gcd(unsigned int m,
14、 unsigned int n) unsigned int r; while(n) r = m%n; m = n; n = r; return m; ,/ 最小公倍数 Lowest Common Multiple unsigned int lcm(unsigned int m, unsigned int n) unsigned int gcd(unsigned int, unsigned int); / 函数原型用于函数声明 unsigned int g = gcd(m, n); if(g=0) return 0; else return m/g*n;/ 不要写成m*n/g以免溢出 如 m=3
15、6, n=14 36, 14 = 36/(36,14)14 = 36/214=252,4.3 标志变量的设计与应用,4.3.1 整除问题 方法1 方法2（将计算与I/O分开处理，利于程序移植） 4.3.2 三角形的周长及面积 返回多个值,4.3.1 整除问题,例4.6 编程实现输入一个整数，判断其是否能被 3, 5或7整除，并输出以下信息之一 能同时被3, 5, 7整除。 能被两个数（要指出哪两个数）整除。 能被一个数（要指出哪一个数）整除。 不能被3, 5, 7整除。,#include using namespace std; void f(int n) if(n%(3*5*7)=0) cout n ”能同时被3, 5, 7整除。”; else if(n%3=0 ,方法2：将计算与输出相分离,先完成所有的判断然后输出，使计算与输出两个环节相分离 设计一个标志量与整数n对应，记录n被3, 5, 7整除的情况。我们约定标志量的 二进制最低位：1表示n能被3整除，0表示n不能被3整除 二进制第2位：1表示n能被5整除，0表示n不能被5整除 二进制第3位：1表示n能被7整除，0表示
