ok
第三章 基本控制结构程序设计
结构化程序设计的特点是任何程序都可由 三种基
本结构 及其组合来描述，这三种分别是 顺序结构、
选择结构和循环结构 。本章将介绍 C++分支结构和
循环结构的设计方法。这两种结构分别用 C++提供
的两类流程控制语句 分支语句 和 循环语句 来实现。
所谓 流程控制语句,是专门用来控制程序执行流程
的语句，也称为 过程化语句 。在介绍分支语句、循
环语句及其程序设计的同时，还将介绍一些 常用算
法,并通过实例实践结构化程序设计的方法。
ok
第三章 基本控制结构程序设计
3,1 分支结构程序设计
3,4 常用算法的应用实例
3,3 转向语句
3,2 循环结构 程序设计
ok
3.1 分支结构程序设计
对程序的运行流程进行控制，主要通过某些
条件进行判断来执行不同的语句。 分支语句 是三
种基本流程控制语句之一。 C++提供以下三种分
支语句：
3.1.1 if语句
3.1.2 条件运算符,?:‖
3.2.1 swich语句
ok
3.1.1 if 语句
if语句有三种格式为：
1,if(<表达式 >) <语句 1>;
2,if(<表达式 >) <语句 1>;
else <语句 2>;
3,if(<表达式 1>) <语句 1>;
else if (<表达式 2>) <语句 2>;
……
else if (<表达式 n>) <语句 n>;
else 语句 n+1；
ok
【 例 3,1】 输入一个年份，判断是否闰年。
算法分析, 假定年份为 year,闰年的条件是,
year%4==0&&year%100!=0||year%400==0。
#include <iostream.h>
void main( )
{ int year;
cout<<"输入年份,"<<endl;
cin>>year;
if(year%4==0&&year%100!=0
||year%400==0)
cout<<year<<"是闰年 "<<endl;
else
cout<< year<<"不是闰年 "<<endl;
}ok
ok
分析：读入三个数, 先求出两个数中较大者, 再将该大数与
第三个数比较, 求出最大数 。
#include <iostream.h>
class ThreeNumber {
private:
int a,b,c;
public:
void Input3Integers();
void GetMax();
};
int main()
{ ThreeNumber a;
a.Input3Integers();
a.GetMax();
return 0;
}
【 例 3,2】 从键盘上输入三个整数，输出其中的最大数。
ok
void ThreeNumber::Input3Integers()
{ cout << ―Input 3 Integers:\n‖;\
cin >> a >> b >> c;
}
int ThreeNumber::GetMax()
{ int max;
if(a > b)
if(a > c) max = a;
else max = c;
else
if(b > c) max = b;
else max = c;
cout << ―The Max Integers is,‖
<< max << endl;
}
ok
if 语句中, 如果内嵌语句又是 if语句, 就构
成了 嵌套 if语句 。 if 语句可实现 二选一 分支, 而
嵌套 if语句则可以实现 多选一 的多路分支情况 。
嵌套有两种形式, 第一种是嵌套在 else分支中,
if (<表达式 1>) <语句 1>;
else if (<表达式 2>) 语句 2;
else if …
else <语句 n>;
第二种是嵌套在 if分支中为：
if (<表达式 1>) if (<表达式 2>) <语句 1>；
else <语句 2>;
我们可以见上面的 GetMax()函数
ok
要 特别注意 else和 if的配对关系 。 C++规定了
if和 else的,就近配对,原则，即相距最近且还
没有配对的一对 if和 else首先配对。按上述规定，
第二种嵌套形式中的 else应与第二个 if配对。如
果根据程序的逻辑需要改变配对关系，则要将属于
同一层的语句放在一对,{}‖中。如第二种嵌套形
式中，要让 else和第一个 if配对，语句必须写成：
if (表达式 1) {
if (表达式 2) 语句 1 ;
}
else 语句 2 ;
第二种嵌套形式较容易产生逻辑错误，而第
一种形式配对关系则非常明确，因此从程序可读性
角度出发，建议尽量使用第一种嵌套形式。
ok
请看以下两个语句,//语句 1：
if(n%3==0)
if(n%5==0)
cout<<n<<―是 15的倍数” <<endl;
else
cout<<n<<―是 3的倍数但不是 5的倍数 ″
<<endl;
//语句 2：
if(n%3==0){
if(n%5==0)
cout<<n<<―是 15的倍数 ″<<endl;
}
else cout<<n<<―不是 3的倍数 ″
两个语句的差别只在于一个, {}”，但表达的逻辑关系却完
全不同。
ok
3.1.2 条件运算符,?:”
if语句在某些情况下可以用条件运算符,?:‖
来简化表达 。,?:‖是一个三元运算符, 其构成的
表达式格式为,<表达式 1>? <表达式 2>, <表
达式 3>执行逻辑：先计算表达式 1,若其值为真
（ 或非 0）, 则计算表达式 2（ 不计算表达式 3）,
并将该值作为整个表达式的值；反之, 即表达式 1
的值为假或为 0,则计算表达式 3（ 不计算表达式
2）, 并将该值作为整个表达式的值 。 例如：
int a=6,b=7,min=a<b?a:b; //min=6
min=a<b?++a:++b; //min=7 a=7 b=7
min=a<b?a++:b++; //min=6 a=7 b=7ok
ok
3.1.3 switch语句
用嵌套 if语句可以实现多选一的情况 。 另外 C++中
还提供了一个 switch语句, 称为开关语句, 也可以
用来实现多选一：
switch (表达式 ) {
case常量表达式 1:,语句序列 1;》, break;》
case常量表达式 2:,语句序列 2;》, break;》
……
case常量表达式 n:,语句序列 n;》, break;》
,default:语句序列 n+1;》
}
ok
switch语句格式
（ 1）各个 case（包括 default）分支出现的次序
可以任意，通常将 default放在最后。
（ 2） break语句可选，如果没有 break语句，每
一个 case分支都只作为开关语句的 执行入口,执行
完该分支后，还将接着执行其后的所有分支。因此，
为保证逻辑的正确实现，通常每个 case 分支都与
break语句联用。
（ 3）每个常量表达式的取值必须各不相同，否则
将引起歧义。
ok
（ 4）允许多个常量表达式对应同一个语句序列。
例如：
char score;
cin>>score;
switch (score) {
case ?A′,
case ?a′,cout<<″excellent″;
break;
case ?B′,
case ?b′,cout<<″good″;
break;
default,cout<<″fair″;
}
（ 5）从形式上看,switch语句的可读性比嵌套 if
语句好，但不是所有多选一的问题都可由开关
语句完成，这是因为开关语句中限定了条件表
达式的取值类型。ok
ok
switch语句例子
【 例 3,6】 运输公司对所运货物实行分段计费 。
设运输里程为 s,则运费打折情况如下：
s<250 不打折扣
250<=s<500 2%折扣
500<=s<1000 5%折扣
1000<=s<2000 8%折扣
2000<=s<3000 10%折扣
3000<=s 15%折扣
设每公里每吨的基本运费为 p,货物重量为 w,折扣
为 d,则总运费 f为,f=p*w*s*(1-d)
设计程序, 当输入 p,w和 s后, 计算运费 f。
ok
算法
1,输入每吨运费 p,货物重量 w,运输里程 s；
2,根据运输里程 s计算折扣 d；
3,计算总运费 f=p*w*s*(1-d)；
4,输出计算结果；
算法细化,2,根据运输里程 s计算折扣 d
分析,
如果用 switch语句, 必须使表达式符合语法要
求, 分析发现, 里程 s的 分段点均是 250的倍数,
因此, 将里程 s除以 250,取整数商, 便得到若
干整数值 。ok
ok
switch(c=s/250) {
case 0,d=0; break;
case 1,d=0.02; break;
case 2:
case 3,d=0.05; break;
case 4:
case 5:
case 6:
case 7,d=0.08; break;
case 8:
case 9:
case 10:
case 11:d=0.1;break;
default:d=0.15;
}
s<250 不打折扣
250<=s<500 2%折扣
500<=s<1000
5%折扣
1000<=s<2000
8%折扣
2000<=s<3000
10%折扣
3000<=s 15%折扣
ok
#include <iostream.h>
#include <iomanip.h>
void main( )
{ int c,s; float p,w,d,f;
cout<<"输入运输单价 p,重量 w和里程 s:"<<endl;
cin>>p>>w>>s; c=s/250;
switch(c){
case 0:d=0;break;
case 1:d=0.02;break;
case 2:case 3:d=0.05;break;
case 4:case 5:case 6:case 7:d=0.08;
break;
case 8:case9:case10:case11:d=0.1;break;
default:d=0.15;
}
f=p*w*s*(1-d);
cout<<"单价为 "<<p<<'\t'<<"重量为 "<<w<<'\t?
<<"里程为 "<<s<<endl;
cout<<"折扣为 "<<d<<endl<<"运费为 "<<f<<endl;}
请在 VC++平台上运行, 输入不同的里程, 使程序所有分支都可以被执行一次 。
ok
ok
【 例 3,7】 设计一个计算器程序，实现加、减、乘、除运算。
#include <iostream.h>
void main( )
{ float num1,num2,result;
char op;
cout<<"输入操作数 1，运算符，操作数 2,"<<endl;
cin>>num1>>op>>num2;
switch(op){
case '+',result = num1+num2; break;
case ?-',result = num1-num2; break;
case ?*',result = num1*num2; break;
case ?/',result = num1/num2; break;
default, cout<<op<<―是无效运算符 !‖;
}
if(op==?+‘||op==?-‘||op==?*‘||op==?/‘)
cout<<num1<<op<<num2<<"="<<result<<endl;
}
常量表达式采用字符型，上机运行一下。
ok
循环控制语句 是三种基本流程控制语句之
一。 C++提供以下三种循环语句：
? while语句
? do-while 语句
? for语句
3.2 循环结构程序设计
ok
循环结构程序设计
3.2.1 while语句
3.2.4 循环的嵌套
3.2.3 for语句
3.2.2 do-while 语句
ok
3.2.1 while 语句
while语句也称为当循环 。
语句格式为：
while (表达式 )
循环体语句；
图 3.1 while语句的执行流程图
求表达式的值
表达式
值为真?
是
否
执行循环体语句
ok
while 语句
【 例 3,8】 求 1+2+3+4+…+100 的值。
ok
N个连续整数相加算法
1、设置变量 i用来放被加数，变量 sum用来放和值,
并初始化 ;
2、从第一个数开始，依次将被加数赋给 i，并进行
操作 sum?sum+i;
3、输出 sum；
细化算法 2：
while(还有被加数 )
{ i=当前被加数；
sum += i;
i准备接受下一个被加数；
}
ok
源程序如下：
#include <iostream.h>
void main( )
{
int i=1,sum=0;//循环初始条件
while(i<=100) {
sum+=i;
i++; //修改循环条件
}
cout<<"sum="<<sum<<endl;
}
在 VC++平台上运行，试一试是否正确ok
ok
while 语句
注意：
在有循环语句的程序中，通常循环开始前
对循环条件进行初始化；而在循环体语
句中要包含修改循环条件的语句，否则
循环将不能终止而陷入死循环。
C++表达方式灵活，上例中的循环语句
还可以写成：
while (i<=n) sum += i++;
修改程序后在 VC++平台上运行，看是否正
确
ok
3.2.2 do-while 语句
do-while语句称为 直到循环,
格式为：
do 循环体语句
while( 表达式 )
否
是 表达式的
值为真?
执行循环体语句
求表达式的值
图 3.2 do-while语句的执行流程图
ok
do-while 语句
do/while语句和 while语句的区别：
多数情况下可以互相替代。
区别是,
do/while语句至少执行一次循环体后 再
判断循环条件是否满足；
while语句先判断条件是否满足，然后才
执行循环体。
ok
【 例 3,9】 用迭代法求 a的平方根近似值。
求平方根的迭代公式为：
要求前后两个迭代根之差小于 10- 5。
do-while 语句
迭代法求解,a是已知正数,x0是迭代初值，给 x0
一个值，假定 x0=a/2；则用迭代公式依次计算：
x1=(x0+a/x0)/2； x2=(x1+a/x1)/2； ……
xk+1=(xk+a/xk)/2；
当 |xk+1 –xk|<ε(ε是一个较小的正数 )时，迭代终
止,取 xk+1的值为 a的平方根近似值 。ok
ok
1、输入 a(a>0)及较小正数 delta(也可用常变量 )；
2,x0=a/2； 用迭代公式算 x1=(x0+a/x0)/2；
3,while（ |x1–x0|>=delta） {
x0=x1 ； //把最近的值给 x 0 ；
x1=(x0+a/x0)/2；
} //求 xk+1时只需要知道 xk的值，所以只需 2个变量；
4、取 x1的值为 a的平方根近似值，输出。
2,3步骤很适合用 do/while语句实现：
x1=a/2；
do {
x0=x1;
x1=(x0+a/x0)/2；
} while（ |x1–x0|>=delta） ;
和迭代法对应的程序算法是
递推算法：
回到
题目
ok
#include<iostream.h>
#include<math.h>
void main( ){
float x0,x1,a;
cout<<―输入一个正数：, ;
cin>>a;
if(a<0)cout<<a<<"不能开平方 !"<<endl;
else { //有实数解的情况
x1=a/2; //x1用于保存结果
do{
x0=x1;
x1=(x0+a/x0)/2;
} while(fabs(x1-x0)>=1e-5);
cout<<a<<"的平方根为,"<<x1<<endl;
}
}
在 VC++平台上运行, 输入 2,3,4,5试一试是否正确
回到
题目
ok
【 例 3,10】 输入一段文本, 统计文本的行数,
单词数及字符数 。 假定单词之间以空格或跳格或
换行符间隔, 且文本开始没有空行 。
算法分析,
1,逐个读入文本中的字符, 直到读到一个输入结
束符 EOF为止 。
2,如何算行数？ 行结束标志为读到字符 ′\n′；
3,如何算单词数？ 设一个变量 isword,读到字
符时 isword=1,读到间隔符时 isword=0；如果
读到一个字符而此时 isword值为 0,则说明刚开
始读一个单词； （ 如果读到一个间隔符而此时
isword值为 1,则说明刚读完一个单词； ）
4,如何算字符数？
do-while 语句
ok
ok
算法
1、设置变量 line,word,ch分别代表行数、
单词数、非分隔字符数，并初始化 ;设置变量
isword来辅助统计单词数 ;
2,do{
从键盘读入一个字符 c；
if(c==‘\n‘) line++;
if(是单词开头 ) word++;
if(c不是分隔符 ) ch++;
} while(c!= EOF );
3、输出统计结果。
将下面的程序在 VC++平台上运行，试一试是否正确
ok
#include<iostream.h>
void main()
{ char c;
int line=0,word=0,ch=0;
int isword=0;
do {
c=cin.get();
if(c==?\n‘) line++; //遇换行符行数 +1
if(c!=? ?&&c!=?\t‘&&c!=?\n‘){
//读到非间隔符
if(isword==0) word++;
//在单词的起始处给单词数 +1
ch++; //字符数加 +1
isword=1;
}
else isword=0; //读到间隔符
} while(c!=EOF);
cout<<‖行数：, <<line<<endl;
cout<<‖单词数：, <<word<<endl;
cout<<‖字符数：, <<char<<endl;
}
ok
3.2.3 for 语句
for循环语句的格式
为：
for ( <表达式 1>;
<表达式 2>;
<表达式 3> )
<循环体语句 >
图 3.3 for语句的执行流程图
否
是
求表达式 1的值
求表达式 2的值
表达式 2值
为真?
执行循环体语句
求表达式 3的值ok
ok
for语句,while语句,do/while语句
实现相同的功能,1+2+3+4+…+100
int i=1,sum=0;
//循环初始条件
while(i<=100)
{ sum+=i;
i++;
//修改循环条件
}
int i=1,sum=0;
//循环初始条件
do{ sum+=i;
i++;
//修改循环条件
}while(i<=100);
for( int i=1,sum=0; i<=100; i++ )
{ sum+=i;}
/*习惯上：表达式 1：循环初始条件；表达式 2：循环
终止条件；表达式 3：修改循环条件 */ok
ok
for 语句的应用
?for语句的几点说明：
1、是先判断型的，同 while语句；
2、使用更为灵活：
三个表达式可以是任意表达式，因此他们
就可以实现循环初始化、计算、修改循
环条件等任务，而不一定非在循环体中
进行；
ok
for 语句的应用
【 例 3,11】 设计程序输出 Fibonacii数列的前
20项, 要求每行输出 5个数据 。
Fibonacii数列定义如下：
算法分析,除了第 0项和第 1项外, 每一项都是
由类似方法产生, 即前两项之和；所以求当前
项时, 只需要记住前两项；程序不需要为每一
项设置专用变量；
属 递推算法 。
ok
算法：
1,设置变量 n表示第几项, 变量 f0和 f1用来记住
当前项 f2之前的两项 ；变量初始化 n=0；
2,while（ 当前项不到第 20项 ） {
if(当前项是第 0项 ) f0=0;
if(当前项是第 1项 ) f1=1;
if(当前项是第 2项或更高项 ) f2=f0+f1;
按要求输出 f2 ;
f0=f1; f1=f2; //记住最近两项
当前项后移一位；
}
ok
??
?
?
?
??
?
?
?
1n 1)-fi b ( n2)-fi b ( n
1n 1
0n 0
fi b ( n )
【 例 3,11】 设计程序输出 Fibonacii数列的前 20项, 要求
每行输出 2个数据 。 Fibonacii数列定义如下：
程序如下：
#include<iostream.h>
#include<iomanip.h>
void main()
{ int f0=1,f1=1,f2;
cout<<setw(5)<<f0<<setw(5)<<f1<<endl;
for(int n=2;n<20;n++){
f2=f0+f1;
cout<<setw(5)<<f2;
if(n%5==0) cout<<endl;
//控制每行 2个数据
f0=f1;
f1=f2;
}
}
ok
for 语句的应用
在 VC++平台上运行
运行结果：
0 1 1 2 3
5 8 13 21 34
55 89 144 233 377
610 987 1597 2584 4181
ok
【 例 3.12】 输入一个非负的整数, 将其反向后
输出 。 例如输入 24789,变成 98742输出 。
算法分析,
1,将整数的各个数位逐个位分开, 一个一个分别
输出 。
2,将整数各位数字分开的方法是, 通过对 10进
行求余得到个位数, 然后将整数缩小十倍, 再求
余, 并 重复上述过程, 分别得到十位, 百位 ……，
直到 整数的值变成 0为止 。
for 语句的应用
ok
ok
算法：
1,输入 num; 变量初始化,i=0;
2,while（ num!=0） {
num对 10取余,得 num的当前个位数并输出；
num整除 10并赋给 num,即去掉个位数,
十位变个位, 百位变十位, ……；
}
ok
程序如下：
#include <iostream.h>
class RevNumber {
private:
long int n;
public:
void InputData();
void OutRevData();
};
void main()
{ RevNumber a;
a.InputData();
a.OutRevData();
}
ok
void RevNumber::InputData()
{ cout << ―请输入一个非负整数：,
cin >> n;
}
void RevNumber::OutRevData()
{ while(n>0) {
cout << n%10;
n = n/10;
}
}
ok
3.2.4 循环的嵌套
【 例 3,13】 打印九九表 。 打印格式为：
* 1 2 3 4 5 6 7 8 9
----------------------------
1 1
2 2 4
3 3 6 9
……
9 9 18 27 36 45 54 63 72 81
当循环语句中的循环体中又有循环语句时，就构
成了嵌套循环。
嵌套层次一般不超过 3层，已保证可读性。
ok
循环的嵌套
分析,
1,计算机的输出是按行进行的, 因此可以先用一
个循环语句输出第一行表头 。
2,表中各行数据的输出可以用下面的算法描述：
for (i=1; i<10; i++)
{ cout<<i; //输出行号
输出第 i行数据； //A
cout<<endl; //准备输出下一行
}
ok
3,第 A行需要进一步细化 。 由于第 i行数据是一组
有规律的数列, 每个数的值是其所在行与列的乘
积, 因此输出第 i行可以：
for(j=1;j<10;j++)cout<<setw(5)<<i*j;
4,按上述算法输出的每一行都将有九列, 即打印
出的是矩形表而不是下三角形表 。 进一步分析发
现每一行的列数与所在行数相关, 因此要输出三
角形表, 上面的循环语句需稍作修改：
for(j=1;j<=i;j++)cout<<setw(5)<<i*j;
将此语句放到顶层算法的 A行即可 。
循环的嵌套
ok
#include <iostream.h>
#include <iomanip.h>
void main(){
cout<<'*'<<? ‘;
for(int i=1;i<10;i++)
cout<<setw(5)<<i; //输出表头
cout<<endl;
for(i=1;i<10;i++){
cout<<i<<' ';
//输出行号 (被乘数 )
for(int j=1;j<=i;j++)
cout<<setw(5)<<i*j;//输出表中数据
cout<<endl; //准备输出下一行
}
}
3.2.4 循环嵌套 __打印九九表
ok
3.3 转向语句
3,3,1 break语句
3,3,4 return语句
3,3,3 goto 语句
3,3,2 continue语句
ok
3.3.1 break 语句
break语句只能用在 switch语句 和 循环语
句 中，用来跳出 switch语句或提前终止循环，
转去执行 switch语句或循环语句之后的语句。
在 for循环中可以用 break结束循环：
for(; ;) {
…
if(<表达式 >) break;
…
}
ok
break 语句应用
【 例 3.14】 给定正整数 m,判定其是否为素数 。
分析,如果 m>2,m是素数的条件是不能被 2,3,…,（ 取整 ）
整除 。 因此可以用 2,3,…,（ 取整 ） 逐个去除 m,如果被其
中某个数整除了, 则 m不是素数, 否则是素数 。 ——算法属于
穷举法 。
1、输入被测数 m（ m>2）；令整型变量 k= sqrt(m)
2、判断 m是否素数：设置辅助整型变量 i,使 i从 2开始直到
k依次测试 m能否整除 i,若能，则不是素数；
for(i=2;i<=k;i++） if(m%i==0) break；
/* 条件满足,m不是素数,停止测试,结束 for语句。 */
3、根据 i是否已达到 k，输出结果是否为素数。
ok
#include <iostream.h>
#include <math.h>
void main()
{ int m,i,k;
cout<<"输入整数 m,"<<endl;
cin>>m;
if(m==2) cout<<m<<"是素数 "<<endl;
else{
k=sqrt(m);
for(i=2;i<=k;i++) if (m%i==0) break;
//只要有一个整除，就可停止
if(i>k) cout<< m<<"是素数 "<<endl;
//循环提前终止表示是非素数
else cout<< m<<"不是素数 "<<endl;
}
}
在 VC++平台上运行，改一下，使程序自动算出 100以内的素数
ok
3.3.2 continue 语句
continue语句只能用在 循环语句 中，用
来 终止本次循环 。当程序执行到 continue语
句时，将跳过其后尚未执行的循环体语句，
开始下一次循环 。下一次循环是否执行仍然
取决于循环条件的判断。
continue语句与 break语句的区别在于，
continue语句结束的只是 本次循环,而
break结束的是 整个循环 。
ok
例：输出 1～ 100内 3的倍数。
分析：设置整型变量 I从 1变化到 100，依次测试
I是否 3的倍数，算法属于穷举法。
for (I=1;I<=100;I++)
{ if ( I%3！ =0) continue;
//I不是 3的倍数，不输出，继续下一个 I;
输出 I的值； //I是 3的倍数才输出
}
ok
3.3.3 goto 语句
goto语句和标号语句一起使用，所谓标号语句
是用标识符标识的语句，它控制程序从 goto语句所
在的地方转移到标号语句处。 goto语句会导致程序
结构混乱，可读性降低，而且它所完成的功能完全
可以用算法的三种基本结构实现，因此一般不提倡
使用 goto语句。但在某些特定场合下 goto语句可能
会显出价值，比如在多层循环嵌套中，要从深层地
方跳出所有循环，如果用 break语句，不仅要使用多
次，而且可读性较差，这时 goto语句可以发挥作用。
ok
3.3.4 return 语句
return语句用于结束函数的执行，返回调用者，
如果是主函数，则返回至操作系统。
利用一个 return语句可以将一个数据返回给调
用者。通常，当函数的返回类型为 void时，
return语句可以省略，如果使用也仅作为函数
或程序结束的标志。
ok
3.4 常用算法及其应用实例介绍
算法,通俗地说，就是解决问题的方法和步骤。
它是一组有穷的规则，规定了解决某一特定类型问
题的一系列运算，算法是程序设计学习的重点。用
计算机解决问题的算法应具有以下特征：可执行性、
确定性、有穷性、可输入输出信息等特点。常见的
方法有,直接法、穷举法、递推法、递归法、回溯法等。
3.4.1 穷举法
3.4.2 递推法
3.4.3 递归法
ok
3.4.1 穷举法
穷举法是最简单、最常见的程序设计方法
之一，它充分利用计算机的高速特性，借助循
环结构实现特定范围里的穷举。
例：大奖赛评分程序，在唱歌比赛中，一
般有若干个评委，记分规则：去掉一个最高分
和最低分，再计算平均分。试编写一个在百分
制记分的情况下的程序实现。
算法分析,本问题的关键在于找出所有分中的
最大值和最小值，我们假设设置一个变量 max，
它的初始值为 0，来记录最大值，然后对所有
分进行穷举，如果还有比 max更大的，则把它
赋给 max，待所有分都穷举完毕后，则 max就
是最大值，求最小值的方法也类似。
ok
#include <iostream.h>
Class Score {
private:
int mNumber;
public:
Score(int i_Num) { mNumber = i_num; }
void GetResult();
}
void main()
{ Score m(15);
m.GetResult();
}
Void Score::GetResult()
{ int iScore,i,max = 0,min = 100; float fSum = 0;
for(I = 1; I <= mNumber; I ++) {
cout <<,输入第, << I <<,个分：” ;
cin >> iScore;
fSum += iScore;
if(iScore > max) max = iScore;
if(iScore < min) min = iScore;
}
cout <<,\n最后得分：” << (fSum-max-min)/(mNumber-2));
}
ok
3.4.1 穷举法
例, 世界数学史上著名的, 百鸡问题,,鸡翁一,
值钱五, 鸡母一, 值钱三, 鸡雏三, 值钱一 。
百钱买百鸡, 问鸡翁, 母, 雏各几何？
分析,设鸡翁, 母, 雏分别为 i,j,k,根据题
意可得,i*5+j*3+k/3*1=100;
i+j+k=100;
两个方程无法解出三个变量, 只能将各种可能
的取值代入, 其中能满足两个方程的就是所需
的解, 因此这是枚举算法 （ 也叫穷举法 ） 的应
用 。
i,j,k可能的取值有哪些？ 分析可知, 百钱
最多可买鸡翁 20,鸡母 33,鸡雏 300。
ok
3.4.1 穷举法
算法：
for (i=0; i<=20;i++)
for (j=0; j<=33;j++)
for (k=0; k<=300;k++)
if((i+j+k==100)&&(5*i+3*j+k/3==100))
cout<<i<<j<<k;
这个算法使用三重循环, 执行时间函数是方阶,
循环体将执行 20*33*300=198000次 。
我们希望在算法上改进一下，如能减少一重循环，
将大大缩短运行时间。
ok
3.4.1 穷举法
实际上，当 i,j确定时,k就可由题目要求确定为 100-i-j，因此
实际上只要用 i,j去测试，用钱数检测就可以了。循环体将执行,
20*33=660次。
程序如下：
#include <iostream.h>
#include <iomanip.h>
void 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)非常重要,想一想为什么
cout<<setw(6)<<i<<setw(10)
<<j<<setw(10)<<k<<endl;
}
}
ok
3.4.2 递推法
递推法 的思想：通过分析问题，找出问题的
规律和性质。然后设计算法，按照找出的规律
从初始条件进行递推，最终找出问题的答案。
例：用 欧基里德算法（也称辗转法） 求两个非
负整数的最大公因子。
分析,假定两个整数分别为 u和 v,最大公
约数应当是不超过其中较小数的一个整数 。
辗转法的思想是,用 u除以 v,求出余数 r，
如果 r==0,则当前 v就是最大公约数, 否则如
果 r!=0,u=v,v=r,重复以上过程, 直到
r==0为止 。
ok
程序如下：
#include<iostream.h>
void main( )
{ int u,v,resd;
cout<<"输入两个整数,"<<endl;
cin>>u>>v;
cout<<u<<" 和 "<<v <<,的最大公约数
为：, ;
while(r = u%v) {
u = v;
v = r;
}
cout<<v<<endl;
}
ok
3.4.3 递归法
递归法,指一个函数直接或间接地调用
本身，便构成了递归调用，使用递归调
用一般要符合三个条件：
? 可以把一个问题转化为一个新问题，而
这个新问题的解决方法和原问题的解法
相同，只是所处理的对象不同，但他们
是有规律的递增或递减。
? 可以通过转化过程使问题得到解决
? 必须要有一个结束递归的条件，否则递
归将会无休止地进行下去
ok
3.4.3 递归法
在函数调用中，有这样两种情况，一种是在函数 A的定义
中有调用函数 A的语句，即自己调用自己；另一种是
函数 A的定义中出现调用函数 B的语句，而函数 B的定
义中也出现调用函数 A的语句，即相互调用。前者称
直接递归,后者称 间接递归 。本节只介绍直接递归。
递归函数必须定义递归 终止条件 （ Stopping
condition），避免无穷递归（ Infinite Recursion
）。
递归定义的阶乘算法用函数描述为：
fac(int n){
if (n==0||n==1) return 1;
else return n*fac(n-1);
}
只要设计主函数调用阶乘函数，即可实现计算阶乘。
?
?
?
?
?
?
?
?
?
1n 1 ) !-(n*n
1n 1
0n 1
n
ok
3.4.3 递归法
【 例 4,12】 求 4！
#include <iostream.h>
int fac(int n)
{ int y;
if(n==0||n==1) y=1;
else y=n*fac(n-1);
return y;
}
void main() {
cout<<"\n4!="<<fac(4)<<endl;
}
n=4
y=4*fac(3);fac(4)= y=2*fac(1);
n=2
y=1;
return 1;
n=1n=3
y=3*fac(2);
return 24; return 6; return 2;
24
ok
3.4.3 递归法
递归函数的执行分为, 递推, 和, 回归, 两个过
程，这两个过程由递归终止条件控制，即 逐层
递推,直至 递归终止条件,然后 逐层回归 。每
次调用发生时都首先判断递归终止条件。递归
调用同普通的函数调用一样，每当调用发生时
，在栈中分配单元保存返回地址以及参数和局
部变量；而与普通的函数调用不同的是，由于
递推的过程是一个逐层调用的过程，因此存在
一个逐层连续的参数入栈过程，直至遇到递归
终止条件时，才开始回归，这时才逐层释放栈
空间，返回到上一层，直至最后返回到主调函
数。
ok
3.4.3 递归法
【 例 4,13】 汉诺塔问题 。 有 A,B,C三根柱子, A柱
上有 n个大小不等的盘子, 大盘在下, 小盘在上 。 要求
将所有盘子由 A柱搬动到 C柱上, 每次只能搬动一个盘
子, 搬动过程中可以借助任何一根柱子, 但必须满足大
盘在下, 小盘在上 。 打印出搬动的步骤 。
A柱 B柱 C柱
ok
3.4.3 递归法
分析：
1,A柱只有一个盘子的情况,A柱 ?C柱；
2,A柱有两个盘子的情况：小盘 A柱 ?B柱, 大盘 A柱 ?C 柱,
小盘 B柱 ?C柱 。
3,A柱有 n个盘子的情况：将此问题看成上面 n-1个盘子和
最下面第 n个盘子的情况 。 上面 n-1个盘子借助 C柱, 从 A
柱 ?B柱, 第 n个盘子就可以直接从 A柱 ?C柱, 然后再将
n-1个盘子再借助 A柱, 从 B柱 ?C柱 。 问题转化成搬动 n-
1
个盘子的问题, 上面的移动是假设 n-1个盘子可以移动
的
前提下进行的, 那么 n-1个盘子怎么移动呢, 同样,
将 n-1个盘子看成上面 n-2个盘子和下面第 n-1个盘子的
情况, 进一步转化为搬动 n-2个盘子的问题, ……, 类
推下去, 一直到最后成为搬动一个盘子的问题 。
这是一个典型的递归问题, 递归结束于只搬动一个盘子 。
ok
3.4.3 递归法
上面的算法可以归纳为下面三步：
（１） 先将 A柱 上面的 n-1个盘子借助 C移到 B柱
（２） 再将 A柱 的剩下一个盘子移到 C柱
（３） 最后将 B柱 的 n-1盘子借助 A移到 C柱
上面的三个步骤其实可以进一步地变为两个动作：
（１） 将 n-1个盘子从一柱移到另一柱
（２） 将一个盘子从一柱移到另一柱
根据这个思路：上面两步我们可以编写两个函数进行处
理，用函数 MoveDisc来实现第一步操作，函数调用
MoveDisc(n,a,b,c) 表示将 n个盘子从, a”柱 移动, c”
柱,借助, b”柱,那么程序实现如下：
ok
3.4.3 递归法
#include <iostream.h>
class Hanoi {
private:
int mDiscNumber;
public:
Hanoi(int iDiscNum) {mDiscNumber = iDiscNum; }
void MoveDisc(int n,char a,char b,char c);
}
void main()
{ Hanoi h(3);
h.MoveDisc();
} /* 将 n个盘子从 a借助 c移到 b处 */
void Hanoi:,MoveDisc(int n,char a,char b,char c)
{ if(n == 1) cout <<,move disc n：” <<n<<“from pile：”
<<a<<,to,<<c << endl; /* 递归结束条件 */
else {
MoveDisc(n-1,a,c,b);
cout <<,move disc n：” <<n<<“from pile：”
<<a<<,to,<<c << endl;
MoveDisc(n-1,b,a,c);
}
}
ok
3.4.3 递归法
【 例 4,14】 输入一个整数，用递归算法将整数倒序输出。
分析,在递归过程的递推步骤中用求余运算将整数的各个位分
离，并打印出来。
#include<iostream.h>
void backward(int n){
cout<<n%10;
if(n<10) return;
else backward(n/10);
}
void main(){
int n;
cout<<"输入整数,"<<endl;
cin>>n;
cout<<"原整数,"<<n<<endl<<"反向数,";
backward(n);
cout<<endl;
}
ok
3.4.3 递归法
n=247
cout<<7;
backward(24);
n=2
cout<<2;
return;
n=24
cout<<4;
backward(2);
backward(247)
return;return;cout<<endl;
求余总是取当前整数的最右一位，所以先输出余数后递
归可实现倒序输出。如果先递归后输出余数，则是在回归的
过程中输出，实现的就是正序输出。
从以上几例可以看出，递归算法一般不需要借助循环，但通
过不断 递推 和 回归 的过程实现了其他算法用循环完成的功能
。因此，递归的终止条件非常重要，否则将会无休止地递归
下去，陷入死循环状态。
第三章 基本控制结构程序设计
结构化程序设计的特点是任何程序都可由 三种基
本结构 及其组合来描述，这三种分别是 顺序结构、
选择结构和循环结构 。本章将介绍 C++分支结构和
循环结构的设计方法。这两种结构分别用 C++提供
的两类流程控制语句 分支语句 和 循环语句 来实现。
所谓 流程控制语句,是专门用来控制程序执行流程
的语句，也称为 过程化语句 。在介绍分支语句、循
环语句及其程序设计的同时，还将介绍一些 常用算
法,并通过实例实践结构化程序设计的方法。
ok
第三章 基本控制结构程序设计
3,1 分支结构程序设计
3,4 常用算法的应用实例
3,3 转向语句
3,2 循环结构 程序设计
ok
3.1 分支结构程序设计
对程序的运行流程进行控制，主要通过某些
条件进行判断来执行不同的语句。 分支语句 是三
种基本流程控制语句之一。 C++提供以下三种分
支语句：
3.1.1 if语句
3.1.2 条件运算符,?:‖
3.2.1 swich语句
ok
3.1.1 if 语句
if语句有三种格式为：
1,if(<表达式 >) <语句 1>;
2,if(<表达式 >) <语句 1>;
else <语句 2>;
3,if(<表达式 1>) <语句 1>;
else if (<表达式 2>) <语句 2>;
……
else if (<表达式 n>) <语句 n>;
else 语句 n+1；
ok
【 例 3,1】 输入一个年份，判断是否闰年。
算法分析, 假定年份为 year,闰年的条件是,
year%4==0&&year%100!=0||year%400==0。
#include <iostream.h>
void main( )
{ int year;
cout<<"输入年份,"<<endl;
cin>>year;
if(year%4==0&&year%100!=0
||year%400==0)
cout<<year<<"是闰年 "<<endl;
else
cout<< year<<"不是闰年 "<<endl;
}ok
ok
分析：读入三个数, 先求出两个数中较大者, 再将该大数与
第三个数比较, 求出最大数 。
#include <iostream.h>
class ThreeNumber {
private:
int a,b,c;
public:
void Input3Integers();
void GetMax();
};
int main()
{ ThreeNumber a;
a.Input3Integers();
a.GetMax();
return 0;
}
【 例 3,2】 从键盘上输入三个整数，输出其中的最大数。
ok
void ThreeNumber::Input3Integers()
{ cout << ―Input 3 Integers:\n‖;\
cin >> a >> b >> c;
}
int ThreeNumber::GetMax()
{ int max;
if(a > b)
if(a > c) max = a;
else max = c;
else
if(b > c) max = b;
else max = c;
cout << ―The Max Integers is,‖
<< max << endl;
}
ok
if 语句中, 如果内嵌语句又是 if语句, 就构
成了 嵌套 if语句 。 if 语句可实现 二选一 分支, 而
嵌套 if语句则可以实现 多选一 的多路分支情况 。
嵌套有两种形式, 第一种是嵌套在 else分支中,
if (<表达式 1>) <语句 1>;
else if (<表达式 2>) 语句 2;
else if …
else <语句 n>;
第二种是嵌套在 if分支中为：
if (<表达式 1>) if (<表达式 2>) <语句 1>；
else <语句 2>;
我们可以见上面的 GetMax()函数
ok
要 特别注意 else和 if的配对关系 。 C++规定了
if和 else的,就近配对,原则，即相距最近且还
没有配对的一对 if和 else首先配对。按上述规定，
第二种嵌套形式中的 else应与第二个 if配对。如
果根据程序的逻辑需要改变配对关系，则要将属于
同一层的语句放在一对,{}‖中。如第二种嵌套形
式中，要让 else和第一个 if配对，语句必须写成：
if (表达式 1) {
if (表达式 2) 语句 1 ;
}
else 语句 2 ;
第二种嵌套形式较容易产生逻辑错误，而第
一种形式配对关系则非常明确，因此从程序可读性
角度出发，建议尽量使用第一种嵌套形式。
ok
请看以下两个语句,//语句 1：
if(n%3==0)
if(n%5==0)
cout<<n<<―是 15的倍数” <<endl;
else
cout<<n<<―是 3的倍数但不是 5的倍数 ″
<<endl;
//语句 2：
if(n%3==0){
if(n%5==0)
cout<<n<<―是 15的倍数 ″<<endl;
}
else cout<<n<<―不是 3的倍数 ″
两个语句的差别只在于一个, {}”，但表达的逻辑关系却完
全不同。
ok
3.1.2 条件运算符,?:”
if语句在某些情况下可以用条件运算符,?:‖
来简化表达 。,?:‖是一个三元运算符, 其构成的
表达式格式为,<表达式 1>? <表达式 2>, <表
达式 3>执行逻辑：先计算表达式 1,若其值为真
（ 或非 0）, 则计算表达式 2（ 不计算表达式 3）,
并将该值作为整个表达式的值；反之, 即表达式 1
的值为假或为 0,则计算表达式 3（ 不计算表达式
2）, 并将该值作为整个表达式的值 。 例如：
int a=6,b=7,min=a<b?a:b; //min=6
min=a<b?++a:++b; //min=7 a=7 b=7
min=a<b?a++:b++; //min=6 a=7 b=7ok
ok
3.1.3 switch语句
用嵌套 if语句可以实现多选一的情况 。 另外 C++中
还提供了一个 switch语句, 称为开关语句, 也可以
用来实现多选一：
switch (表达式 ) {
case常量表达式 1:,语句序列 1;》, break;》
case常量表达式 2:,语句序列 2;》, break;》
……
case常量表达式 n:,语句序列 n;》, break;》
,default:语句序列 n+1;》
}
ok
switch语句格式
（ 1）各个 case（包括 default）分支出现的次序
可以任意，通常将 default放在最后。
（ 2） break语句可选，如果没有 break语句，每
一个 case分支都只作为开关语句的 执行入口,执行
完该分支后，还将接着执行其后的所有分支。因此，
为保证逻辑的正确实现，通常每个 case 分支都与
break语句联用。
（ 3）每个常量表达式的取值必须各不相同，否则
将引起歧义。
ok
（ 4）允许多个常量表达式对应同一个语句序列。
例如：
char score;
cin>>score;
switch (score) {
case ?A′,
case ?a′,cout<<″excellent″;
break;
case ?B′,
case ?b′,cout<<″good″;
break;
default,cout<<″fair″;
}
（ 5）从形式上看,switch语句的可读性比嵌套 if
语句好，但不是所有多选一的问题都可由开关
语句完成，这是因为开关语句中限定了条件表
达式的取值类型。ok
ok
switch语句例子
【 例 3,6】 运输公司对所运货物实行分段计费 。
设运输里程为 s,则运费打折情况如下：
s<250 不打折扣
250<=s<500 2%折扣
500<=s<1000 5%折扣
1000<=s<2000 8%折扣
2000<=s<3000 10%折扣
3000<=s 15%折扣
设每公里每吨的基本运费为 p,货物重量为 w,折扣
为 d,则总运费 f为,f=p*w*s*(1-d)
设计程序, 当输入 p,w和 s后, 计算运费 f。
ok
算法
1,输入每吨运费 p,货物重量 w,运输里程 s；
2,根据运输里程 s计算折扣 d；
3,计算总运费 f=p*w*s*(1-d)；
4,输出计算结果；
算法细化,2,根据运输里程 s计算折扣 d
分析,
如果用 switch语句, 必须使表达式符合语法要
求, 分析发现, 里程 s的 分段点均是 250的倍数,
因此, 将里程 s除以 250,取整数商, 便得到若
干整数值 。ok
ok
switch(c=s/250) {
case 0,d=0; break;
case 1,d=0.02; break;
case 2:
case 3,d=0.05; break;
case 4:
case 5:
case 6:
case 7,d=0.08; break;
case 8:
case 9:
case 10:
case 11:d=0.1;break;
default:d=0.15;
}
s<250 不打折扣
250<=s<500 2%折扣
500<=s<1000
5%折扣
1000<=s<2000
8%折扣
2000<=s<3000
10%折扣
3000<=s 15%折扣
ok
#include <iostream.h>
#include <iomanip.h>
void main( )
{ int c,s; float p,w,d,f;
cout<<"输入运输单价 p,重量 w和里程 s:"<<endl;
cin>>p>>w>>s; c=s/250;
switch(c){
case 0:d=0;break;
case 1:d=0.02;break;
case 2:case 3:d=0.05;break;
case 4:case 5:case 6:case 7:d=0.08;
break;
case 8:case9:case10:case11:d=0.1;break;
default:d=0.15;
}
f=p*w*s*(1-d);
cout<<"单价为 "<<p<<'\t'<<"重量为 "<<w<<'\t?
<<"里程为 "<<s<<endl;
cout<<"折扣为 "<<d<<endl<<"运费为 "<<f<<endl;}
请在 VC++平台上运行, 输入不同的里程, 使程序所有分支都可以被执行一次 。
ok
ok
【 例 3,7】 设计一个计算器程序，实现加、减、乘、除运算。
#include <iostream.h>
void main( )
{ float num1,num2,result;
char op;
cout<<"输入操作数 1，运算符，操作数 2,"<<endl;
cin>>num1>>op>>num2;
switch(op){
case '+',result = num1+num2; break;
case ?-',result = num1-num2; break;
case ?*',result = num1*num2; break;
case ?/',result = num1/num2; break;
default, cout<<op<<―是无效运算符 !‖;
}
if(op==?+‘||op==?-‘||op==?*‘||op==?/‘)
cout<<num1<<op<<num2<<"="<<result<<endl;
}
常量表达式采用字符型，上机运行一下。
ok
循环控制语句 是三种基本流程控制语句之
一。 C++提供以下三种循环语句：
? while语句
? do-while 语句
? for语句
3.2 循环结构程序设计
ok
循环结构程序设计
3.2.1 while语句
3.2.4 循环的嵌套
3.2.3 for语句
3.2.2 do-while 语句
ok
3.2.1 while 语句
while语句也称为当循环 。
语句格式为：
while (表达式 )
循环体语句；
图 3.1 while语句的执行流程图
求表达式的值
表达式
值为真?
是
否
执行循环体语句
ok
while 语句
【 例 3,8】 求 1+2+3+4+…+100 的值。
ok
N个连续整数相加算法
1、设置变量 i用来放被加数，变量 sum用来放和值,
并初始化 ;
2、从第一个数开始，依次将被加数赋给 i，并进行
操作 sum?sum+i;
3、输出 sum；
细化算法 2：
while(还有被加数 )
{ i=当前被加数；
sum += i;
i准备接受下一个被加数；
}
ok
源程序如下：
#include <iostream.h>
void main( )
{
int i=1,sum=0;//循环初始条件
while(i<=100) {
sum+=i;
i++; //修改循环条件
}
cout<<"sum="<<sum<<endl;
}
在 VC++平台上运行，试一试是否正确ok
ok
while 语句
注意：
在有循环语句的程序中，通常循环开始前
对循环条件进行初始化；而在循环体语
句中要包含修改循环条件的语句，否则
循环将不能终止而陷入死循环。
C++表达方式灵活，上例中的循环语句
还可以写成：
while (i<=n) sum += i++;
修改程序后在 VC++平台上运行，看是否正
确
ok
3.2.2 do-while 语句
do-while语句称为 直到循环,
格式为：
do 循环体语句
while( 表达式 )
否
是 表达式的
值为真?
执行循环体语句
求表达式的值
图 3.2 do-while语句的执行流程图
ok
do-while 语句
do/while语句和 while语句的区别：
多数情况下可以互相替代。
区别是,
do/while语句至少执行一次循环体后 再
判断循环条件是否满足；
while语句先判断条件是否满足，然后才
执行循环体。
ok
【 例 3,9】 用迭代法求 a的平方根近似值。
求平方根的迭代公式为：
要求前后两个迭代根之差小于 10- 5。
do-while 语句
迭代法求解,a是已知正数,x0是迭代初值，给 x0
一个值，假定 x0=a/2；则用迭代公式依次计算：
x1=(x0+a/x0)/2； x2=(x1+a/x1)/2； ……
xk+1=(xk+a/xk)/2；
当 |xk+1 –xk|<ε(ε是一个较小的正数 )时，迭代终
止,取 xk+1的值为 a的平方根近似值 。ok
ok
1、输入 a(a>0)及较小正数 delta(也可用常变量 )；
2,x0=a/2； 用迭代公式算 x1=(x0+a/x0)/2；
3,while（ |x1–x0|>=delta） {
x0=x1 ； //把最近的值给 x 0 ；
x1=(x0+a/x0)/2；
} //求 xk+1时只需要知道 xk的值，所以只需 2个变量；
4、取 x1的值为 a的平方根近似值，输出。
2,3步骤很适合用 do/while语句实现：
x1=a/2；
do {
x0=x1;
x1=(x0+a/x0)/2；
} while（ |x1–x0|>=delta） ;
和迭代法对应的程序算法是
递推算法：
回到
题目
ok
#include<iostream.h>
#include<math.h>
void main( ){
float x0,x1,a;
cout<<―输入一个正数：, ;
cin>>a;
if(a<0)cout<<a<<"不能开平方 !"<<endl;
else { //有实数解的情况
x1=a/2; //x1用于保存结果
do{
x0=x1;
x1=(x0+a/x0)/2;
} while(fabs(x1-x0)>=1e-5);
cout<<a<<"的平方根为,"<<x1<<endl;
}
}
在 VC++平台上运行, 输入 2,3,4,5试一试是否正确
回到
题目
ok
【 例 3,10】 输入一段文本, 统计文本的行数,
单词数及字符数 。 假定单词之间以空格或跳格或
换行符间隔, 且文本开始没有空行 。
算法分析,
1,逐个读入文本中的字符, 直到读到一个输入结
束符 EOF为止 。
2,如何算行数？ 行结束标志为读到字符 ′\n′；
3,如何算单词数？ 设一个变量 isword,读到字
符时 isword=1,读到间隔符时 isword=0；如果
读到一个字符而此时 isword值为 0,则说明刚开
始读一个单词； （ 如果读到一个间隔符而此时
isword值为 1,则说明刚读完一个单词； ）
4,如何算字符数？
do-while 语句
ok
ok
算法
1、设置变量 line,word,ch分别代表行数、
单词数、非分隔字符数，并初始化 ;设置变量
isword来辅助统计单词数 ;
2,do{
从键盘读入一个字符 c；
if(c==‘\n‘) line++;
if(是单词开头 ) word++;
if(c不是分隔符 ) ch++;
} while(c!= EOF );
3、输出统计结果。
将下面的程序在 VC++平台上运行，试一试是否正确
ok
#include<iostream.h>
void main()
{ char c;
int line=0,word=0,ch=0;
int isword=0;
do {
c=cin.get();
if(c==?\n‘) line++; //遇换行符行数 +1
if(c!=? ?&&c!=?\t‘&&c!=?\n‘){
//读到非间隔符
if(isword==0) word++;
//在单词的起始处给单词数 +1
ch++; //字符数加 +1
isword=1;
}
else isword=0; //读到间隔符
} while(c!=EOF);
cout<<‖行数：, <<line<<endl;
cout<<‖单词数：, <<word<<endl;
cout<<‖字符数：, <<char<<endl;
}
ok
3.2.3 for 语句
for循环语句的格式
为：
for ( <表达式 1>;
<表达式 2>;
<表达式 3> )
<循环体语句 >
图 3.3 for语句的执行流程图
否
是
求表达式 1的值
求表达式 2的值
表达式 2值
为真?
执行循环体语句
求表达式 3的值ok
ok
for语句,while语句,do/while语句
实现相同的功能,1+2+3+4+…+100
int i=1,sum=0;
//循环初始条件
while(i<=100)
{ sum+=i;
i++;
//修改循环条件
}
int i=1,sum=0;
//循环初始条件
do{ sum+=i;
i++;
//修改循环条件
}while(i<=100);
for( int i=1,sum=0; i<=100; i++ )
{ sum+=i;}
/*习惯上：表达式 1：循环初始条件；表达式 2：循环
终止条件；表达式 3：修改循环条件 */ok
ok
for 语句的应用
?for语句的几点说明：
1、是先判断型的，同 while语句；
2、使用更为灵活：
三个表达式可以是任意表达式，因此他们
就可以实现循环初始化、计算、修改循
环条件等任务，而不一定非在循环体中
进行；
ok
for 语句的应用
【 例 3,11】 设计程序输出 Fibonacii数列的前
20项, 要求每行输出 5个数据 。
Fibonacii数列定义如下：
算法分析,除了第 0项和第 1项外, 每一项都是
由类似方法产生, 即前两项之和；所以求当前
项时, 只需要记住前两项；程序不需要为每一
项设置专用变量；
属 递推算法 。
ok
算法：
1,设置变量 n表示第几项, 变量 f0和 f1用来记住
当前项 f2之前的两项 ；变量初始化 n=0；
2,while（ 当前项不到第 20项 ） {
if(当前项是第 0项 ) f0=0;
if(当前项是第 1项 ) f1=1;
if(当前项是第 2项或更高项 ) f2=f0+f1;
按要求输出 f2 ;
f0=f1; f1=f2; //记住最近两项
当前项后移一位；
}
ok
??
?
?
?
??
?
?
?
1n 1)-fi b ( n2)-fi b ( n
1n 1
0n 0
fi b ( n )
【 例 3,11】 设计程序输出 Fibonacii数列的前 20项, 要求
每行输出 2个数据 。 Fibonacii数列定义如下：
程序如下：
#include<iostream.h>
#include<iomanip.h>
void main()
{ int f0=1,f1=1,f2;
cout<<setw(5)<<f0<<setw(5)<<f1<<endl;
for(int n=2;n<20;n++){
f2=f0+f1;
cout<<setw(5)<<f2;
if(n%5==0) cout<<endl;
//控制每行 2个数据
f0=f1;
f1=f2;
}
}
ok
for 语句的应用
在 VC++平台上运行
运行结果：
0 1 1 2 3
5 8 13 21 34
55 89 144 233 377
610 987 1597 2584 4181
ok
【 例 3.12】 输入一个非负的整数, 将其反向后
输出 。 例如输入 24789,变成 98742输出 。
算法分析,
1,将整数的各个数位逐个位分开, 一个一个分别
输出 。
2,将整数各位数字分开的方法是, 通过对 10进
行求余得到个位数, 然后将整数缩小十倍, 再求
余, 并 重复上述过程, 分别得到十位, 百位 ……，
直到 整数的值变成 0为止 。
for 语句的应用
ok
ok
算法：
1,输入 num; 变量初始化,i=0;
2,while（ num!=0） {
num对 10取余,得 num的当前个位数并输出；
num整除 10并赋给 num,即去掉个位数,
十位变个位, 百位变十位, ……；
}
ok
程序如下：
#include <iostream.h>
class RevNumber {
private:
long int n;
public:
void InputData();
void OutRevData();
};
void main()
{ RevNumber a;
a.InputData();
a.OutRevData();
}
ok
void RevNumber::InputData()
{ cout << ―请输入一个非负整数：,
cin >> n;
}
void RevNumber::OutRevData()
{ while(n>0) {
cout << n%10;
n = n/10;
}
}
ok
3.2.4 循环的嵌套
【 例 3,13】 打印九九表 。 打印格式为：
* 1 2 3 4 5 6 7 8 9
----------------------------
1 1
2 2 4
3 3 6 9
……
9 9 18 27 36 45 54 63 72 81
当循环语句中的循环体中又有循环语句时，就构
成了嵌套循环。
嵌套层次一般不超过 3层，已保证可读性。
ok
循环的嵌套
分析,
1,计算机的输出是按行进行的, 因此可以先用一
个循环语句输出第一行表头 。
2,表中各行数据的输出可以用下面的算法描述：
for (i=1; i<10; i++)
{ cout<<i; //输出行号
输出第 i行数据； //A
cout<<endl; //准备输出下一行
}
ok
3,第 A行需要进一步细化 。 由于第 i行数据是一组
有规律的数列, 每个数的值是其所在行与列的乘
积, 因此输出第 i行可以：
for(j=1;j<10;j++)cout<<setw(5)<<i*j;
4,按上述算法输出的每一行都将有九列, 即打印
出的是矩形表而不是下三角形表 。 进一步分析发
现每一行的列数与所在行数相关, 因此要输出三
角形表, 上面的循环语句需稍作修改：
for(j=1;j<=i;j++)cout<<setw(5)<<i*j;
将此语句放到顶层算法的 A行即可 。
循环的嵌套
ok
#include <iostream.h>
#include <iomanip.h>
void main(){
cout<<'*'<<? ‘;
for(int i=1;i<10;i++)
cout<<setw(5)<<i; //输出表头
cout<<endl;
for(i=1;i<10;i++){
cout<<i<<' ';
//输出行号 (被乘数 )
for(int j=1;j<=i;j++)
cout<<setw(5)<<i*j;//输出表中数据
cout<<endl; //准备输出下一行
}
}
3.2.4 循环嵌套 __打印九九表
ok
3.3 转向语句
3,3,1 break语句
3,3,4 return语句
3,3,3 goto 语句
3,3,2 continue语句
ok
3.3.1 break 语句
break语句只能用在 switch语句 和 循环语
句 中，用来跳出 switch语句或提前终止循环，
转去执行 switch语句或循环语句之后的语句。
在 for循环中可以用 break结束循环：
for(; ;) {
…
if(<表达式 >) break;
…
}
ok
break 语句应用
【 例 3.14】 给定正整数 m,判定其是否为素数 。
分析,如果 m>2,m是素数的条件是不能被 2,3,…,（ 取整 ）
整除 。 因此可以用 2,3,…,（ 取整 ） 逐个去除 m,如果被其
中某个数整除了, 则 m不是素数, 否则是素数 。 ——算法属于
穷举法 。
1、输入被测数 m（ m>2）；令整型变量 k= sqrt(m)
2、判断 m是否素数：设置辅助整型变量 i,使 i从 2开始直到
k依次测试 m能否整除 i,若能，则不是素数；
for(i=2;i<=k;i++） if(m%i==0) break；
/* 条件满足,m不是素数,停止测试,结束 for语句。 */
3、根据 i是否已达到 k，输出结果是否为素数。
ok
#include <iostream.h>
#include <math.h>
void main()
{ int m,i,k;
cout<<"输入整数 m,"<<endl;
cin>>m;
if(m==2) cout<<m<<"是素数 "<<endl;
else{
k=sqrt(m);
for(i=2;i<=k;i++) if (m%i==0) break;
//只要有一个整除，就可停止
if(i>k) cout<< m<<"是素数 "<<endl;
//循环提前终止表示是非素数
else cout<< m<<"不是素数 "<<endl;
}
}
在 VC++平台上运行，改一下，使程序自动算出 100以内的素数
ok
3.3.2 continue 语句
continue语句只能用在 循环语句 中，用
来 终止本次循环 。当程序执行到 continue语
句时，将跳过其后尚未执行的循环体语句，
开始下一次循环 。下一次循环是否执行仍然
取决于循环条件的判断。
continue语句与 break语句的区别在于，
continue语句结束的只是 本次循环,而
break结束的是 整个循环 。
ok
例：输出 1～ 100内 3的倍数。
分析：设置整型变量 I从 1变化到 100，依次测试
I是否 3的倍数，算法属于穷举法。
for (I=1;I<=100;I++)
{ if ( I%3！ =0) continue;
//I不是 3的倍数，不输出，继续下一个 I;
输出 I的值； //I是 3的倍数才输出
}
ok
3.3.3 goto 语句
goto语句和标号语句一起使用，所谓标号语句
是用标识符标识的语句，它控制程序从 goto语句所
在的地方转移到标号语句处。 goto语句会导致程序
结构混乱，可读性降低，而且它所完成的功能完全
可以用算法的三种基本结构实现，因此一般不提倡
使用 goto语句。但在某些特定场合下 goto语句可能
会显出价值，比如在多层循环嵌套中，要从深层地
方跳出所有循环，如果用 break语句，不仅要使用多
次，而且可读性较差，这时 goto语句可以发挥作用。
ok
3.3.4 return 语句
return语句用于结束函数的执行，返回调用者，
如果是主函数，则返回至操作系统。
利用一个 return语句可以将一个数据返回给调
用者。通常，当函数的返回类型为 void时，
return语句可以省略，如果使用也仅作为函数
或程序结束的标志。
ok
3.4 常用算法及其应用实例介绍
算法,通俗地说，就是解决问题的方法和步骤。
它是一组有穷的规则，规定了解决某一特定类型问
题的一系列运算，算法是程序设计学习的重点。用
计算机解决问题的算法应具有以下特征：可执行性、
确定性、有穷性、可输入输出信息等特点。常见的
方法有,直接法、穷举法、递推法、递归法、回溯法等。
3.4.1 穷举法
3.4.2 递推法
3.4.3 递归法
ok
3.4.1 穷举法
穷举法是最简单、最常见的程序设计方法
之一，它充分利用计算机的高速特性，借助循
环结构实现特定范围里的穷举。
例：大奖赛评分程序，在唱歌比赛中，一
般有若干个评委，记分规则：去掉一个最高分
和最低分，再计算平均分。试编写一个在百分
制记分的情况下的程序实现。
算法分析,本问题的关键在于找出所有分中的
最大值和最小值，我们假设设置一个变量 max，
它的初始值为 0，来记录最大值，然后对所有
分进行穷举，如果还有比 max更大的，则把它
赋给 max，待所有分都穷举完毕后，则 max就
是最大值，求最小值的方法也类似。
ok
#include <iostream.h>
Class Score {
private:
int mNumber;
public:
Score(int i_Num) { mNumber = i_num; }
void GetResult();
}
void main()
{ Score m(15);
m.GetResult();
}
Void Score::GetResult()
{ int iScore,i,max = 0,min = 100; float fSum = 0;
for(I = 1; I <= mNumber; I ++) {
cout <<,输入第, << I <<,个分：” ;
cin >> iScore;
fSum += iScore;
if(iScore > max) max = iScore;
if(iScore < min) min = iScore;
}
cout <<,\n最后得分：” << (fSum-max-min)/(mNumber-2));
}
ok
3.4.1 穷举法
例, 世界数学史上著名的, 百鸡问题,,鸡翁一,
值钱五, 鸡母一, 值钱三, 鸡雏三, 值钱一 。
百钱买百鸡, 问鸡翁, 母, 雏各几何？
分析,设鸡翁, 母, 雏分别为 i,j,k,根据题
意可得,i*5+j*3+k/3*1=100;
i+j+k=100;
两个方程无法解出三个变量, 只能将各种可能
的取值代入, 其中能满足两个方程的就是所需
的解, 因此这是枚举算法 （ 也叫穷举法 ） 的应
用 。
i,j,k可能的取值有哪些？ 分析可知, 百钱
最多可买鸡翁 20,鸡母 33,鸡雏 300。
ok
3.4.1 穷举法
算法：
for (i=0; i<=20;i++)
for (j=0; j<=33;j++)
for (k=0; k<=300;k++)
if((i+j+k==100)&&(5*i+3*j+k/3==100))
cout<<i<<j<<k;
这个算法使用三重循环, 执行时间函数是方阶,
循环体将执行 20*33*300=198000次 。
我们希望在算法上改进一下，如能减少一重循环，
将大大缩短运行时间。
ok
3.4.1 穷举法
实际上，当 i,j确定时,k就可由题目要求确定为 100-i-j，因此
实际上只要用 i,j去测试，用钱数检测就可以了。循环体将执行,
20*33=660次。
程序如下：
#include <iostream.h>
#include <iomanip.h>
void 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)非常重要,想一想为什么
cout<<setw(6)<<i<<setw(10)
<<j<<setw(10)<<k<<endl;
}
}
ok
3.4.2 递推法
递推法 的思想：通过分析问题，找出问题的
规律和性质。然后设计算法，按照找出的规律
从初始条件进行递推，最终找出问题的答案。
例：用 欧基里德算法（也称辗转法） 求两个非
负整数的最大公因子。
分析,假定两个整数分别为 u和 v,最大公
约数应当是不超过其中较小数的一个整数 。
辗转法的思想是,用 u除以 v,求出余数 r，
如果 r==0,则当前 v就是最大公约数, 否则如
果 r!=0,u=v,v=r,重复以上过程, 直到
r==0为止 。
ok
程序如下：
#include<iostream.h>
void main( )
{ int u,v,resd;
cout<<"输入两个整数,"<<endl;
cin>>u>>v;
cout<<u<<" 和 "<<v <<,的最大公约数
为：, ;
while(r = u%v) {
u = v;
v = r;
}
cout<<v<<endl;
}
ok
3.4.3 递归法
递归法,指一个函数直接或间接地调用
本身，便构成了递归调用，使用递归调
用一般要符合三个条件：
? 可以把一个问题转化为一个新问题，而
这个新问题的解决方法和原问题的解法
相同，只是所处理的对象不同，但他们
是有规律的递增或递减。
? 可以通过转化过程使问题得到解决
? 必须要有一个结束递归的条件，否则递
归将会无休止地进行下去
ok
3.4.3 递归法
在函数调用中，有这样两种情况，一种是在函数 A的定义
中有调用函数 A的语句，即自己调用自己；另一种是
函数 A的定义中出现调用函数 B的语句，而函数 B的定
义中也出现调用函数 A的语句，即相互调用。前者称
直接递归,后者称 间接递归 。本节只介绍直接递归。
递归函数必须定义递归 终止条件 （ Stopping
condition），避免无穷递归（ Infinite Recursion
）。
递归定义的阶乘算法用函数描述为：
fac(int n){
if (n==0||n==1) return 1;
else return n*fac(n-1);
}
只要设计主函数调用阶乘函数，即可实现计算阶乘。
?
?
?
?
?
?
?
?
?
1n 1 ) !-(n*n
1n 1
0n 1
n
ok
3.4.3 递归法
【 例 4,12】 求 4！
#include <iostream.h>
int fac(int n)
{ int y;
if(n==0||n==1) y=1;
else y=n*fac(n-1);
return y;
}
void main() {
cout<<"\n4!="<<fac(4)<<endl;
}
n=4
y=4*fac(3);fac(4)= y=2*fac(1);
n=2
y=1;
return 1;
n=1n=3
y=3*fac(2);
return 24; return 6; return 2;
24
ok
3.4.3 递归法
递归函数的执行分为, 递推, 和, 回归, 两个过
程，这两个过程由递归终止条件控制，即 逐层
递推,直至 递归终止条件,然后 逐层回归 。每
次调用发生时都首先判断递归终止条件。递归
调用同普通的函数调用一样，每当调用发生时
，在栈中分配单元保存返回地址以及参数和局
部变量；而与普通的函数调用不同的是，由于
递推的过程是一个逐层调用的过程，因此存在
一个逐层连续的参数入栈过程，直至遇到递归
终止条件时，才开始回归，这时才逐层释放栈
空间，返回到上一层，直至最后返回到主调函
数。
ok
3.4.3 递归法
【 例 4,13】 汉诺塔问题 。 有 A,B,C三根柱子, A柱
上有 n个大小不等的盘子, 大盘在下, 小盘在上 。 要求
将所有盘子由 A柱搬动到 C柱上, 每次只能搬动一个盘
子, 搬动过程中可以借助任何一根柱子, 但必须满足大
盘在下, 小盘在上 。 打印出搬动的步骤 。
A柱 B柱 C柱
ok
3.4.3 递归法
分析：
1,A柱只有一个盘子的情况,A柱 ?C柱；
2,A柱有两个盘子的情况：小盘 A柱 ?B柱, 大盘 A柱 ?C 柱,
小盘 B柱 ?C柱 。
3,A柱有 n个盘子的情况：将此问题看成上面 n-1个盘子和
最下面第 n个盘子的情况 。 上面 n-1个盘子借助 C柱, 从 A
柱 ?B柱, 第 n个盘子就可以直接从 A柱 ?C柱, 然后再将
n-1个盘子再借助 A柱, 从 B柱 ?C柱 。 问题转化成搬动 n-
1
个盘子的问题, 上面的移动是假设 n-1个盘子可以移动
的
前提下进行的, 那么 n-1个盘子怎么移动呢, 同样,
将 n-1个盘子看成上面 n-2个盘子和下面第 n-1个盘子的
情况, 进一步转化为搬动 n-2个盘子的问题, ……, 类
推下去, 一直到最后成为搬动一个盘子的问题 。
这是一个典型的递归问题, 递归结束于只搬动一个盘子 。
ok
3.4.3 递归法
上面的算法可以归纳为下面三步：
（１） 先将 A柱 上面的 n-1个盘子借助 C移到 B柱
（２） 再将 A柱 的剩下一个盘子移到 C柱
（３） 最后将 B柱 的 n-1盘子借助 A移到 C柱
上面的三个步骤其实可以进一步地变为两个动作：
（１） 将 n-1个盘子从一柱移到另一柱
（２） 将一个盘子从一柱移到另一柱
根据这个思路：上面两步我们可以编写两个函数进行处
理，用函数 MoveDisc来实现第一步操作，函数调用
MoveDisc(n,a,b,c) 表示将 n个盘子从, a”柱 移动, c”
柱,借助, b”柱,那么程序实现如下：
ok
3.4.3 递归法
#include <iostream.h>
class Hanoi {
private:
int mDiscNumber;
public:
Hanoi(int iDiscNum) {mDiscNumber = iDiscNum; }
void MoveDisc(int n,char a,char b,char c);
}
void main()
{ Hanoi h(3);
h.MoveDisc();
} /* 将 n个盘子从 a借助 c移到 b处 */
void Hanoi:,MoveDisc(int n,char a,char b,char c)
{ if(n == 1) cout <<,move disc n：” <<n<<“from pile：”
<<a<<,to,<<c << endl; /* 递归结束条件 */
else {
MoveDisc(n-1,a,c,b);
cout <<,move disc n：” <<n<<“from pile：”
<<a<<,to,<<c << endl;
MoveDisc(n-1,b,a,c);
}
}
ok
3.4.3 递归法
【 例 4,14】 输入一个整数，用递归算法将整数倒序输出。
分析,在递归过程的递推步骤中用求余运算将整数的各个位分
离，并打印出来。
#include<iostream.h>
void backward(int n){
cout<<n%10;
if(n<10) return;
else backward(n/10);
}
void main(){
int n;
cout<<"输入整数,"<<endl;
cin>>n;
cout<<"原整数,"<<n<<endl<<"反向数,";
backward(n);
cout<<endl;
}
ok
3.4.3 递归法
n=247
cout<<7;
backward(24);
n=2
cout<<2;
return;
n=24
cout<<4;
backward(2);
backward(247)
return;return;cout<<endl;
求余总是取当前整数的最右一位，所以先输出余数后递
归可实现倒序输出。如果先递归后输出余数，则是在回归的
过程中输出，实现的就是正序输出。
从以上几例可以看出，递归算法一般不需要借助循环，但通
过不断 递推 和 回归 的过程实现了其他算法用循环完成的功能
。因此，递归的终止条件非常重要，否则将会无休止地递归
下去，陷入死循环状态。
