#例题 链接：https://ac.nowcoder.com/acm/contest/93968/K 来源：牛客网
题目描述 请实现一个抽象类Shape及接口方法（double area();double perimeter()）和三个派生类Rect、Triangle、Circle，通过构造三种派生类的对象的方式来计算给出的矩形、三角形和圆形的面积area和周长perimeter。
输入描述: 有多行输入，第一行为几何形状的数目n，其余n行，每行代表一个形状
其中每行第一个字符串为几何形状字符串，矩形为Rect，三角形为Triangle，圆形为Circle（请注意大小写）。
其余为相应形状的几何数据数字，之间用空格分隔（每个点用x,y两个坐标表示，x坐标在前，y坐标在后），如
Rect x1 y1 x2 y2
Circle x y r
Triangle x1 y1 x2y2 x3 y3
输出描述: 有多行结果，每行为对应几何形状的面积和周长(保留到小数点后5位)，两个数字之间用一个空格分隔。
示例1
输入
3
Rect 0 0 2 4
Circle 0 0 3
Triangle 0 0 2 2 2 0
输出
复制
8.00000 12.00000
28.27433 18.84956
2.00000 6.82843
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <iostream>
#include <vector>
#include <new>
#include<algorithm>
#include <cstdlib>
#include <cmath>
#define PI 3.1415926
using namespace std;
double distance1(double x1,double y1,double x2,double y2);
class Shape {
public:
virtual double area()=0;//纯虚函数，这样子可以保证同样的函数，可以在不同的子类里面定义，不会引起系统报错
virtual double perimeter()=0;
};
class Rect:virtual public Shape{//矩形的相关计算函数
public:
double area(){
return abs(x1-x2) * abs(y1-y2);//abs（）代表的是取绝对值
}
double perimeter(){
return (abs ( x1 - x2 ) + abs ( y1 - y2 ) )*2;
}
Rect(double a,double b,double c,double d):x1(a),y1(b),x2(c),y2(d){}
private://所有的子类如果想要创建自己的新的成员，就必须写成private的形式。
double x1,x2;
double y1,y2;
};
class Triangle:virtual public Shape{//三角形的相关函数
public:
Triangle(double a1,double a2,double a3,double a4,double a5,double a6):x1(a1),y1(a2),x2(a3),y2(a4),x3(a5),y3(a6){
a=distance1(x1,y1,x2,y2);
b=distance1(x1,y1,x3,y3);//给新的变量更改值只能在构造函数里面
c=distance1(x2,y2,x3,y3);//对于子类而言，想要给子类新定义的成员赋一个初始值，就只能在构造函数里面进行。
s=x1*(y2-y3)-y1*(x2-x3)+(x2*y3-x3*y2);//这个时候求三角形面积还可以用海伦公式，s=sqrt( p * ( p - a ) * ( p - b ) * ( p - c ) );p=(a+b+c)/2;
}
double area(){
return fabs(s/2);
}
double perimeter(){
return a+b+c;
}
private:
double x1,x2,x3;
double y1,y2,y3;
double a,b,c;
double s;
};
class Circle:virtual public Shape{
public:
Circle(double a,double b,double c):x(a),y(b),r(c){}
double area(){
return PI*r*r;
}
double perimeter(){
return 2*PI*r;
}
private:
double x,y,r;
};
double distance1(double x1,double y1,double x2,double y2){
return sqrt( pow ( ( x1 - x2 ) , 2.0 ) + pow ( ( y1 - y2 ) , 2.0 ) );
}
int main()
{
int n;
cin>>n;
char name[20];
for(int i=0;i<n;i++){
cin>>name;
if(strcmp(name,"Rect")==0){
double x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
Rect r(x1,y1,x2,y2);
printf("%.5lf ",r.area() );
printf("%.5lf \n",r.perimeter() );
}
if(strcmp(name,"Circle")==0){
double x,y,r;
cin>>x>>y>>r;
Circle c(x,y,r);
printf("%.5lf ",c.area() );
printf("%.5lf \n",c.perimeter() );
}
if(strcmp(name,"Triangle")==0){
double x1,x2,x3,y1,y2,y3;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
Triangle t(x1,y1,x2,y2,x3,y3);
printf("%.5lf ",t.area() );
printf("%.5lf \n",t.perimeter() );
}
}
return 0;
}
#冒泡排序 冒泡排序（Bubble Sort）是一种简单的排序算法。
一、基本原理
它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列的情况下），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样。
二、具体步骤（以升序排列为例）
- 比较相邻的元素。从数列的第一个元素开始，比较第1个和第2个元素，如果第1个元素大于第2个元素，就交换它们的位置。然后比较第2个和第3个元素，依此类推，直到比较完最后两个元素。这样，在第一次遍历完整个数列后，最大的元素就会“浮”到数列的最后一个位置。
- 例如，有数列[5, 4, 3, 2, 1]。首先比较5和4，因为5 > 4，所以交换它们的位置，得到[4, 5, 3, 2, 1]。接着比较5和3，交换后得到[4, 3, 5, 2, 1]，以此类推，经过这一轮比较后，数列变为[4, 3, 2, 1, 5]。
- 对除了最后一个元素之外的数列进行上述同样的操作。因为经过第一轮后，最大的元素已经在最后位置了，所以第二次只需要对前面n - 1个元素进行比较和交换操作。在这一轮结束后，第二大的元素会被移到倒数第二个位置。
- 对于刚才得到的[4, 3, 2, 1, 5]，第二次比较时，对[4, 3, 2, 1]进行操作，经过这一轮后得到[3, 2, 1, 4, 5]。
- 重复这个过程，每次比较的范围都向前缩小一个元素，直到数列完全有序。
三、时间复杂度和空间复杂度
- 时间复杂度
- 最坏情况和平均情况：在最坏的情况下，也就是数列是倒序排列的（例如要升序排列一个从大到小的数列），需要进行
次比较和交换操作，时间复杂度是
。其中n是数列的元素个数。
- 最好情况：如果数列已经是有序的，只需要进行一次遍历比较（不需要交换），时间复杂度是
。
- 最坏情况和平均情况：在最坏的情况下，也就是数列是倒序排列的（例如要升序排列一个从大到小的数列），需要进行
- 空间复杂度
- 冒泡排序是一种原地排序算法，它只需要一个额外的空间来交换元素，空间复杂度是
。这意味着它在排序过程中不需要大量的额外存储空间，只需要少量的临时变量来交换元素即可。
- 冒泡排序是一种原地排序算法，它只需要一个额外的空间来交换元素，空间复杂度是
四、适用场景和优缺点
-
优点
- 实现简单，容易理解，代码编写相对容易，是学习排序算法很好的入门例子。
- 是一种稳定的排序算法。稳定排序是指在排序过程中，相等元素的相对顺序不会改变。例如，有数列[3(a), 3(b), 2]，如果按照升序排序后得到[2, 3(a), 3(b)]，相等元素3(a)和3(b)的相对顺序没有改变，这在某些应用场景中很重要。
-
缺点
- 时间复杂度较高，对于大规模的数据排序效率较低。当数据量很大时，
- 时间复杂度较高，对于大规模的数据排序效率较低。当数据量很大时，
-
适用场景
- 数据量较小且基本有序的情况。例如，对一个已经接近有序的小数据集进行排序，冒泡排序可以快速地完成排序任务，并且由于其稳定性，能保证数据的相对顺序符合要求。
#冒泡排序实际案例
#include <iostream>
#include <iomanip>
#include <cmath>
#define SQUARE(x) x*x
#include <cstring>
using namespace std;
int main(){
int n;
int *arr;
cin>>n;
arr=(int*)malloc(n*sizeof(int));
for(int i=0;i<n;i++)cin>>arr[i];
for(int i=0;i<n;i++){//相当于输入了n个数字，对n个数字进行排序，每个数字都要排序一次，然后会排到后面，故每次都要多减一，进而简化计算
for(int g=0;g<n-i-1;g++){
if(arr[g]>arr[g+1]){
int zhong=arr[g];
arr[g]=arr[g+1];
arr[g+1]=zhong;
}
}
}
for(int i=0;i<n;i++)cout<<arr[i]<<" ";
#排序函数的运用（sort）
sort函数需要用#include <algorithm>数据库提前声明
sort函数默认是从小到大排序，我们也可以声明compare函数来规定sort函数的排序模式，下面有一道例题
```
链接：https://ac.nowcoder.com/acm/contest/93965/H
来源：牛客网
题目描述
感染新病毒后，来医院就诊的病人越来越多，每位病人包括的信息如下：姓名、病重程度和年龄。 对于来就诊的病人，医院按照如下规则对病人进行排序并进行诊治，具体规则为：病重程度高的优先诊治，同样病重程度，优先诊治年龄大的，如果年龄也相同，优先诊治名字按照字典顺序排在前面的。现在给出n个病人的信息，请编程输出排序后病人的信息。
输入描述:
共n + 1行，
第一行，一个整数n（3≤n≤1000），表示n个病人，
第2至第n + 1行，每行为一个病人的信息，包括姓名（长度小于100）、病重程度和年龄，用空格分隔。
输出描述:
排序后病人的信息，共n行，每行为一个病人的信息，详见输出样例。
示例1
输入
5
zhaoyi 9 66
qianer 9 68
sunsan 6 33
zhousi 9 68
lisan 6 32
输出
qianer 9 68
zhousi 9 68
zhaoyi 9 66
sunsan 6 33
lisan 6 32
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct student{
string name;
int now;
int age;
};
bool compare(student a,student b){
if(a.now==b.now&&a.age!=b.age)return a.age>b.age;//年龄大的在前
else if(a.age==b.age&&a.now==b.now)return a.name<b.name;//名字在字典前面的排在前
return a.now>b.now;
}
int main() {
int n;
cin>>n;
student stu[n];
for(int i=0;i<n;i++){
cin>>stu[i].name;
cin>>stu[i].now;
cin>>stu[i].age;
}
sort(stu,stu+n,compare);
for(int i=0;i<n;i++){
cout<<stu[i].name<<" "<<stu[i].now<<" "<<stu[i].age;
cout<<endl;
}
return 0;
}
京公网安备 11010502036488号