头歌数据结构与算法课程设计-算法与竞赛（第2章）-C++与算法基础⼀
Algorithm中⽂意思是算法，是⼀个计算的具体步骤，常⽤于数据处理、计算以及⾃动推理。它作为C++标准模版库STL中最重要的头⽂件之⼀，其提供了⼤量⾮成员模版函数，例如排序操作、⼆分查操作、集合操作以及堆操作等。同时可以通过迭代器或指针访问的任何对象序列，例如STL容器数组或实例。
本实训主要设置了三个关卡：第⼀关介绍了Algorithm中的Min/Max操作；第⼆关是⾃定义数据类型结构体下的Min函数应⽤；第三关讲的是C++模板中的快速排序算法。最后在每个关卡都设置了实例，考察学员对所讲内容的理解和在线编程能⼒。
第1关：Algorithm模板中的Min/Max应⽤
任务描述
本关任务：基于Algorithm中的模板函数Min/Max编写⼀个程序：在整型、浮点型、字符类型、字符串类型中，计算出两个相同类型数据间的最⼩值和最⼤值。
相关知识
为了完成本关任务，你需要掌握：1.Algorithm模板函数min，2.Algorithm模板函数max，3.Algorithm模板函数minmax。
Algorithm 模板函数 min
在Algorithm模板函数中，关于min的⽤法主要有两个：基础数据类型的最⼩值函数和⾃定义数据类型的最⼩值函数。基础数据类型指整型int，单精度浮点型float，双精度浮点型double，字符类型char，字符串指针类型char*，字符串对象类型string等数据类型，⽽⾃定义的数据类型通常为结构体数据类型。其函数原型如下：
1default (1): // 默认的基础数据类型最⼩值函数
数据结构与算法c++版 pdf2 template <class T> const T& min (const T& a, const T& b);
3 custom (2): // ⾃定义的数据类型最⼩值函数
4 template <class T, class Compare>
5const T& min (const T& a, const T& b, Compare comp);
在本关卡中，主要是介绍默认的基础类型最⼩值函数及其实战，有关⾃定义数据类型的最⼩值函数的详细介绍和实战将在下⼀个关卡给出。使⽤⽰例如下：
1 #include <algorithm> // algorithm头⽂件
2int a=1, b=2;
3int c = std::min(a, b); // 调⽤min函数⽅式⼀
4using namespace std; // or 调⽤min函数⽅式⼆
5int d = min(a, b);
Algorithm 模板函数 max
最⼤值函数与最⼩值函数类似，使⽤⽅法也是⼀样的，也包含两个主要的⽤法。其函数原型如下：
1default (1)：
2 template <class T> const T& max (const T& a, const T& b);
3 custom (2)：
4 template <class T, class Compare>
5const T& max (const T& a, const T& b, Compare comp);
Algorithm 模板函数 minmax
特别的，在Algorithm模板函数中还包含⼀个特殊的函数：最⼩值最⼤值函数，它以数据对pair的形式返回两个值：最⼩值和最⼤值。同样的，该函数也能处理基础数据类型和⾃定义数据类型，其函数原型如下：
1default (1)：
2 template <class T>
3 pair <const T&,const T&> minmax (const T& a, const T& b);
4 custom (2)：
5 template <class T, class Compare>
6 pair <const T&,const T&> minmax (const T& a, const T& b, Compare comp);
因为 minmax 的返回值的使⽤⽅式⽐较特殊，通过 .first 和 .second 来分别获取最⼩值和最⼤值，⼀个⽰例如下：
1// minmax example
2 #include <iostream> // std::cout
3 #include <algorithm> // std::minmax
4int main () {
5 auto result = std::minmax({1,2,3,4,5});
6 std::cout << "minmax({1,2,3,4,5}): ";
7 std::cout << result.first << '' << result.second << '\n';
8int a = 1, b = 2;
9 auto result2 = std::minmax(a, b);
10 std::cout << "minmax({1,2}): ";
11 std::cout << result2.first << '' << result2.second << '\n';
12return0;
13 }
14/* 输出结果：
15minmax({1,2,3,4,5}): 1 5
16minmax({1,2}): 1 2
17*/
编程要求
本关的编程任务是补全右侧代码⽚段main中Begin⾄End中间的代码，具体要求如下：
在main中，⾸先按照整型、浮点型、字符类型、字符串类型依次读取数据，然后调⽤min和max操作（或者minmax操作）计算出最⼩值和最⼤值，最后按照⽰例的格式严格输出最⼩值和最⼤值结果。
测试说明
平台将⾃动编译补全后的代码，并⽣成若⼲组测试数据，接着根据程序的输出判断程序是否正确。以下是平台的测试样例：
测试输⼊： 53 86
0.04 0.41
g y
ertg erty
预期输出：
min(53,86)==53
max(53,86)==86
min(0.04,0.41)==0.04
max(0.04,0.41)==0.41
min(g,y)==g
max(g,y)==y
min(ertg,erty)==ertg
max(ertg,erty)==erty
输⼊格式：第⼀⾏：两个整型类型数据
第⼆⾏：两个浮点类型数据
第三⾏：两个字符类型数据
第四⾏：两个字符串类型数据
输出格式：最后⼀⾏末尾有换⾏符\n
请严格参照上述⽰例预期输出的格式
开始你的任务吧，祝你成功！
1//
2// main.cpp
3// step1
4//
5// Created by ljpc on 2018/7/2.
6// Copyright © 2018年 ljpc. All rights reserved.
7//
8
9 #include <iostream>
10 #include <algorithm>
11 #include <string>
12 #include <cstdio>
13using namespace std;
14
15int main(int argc, const char * argv[]) {
16
17
18// 请在这⾥补充代码，完成本关任务
19/********** Begin *********/
20int a,b;
21float c,d;
22char e,f;
23string g,h;
24 cin>>a>>b>>c>>d>>e>>f>>g>>h;
25 cout<<"min("<<a<<","<<b<<")=="<<min(a,b)<<endl;
26 cout<<"max("<<a<<","<<b<<")=="<<max(a,b)<<endl;
27 cout<<"min("<<c<<","<<d<<")=="<<min(c,d)<<endl;
28 cout<<"max("<<c<<","<<d<<")=="<<max(c,d)<<endl;
29 cout<<"min("<<e<<","<<f<<")=="<<min(e,f)<<endl;
30 cout<<"max("<<e<<","<<f<<")=="<<max(e,f)<<endl;
31 cout<<"min("<<g<<","<<h<<")=="<<min(g,h)<<endl;
32 cout<<"max("<<g<<","<<h<<")=="<<max(g,h)<<endl;
33/********** End **********/
34
35return0;
36 }
点击查看代码
第2关：min函数在⾃定义数据类型下的应⽤
任务描述
本关任务：编写⼀个程序，基于结构体存储学⽣信息，包含学号，姓名和学科成绩，并使⽤模板函数min获取学科成绩较低的学⽣信息，如果成绩相同，则获取学号靠前的学⽣信息。相关知识
为了完成本关任务，你需要掌握：1.⾃定义数据类型的模板函数min。
⾃定义数据类型的模板函数min
⾃定义数据类型的的学⽣信息结构体⾄少包含三项数据类型：
1. 整型类型：学号；
2. 字符串类型：姓名；
3. 整型类型：学科成绩：
1struct Student{
2int numberID;
3char name[20];
4int score;
5 };
模板函数min在处理⾃定义数据类型的时候，需要依据该数据类型的⽐较规则定义⼀个⽐较函数，该⽐较函数返回⽐较的真值。⽐如两个整数 a 和 b ：
1bool comp(int a, int b){ return a<b;}
2int c = min(a, b, comp);
在本关卡中，⾸先⽐较学⽣的成绩：若成绩不同，则返回成绩低的；若成绩相同，返回学号靠前的（即数值⼩的）。模板函数 min 处理⾃定义数据类型的函数原型如下：
1 template <class T, class Compare>
2bool comp(const T& a, const T& b);// 按定义的⽐较规则返回a<b的真值
3const T& min (const T& a, const T& b, Compare comp);
编程要求
本关的编程任务是补全右侧代码⽚段 min_cmp 和 main 中 Begin ⾄ End 中间的代码，具体要求如下：
在 min_cmp 中，完成两个学⽣信息的⽐较，⾸先⽐较学⽣的成绩：若成绩不同，则返回成绩⽐较的真值；若成绩相同，返回学号⽐较的真值。
在 main 中，使⽤结构体读取和记录学⽣信息，并基于模板函数 min 实现学⽣信息的⽐较，获取较⼩成绩的学⽣信息并输出。
测试说明
平台将⾃动编译补全后的代码，并⽣成若⼲组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输⼊：
20180108 Henry 54
20180126 Charles 72
预期输出：
20180108 Henry 54
测试输⼊：
20180122 Niki 71
20180110 Barbara 71
预期输出：
20180110 Barbara 71
输⼊格式：两⾏，每⾏⼀个学⽣信息：学号姓名成绩
输出格式：⼀⾏，输出学⽣信息，末尾换⾏\n
开始你的任务吧，祝你成功！
1//
2// main.cpp
3// step2
4//
5// Created by ljpc on 2018/7/6.
6// Copyright © 2018年 ljpc. All rights reserved.
7//
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstdio>
12 #include <cstring>
13 #include <string>
14
15using namespace std;
16
17struct Student{
18int numberID;
19char name[20];
20int score;
21 Student(){}
22 Student(int id_, char *name_, int score_){
23 numberID = id_;
24 strcpy(name, name_);
25 score = score_;
26 }
27void in()
28 {
29 scanf("%d %s %d", &numberID, name, &score);
30 }
31void out()
32 {
33 printf("%d %s %d\n", numberID, name, score);
34 }
35 };
36
37bool min_cmp(Student S1, Student S2){
38// 请在这⾥补充代码，完成本关任务
39/********** Begin *********/
40if (S1.score!=S2.score) return S1.score<S2.score;
41else return S1.numberID<S2.numberID;
42
43/********** End **********/
44 }
45
46int main(int argc, const char * argv[])
47 {
48
49// 请在这⾥补充代码，完成本关任务
50/********** Begin *********/
51 Student stu1,stu2;
52 stu1.in();
53 stu2.in();
54 Student stu;
55 stu=min(stu1,stu2,min_cmp);
56 stu.out();
57
58/********** End **********/
59
60return0;
61 }
点击查看代码
第3关：使⽤模板函数sort对学⽣成绩进⾏排序
任务描述
本关任务：编写⼀个程序，基于结构体存储N个学⽣信息，包含学号，姓名和学科成绩，并使⽤模板函数sort完成对学⽣信息的排序：成绩⾼的排序靠前，若成绩相同，则学号⼩的排序靠前。
相关知识
为了完成本关任务，你需要掌握：1.⾃定义数据类型下的排序模板函数sort。
⾃定义数据类型下的排序模板函数sort
Algorithm中的排序函数是基于快速排序算法实现的，复杂度为O(N*logN)。快速排序算法在1962年由C. A. R. Hoare提出，其基本思想是：通过⼀趟排序将待排序的数据分割成独⽴的两部分，左边部分的所有数据⽐右边部分的所有数据都要⼩，然后再按此⽅法对这两部分数据分别进⾏快速排序，整个排序过程可以递归进⾏，最后达到整个数据变成有序序列。
模板函数sort具有两种模式，⼀种是数据之间已有排序规则，⽐如整型数据、浮点数据，它们的⼤⼩⽐较是确定的；另⼀种是数据之间没有现成的排序规则，需要⾃定义排序规则，这类适⽤于⾃定义数据类型。它们函数原型如下：
1default (1):
2 template <class RandomAccessIterator>
3void sort (RandomAccessIterator first, RandomAccessIterator last);
4 custom (2):
5 template <class RandomAccessIterator, class Compare>
6void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
本关卡是对存储有N个学⽣信息的结构体数组进⾏排序，⼀般有两种⽅式：
在结构体中重载⼩于⽐较符<，因为sort函数默认使⽤<⽐较符，只要返回this.score>S.score的⽐较真值，那么使⽤sort排序将得到成绩从⾼到低的排序结果。由此，最后直接调⽤sort函数对结构体数组进⾏排序即可：
1struct Student{
2int numberID;
3char name[20];
4int score;
5bool operator < (const Student &S)const{
6//完成结构体⽐较规则：Student this VS. Student S
7//先⽐较成绩，若成绩相同，则⽐较学号
8 }
9 }
10 Student student[10];
11 sort(student, student+10);
实现⼀个结构体⽐较函数，然后作为参数传⼊sort函数完成排序中的结构体间的⼤⼩⽐较：
1bool max_cmp(Student S1, Student S2){
2//完成结构体⽐较规则：Student S1 VS. Student S2
3//先⽐较成绩，若成绩相同，则⽐较学号
4 }
5 Student student[10];
6 sort(student, student+10, max_cmp);
编程要求
本关的编程任务是补全右侧代码⽚段 operator < ，max_cmp 和 main 中 Begin ⾄ End 中间的代码，具体要求如下：
在 operator < 中，按照先进⾏学⽣成绩的⽐较，若成绩相等，再⽐较学号的⽐较规则，完成结构体 this 和结构体 S 的⼤⼩⽐较，并返回⽐较真值。
在 max_cmp 中，按照以上规则完成结构体 S1 和结构体 S2 的⼤⼩⽐较，并返回⽐较真值。
在 main 中，基于⾃定义的结构体数据类型读取和存储学⽣信息，然后使⽤ sort 函数完成学⽣成绩的从⼤到⼩排序，最后输出排序后的学⽣信息。测试说明
平台将⾃动编译补全后的代码，并⽣成若⼲组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输⼊：
7
20180127 Helen 88
20180111 Martin 51
20180102 James 88
20180114 Joseph 60
20180106 Joan 99
20180120 Lily 91
20180105 Malcolm 88
预期输出：
20180106 Joan 99
20180120 Lily 91
20180102 James 88
20180105 Malcolm 88
20180127 Helen 88
20180114 Joseph 60
20180111 Martin 51
输⼊格式：第⼀⾏学⽣数N，余下 N ⾏学⽣信息
输出格式： N ⾏排序后的学⽣信息，每⾏学⽣信息中间空格隔开，末尾换⾏。
开始你的任务吧，祝你成功！
1//
2// main.cpp
3// step3
4//
5// Created by ljpc on 2018/7/6.
6// Copyright ? 2018年 ljpc. All rights reserved.
7//
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstdio>
12 #include <cstring>
13 #include <string>
14
15using namespace std;
16
17struct Student {
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论