- 算法竞赛宝典（第一部）：语言及算法入门
- 张新华
- 1968字
- 2021-03-19 19:27:45
选择结构
选择结构用于判断给定的条件，根据判断的结果来控制程序的流程。
要使用选择结构，我们先来学习关系运算。所谓关系运算，实际上就是“比较运算”。将两个值进行比较，判断其比较的结果是否符合给定的条件。例如a>4是一个关系表达式，大于号是一个关系运算符，如果满足a>4的条件下，则该关系表达式的值为“真”，否则该关系表达式的值为“假”。
C++语言提供6种关系运算符，如表2.1所示。
表2.1
if语句是用来判定所给定的条件是否满足，根据结果的真或假决定执行给出的两种操作之一。
C++语言提供了三种形式的if语句：
1. if(表达式成立)
执行语句
2. if(表达式成立)
执行语句1
else
执行语句2
3. if(表达式1成立)
执行语句1
else if(表达式2成立)
执行语句2
else if(表达式3成立)
执行语句3
…
else if(表达式m成立)
执行语句m
else
执行语句n
这个很容易理解，我可以举生活中的例子如下：
1. if(天气好) 我就上街逛逛; 2. if(天气好) 我就上街逛逛; else 我就待在家; 3. if (我至少有五百块钱) 我可以买五件货; else if(我至少有四百块钱) 我可以买四件货; else if(我至少有三百块钱) 我可以买三件货; else if(我至少有两百块钱) 我可以买两件货; else if(我至少有一百块钱) 我可以买一件货; else 回家吧，什么都不说了，一说都是泪啊;
【例题描述】 求绝对值
魔法师使用的能量除了正能量以外，还有一种神秘的暗能量，暗能量是一种不可见的、能推动宇宙运动的能量。如图2.4所示，与正能量级别相对应的，魔法师将暗能量的级别以负数表示，现已知某种能量的级别，试用if语句显示该能量级别的绝对值。
图2.4
我是这样写的：
1 //求绝对值1
2 # include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int x;
8 cin>>x;
9 if (x<0)
10 x=-x;
11 cout<<x<<endl;
12 system("pause");
13 return 0;
14 }
我是这样写的：
1 //求绝对值2
2 # include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int x;
8 cin>>x;
9 if (x<0)
10 cout<<-x<<endl;
11 else
12 cout<<x<<endl;
13 system("pause");
14 return 0;
15 }
在if和else后面只含一个内嵌的操作语句（如上例），如果有多个操作语句，就必须要用花括号“{ }”将几个语句括起来成为一个复合语句。如：
if(x>y)
{
number=0; //语句1
cout<<x<<endl; //语句2
}
else
{
number=1; //语句1
cout<<y<<endl; //语句2
}
我明白了，我举一个生活中的例子：
if(天气好) { 我就购物； 我就看电影； 我就吃冰淇淋； } else { 我就在家看书； 我就在家看动画片； }
【例题描述】 两实数排序
输入两个实数a和b，按代数值由小到大的次序输出这两个数，例如输入“3 2”，输出“2 3”，输入“2 3”，输出仍是“2 3”。注意只允许使用cout<<a<<" "<<b这样的语句，而不允许使用诸如cout<<b<<" "<<a这样取巧的语句。
根据题目要求，显然当a>b的时候，a和b的值要互换，但a和b的值不能直接互换，而要通过一个中间变量（例如t）互换a，b的值。可以这样想象：假设有一瓶酱油和一瓶醋，如果要把酱油装入醋瓶，醋装入酱油瓶，就必须要有一个空瓶子作为临时盛放的容器。中间变量t就相当于这个空瓶子。
参考程序如下所示：
1 //两实数排序
2 # include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 float a,b,t;
8 cin>>a>>b;;
9 if(a>b)
10 {t=a;a=b;b=t;}
11 cout<<a<<" "<<b<<endl;
12 system("pause");
13 return 0;
14 }
【上机实践】 三实数排序
输入3个数a、b、c，要求模拟两实数排序的程序按由小到大的顺序输出。
伪代码如下所示：
1 定义浮点数a,b,c,t 2 输入a,b,c 3 如果(a>b) 4 a,b两值交换 5 如果(a>c) 6 a,c两值交换 7 如果(b>c) 8 b,c两值交换 9 输出a，b，c的值
注意该程序中三个变量的比较过程，即先比较a是否大于b，再比较a是否大于c，最后比较b是否大于c。想想看，如果改变比较顺序，结果是否仍然正确？
【上机实践】 等级制
魔法学院的考试采用等级制，即将百分制转化为A、B、C、D、E五个等级，设成绩为X，则X≥90为A等，X≥80为B等，X≥70为C等，X≥60为D等，否则为E等。试编写一个程序，将输入的分数转换成A、B、C、D和E五个等级。
伪代码如下所示：
1 定义分数为浮点数x 2 输入x的值 3 如果(x>=90) 4 输出"A" 5 否则如果(x>=80) 6 输出"B" 7 否则如果(x>=70) 8 输出"C" 9 否则如果(x>=60) 10 输出"D" 11 否则 12 输出"E"
C++有一个可替代if-else语句的操作符，这个操作符被称为三目运算符（?:），它是C++中唯一一个需要3个操作数的操作符。如a>b?c:d;此句的含义是：a大于b吗？如果是，则取c的值，否则取d的值。
例如下面的语句：
if(a>b)
Max=a;
else
Max=b;
可以写成Max=(a>b)?a:b;
【例题描述】 找最大值
编程输出两个整数的最大值。
1 //求最大值
2 # include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int x,y;
8 cin>>x>>y;
9 int c=x>y?x:y;
10 cout<<c<<endl;
11 system("pause");
12 return 0;
13 }
分析以下程序的执行错误：
1 //输出星期几
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int n;
8 cin>>n;
9 if(n=1)
10 cout<<"星期一"<<endl;
11 if(n=2)
12 cout<<"星期二"<<endl;
13 if(n=3)
14 cout<<"星期三"<<endl;
15 if(n=4)
16 cout<<"星期四"<<endl;
17 if(n=5)
18 cout<<"星期五"<<endl;
19 if(n=6)
20 cout<<"星期六"<<endl;
21 if(n=7)
22 cout<<"星期日"<<endl;
23 system("pause");
24 return 0;
25 }
我找到了，对于n=1来说，它的意思是将1赋给n，所以，这是一条赋值语句，整个表达式返回值为1，表示true，所以输出星期一，而对于其他的if语句也同样执行。改正方法是将所有if条件表达式中的“=”改为“==”。
在if语句中又包含一个或多个if语句称为if语句的嵌套，一般形式如下：
应当注意if与else的配对关系。else总是与它上面的最近的未配对的if配对。就好像穿衣服一样，总是一层套一层的。
类似的生活中的例子有：
if(天气好) if(是周末) 我就逛街; else 我就看电影; else if(是周末) 我就看电视； else 我就学习
【上机实践】 完整的解一元二次方程
完整解方程ax2+bx+c=0的解实际上应该有以下几种可能：
（1）a=0，不是二次方程。
（2）b2-4ac=0，有两个相等实根。
（3）b2-4ac>0，有两个不等实根。
（4）b2-4ac<0，没有实根（注意：引入虚数概念后，应该有两个共轭复根）。
这题要注意的是：因为a是实数，而实数在计算和存储时会有一些微小的误差，因此本来是零的值，由于误差原因而判别为非零的值。所以不能通过（a==0）的方式判断a是否等于0。我们采取的办法是判断a的绝对值是否小于一个很小的数（例如0.000001）。
fabs函数为求一个double类型的绝对值，例如fabs（-3）=3。使用fabs函数，程序头需引用math.h头文件。顺便提一下，abs函数为求一个整数变量的绝对值。
伪代码如下所示：
1 定义浮点数a,b,c,disc,x1,x2
2 输入a,b,c的值
3 如果(fabs(a)<=1e-6) //1e-6为科学计数法，即1×10-6
4 输出“不是一元二次方程”
5 否则
6 {
7 设disc=b*b-4ac
8 如果(disc＝＝0) //注意实际代码的括号内应写成(fabs(disc)<=0.000001)
9 输出两个相同的实根
10 否则如果(disc>0) //此处的代码应该怎么写？
11 输出两不同的实根
12 否则
13 输出“无实根”
14 }
【例题描述】 判断闰年
闰年（Leap Year）是为了弥补因人为历法规定造成的年度天数与地球实际公转周期的时间差而设立的。因为地球绕太阳运行周期为365天5小时48分46秒（合365.24219天）即一回归年（tropical year）。公历的平年只有365日，比回归年短约0.2422日，所余下的时间约为四年累计一天，故四年于2月加1天，使当年的历年长度为366日，这一年就为闰年。现行公历中每400年有97个闰年。
闰年的条件是符合下面二者之一：（1）能被4整除，但不能被100整除。（2）能被4整除，又能被400整除。请编程判断某一年是否是闰年。
这个程序看上去很简单嘛，只要进行几次选择判断就可以了，这是我写的程序，你能写一个和我这个程序不一样的代码吗？
1 //判断闰年1
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int year,leap;
8 cin>>year;
9 if(year%400==0)
10 cout<<"是闰年";
11 else if(year%100!=0)
12 {
13 if (year%4==0)
14 cout<<"是闰年";
15 else
16 cout<<"不是闰年";
17 }
18 else
19 cout<<"不是闰年";
20 system("pause");
21 return 0;
22 }
学过下面要讲的逻辑运算符后，这道题也可以只用一个逻辑表达式来表示：
（year%4==0 && year%100!=0）||year%400==0
或者加一个“！”用来判别非闰年：
！（（year%4==0 && year%100!=0）||year%400==0）
关系表达式的值是一个逻辑值，即“真”或“假”。例如，关系表达式“3==4”的值为假，“4>=0”的值为真。C++语言以“1”代表真，以“0”代表假。
C++语言里只要系统给出的逻辑运算结果非零，即为真。
C++语言提供三种逻辑运算符，如表2.2所示。
表2.2
逻辑运算举例如下：
a && b：若a、b为真，则a && b为真。
a || b：若a、b之一为真，则a || b为真。
！a：若a为真，则！a为假。
表2.3为逻辑运算的“真值表”。
表2.3
在一个逻辑表达式中如果包含多个逻辑运算符，例如：
！a&&b||x>y&&c 按以下优先次序： (1)！> && > || (2)&&和||低于关系运算符，！高于算术运算符。 例如： (a>b)&&(x>y) 可写成a>b && x>y (a==b)||(x==y) 可写成a==b||x==y (!a)||(a>b) 可写成!a||a>b
为了提高C++程序的运行效率，在逻辑表达式的求解中，并不是所有的逻辑运算符都被执行，只是在必须执行下一个逻辑运算符才能求出表达式的解时，才执行该运算符。例如：
（1）a && b && c只有在a为真时，才需要判别b的值。只有a和b都为真的情况下才需要判别c的值。只要a为假，就不必判别b和c的值。如果a和b为假，则不判别c。
（2）a || b || c只要a为真，就不必判断b和c，只有a为假，才判别b。a和b都为假才判别c。
例如下例中输出的a、b、c的值分别为0、1、1。
1 //逻辑表达式示例
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int a=0;
8 int b=1;
9 int c=1;
10 if(a && b++ && c++)
11 b++;
12 cout<<a<<b<<c<<endl;
13 system("pause");
14 return 0;
15 }
那这样就很容易写了，看看我的代码对不对？
1 //判断闰年2
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int year;
8 cin>>year;
9 if((year%400==0) || ((year%4==0) && (year%100!=0)))
10 cout<<year <<"是闰年"<<endl;
11 else
12 cout<<year<<"不是闰年"<<endl;
13 system("pause");
14 return 0;
15 }
switch语句是多分支选择语句。用来实现多分支选择结构。如学生的成绩‘A’等为85分以上，‘B’等为70~84分，‘C’等为60~69分，‘D’等为50~59，其余的为‘E’等，我们可以实现如下：
switch(grade) //比较grade值，grade值为一个字符
{
case 'A':cout<<“85-100分＼n”; //若grade值为'A'
case 'B':cout<<“70-84分＼n”; //若grade 值为'B'
case 'C':cout<<“60-69分＼n”; //若 grade 值为'C'
case 'D':cout<<“50-59分＼n”; //若 grade 值为'D'
default:cout<<“低于50分＼n”; //否则为E
}
switch后面括弧内的表达式，可以为任何类型。如上例中grade为字符型。
表达式的值必须与某一case后面的常量表达式的值完全匹配，才执行此case后面的语句，若所有的case中的常量表达式的值都没有与表达式的值相匹配，就执行default后面的语句。
每一个case的常量表达式的值必须互不相同，否则会出现互相矛盾的现象。
每个case和default的出现次序不影响执行结果。
要注意的是：执行完一个case后面的语句后，流程控制转移到下一个case继续执行。“case常量表达式”只是起语句标号作用，并不是在该处进行条件判断。在执行switch语句时，根据switch后面表达式的值找到匹配的入口标号后，就从此标号开始执行下去，不再进行判断。例如上面的例子中，若grade的值等于‘A’，则将连续输出。输出结果如下：
85-100分
70-84分
60-69分
50-59分
低于50分
应该在执行一个case分支后，使流程跳出switch结构，即终止switch语句的执行。我们可以用一个break语句来跳出结构。程序如下：
switch(grade) //比较grade值，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<<"50-59分＼n"; break;
default:cout<<"低于50分＼n"; //此处可以不加break语句。
}
那我可以少写一些语句了，因为多个case可以共用一组执行语句，例如：
switch(grade) { case 'A': case 'B': case 'C': cout<<"高于60分＼n";break; //语句1 case 'D': default:cout<<"低于60分＼n"; //语句2 } 则当grade的值为A、B、C时执行语句1，当grade的值为C，D时执行语句2。
【例题描述】 五分制
魔法学校实行五分制，即5分为最高分，现在输入一个学生的分数，如果是5分，则输出“优秀”，如果是4分，则输出“良”，如果是3分，则输出“及格”，如果是2分，则输出“不及格”，如果是1分，则输出“太糟糕了”。
1 //五分制
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int grade; //注意此处是整数
8 cin>>grade;
9 switch(grade) //比较grade值，grade值为一个整数
10 {
11 case 5:
12 cout<<"优秀＼n"; break;
13 case 4:
14 cout<<"良＼n"; break;
15 case 3:
16 cout<<"及格＼n"; break;
17 case 2:
18 cout<<"不及格＼n"; break;
19 default:cout<<"太糟糕了＼n"; //此处可以不加break语句
20 }
21 system("pause");
22 return 0;
23 }
【例题描述】 等级划分
魔法学校实行等级制，即A、B、C、D、E，现在输入一个学生的等级，如果是A，则输出“优秀”，如果是B，则输出“良”，如果是C，则输出“及格”，如果是D，则输出“不及格”，如果是E，则输出“太糟糕了”。
1 //等级划分
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 char grade; //注意此处是字符型
8 cin>>grade;
9 switch(grade) //比较grade值，grade值为一个字符
10 {
11 case'A':
12 cout<<"优秀＼n"; break;
13 case'B':
14 cout<<"良＼n"; break;
15 case'C':
16 cout<<"及格＼n"; break;
17 case'D':
18 cout<<"不及格＼n"; break;
19 default:cout<<"太糟糕了＼n"; //此处可以不加break语句
20 }
21 system("pause");
22 return 0;
23 }
【例题描述】 运费计算
魔法学院需要运输一批魔法材料，已知运费计算公式为f=p×w×s×（1-d），其中p为运输物品价值，w为运送物品重量，s为运送物品距离，d为折扣。现已知p、w、s的值，而折扣d的计算遵守以下规则：
s<250 没有折扣
250≤s<500 2%折扣
500≤s<1000 5%折扣
1000≤s<2000 8%折扣
2000≤s<3000 10%折扣
3000≤s 15%折扣
试计算运费f的值。注意，只能用switch语句判断和计算折扣值。
这个程序如果用判断语句解决并不是特别困难，可是如果用switch语句来解决，好像有点困难。因为表达式的值必须与某一case后面的常量表达式的值完全匹配，所以显然不能写成case s<250或者case（2000<=s）&&（s<3000）这样的错误形式。
可也总不能写几千个case吧？因此我们需要想办法将无尽的数集映射为有限的数集，你想到怎么做了吗？
参考程序如下所示：
1 //计算运费
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 int c,s;
8 float p,w,d,f;
9 cin>>p>>w>>s;
10 c=s/250; //c是s的映射
11 switch(c)
12 {
13 case 0:d=0;break;
14 case 1:d=2;break;
15 case 2:
16 case 3:d=5;break;
17 case 4:
18 case 5:
19 case 6:
20 case 7:d=8;break;
21 case 8:
22 case 9:
23 case 10:
24 case 11:d=10;break;
25 default:d=15;break;
26 }
27 f=p*w*s*(1-d/100.0);
28 cout<<"总运费="<<f<<endl;
29 system("pause");
30 return 0;
31 }
由于折扣的变化是有规律的，折扣的变化点都是250的倍数，（250、500、1000、2000、3000）。所以利用这一特点，加一个变量c=s/250，c代表250的倍数。
【上机实践】 判断某日是一年的第几天
键盘上按照年月日的格式输入年份、月和日期，运行程序以后，判断这一天是这一年的第几天。
一年有12个月，每个月的天数是一定的，因此在解决问题时，可以用switch语句对应每个月，然后将天数进行累加。需要考虑的是2月的天数计算，2月天数可以先看成28，计算完毕后再根据年份的闰/平年的不同考虑是否加1。