《专业C9讲变量设计ppt课件》由会员分享，可在线阅读，更多相关《专业C9讲变量设计ppt课件（49页珍藏版）》请在金锄头文库上搜索。
1、单击此处编辑母版副标题样式单击此处编辑母版副标题样式华中农业大学理学院华中农业大学理学院 章章 英英 C/C+语言程序设计语言程序设计 1/59本章通过几种不同类型的算法实现，着重讨论算法本章通过几种不同类型的算法实现，着重讨论算法实现中的变量设计问题，包括函数的参数、局部变实现中的变量设计问题，包括函数的参数、局部变量、标志变量的设计与应用。量、标志变量的设计与应用。从本章起，将围绕所谓的从本章起，将围绕所谓的“评委评分评委评分”程序的设计程序的设计和优化、程序功能的扩充逐步展开讨论。和优化、程序功能的扩充逐步展开讨论。本章涉及一些基本算法，这些算法的设计思想是朴本章涉及一些基本算法，这些算
2、法的设计思想是朴素的。素的。第九讲第九讲 变量设计变量设计2/494.14.2 穷举、迭代计算穷举、迭代计算4.1 穷举计算穷举计算 4.1.1 “百钱买百鸡百钱买百鸡”问题问题 4.1.2 判定素数判定素数4.2 迭代计算迭代计算 4.2.1 牛顿迭代法牛顿迭代法 4.2.2 级数计算（即：级数计算（即：数列求和数列求和）指数函数指数函数正弦函数正弦函数 4.2.3 最大公因数和最小公倍数最大公因数和最小公倍数3/494.1.1 “百钱买百鸡百钱买百鸡”问题问题 例例4.1 公元前公元前5世纪，我国古代数学家张丘建世纪，我国古代数学家张丘建在在算经算经一书中提出了一书中提出了“百鸡问题百鸡问
3、题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？百钱买百鸡，问鸡翁、母、雏各几何？【数学模型数学模型】记记x, y, z分别表示购买鸡翁、母、雏的数量，则分别表示购买鸡翁、母、雏的数量，则有有这是一个不定方程，数学方法求解有较大难度。这是一个不定方程，数学方法求解有较大难度。4/494.1.1 “百钱买百鸡百钱买百鸡”问题问题【算法设计算法设计】显然有显然有即：将解集合投影到即：将解集合投影到xoy平面上，将被包含在如下集合中平面上，将被包含在如下集合中 集合集合A共有共有 2134714个元素个元素利用计算机的高速度
4、，对上述利用计算机的高速度，对上述714个元素个元素逐个试算逐个试算，判断，判断是否满足题意，并输出满足题意者。是否满足题意，并输出满足题意者。 这就是这就是穷举法穷举法、亦称为、亦称为枚举法枚举法。5/49计算流程计算流程6/49 / Hundredchicken.cpp源程序文件名源程序文件名 #include using namespace std; int chicken100();/ 函数原型用于函数声明函数原型用于函数声明 int main() chicken100();/ 函数调用函数调用 return 0; / 主函数起调度作用，尽可能地简单主函数起调度作用，尽可能地简单7/4
5、9 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; 8/49 int chicken100() int cocks, hens, chick
6、s, 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 ” 只。只。” 4.8倍）倍）考察考察(x,y,z)组合组合有有21341017211种情形（种情形（72114/714101倍）倍）不同方案的计算量有巨大差别不同方案的计算量有巨大差别穷举法成功的关键穷举法成功的关键 裁剪搜
7、索空间；裁剪搜索空间；当搜索空间中的元素个数巨大时，穷举算法失效。当搜索空间中的元素个数巨大时，穷举算法失效。 11/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 只。只。建议将常量写在左侧，有利
8、于减少将建议将常量写在左侧，有利于减少将“=”误用误用成成“=”的机会的机会因为因为 if(3=a) 为语法错，编译时被系统发现为语法错，编译时被系统发现而而 if(a=3) 没有语法错，编译时只有警告没有语法错，编译时只有警告不是不是3的的整数倍整数倍12/494.1.2 判定素数判定素数例例4.2 给定一个正整数给定一个正整数n，判断其是否为素数，判断其是否为素数( (亦称为质数，即只有亦称为质数，即只有1 1及自身两个平凡因数的正整数。及自身两个平凡因数的正整数。 整数整数1 1不是素数不是素数) )。【算法设计算法设计】穷举法穷举法1.令令k=2，3，n-1逐个试算，考察逐个试算，考察
9、n%k是否为是否为0计算量约为计算量约为n次除法及判断次除法及判断2.令令m=sqrt(n);考察考察k=2，3，m逐个试算即可逐个试算即可计算量约为计算量约为m次除法及判断，约为前一种方法的次除法及判断，约为前一种方法的1/m。计算量计算量n=100n=10000n=1000000方法方法1100100001000000方法方法2101001000比值比值10倍倍100倍倍1000倍倍13/49 #include int isprime(unsigned int n) if(n2) return 0; unsigned int k, m; m = (unsigned int)sqrt(dou
10、ble(n); for(k=2; k=m; k+) if(n%k = 0) return 0; return 1; 测试程序见教材测试程序见教材主函数中反复调用上述函数判断主函数中反复调用上述函数判断21000内的整数，内的整数， 输出其中的素数，并统计其中素数的个数。输出其中的素数，并统计其中素数的个数。 输出的每个素数占输出的每个素数占4个字符宽，显示器上每行输出个字符宽，显示器上每行输出 20个素数后自动换行。个素数后自动换行。14/49测试程序的运行结果测试程序的运行结果15/49 #include int isprime(unsigned int n) unsigned int k,
11、 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; 注意：自动变量注意：自动变量k16/49 #include int isprime(unsigned int n) unsigned int m; m = (unsigned int)sqrt(double(n);
12、for(int k=2; k=m; k+) if(n%k = 0) break; if(k=m) return 0; else return 1; for循环中定义的变循环中定义的变量的生命期：量的生命期：循环结束后销毁。循环结束后销毁。错误：变量错误：变量k未定义未定义但但Visual C+未按标准未按标准C+实现，认为上述函数正确实现，认为上述函数正确 17/49 int test() for(int i=0; i10; i+) cout i ; cout endl; for(int i=0; i10; i+) cout char(A+i) ; cout =epsilon | delta=
13、-epsilon); return y; 头文件头文件 中声明的标准函数中声明的标准函数 double sqrt(double);的具体实现过程无法得知（是个黑箱），可能同上，不过精度的具体实现过程无法得知（是个黑箱），可能同上，不过精度控制可能更高，如控制可能更高，如 epsilon=1e-16。21/494.2.2 级数计算级数计算指数函数指数函数分析分析化成递推公式化成递推公式22/49 double myexp(double x) int n; double s, p, epsilon=1e-8; s = p = n = 1; do p *= x/n;/ 这里有一个隐式类型转换这里有一
14、个隐式类型转换 s += p; n+; while(p=epsilon | p=epsilon | p=-epsilon); return s; 25/49综合测试综合测试 综合测试函数（主函数）见教材综合测试函数（主函数）见教材 从测试结果可见，与标准函数计算结果的误差从测试结果可见，与标准函数计算结果的误差 小于自定义函数的控制误差小于自定义函数的控制误差 1e-8。26/494.2.3 最大公因数和最小公倍数最大公因数和最小公倍数 例例4.5 求两个整数求两个整数m, n的最大公因数的最大公因数(m, n)和和最小公倍数最小公倍数m, n.【分析分析】 (m, n) = (|m|, |n
15、|) m, n = |m|, |n| 若若m, n均非负均非负27/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,
16、6) 8 = 16 + 2(8, 6) = (6, 2) 6 = 32 + 0(6, 2) = (2, 0) = 228/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; 29/49 / 最小公倍数最小公倍数 Lowest Common Multiple unsigned int lcm(unsigned int m, unsigned int n) u
17、nsigned 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=25230/494.3 标志变量的设计与应用标志变量的设计与应用4.3.1 整除问题整除问题方法方法1方法方法2（将计算与（将计算与I/O分开处理，利于程序移植）分开处理，利于程序移植）4.3.2 三
18、角形的周长及面积三角形的周长及面积返回多个值返回多个值31/494.3.1 整除问题整除问题例例4.6 编程实现输入一个整数，判断其是否能被编程实现输入一个整数，判断其是否能被 3, 5或或7整除，并输出以下信息之一整除，并输出以下信息之一1.能同时被能同时被3, 5, 7整除。整除。2.能被两个数（要指出哪两个数）整除。能被两个数（要指出哪两个数）整除。3.能被一个数（要指出哪一个数）整除。能被一个数（要指出哪一个数）整除。4.不能被不能被3, 5, 7整除。整除。32/49 #include using namespace std; void f(int n) if(n%(3*5*7)=0
19、) cout n ”能同时被能同时被3, 5, 7整除。整除。”; else if(n%3=0 & n%5!=0 & n%7!=0) cout n ” 仅能被一个数仅能被一个数 (3) 整除。整除。”; else if(n%3!=0 & n%5=0 & n%7!=0) cout n ” 仅能被一个数仅能被一个数 (5) 整除。整除。”; else if(n%3!=0 & n%5!=0 & n%7=0) cout n ” 仅能被一个数仅能被一个数 (7) 整除。整除。”; else if(n%3=0 & n%5=0 & n%7!=0) cout n ” 能被两个数能被两个数 (3, 5) 整除。
20、整除。”; else if(n%3=0 & n%5!=0 & n%7=0) cout n ” 能被两个数能被两个数 (3, 7) 整除。整除。”; else if(n%3!=0 & n%5=0 & n%7=0) cout n ” 能被两个数能被两个数 (5, 7) 整除。整除。”; else cout n ” 不能被不能被 3, 5, 7 整除。整除。”; cout endl;33/49方法方法2：将计算与输出相分离：将计算与输出相分离 先完成所有的判断然后输出，使计算与输出两个环先完成所有的判断然后输出，使计算与输出两个环节相分离节相分离设计一个标志量与整数设计一个标志量与整数n对应，记录对
21、应，记录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种情形种情形最后，根据标志值输出结果最后，根据标志值输出结果34/49 int mod_3_5_7(int n) int
22、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;35/49 case 1: cout n ” 仅能被一个数仅
23、能被一个数 (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 ” 能同时被
24、能同时被 3, 5, 7 整除。整除。”; cout endl;36/49 int main() int n; while(1) cout n; if(n0) break; show_result(n); return 0; 37/494.3.2 三角形的周长及面积三角形的周长及面积例例4.7 给定三条线段的长度给定三条线段的长度a, b, c，判断它们，判断它们能否组成一个三角形，若能则计算并能否组成一个三角形，若能则计算并“返回返回”该三该三角形的周长和面积，否则令其周长和面积全为零。角形的周长和面积，否则令其周长和面积全为零。【分析分析】要求返回周长、面积（要求返回周长、面积（2个值）；
25、个值）；由于函数只能返回一种数据类型的一个值，故需要借助函由于函数只能返回一种数据类型的一个值，故需要借助函数的引用型形参（双向传递）数的引用型形参（双向传递）“返回返回”周长和面积周长和面积；利用函数返回值，返回能否构成三角形的判断结果。利用函数返回值，返回能否构成三角形的判断结果。 38/49 #include int triangle(double a, double b, double c, double & perimeter, double & area) double s = (a + b + c)/2; if(sa & sb & sc) perimeter = a + b +
26、c; area = sqrt(s*(s-a)*(s-b)*(s-c); return 1; perimeter = area = 0; return 0; 39/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 ”不能构成三角形。不能构成三角形。” en
27、dl; return 0; 说明：说明：triangle函数的返回类型可以设计成函数的返回类型可以设计成void。然而，设置。然而，设置函数的返回值，几乎不增加函数的设计工作量和难度，却给使用函数的返回值，几乎不增加函数的设计工作量和难度，却给使用该函数的程序员带来便利：程序员不必在函数调用后通过判断该函数的程序员带来便利：程序员不必在函数调用后通过判断近近似表示的浮点数似表示的浮点数area是否是否精确地精确地等于等于0来获知能否构成三角形。来获知能否构成三角形。40/494.3 单变量版单变量版“评委评分评委评分”程序设计程序设计 问题描述问题描述有有n位选手参加的某大奖赛，组委会聘请了位
28、选手参加的某大奖赛，组委会聘请了m个评委为每个评委为每一位参赛选手评分。每位选手在其所得的一位参赛选手评分。每位选手在其所得的m个分数中按个分数中按“去掉一个最高分，去掉一个最低分，剩下的去掉一个最高分，去掉一个最低分，剩下的m-2个分数的个分数的算术平均分算术平均分”确定最后得分。确定最后得分。现要求编写一个程序，帮助大奖赛组委会计算并输出各选现要求编写一个程序，帮助大奖赛组委会计算并输出各选手的最后得分。手的最后得分。算法分析算法分析按选手序号依次处理按选手序号依次处理对每一位选手对每一位选手接收接收m个评委所给出的分数个评委所给出的分数计算出最高分、最低分、总分计算出最高分、最低分、总分
29、计算最后得分计算最后得分41/49程序实现程序实现变量设计变量设计42/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=2) cout ”评委人数太少。评委人数太少。”endl; return -1; cout players; time_t t; sran
30、d(time(&t);/ 为了获得更好的随机数为了获得更好的随机数43/49 for(int i=0; iplayers; i+) cout ”nn= No. ” i+1 endl; min = 10; / 擂台上先放置一个不经打者擂台上先放置一个不经打者 max = sum = 0; for(int j=0; jreferees; j+) x =(80+rand()%21)/10.0; cout x max) max = x;/ 打擂台算法打擂台算法 if(x min) min = x; sum += x; aver = (sum-max-min)/(referees-2); cout ”n
31、 去掉一个最高分去掉一个最高分 ” max ” 分分, 去掉一个最低分去掉一个最低分 ” min ” 分，最后得分分，最后得分 ” aver ” 分。分。” endl; getch(); / 暂停，按任意键继续暂停，按任意键继续 return 0;44/49程序（某次）运行结果程序（某次）运行结果请输入评委人数请输入评委人数: 5 请输入参赛选手人数请输入参赛选手人数: 4 = No. 110 8.4 9.5 9.3 9.6 去掉一个最高分去掉一个最高分 10 分分, 去掉一个最低分去掉一个最低分 8.4 分，最后得分分，最后得分 9.46667 分。分。= No. 28.4 9.3 8.1
32、9.2 9.1 去掉一个最高分去掉一个最高分 9.3 分分, 去掉一个最低分去掉一个最低分 8.1 分，最后得分分，最后得分 8.9 分。分。= No. 39.5 8.9 8.4 8 9.9 去掉一个最高分去掉一个最高分 9.9 分分, 去掉一个最低分去掉一个最低分 8 分，最后得分分，最后得分 8.93333 分。分。= No. 48.7 9.7 9 8.6 9.8 去掉一个最高分去掉一个最高分 9.8 分分, 去掉一个最低分去掉一个最低分 8.6 分，最后得分分，最后得分 9.13333 分。分。45/49说明说明 函数函数 int rand(); 的应用的应用功能：产生功能：产生0RAN
33、D_MAX之间的随机数（见第之间的随机数（见第2.2节）节）语句语句 x = (80+rand()%21)/10.0;将产生的随机数变换到将产生的随机数变换到8.010.0之间，且仅有一位小数，之间，且仅有一位小数，以避免大量数据的键盘输入。以避免大量数据的键盘输入。 “打擂台算法打擂台算法”是求最大（最小）值的典型算法是求最大（最小）值的典型算法 max = 0; for(int j=0; jmax) max = x; / 出现更大者时，擂主易人出现更大者时，擂主易人 46/49说明说明 主函数中的主函数中的 return 整型表达式；整型表达式； 语句，如：语句，如： return -1;
34、return 0; 等等等等引起程序结束；引起程序结束；将一个整数值返回给操作系统将一个整数值返回给操作系统通常情况下，返回通常情况下，返回0表示程序正常结束；表示程序正常结束；操作系统可以获得该值，以便判断程序是因何种原因结束操作系统可以获得该值，以便判断程序是因何种原因结束的。的。47/49说明说明 为何称程序为为何称程序为“单变量版单变量版”的？的？原始分数应该有原始分数应该有 referees*players 个（若有个（若有10位位评委，评委，20名参赛选手，则有名参赛选手，则有10*20200个原始分数）个原始分数）程序中仅用了一个变量程序中仅用了一个变量double x;（意味着
35、系统只分配了（意味着系统只分配了8字节的内存空间）仅能存放一个分数字节的内存空间）仅能存放一个分数这些分数在使用（比较求最大值、最小值、总分）后便被这些分数在使用（比较求最大值、最小值、总分）后便被新的分数覆盖新的分数覆盖虽然显示器上还显示着所有分数，但是显示器属于计算机外部设虽然显示器上还显示着所有分数，但是显示器属于计算机外部设备，这些信息已经不在计算机内存中。备，这些信息已经不在计算机内存中。程序执行到程序执行到 return 0; 语句之前时，变量语句之前时，变量x，max，min，aver的值是最后一位选手的相关数据。而的值是最后一位选手的相关数据。而x是最后一位评是最后一位评委为其评的分数。委为其评的分数。48/49作业及实验作业及实验第三章作业：第三章作业：HZAU-专业专业C+作业作业ch3第三次实验：第三次实验：HZAU-专业专业C+实验实验3(计算机计算机1-2班班)抓紧时间！抓紧时间！49/49
