头歌数据结构与算法课程设计-算法与竞赛（第3章）-C++与算法基础⼆
Algorithm 中⽂意思是算法，是⼀个计算的具体步骤，常⽤于数据处理、计算以及⾃动推理。它作为 C++ 标准模版库 STL 中最重要的头⽂件之⼀，其提供了⼤量⾮成员模版函数，例如排序操作、⼆分查操作、集合操作以及堆操作等。同时可以通过迭代器或指针访问任何对象序列，例如 STL 容器数组或实例。更多的了解请参考。
本实训主要设置了四个关卡：第⼀关和第⼆关介绍了 Algorithm 中的⼆分搜索操作 binary_search 及其相关搜索操作；第三关是修改序列操作 Modifying sequence operations ；第四关讲的是⾮修改序列操作 Non-modifying sequence operations 。最后在每个关卡都设置了实例，考察学员对所讲内容的理解和在线编程能⼒。
第1关：⼆分查：在N个⽆序整数⾥⾯查M个指定整数
任务描述
本关任务：给定包含 N 个整数的⽆序序列 S(a1,a2,..,aN)，以及 M 次查询序列 Q(b1,b2,..,bM)，判定 bj是否在序列 S 中。
相关知识
为了完成本关任务，你需要掌握：1.解题思路，2.快速排序算法，3.⼆分查算法。
解题思路
本关卡问题清晰，解法简单：对于每次查询bj，在序列S中遍历ai是否等于bj。虽然该解法实现简单，但是执⾏效率低，运算复杂度⾼O(N×M)。
⾼效解法：⾸先运⽤快速排序算法，将⽆序序列变为有序（升序），然后对每次查操作，使⽤⼆分查算法判断元素是否存在。该解法实现稍微有点复杂，但是执⾏效率⾼，运算复杂度低O(N×logN+M×logN)。
快速排序算法
快速排序算法的背景和原理前⾯已有很多实训介绍过了，为了⽅便实现，⼀般使⽤ algorithm 中模板函数 sort ，请认真参考的第三个关卡，之后的实训将不再对sort进⾏讲解。
⼆分查算法
⼆分查算法也称折半查算法 Binary Search Algorithm ，它是⼀种效率较⾼的查⽅法，复杂度为O(logN)。⼆分查算法要求线性表（序列）必须采⽤顺序存储结构，⽽且表中元素按关键字有序排列。
核⼼思想：将表中间位置记录的关键字与待查的关键字进⾏⽐较，如果两者相等，则查成功；否则利⽤中间位置记录将表分成前、后两个⼦表，如果中间位置记录的关键字⼤于查关键字，则进⼀步查前⼀⼦表，否则进⼀步查后⼀⼦表。重复以上过程，直到到满⾜条件的记录，使查成功，或直到⼦表不存在为⽌，此时查不成功。
幸运的是，C++ 在 Algorithm 算法模板中集成了⼆分查算法，这样仅仅调⽤⼀个模板函数 binary_search 就可以实现指定元素（关键字）的查了。其函数原型及其应⽤实例如下：
1 \\ binary_search函数原型
2default (1):
3 template <class ForwardIterator, class T>
4bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);
5 custom (2):
6 template <class ForwardIterator, class T, class Compare>
7bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
8 \\ binary_search应⽤实例
9int arr[4] = {1,2,3,4}; // 升序数组
10bool judge1 = binary_search(arr, arr+4, 1); // judge1结果为true
11bool judge2 = binary_search(arr, arr+4, 5); // judge2结果为false
本关卡使⽤的是整型数据，使⽤默认的模板函数即可。若有兴趣学习⾃定义数据类型下的⼆分查，请参考实训《算法与竞赛(第2章) - C++与Algorithm基础⼀》第三个关卡对⾃定义数据类型的相关操作。
编程要求
本关的编程任务是补全右侧代码⽚段 main 中 Begin ⾄ End 中间的代码，具体要求如下：
在 main 中，读取N个⽆序序列，并存储在数组中，然后对⽆序数组进⾏排序，最后调⽤⼆分查算法完成 M 次指定元素的查任务，并输出查结果。若在序列中，输出 bj in array，否则输出 bj not in array。
测试说明
平台将⾃动编译补全后的代码，并⽣成若⼲组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输⼊：
7
2 5 9 5 5
3 1
3
4 7 5
预期输出：
4 not in array
7 not in array
5 in array
输⼊格式：
第⼀⾏：序列元素个数N
第⼆⾏：N个⽆序序列元素
第三⾏：查询次数M
第四⾏：M个待查询元素
输出格式：
输出M⾏，每⾏对应查询结果，每⾏末尾换⾏
开始你的任务吧，祝你成功！
1//
2// main.cpp
3// step1
4//
5// Created by ljpc on 2018/7/8.
6// Copyright ? 2018年 ljpc. All rights reserved.
7//
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstdio>
12
13using namespace std;
14
15int main(int argc, const char * argv[])
16 {
17
18// 请在这⾥补充代码，完成本关任务
19/********** Begin *********/
20int n,m;
21 cin>>n;
22int a[n+10];//需要注意的是，有的编译器⽀持这种定义⽅法，有的不⽀持
23//可以考虑直接定义⼀个很⼤的数组
24//如果这样定义的话，顺序不能颠倒，只有有了n之后才可以定义这个数组
25
26for(int i=1;i<=n;i++) cin>>a[i];//依次输⼊这n个⽆序序列并储存在数组中
27
28 sort(a,a+n+1);//利⽤sort函数对⽆序数组进⾏排序，sort默认使⽤ < 号
29
30 cin>>m;
31int b[m+10];
32for(int i=1;i<=m;i++)
33 cin>>b[i];
34
35for(int i=1;i<=m;i++){//利⽤for循环依次对数组中存储的每⼀个数在有序数组a中进⾏查
36if(binary_search(a,a+n,b[i])) //binary_search函数题⽬中有写到，是对有序数组进⾏查的
37 cout<<b[i]<<" in array"<<endl;
38else cout<<b[i]<<" not in array"<<endl;
39 }
40/********** End **********/
41
42return0;
43 }
点击查看代码
第2关⼆分查：在N个有序整数⾥⾯查M个指定整数的闭区间位置
任务描述
本关任务：给定包含N个整数的升序序列S(a1,a2,..,aN)，以及M次查询序列Q(b1,b2,..,bM)，求bj在序列S中的闭区间位置（测试数据保证bj存在序列S中），例如2在升序序
列 1，2，2，3 中的闭区间位置为 [1,2] 。
相关知识
为了完成本关任务，你需要掌握：1.模板函数 lower_bound ，2.模板函数 upper_bound ，3.模板函数 equal_range 。
模板函数 lower_bound
上个关卡介绍了 binary_search 的模板函数，实际上它的内部实现是基于 lower_bound 函数实现的，通过 lower_bound 在有序序列⾥查不⼩于关键字的元素，并返回元素索引位置最低的地址，最后根据地址来判断是否查成功，代码如下：
1 template <class ForwardIterator, class T>
2bool binary_search (ForwardIterator first, ForwardIterator last, const T& val){
3 first = std::lower_bound(first,last,val);
4return (first!=last && !(val<*first));
5//first!=last为true：说明到⼀个不⼩于关键字的元素
6//!(val<*first) 为true：说明该元素与待查关键字相等
7 }
模板函数 lower_bound 的基本⽤途是查有序区间中第⼀个⼤于或等于某给定值的元素的位置，由此本关卡的任务可以利⽤ lower_bound 获取序列中等于待查关键字的元素的位置。其函数原型及其应⽤实例如下：
1 \\ 函数原型
2default (1):
3 template <class ForwardIterator, class T>
4 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
5 custom (2):
6 template <class ForwardIterator, class T, class Compare>
7 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);
8 \\ 应⽤实例
9int arr[5] = {1,2,2,4,5};
10int a = lower_bound(arr, arr+5, 2) - arr; // a结果为1
模板函数 upper_bound
模板函数 upper_bound 的基本⽤途与 lower_bound 相对，是查有序区间中第⼀个⼤于某给定值的元素的位置，由此本关卡的任务可以利⽤ upper_bound 获取序列中第⼀个⼤于待查关键字的元素的位置，往前移⼀位就是最后⼀个等于待查关键字的元素的位置。其函数原型及其应⽤实例如下：
1 \\ 函数原型
2default (1):
3 template <class ForwardIterator, class T>
4 ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
5 custom (2):
6 template <class ForwardIterator, class T, class Compare>
7 ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
8 \\ 应⽤实例
9int arr[5] = {1,2,2,4,5};
10int b = upper_bound(arr, arr+5, 2) - arr; // b结果为3
模板函数 equal_range
模板函数 equal_range 综合了 lower_bound 和 upper_bound 的功能，通过内部调⽤这两个上下界查函数，返回两个地址并组成 pair ：第⼀个地址是序列中第⼀个⼤于等于待查关键字的元素位置，
⽽第⼆个地址是第⼀个⼤于待查关键字的元素位置。因为本关卡的数据保证在序列中存在待查关键字，所以 equal_range 返回的是⼀个左闭右开的区间位置。其函数原型及其应⽤实例如下：
1default (1):
2 template <class ForwardIterator, class T>
3 pair<ForwardIterator,ForwardIterator>
4 equal_range (ForwardIterator first, ForwardIterator last, const T& val);
5 custom (2):
6 template <class ForwardIterator, class T, class Compare>
7 pair<ForwardIterator,ForwardIterator>
8 equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
模板函数 equal_range 基于 lower_bound 和 upper_bound 的函数内部实现如下：
1 \\ 函数原型
2 template <class ForwardIterator, class T>
3 pair<ForwardIterator,ForwardIterator>
4 equal_range (ForwardIterator first, ForwardIterator last, const T& val){
5 ForwardIterator it = std::lower_bound (first,last,val);
6return std::make_pair ( it, std::upper_bound(it,last,val) );
7 }
8 \\ 应⽤实例
9int arr[5] = {1,2,2,4,5};
10 auto bounds = equal_range(arr, arr+5, 2);
11int a = bounds.first-arr; // a结果为1
12int b = bounds.second-arr; // b结果为3
编程要求
本关的编程任务是补全右侧代码⽚段 main 中 Begin ⾄ End 中间的代码，具体要求如下：
在 main 中，读取 N 个升序序列，并存储在数组中，基于 lower_bound 和 upper_bound 算法（或 equal_range ）完成M次指定元素的查任务，并输出查闭区间结果（输出格式严格遵循样例）。
测试说明
平台将⾃动编译补全后的代码，并⽣成若⼲组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输⼊：
7
1 1
2
3 5 5 6
2
5 6
预期输出：
5 at order array position [4,5]
6 at order array position [6,6]
输⼊格式：
第⼀⾏：序列元素个数N
第⼆⾏：N个升序序列元素
第三⾏：查询次数M
第四⾏：M个待查询元素
输出格式：
输出M⾏，每⾏对应查询结果，每⾏末尾换⾏
开始你的任务吧，祝你成功！
1//
2// main.cpp
3// step2
4//
5// Created by ljpc on 2018/7/8.
6// Copyright ? 2018年 ljpc. All rights reserved.
7//
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstdio>
12using namespace std;
13
14int main(int argc, const char * argv[])
15 {
16
17// 请在这⾥补充代码，完成本关任务
18/********** Begin *********/
19int n;
20 cin>>n;//获取有序序列的元素个数，便于利⽤循环输⼊序列
21int a[n+10];//定义⼀个数组⽤于存储序列
22for(int i=0;i<=n-1;i++){//利⽤for循环不断输⼊序列
23//要注意⼀下这⾥，需要从数组的第⼀个位置开始记录
24 cin>>a[i];
25 }
26
27int m;
28 cin>>m;//获取要在有序序列中的查询次数
29int b[m+10];//定义数组b⽤于存储待查元素
30for(int i=0;i<=m-1;i++){
31//要注意⼀下这⾥，需要从数组的第⼀个位置开始记录
32 cin>>b[i];
33
34 }
35for(int i=0;i<=m-1;i++){
36 auto bounds = equal_range(a,a+n,b[i]);
37//利⽤函数equal_range查询
38int j=bounds.first-a;//序列中第⼀个【⼤于等于】待查关键字的元素位置39int p=bounds.second-a;//序列中第⼀个【⼤于】待查关键字的元素位置40 cout<<b[i]<<" at order array position ["<<j<<","<<p-1<<"]"<<endl;
41//因为p是⼤于的位置，⽽我们要求的是闭区间，所以应该减去 1
42 }
点击查看代码
如果因为个⼈习惯问题，喜欢将for循环中的i从1开始记录的话，代码应该这么写：
1 #include <iostream>
2 #include <algorithm>
3 #include <cstdio>
4using namespace std;
5
6int main(int argc, const char * argv[])
7 {
8
9// 请在这⾥补充代码，完成本关任务
10/********** Begin *********/
11int n;
12 cin>>n;//获取有序序列的元素个数，便于利⽤循环输⼊序列
13int a[n+10];//定义⼀个数组⽤于存储序列
14for(int i=1;i<=n;i++){//利⽤for循环不断输⼊序列
15 cin>>a[i];
16 }
17
18int m;
19 cin>>m;//获取要在有序序列中的查询次数
20int b[m+10];//定义数组b⽤于存储待查元素
21for(int i=1;i<=m;i++){
22//要注意⼀下这⾥，需要从数组的第⼀个位置开始记录
23 cin>>b[i];
24
25 }
26for(int i=1;i<=m1;i++){
27 auto bounds = equal_range(a+1,a+n+1,b[i]);
28//利⽤函数equal_range查询
29int j=bounds.first-a;//序列中第⼀个【⼤于等于】待查关键字的元素位置
30int p=bounds.second-a;//序列中第⼀个【⼤于】待查关键字的元素位置
31 cout<<b[i]<<" at order array position ["<<j<<","<<p-1<<"]"<<endl;
32//此时，j和 p所代表的地址实际上⽐要查的关键字的地址还要⼤于 1，所以应该都减 1
33//⼜因为p是⼤于的位置，⽽我们要求的是闭区间，所以应该减去 2
34 }
35
36
37/********** End **********/
38
39return0;
40 }
点击查看代码
第3关修改序列（数组）操作的应⽤
任务描述
本关任务：编写⼀个程序，实现复制Copy_N，交换Swap，取代Replace，填充Fill，倒置Reverse，滚动Rotate等修改序列操作。
相关知识
为了完成本关任务，你需要掌握：1.复制Copy_N，2.交换Swap，3.取代Replace，4.填充Fill，5.倒置Reverse，6.滚动Rotate。
复制Copy_N
Algorithm中有两个常⽤的复制函数：copy和copy_n，其中copy复制整个数组到新的数组中，⽽copy_n则是可选择的复制前n个元素到新的数组。 copy函数原型及其应⽤实例如下，参数first为数组⾸地址，参数last为数组尾地址，参数result为新数组⾸地址：
1 \\ 函数原型
2 template <class InputIterator, class OutputIterator>
3 OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);
4 \\ 应⽤实例
5int arr1[4] = {1,3,2,4};
6int arr2[4];
7 copy(arr1, arr1+4, arr2);
8 \\或者 arr2 = copy(arr1, arr1+4, arr2);
copy_n函数原型及其应⽤实例如下，参数first为数组⾸地址，参数n为要复制的数组元素个数，参数result为新数组⾸地址：
1 \\ 函数原型
2 template <class InputIterator, class Size, class OutputIterator>
3 OutputIterator copy_n (InputIterator first, Size n, OutputIterator result);
4 \\ 应⽤实例
5int arr1[4] = {1,3,2,4};
6int arr2[4];
7 copy_n(arr1, 4, arr2);
交换Swap
记住我Algorithm中交换模板函数为swap，传⼊两个参数地址引⽤，功能是交换这两个参数的数值，其函数原型及其应⽤实例如下：
1 \\ 函数原型
2 template <class T> void swap (T& a, T& b)
3 \\ 应⽤实例
4int a=1, b=2;
5 swap(a, b);
6 \\ a结果为2，b结果为1
取代Replace
Algorithm中取代模板函数为replace，传⼊参数first为数组⾸地址，参数last为数组尾地址，要被替换的旧元素为参数old_value，替换的新的元素为参数new_value，函数功能是将数组中所有的old_value替换为new_value，其函数原型及其应⽤实例如下：
1 \\ 函数原型
2 template <class ForwardIterator, class T>
3void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
4 \\ 应⽤实例
5int arr[4] = {1,2,2,3};
6 replace(arr, arr+4, 2, 0);
7 \\ arr结果为{1,0,0,3}
填充Fill
Algorithm中填充模板函数为fill，传⼊参数first为数组⾸地址，参数last为数组尾地址，填充值为参数val，
函数功能是将数组中的所有元素都重新赋值为val，其函数原型及其应⽤实例如下：
1 \\ 函数原型
2 template <class ForwardIterator, class T>
3void fill (ForwardIterator first, ForwardIterator last, const T& val);
发布评论