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