算法竞赛宝典(第一部):语言及算法入门
上QQ阅读APP看书,第一时间看更新

顺序结构

顺序结构如同自然语言中的文章一样,按照事件的发展顺序,依次自上而下书写需要的程序语句,并以语句出现的顺序来执行。

【例题描述】 魔法石检验

魔法的能量是从魔法石中提取的,如图2.1所示。每一块魔法石的价值由一个三位整数表示,其中百位数表示等级,十位数表示类别,个位数表示纯净度。现已知一个魔法石的三位数表示,试分别输出该魔法石的等级、类别、纯净度。

图2.1

题目本质是分解一个三位整数,而取余运算可以得到数据的各个位数。因此对实际分解过程进行模拟,即不断取余,依次得到数据的各个位数。例如分解数据398,采用的方案为:

(1)取其个位:398%10=8

(2)取其十位:398/10%10=9

(3)取其百位:398/100=3

参考程序如下所示:

1 //魔法石检验
2 #include <iostream>
3 using namespace std;
4 
5 int main()
6 {
7  int num;                   //先定义变量
8  int hundred,ten,indiv;
9  cout<<"请输入一个三位数";
10  cin>>num; //输入一个三位数
11  hundred=num/100; //分解百位数
12  ten=num/10%10; //分解十位数
13  indiv=num%10; //分解个位数
14  cout<<"百位数为"<<hundred<<endl; //输出
15  cout<<"十位数为"<<ten<<endl;
16  cout<<"个位数为"<<indiv<<endl;
17  system("pause");
18  return 0;
19 }

【例题描述】 小数的四舍五入

魔法世界用于魔法石能量检验的仪器可以精确到小数点后7位,但一般使用时只需对小数点后第三位四舍五入就可以了,现输入一个实数,实现小数点后第三位的四舍五入,例如输入1.235,输出1.24。

设输入的实数为x,假设要操作的数据x=2.3567,如果希望保留两位小数从第三位实现四舍五入,那么执行x=(int)(x*100+0.5),即2.3567×100+0.5来实现第三位的进位。

要想保留两位小数,则取整以后进行整除,即x/=100。

参考代码如下所示:

1 //小数的四舍五入
2 #include <iostream>
3 #include <iomanip>
4 using namespace std;
5 
6 int main()
7 {
8  double x;
9  cout<<"请输入一个双精度数";
10  cin>>x;
11  x=(int)(x*100+0.5);
12  x/=100;
13  cout<<setprecision(2)<<fixed<<x<<endl;
14  system("pause");
15  return 0;
16 }

【上机实践】 求三角形面积

如图2.2所示,三角形魔法阵是魔法师公认的最强大的阵形之一,因为三角形有着稳固、坚定、耐压的特点。现输入三角形的三边长,求三角形面积(假设输入的a、b、c能构成三角形)。

图2.2

已知三角形三条边的长度a、b、c,求三角形面积S,可以使用海伦公式,海伦公式是这样的:

,则

求一个数的平方根可以使用sqrt函数,例如sqrt(16)的结果是4。使用sqrt函数需在程序开头写#include <math.h>,即包含数学头文件。

核心伪代码为:

1 注意要包含数学头文件
2 定义浮点数a,b,c,p,area
3 输入a、b、c的值
4 计算p的值
5 计算面积值area
6 输出面积值area

注意,计算p的值不能这样写:p=1/2*(a+b+c),而应该写成p=1.0/2*(a+b+c),或者p=(a+b+c)/2。为什么要用1.0而不是1呢,这是因为如果是1/2,系统将会视之为两个整型数据相除,得到的值也是一个整型数,即1/2的结果舍弃小数部分后结果为0,而0乘以任何数也为0。

这种错误一般都非常隐蔽,在编程中要特别小心。

【上机实践】 求一元二次方程的根

含有一个未知数,且未知数的最高次数是2的整式方程叫作一元二次方程,其一般形式为ax2+bx+c=0(a≠0)。如图2.3所示,魔法学院图书馆珍藏着据说是上古时代古巴比伦人的《泥板文书》的魔法古籍中,就记载有求解一元二次方程根的解法。现已知一元二次方程ax2+bx+c=0,其中a、b、c由键盘输入,试求出方程的根。为了简便起见,假设输入的a、b、c三个值后b2-4ac≥0。例如当程序运行时输入165,输出结果为x1=-1 x2=-5。

图2.3

此题可以使用求一元二次方程式的求根公式

则x1=p+q,x2=p-q

核心伪代码为:

1 定义a,b,c,disc,p,q
2 输入a,b,c的值
3 计算b*b-4*a*c值给disc
4 计算p的值
5 计算q的值
6 输出x1、x2的值