专业C9讲变量设计.ppt

1/59,2/49,本章通过几种不同类型的算法实现，着重讨论算法实现中的变量设计问题，包括函数的参数、局部变量、标志变量的设计与应用。 从本章起，将围绕所谓的“评委评分”程序的设计和优化、程序功能的扩充逐步展开讨论。 本章涉及一些基本算法，这些算法的设计思想是朴素的。,第九讲 变量设计,3/49,4.14.2 穷举、迭代计算,4.1 穷举计算 4.1.1 “百钱买百鸡”问题 4.1.2 判定素数 4.2 迭代计算 4.2.1 牛顿迭代法 4.2.2 级数计算（即：数列求和） 指数函数 正弦函数 4.2.3 最大公因数和最小公倍数,4/49,4.1.1 “百钱买百鸡”问题,例4.1 公元前5世纪，我国古代数学家张丘建在算经一书中提出了“百鸡问题”： 鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？ 【数学模型】 记x, y, z分别表示购买鸡翁、母、雏的数量，则有 这是一个不定方程，数学方法求解有较大难度。,5/49,4.1.1 “百钱买百鸡”问题,【算法设计】 显然有 即：将解集合投影到xoy平面上，将被包含在如下集合中 集合A共有 2134714个元素 利用计算机的高速度，对上述714个元素逐个试算，判断是否满足题意，并输出满足题意者。 这就是穷举法、亦称为枚举法。,6/49,计算流程,7/49,/ Hundredchicken.cpp 源程序文件名 #include using namespace std; int chicken100(); / 函数原型用于函数声明 int main() chicken100(); / 函数调用 return 0; / 主函数起调度作用，尽可能地简单,8/49,int chicken100() int cocks, hens, chicks, n=0; 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; ,9/49,int chicken100() int cocks, hens, chicks, n=0; 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; ,10/49,程序编译、连接生成可执行文件 可执行文件的运行结果,11/49,说明,多种搜索方案 考察(x,y)组合 有2134714种情形 考察(y,z)组合 有341013434种情形 （3434/714 4.8倍） 考察(x,y,z)组合 有21341017211种情形（72114/714101倍） 不同方案的计算量有巨大差别 穷举法成功的关键 裁剪搜索空间； 当搜索空间中的元素个数巨大时，穷举算法失效。,12/49,说明,关于条件判断 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) 没有语法错，编译时只有警告,13/49,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。,14/49,#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) return 0; return 1; 测试程序见教材 主函数中反复调用上述函数判断21000内的整数， 输出其中的素数，并统计其中素数的个数。 输出的每个素数占4个字符宽，显示器上每行输出 20个素数后自动换行。,15/49,测试程序的运行结果,16/49,#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 0; else return 1; ,17/49,#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+实现，认为上述函数正确,18/49,int test() for(int i=0; i10; i+) cout i ; cout endl; for(int i=0; i10; i+) cout char(A+i) ; cout endl; ,该函数符合标准C+，在MinGW Developer Studio 系统下编译通过。 但Visual C+未按标准C+实现，认为上述函数中 变量i重复定义而错。,19/49,4.2.1 牛顿迭代法,算术平方根函数 对于给定的非负实数d，计算d的算术平方根有标准函数sqrt(d) 本小节给出一个自定义函数，仅用四则运算计算非负实数的算术平方根 为了与标准函数区别，自定义函数原型设计如下： double mysqrt(double x);,20/49,4.2.1 牛顿迭代法,原理 牛顿迭代法 时间顺序性：循环结构 空间复用性：覆盖存储（去掉公式中的下标） 精度控制法：前后两次迭代的误差充分小 y = 1; y = y + (d/y-y)/2; 前后两次迭代误差恰好为 (d/y-y)/2 的绝对值,21/49,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。,22/49,4.2.2 级数计算,指数函数 分析 化成递推公式,23/49,double myexp(double x) int 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!可能溢出；再做除法，又 可能出现更大的误差。,24/49,4.2.2 级数计算,正弦函数（符号交错级数） 分析 化成递推公式,25/49,double mysin(double x) int n; double s, p, epsilon=1e-8; s = p = x; n = 3; do p *= -x*x/(n-1)*n); s += p; n += 2; while(p=epsilon | p=-epsilon); return s; ,26/49,综合测试,综合测试函数（主函数）见教材 从测试结果可见，与标准函数计算结果的误差 小于自定义函数的控制误差 1e-8。,27/49,4.2.3 最大公因数和最小公倍数,例4.5 求两个整数m, n的最大公因数(m, n)和 最小公倍数m, n. 【分析】 (m, n) = (|m|, |n|) m, n = |m|, |n| 若m, n均非负,28/49,欧几里得算法,若m,n均为整数，由带余除法 m = q1n + r1 (0r1n) 则 (m, n) = (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,29/49,/ 最大公因数 Greatest Common Divisor unsigned int gcd(unsigned int m, unsigned int n) unsigned int r; while(n) r = m%n; m = n; n = r; return m; ,30/49,/ 最小公倍数 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=36, n=14 36, 14 = 36/(36,14)14 = 36/214=252,31/49,4.3 标志变量的设计与应用,4.3.1 整除问题 方法1 方法2（将计算与I/O分开处理，利于程序移植） 4.3.2 三角形的周长及面积 返回多个值,32/49,4.3.1 整除问题,例4.6 编程实现输入一个整数，判断其是否能被 3, 5或7整除，并输出以下信息之一 能同时被3, 5, 7整除。 能被两个数（要指出哪两个数）整除。 能被一个数（要指出哪一个数）整除。 不能被3, 5, 7整除。,33/49,#include using namespace std; void f(int n) if(n%(3*5*7)=0) cout n ”能同时被3, 5, 7整除。”; else if(n%3=0 ,34/49,方法2：将计算与输出相分离,先完成所有的判断然后输出，使计算与输出两个环节相分离 设计一个标志量与整数n对应，记录n被3, 5, 7整除的情况。我们约定标志量的 二进制最低位：1表示n能被3整除，0表示n不能被3整除 二进制第2位：1表示n能被5整除，0表示n不能被5整除 二进制第3位：1表示n能被7整除，0表示n不能被7整除 这样，对于给定的n，其标志变量可有8种取值之一，分别对应8种情形 最后，根据标志值输出结果,35/49,int mod_3_5_7(int n) int flag = 0; if(n%3 = 0) flag += 1; / 001 或 flag |= 1 if(n%5 = 0) flag += 2; / 010 或 flag |= 2 if(n%7 = 0) flag += 4; / 100 或 flag |= 4 return flag; #include using namespace std; void show_result(int n) switch(mod_3_5_7(n) case 0: cout n ” 不能被 3, 5, 7 整除。”; break;,36/49,case 1: cout n ” 仅能被一个数 (3) 整除。”; break; case 2: cout n ” 仅能被一个数 (5) 整除。”; break; case 3: cout n ” 能被两个数 (3, 5) 整除。”; break; case 4: cout n ” 仅能被一个数 (7) 整除。”; break; case 5: cout n ” 能被两个数 (3, 7) 整除。”; break; case 6: cout n ” 能被两个数 (5, 7) 整除。”; break; default:cout n ” 能同时被 3, 5, 7 整除。”; cout endl; ,37/49,int main() int n; while(1) cout n; if(n0) break; show_result(n); return 0; ,38/49,4.3.2 三角形的周长及面积,例4.7 给定三条线段的长度a, b, c，判断它们 能否组成一个三角形，若能则计算并“返回”该三角形的周长和面积，否则令其周长和面积全为零。 【分析】 要求返回周长、面积（2个值）； 由于函数只能返回一种数据类型的一个值，故需要借助函数的引用型形参（双向传递）“返回”周长和面积； 利用函数返回值，返回能否构成三角形的判断结果。,39/49,#include int triangle(double a, double b, double c, double ,40/49,#include using namespace std; int main() double a, b, c, len, area; int flag; a = 3; b = 4; c = 5; flag = triangle(a, b, c, len, area); if(flag) cout ”周长：” len ”, 面积：” area endl; else cout ”不能构成三角形。” endl; return 0; 说明：triangle函数的返回类型可以设计成void。然而，设置 函数的返回值，几乎不增加函数的设计工作量和难度，却给使用 该函数的程序员带来便利：程序员不必在函数调用后通过判断近 似表示的浮点数area是否精确地等于0来获知能否构成三角形。,41/49,4.3 单变量版“评委评分”程序设计,问题描述 有n位选手参加的某大奖赛，组委会聘请了m个评委为每一位参赛选手评分。每位选手在其所得的m个分数中按“去掉一个最高分，去掉一个最低分，剩下的m-2个分数的算术平均分”确定最后得分。 现要求编写一个程序，帮助大奖赛组委会计算并输出各选手的最后得分。 算法分析 按选手序号依次处理 对每一位选手 接收m个评委所给出的分数 计算出最高分、最低分、总分 计算最后得分,42/49,程序实现,变量设计,43/49,/ contest0.cpp 评委评分（单变量版） #include #include #include / 不是标准C+的头文件 using namespace std; int main() int referees, players; double x, min, max, sum, aver; cout referees; if(referees players; time_t t; srand(time( / 为了获得更好的随机数,44/49,for(int i=0; i max) max = x; / 打擂台算法 if(x min) min = x; sum += x; aver = (sum-max-min)/(referees-2); cout ”n 去掉一个最高分 ” max ” 分, 去掉一个最低分 ” min ” 分，最后得分 ” aver ” 分。” endl; getch(); / 暂停，按任意键继续 return 0; ,45/49,程序（某次）运行结果,请输入评委人数: 5 请输入参赛选手人数: 4 = No. 1 10 8.4 9.5 9.3 9.6 去掉一个最高分 10 分, 去掉一个最低分 8.4 分，最后得分 9.46667 分。 = No. 2 8.4 9.3 8.1 9.2 9.1 去掉一个最高分 9.3 分, 去掉一个最低分 8.1 分，最后得分 8.9 分。 = No. 3 9.5 8.9 8.4 8