1、C+程序设计1第二章第二章 基本控制结构程序设计基本控制结构程序设计C+程序设计2 结构化程序设计的特点是结构化程序设计的特点是任何程序任何程序都可由都可由三种基本结构及其组合三种基本结构及其组合来描述。来描述。本章将介绍本章将介绍C+分支结构和循环结构的设分支结构和循环结构的设计方法。还将介绍一些常用算法。计方法。还将介绍一些常用算法。C+程序设计3 C+程序设计4 2.1.1 算法的概念算法的概念 2.1.2 算法的表示算法的表示 2.1.3 算法描述的三种基本结构算法描述的三种基本结构C+程序设计5算法：算法：为了解决某一问题而采取的有限步骤。为了解决某一问题而采取的有限步骤。计算机算法
2、的特征：计算机算法的特征：(1)(1)可执行性可执行性(2)(2)确定性确定性(3)(3)有穷性有穷性(4)(4)可输入输出信息可输入输出信息算法是程序设计学习的重点。算法是程序设计学习的重点。2.1.1 2.1.1 算算 法法 的的 概概 念念 C+程序设计62.1.2 算法的表示算法的表示流程图：算法的图形化表示方法流程图：算法的图形化表示方法矩形框矩形框:表示要执行的指令，在框内标注指令内容；表示要执行的指令，在框内标注指令内容；菱形框菱形框:表示要判断其中表达式的值是真还是假；表示要判断其中表达式的值是真还是假；箭头线箭头线:标示指令的流程方向。标示指令的流程方向。伪码：伪码：伪码是介
3、于自然语言和程序设计语言之间的一种类自然伪码是介于自然语言和程序设计语言之间的一种类自然语言的表示方法，书写形式自由，容易转换为程序。语言的表示方法，书写形式自由，容易转换为程序。C+程序设计7 顺序结构 分支结构 循环结构2.1.3算法描述的三种基本结构算法描述的三种基本结构任何算法的描述都可以分解为三种基本结任何算法的描述都可以分解为三种基本结构或它们的组合构或它们的组合C+程序设计8 顺序结构顺序结构步骤1步骤2步骤nC+程序设计9 分支结构分支结构条件语句1语句2TF条件语句1TFC+程序设计10 循环结构循环结构条件T循环体F当型（while）循环条件T循环体F直到型循环（do循环的
4、反条件）C+程序设计11 2.2.1 if语句语句 2.2.2 if语句的嵌套语句的嵌套 2.2.3 条件运算符条件运算符 2.2.4 switch语句语句C+程序设计122.2.1 if 语句if(表达式表达式)语句语句1;if(表达式表达式)语句语句1；else语句语句2;C+程序设计13执行流程执行流程false(0)表达式表达式 语语 句句格式格式1：if(表达式表达式)语句语句1;C+程序设计14执行流程执行流程 表达式表达式 语语 句句 1语语 句句 2格式格式2：if(表达式表达式)语句语句1；else 语句语句2;C+程序设计15分析：读入三个数，先求出两个数中分析：读入三个数
5、，先求出两个数中较大者，再将该大数与第三个数比较，较大者，再将该大数与第三个数比较，求出最大数。求出最大数。int main()int a,b,c,max;coutabc;couta=atb=b tc=c=b)max=a;else max=b;if(cmax)max=c;cout“最大数为最大数为:”maxendl;return 0;【例例2.5】从键盘上输入三个整数，输出其中的最大数。从键盘上输入三个整数，输出其中的最大数。C+程序设计16例例2.4 2.4 输入一个年份，判断是否为闰年输入一个年份，判断是否为闰年#includeusing namespace std;int main()i
6、nt year;cout“输入年份输入年份”year;if(year%4=0&year%100!=0|year%400=0)cout year “年时闰年年时闰年”endl;else coutyear“年不是闰年年不是闰年”endl;return 0;C+程序设计17 2.2.2 if 语句的嵌套 嵌套嵌套if语句：语句：if 语句中，如果内嵌语句又是语句中，如果内嵌语句又是if语句，就构成了语句，就构成了嵌套嵌套if语句。语句。if 语句可实现二选一分支，而嵌套语句可实现二选一分支，而嵌套if语句则可以实现多选一的多路分支情况。语句则可以实现多选一的多路分支情况。嵌套在嵌套在else分支中分
7、支中:if(表达式表达式1)语句语句1;else if(表达式表达式2)语句语句2;else if else 语句语句n;嵌套在嵌套在if分支中：分支中：if()if()；else ;C+程序设计18 2.2.2 if 语句的嵌套语句的嵌套配对关系实例：配对关系实例：/语句语句1：if(n%3=0)if(n%5=0)coutn是是15的倍数的倍数endl;else cout n是是3的倍数但不是的倍数但不是5的倍数的倍数 endl;/语句语句2：if(n%3=0)if(n%5=0)coutn是是15的倍数的倍数endl;else cout n 0，方程有两个不同实根；方程有两个不同实根；*若若
8、delta0，方程无实根。，方程无实根。【例例2.82.8】求一元二次方程的根。求一元二次方程的根。C+程序设计20#include#include using namespace std;int main()float a,b,c;float delta,x1,x2;cout输入三个系数输入三个系数a(a!=0),b,c:abc;couta=atb=btc=cendl;delta=b*b-4*a*c;C+程序设计21if(delta=0)cout方程有两个相同实根方程有两个相同实根:;coutx1=x2=-b/(2*a)0)delta=sqrt(delta);x1=(-b+delta)/(2
9、*a);x2=(-b-delta)/(2*a);cout方程有两个不同实根方程有两个不同实根:;coutx1=x1tx2=“x2endl;else cout方程无实根方程无实根!endl;/delta0return 0;请在请在VC+VC+平台上运行，输入不同的系数，使程序所有分支都可平台上运行，输入不同的系数，使程序所有分支都可以被执行一次。以被执行一次。C+程序设计222.2.3 条件运算符“?:”三元运算符三元运算符“?:”可以用来简化可以用来简化if语句表达。其构成语句表达。其构成的表达式格式为：的表达式格式为：表达式表达式1?表达式表达式2:表达式表达式3C+程序设计23例如：例如：
10、int a=6,b=7,min;min=ab?a:b;/min=6min=ab?+a:+b;/min=7 a=7 b=7 min=ab?a+:b+;/min=6 a=7 b=7C+程序设计24#include using namespace std;int main()char ch;cout ch;if(ch=A&ch=Z)ch+=32;cout ch=A&ch=Z)?ch+32:ch;把输入字符转换为小写字母。对输入字符进行判把输入字符转换为小写字母。对输入字符进行判断，如果是大写字母，则转换为小写字母；否则，不断，如果是大写字母，则转换为小写字母；否则，不转换。转换。C+程序设计25 s
11、witch(表达式表达式)case 常量表达式常量表达式 1 :语句语句 1 case 常量表达式常量表达式 2 :语句语句 2 case 常量表达式常量表达式 n :语句语句 n default :语句语句 n+1 注：注：表达式类型为非浮点型表达式类型为非浮点型 各常量表达式类型要与之匹配各常量表达式类型要与之匹配 各常量表达式要求各不相等各常量表达式要求各不相等 defaultdefault子句可选。缺省时，子句可选。缺省时，没有匹配值没有匹配值switch switch 语句为空语句为空2.2.4 switch语句 根据一个整型表达式的值决定程序分支根据一个整型表达式的值决定程序分支C
12、+程序设计26表达式表达式 语句语句 1 语句语句 2 语句语句 3 语句语句 n 语句语句n+1=常量常量1 1=常量常量2 2=常量常量3 3=常量常量n ndefaultdefault执行流程执行流程2.2.4 switch语句C+程序设计27例题根据考试成绩的等级打印出百分制分数段。例题根据考试成绩的等级打印出百分制分数段。#include using namespace std;int main()char grade;cout “输入等级输入等级(ad):grade;switch(grade)case a:cout 85_100 n ;case b:cout 70_84 n ;ca
13、se c:cout 60_69 n ;case d:cout 60 n ;default :cout error n ;return 0;C+程序设计28例题例题 根据考试成绩的等级打印出百分制分数段。根据考试成绩的等级打印出百分制分数段。#include using namespace std;int main()char grade;cout 输入等级输入等级(ad):grade;switch(grade)case a:cout 85_100 n ;break;case b:cout 70_84 n ;break;case c:cout 60_69 n ;break;case d:cout
14、 60 n ;break;default :cout error n ;return 0;C+程序设计29if if 语句语句switch switch 语句语句 形成分支控制流程形成分支控制流程 不形成程序控制流程不形成程序控制流程 用于复杂条件判断用于复杂条件判断 表达式的值为数值集合时作多分支表达式的值为数值集合时作多分支 控制控制,可读性较好可读性较好 switch语句与语句与 if 语句比较语句比较:C+程序设计30【例例2.10】设计一个计算器程序，实现加、减、乘、除运算。设计一个计算器程序，实现加、减、乘、除运算。分析：读入两个操作数和运算符，根据运算符完成相应运算。分析：读入两
15、个操作数和运算符，根据运算符完成相应运算。#include using namespace std;int main()float num1,num2;char op;cout输入操作数输入操作数1，运算符，操作数，运算符，操作数2：num1opnum2;switch(op)case+:coutnum1opnum2=num1+num2endl;break;case-:coutnum1opnum2=num1-num2endl;break;case*:coutnum1opnum2=num1*num2endl;break;case/:coutnum1opnum2=num1/num2endl;brea
16、k;default:coutop是无效运算符是无效运算符!;return 0;C+程序设计31 2.3.1 while语句语句 2.3.2 do-while 语句语句 2.3.3 for语句语句 2.3.4 循环的嵌套循环的嵌套 C+程序设计32循环条件 循环体 truefalse注意：注意：1）循环开始）循环开始前前对对循环条件循环条件进行进行初始化初始化；2）在循环体语句中要包含修改循环条件的语句，否则循环）在循环体语句中要包含修改循环条件的语句，否则循环将不能终止而陷入死循环。将不能终止而陷入死循环。2.3.1 while语句 while语句也称为当循环语句也称为当循环,语句格式为：语句
17、格式为：while(表达式表达式)循环体语句；循环体语句；C+程序设计33#include using namespace std;int main()int i=1,sum=0;while(i=100)sum=sum+i;i+;cout sum=sum endl;return 0;i=100sum=sum+i;i+;1 10 0 i=1;sum=0;想一想：想一想：循环条件是什么？循环条件是什么？循环结束条件是什么？循环结束条件是什么？哪一个语句修改循环条件？哪一个语句修改循环条件？一个简单的循环跟踪：一个简单的循环跟踪：求求1001iisumC+程序设计34while(i=n)sum+=i
18、+;while(sum+=i+,i=n);/循环体为空语句循环体为空语句这两种表达方式与例这两种表达方式与例2.11中的循环语句从执中的循环语句从执行结果看是完全等价的。需要说明的是，行结果看是完全等价的。需要说明的是，虽然虽然C+可以让代码最大限度优化，但往往造成可读可以让代码最大限度优化，但往往造成可读性降低性降低，因此程序设计者只需理解这种表达方法，因此程序设计者只需理解这种表达方法的意义，而设计时主要追求的目标应是的意义，而设计时主要追求的目标应是可读性可读性。C+程序设计35循环条件 循环体 truefalse直到型循环直到型循环2.3.2 do-while 语句 do-while语
19、句称为直语句称为直到循环，格式为：到循环，格式为：do 循环体语句循环体语句 while(表达式表达式)；C+程序设计36 do/while语句和语句和while语句的区别：语句的区别：do/while语句至少执行一次循环体后再判断循语句至少执行一次循环体后再判断循环条件是否满足；环条件是否满足；while语句先判断条件是否满足，然后才执行语句先判断条件是否满足，然后才执行循环体。可能一次也不执行。循环体。可能一次也不执行。多数情况下可以互相替代。多数情况下可以互相替代。C+程序设计37【例例2.12】用迭代法求用迭代法求a的平方根近似值。的平方根近似值。求平求平方根的迭代公式为：方根的迭代公
20、式为：要求前后两个迭代根之差小于要求前后两个迭代根之差小于10-5。迭代法求解：迭代法求解：a是已知正数，是已知正数，x 0是迭代初值，给是迭代初值，给x 0一个值，假定一个值，假定 x 0=a/2；则用迭代公式依次计算：；则用迭代公式依次计算：x1=(x0+a/x0)/2；x2=(x1+a/x1)/2；xk+1=(xk+a/xk)/2；当当|xk+1 xk|0)及较小正数delta(也可用常变量)；2、x 0=a/2；用迭代公式算 x1=(x0+a/x0)/2；3、while(|x1 x0|=delta)x 0=x 1 ；/把最近的值给把最近的值给x 0 x1=(x0+a/x0)/2；/求求
21、xk+1时只需要知道时只需要知道xk的值，所以只需的值，所以只需2个变量个变量4、取x1的值为a的平方根近似值，输出。和迭代法对应的程序算法是递推算法：C+程序设计39#include#include using namespace std;int main()float x0,x1,a;couta;if(a0)couta不能开平方不能开平方!=1e-5);cout a的平方根为：的平方根为：x1endl;return 0;C+程序设计402.3.3 for 语句 for循环语句的格式循环语句的格式for(表达式表达式1;表达式表达式2;表达式表达式3)循环体语句循环体语句 表达式表达式2循环
22、体循环体表达式表达式1表达式表达式3关键字关键字初始表达式初始表达式循环控制循环控制逻辑表达式逻辑表达式循环后置表达式循环后置表达式C+程序设计41例如，用例如，用 for for 语句的求和式语句的求和式 的程序的程序1001iisum#include using namespace std;int main()int i,sum=0;for(i=1;i=100;i+)sum+=i;cout sum=sum endl;return 0;#include using namespace std;int main()int i=1,sum=0;while(i=100)sum=sum+i;i+;c
23、out sum=sum endl;return 0;C+程序设计42for语句、while语句、do/while语句比较：int i=1,sum=0;/循环初始条件循环初始条件while(i=4)sum+=i;i+;/修改循环条件修改循环条件 int i=1,sum=0;/循环初始条件循环初始条件do sum+=i;i+;/修改循环条件修改循环条件 while(i=4);int i,sum=0;for(i=1;i=4;i+)sum+=i;/*习惯上：表达式习惯上：表达式1 1：循环初始条件；表达式：循环初始条件；表达式2 2：循环终：循环终止条件；表达式止条件；表达式3 3：修改循环条件：修改
24、循环条件*/C+程序设计43(1)for语句属于先判断型，与语句属于先判断型，与while语句完全等同。语句完全等同。(2)for语句中的三个表达式都是包含逗号表达式在内的任意语句中的三个表达式都是包含逗号表达式在内的任意表达式。表达式。如如【例例2.11】中的循环部分用中的循环部分用for语句可描述为：语句可描述为：for(i=1,sum=0;i=100;i+)sum+=i;(3)for语句中的三个表达式可部分或全部省略，但两个分号语句中的三个表达式可部分或全部省略，但两个分号不能省略。如上述语句还可写为：不能省略。如上述语句还可写为：i=1;sum=0;for(;i=100;)sum+=i
25、;i+;实际上，表达式实际上，表达式2也可省略，形如也可省略，形如for(;)这种情况下，约定表达式这种情况下，约定表达式2的值为的值为1，即等同，即等同for(;1;)死循环，用死循环，用break跳出。跳出。for语句的几点说明：C+程序设计44【例例2.142.14】运行结果：运行结果：0 1 1 2 35 8 13 21 3455 89 144 233 377610 987 1597 2584 4181【例例2.142.14】设计程序输出设计程序输出FibonaciiFibonacii数列的前数列的前2020项，要求每行输出项，要求每行输出5 5个数据。个数据。C+程序设计45Fibo
26、nacii数列定义如下：数列定义如下：1n 1)-fib(n2)-fib(n1n 1 0n 0 fib(n)算法分析：除了第算法分析：除了第0项和第项和第1项外，每一项都是由类项外，每一项都是由类似方法产生，即前两项之和；所以求当前项时，只似方法产生，即前两项之和；所以求当前项时，只需要记住前两项；程序不需要为每一项设置专用变需要记住前两项；程序不需要为每一项设置专用变量；量；属属递推算法递推算法。C+程序设计46算法：算法：1、设置变量、设置变量n表示第几项，变量表示第几项，变量 f 1和和 f 2用来记住用来记住当前项当前项f 3之前的两项之前的两项；变量初始化；变量初始化n=0；2、第、
27、第0项项 f 1=0;第第1项项 f 2=1;输出第输出第0项和第项和第1项；项；while（当前项不到第（当前项不到第20项）项）当前项等于前两项之和：当前项等于前两项之和：f 3=f 1+f 2;按要求输出按要求输出当前项当前项 f 3;修改最前两项：修改最前两项：f 1=f 2;f 2=f 3;C+程序设计47#include#include using namespace std;int main()int fib0=0,fib1=1,fib2,n;coutsetw(5)fib0setw(5)fib1;for(n=3;n=20;n+)fib2=fib0+fib1;coutsetw(5)
28、fib2;if(n%5=0)coutendl;/控制每行控制每行5个数据个数据fib0=fib1;fib1=fib2;return 0;C+程序设计48【例例2.15】输入一个不超过输入一个不超过9 9位的整数，将其反向后位的整数，将其反向后输出。例如输入输出。例如输入247247，变成，变成742742输出。输出。算法分析：算法分析：1、将整数的各个数位逐个分开，用一个数组保存各、将整数的各个数位逐个分开，用一个数组保存各位的值，然后反向组成新的整数。位的值，然后反向组成新的整数。2、将整数各位数字分开的方法是，通过求余得到个、将整数各位数字分开的方法是，通过求余得到个位数，然后将整数缩小十
29、倍，再求余，并位数，然后将整数缩小十倍，再求余，并重复上述过重复上述过程程，分别得到十位、百位，分别得到十位、百位，直到直到整数的值变成整数的值变成0为止为止。C+程序设计49数据处理：数据处理：1、设置变量、设置变量num表示输入的整数，整型数组表示输入的整数，整型数组digit9用来存放用来存放num 的各个位；变量的各个位；变量i用来表示数组的当前下标；用来表示数组的当前下标；算法：算法：1、输入、输入num;变量初始化：变量初始化：i=0;2、while（num!=0）num对对10取余取余,得得num的当前个位数放入的当前个位数放入digiti；num整除整除10，即去掉个位数，十位
30、变个位，即去掉个位数，十位变个位，百位变十位，百位变十位，；i+;/数组数组digit准备记录下一位；准备记录下一位；3、将数组元素按下标从低到高的顺序反向组合；、将数组元素按下标从低到高的顺序反向组合；C+程序设计50#include using namespace std;int main()int i,num,subscript,digit9;cout输入一个不超过输入一个不超过9位的整数：位的整数：num;cout原来的整数为：原来的整数为：num0);for(i=0;isubscript;i+)/整数的反向组合整数的反向组合num=num*10+digiti;cout反向后整数为：反
31、向后整数为：numendl;return 0;C+程序设计512.3.4 循环的嵌套 嵌套循环：嵌套循环：当循环语句中的循环体中又有循环语句时，就当循环语句中的循环体中又有循环语句时，就构成了嵌套循环。构成了嵌套循环。嵌套层次一般嵌套层次一般不超过不超过3层层，以保证可读性。，以保证可读性。C+程序设计52【例例2.16】打印九九表。打印格式为：打印九九表。打印格式为：*1 2 3 4 5 6 7 8 9 1 1 2 2 43 3 6 99 9 18 27 36 45 54 63 72 812.3.4 循环的嵌套C+程序设计53算法：算法：1、输出表头，用一个循环语句即可；、输出表头，用一个循
32、环语句即可；2、输出表体：、输出表体：for(i=1;i10;i+)couti;/输出行号输出行号 输出第输出第i行数据；行数据；/A coutendl;/准备输出下一行准备输出下一行 3、A行细化：行细化：for(j=1;j=i;j+)coutsetw(4)i*j;C+程序设计54#include#include using namespace std;int main()int i,j;coutsetw(3)*setw(4);for(i=1;i10;i+)coutsetw(4)i;/输出表头输出表头(乘数乘数)coutendlendl;for(i=1;i10;i+)coutsetw(3)i
33、setw(4);/输出行号输出行号(被乘数被乘数)for(j=1;j=i;j+)coutsetw(4)i*j;/输出表中数据输出表中数据(乘积乘积)coutendl;/准备输出下一行准备输出下一行 return 0;C+程序设计55 break&continue goto returnC+程序设计56break&continue break语句语句 无条件地结束无条件地结束switch语句，或循环语句，转语句，或循环语句，转向执行语句块的后续语句向执行语句块的后续语句 continue语句语句 用于循环体中，终止当前一次循环用于循环体中，终止当前一次循环C+程序设计57while (E1)语句
34、语句 1 if (E2)break ;语句语句 2while(E1)语句语句 1 if(E2)continue;语句语句 2 语句语句2 E 1 语句语句1 E2 下一语句下一语句 breakbreak 语句语句2 E 1 语句语句1 E 2 下一语句下一语句 continuecontinue break 与与 continue 语句比较语句比较C+程序设计58 for(I=1;I2，m是素数的条件是不能被是素数的条件是不能被2,3,，（，（m的平方根取整）整除。因此可以的平方根取整）整除。因此可以用用2,3,k（k为为m的平方根取整）逐个去除的平方根取整）逐个去除m，如，如果被其中某个数整除
35、了，则果被其中某个数整除了，则m不是素数，否则是不是素数，否则是素数。素数。算法属于穷举法。算法属于穷举法。C+程序设计60#include#include using namespace std;int main()int m,i,k;cout输入整数输入整数m：m;if(m=2)coutm是素数是素数endl;elsek=sqrt(m);for(i=2;ik)cout m是素数是素数endl;elsecout m不是素数不是素数endl;return 0;C+程序设计61goto语句语句goto语句和标号语句一起使用，所谓标号语句是用标识符标语句和标号语句一起使用，所谓标号语句是用标识符标
36、识的语句，它控制程序从识的语句，它控制程序从goto语句所在的地方转移到标号语句语句所在的地方转移到标号语句处。处。goto语句会导致程序结构混乱，可读性降低，语句会导致程序结构混乱，可读性降低，而且它所完成而且它所完成的功能完全可以用算法的三种基本结构实现，的功能完全可以用算法的三种基本结构实现，因此一般不提倡因此一般不提倡使用使用goto语句。语句。但在某些特定场合下但在某些特定场合下goto语句可能会显出价值，比如语句可能会显出价值，比如在多层在多层循环嵌套中，要从深层地方跳出所有循环循环嵌套中，要从深层地方跳出所有循环，如果用，如果用break语句，语句，不仅要使用多次，而且可读性较差
37、，这时不仅要使用多次，而且可读性较差，这时goto语句可以发挥作语句可以发挥作用用。语法：语法：goto 标号标号;标号标号:语句语句C+程序设计62return语句 return语句用于结束函数的执行，返回调用语句用于结束函数的执行，返回调用者，如果是主函数，则返回至操作系统。者，如果是主函数，则返回至操作系统。利用一个利用一个return语句可以将一个数据返回给语句可以将一个数据返回给调用者。通常，当函数的返回类型为调用者。通常，当函数的返回类型为void时，时，return语句可以省略，如果使用也仅作为函语句可以省略，如果使用也仅作为函数或程序结束的标志。数或程序结束的标志。语法：语法：
38、return 表达式表达式;或或return (表达式表达式);或或return;C+程序设计63 筛选法，枚举法，穷举法筛选法，枚举法，穷举法 各种尝试各种尝试C+程序设计64【例例2.202.20】中国中国古代数学史上著名的古代数学史上著名的“百鸡问题百鸡问题”【例例2.212.21】用欧基里德算法（也称辗转法）用欧基里德算法（也称辗转法）求两个整数的最大公约数求两个整数的最大公约数【例例2.232.23】输入一个输入一个8 8位二进制数，将其转位二进制数，将其转换为十进制数输出。换为十进制数输出。【例例2.192.19】用筛选法求用筛选法求100100之内的所有素数之内的所有素数【例例2
39、.222.22】输入一个小于输入一个小于1 1的数的数x x，求，求sinxsinx的的近似值近似值C+程序设计651 1、判断一个数是否素数？、判断一个数是否素数？2 2、100100之内的所有素数？方法：一个个试之内的所有素数？方法：一个个试;综上所述，得到一个循环嵌套的算法：综上所述，得到一个循环嵌套的算法：for（m=2；m=100；m+）/穷举法穷举法 if（m是素数）按要求的格式输出是素数）按要求的格式输出m;k=sqrt(m);for(i=2；ik)m是素数；是素数；/刚才的刚才的for不是由不是由break结束的结束的直接法【例2.19】求100之内的所有素数，并将这些素数输出
40、，每行输出 2个数据。C+程序设计66【例2.19】求100之内的所有素数，并将这些素数输出，每行输出 2个数据。一个数如果是其他数的倍数，则这个数肯定不是素数；在由 多个大于1的数 组成的集合中，剔除所有的非素数，剩下的就都是素数了；筛选法算法二（及所需的相应数据）：1、将100之内的整数映射到一个集合。可以采用一个数组a来表示，数组元素值为各个整数；2、在数组a中，从素数2开始剔除掉新找到的素数的整数倍的元素值（置0，非素数）；3、输出数组a中数组元素值非0的元素，他们都是素数。C+程序设计67 第 2步 的细化：筛选法for(i=0;i=99;i+)/数组下标099，元素值1100 2.
41、1、if(ai=0)continue;/ai已被定为非素数，并已被筛掉2.2、将数组中所有是ai倍数的元素置0；for(j=i+1；j=99；j+)if(aj%ai=0)aj=0;算法二：2、在数组a中，从素数2开始剔除掉新找到的素数的整数倍的元素值（置0，非素数）；C+程序设计68#include#include#includeusing namespace std;const int n=100;int main()int an;int i,j;for(i=0;in;i+)ai=1+i;/用数组保存整数用数组保存整数1-100a0=0;/1不是素数，置不是素数，置0for(i=1;in;i
42、+)if(ai=0)continue;/该数已经置该数已经置0,判断下一个判断下一个 for(j=i+1;jn;j+)if(aj%ai=0)aj=0;/是是ai倍数的元素置倍数的元素置0；【例2.19】求100之内的所有素数，并将这些素数输出，每行输出 2个数据。筛选法C+程序设计69int count=0;cout1 n之间的素数：之间的素数：endl;for(i=0;in;i+)/输出所有素数输出所有素数if(ai!=0)coutsetw(6)ai;count+;if(count%10=0)coutendl;/每行每行10个个coutendl;return 0;运行结果：运行结果：1100
43、之间的素数：之间的素数：2 3 5 7 11 13 17 19 23 2931 37 41 43 47 53 59 61 67 7173 79 83 89 97筛选法C+程序设计70枚举法 枚举法也称穷举法，基本思想是，在有限范围内列举所有可能的结果，找出其中符合要求的解。枚举法适合求解的问题是：可能的答案是有限个且答案是可知的，但又难以用解析法描述。这种算法通常用循环结构来完成。C+程序设计71设鸡翁、母、雏分别为i，j，k，根据题意可得：i*5+j*3+k/3=100;i+j+k=100;两个方程无法解出三个变量，只能将各种可能的取值代入，其中能满足两个方程的就是所需的解，因此这是枚举算法
44、（也叫穷举法）的应用。i、j、k可能的取值有哪些？分析可知，百钱最多可买鸡翁20，鸡母33，鸡雏300。【例2.20】中国古代数学史上著名的“百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？枚举法C+程序设计72这个算法使用三重循环，执行时间函数是立方阶，循环体这个算法使用三重循环，执行时间函数是立方阶，循环体将执行将执行20*33*300=198000次。次。我们希望在算法上改进一下，如能减少一重循环，将大大我们希望在算法上改进一下，如能减少一重循环，将大大缩短运行时间。缩短运行时间。for(i=0;i=20;i+)for(j=0;j=33;j+
45、)for(k=0;k=300;k+)if(i+j+k=100)&(5*i+3*j+k/3=100)coutijk;枚举法 算法：算法：C+程序设计73枚举法 实际上，当实际上，当i、j确定时，确定时，k就可由题目要求确定为就可由题目要求确定为100-i-j，因此实际上只要用因此实际上只要用i、j去测试，用钱数检测就可以了。循去测试，用钱数检测就可以了。循环体将执行环体将执行:20*33=660次。次。算法改进为：算法改进为：for(i=0;i+=20;)for(j=0;j+=33;)if(5*i+3*j+(100-i-j)/3=100)coutijk;C+程序设计74#include#incl
46、ude using namespace std;int main()int i,j,k;cout 公鸡公鸡 母鸡母鸡 小鸡小鸡endl;for(i=0;i=20;i+)for(j=0;j=33;j+)k=100-i-j;if(5*i+3*j+k/3=100)&(k%3=0)/注意注意(k%3=0)非常重要非常重要，想一想为什么，想一想为什么 coutsetw(6)isetw(10)jsetw(10)knum2;2.2、2.2.1、设置变量resd=num1%num2；/包含了步骤2.1 2.2.2、if(resd=0)当前num2就是最大公约数；else num1=num2,num2=resd
47、;重复2.2.1和2.2.2，直到resd=0为止。步骤2辗转法可用以下程序段表示：do resd=num1%num2；if(resd=0)当前num2就是最大公约数；else num1=num2,num2=resd;while(resd!=0);3、输出当前的num2。C+程序设计78int main()int num1,num2,resd;cout输入两个整数：输入两个整数：num1num2;coutnum1和和num2的最大公约数为：的最大公约数为：;for(;)resd=num1%num2;if(resd=0)break;num1=num2;num2=resd;coutnum2endl
48、;return 0;程序递推法C+程序设计79【例2.22】输入一个小于1的数x，求sinx的近似值，要求误差小于0.0001。近似计算公式如下：!7x!5x!3xx)xsin(753这个近似计算可以看作一个累加过程，关键在于累加项数的确定。如果用item保存第n项，则推出第n+1项的方法为：itemitem*x*x/(2*n)*(2*n+1)C+程序设计80程序：程序：int main()const double epsilon=0.0001;/用用epsilon保存误差保存误差double x,sinx,item;int n=2,sign=-1;/sign保存符号保存符号coutx;sin
49、x=x;item=x*x*x/6;/第一项作为初值，第二项为误差项第一项作为初值，第二项为误差项while(itemepsilon)sinx=sinx+item*sign;/将当前项累加进结果，注意符号作为因子将当前项累加进结果，注意符号作为因子item=item*x*x/(2*n)*(2*n+1);/推算新的误差项推算新的误差项sign=-sign;/注意符号的变换注意符号的变换n+;coutsin(x)=sinx=0;i-)/系数从a n 到a 0 依次投入运算 dec=dec*x+(bini-0);/(bini-0)：数字字符转换为数字【例2.23】输入一个8位二进制数，将其转换为十进制
50、数输出C+程序设计83程序：const int n=8;int main()char binn;int x=2,a,dec,i;cout输入二进制序列：=0;i-)cinbini;/先输入的是高位 dec=0;for(i=n-1;i=0;i-)a=bini-0;/数字字符转换为数字dec=dec*x+a;cout=0;i-)coutbini;cout)的值为:decendl;return 0;C+程序设计84 2.7.1 枚举类型的定义枚举类型的定义 2.7.2 枚举变量的使用枚举变量的使用C+程序设计852.7 枚举类型 枚举类型枚举类型(enumerate)是是c+中的一种派生数中的一种派
