头歌 | 数据结构与算法课程设计-算法与竞赛(第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 ,请认真参考实训《算法与竞赛(第2章) - C++与Algorithm基础一》 的第三个关卡,之后的实训将不再对sort进行讲解。

二分查找算法

二分查找算法也称折半查找算法 Binary Search Algorithm ,它是一种效率较高的查找方法,复杂度为O(logN​)。二分查找算法要求线性表(序列)必须采用顺序存储结构,而且表中元素按关键字有序排列。

核心思想:将表中间位置记录的关键字与待查找的关键字进行比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

幸运的是,C++ 在 Algorithm 算法模板中集成了二分查找算法,这样仅仅调用一个模板函数 binary_search 就可以实现指定元素(关键字)的查找了。其函数原型及其应用实例如下:

 1 \\ binary_search函数原型
 2 default (1):
 3     template <class ForwardIterator, class T>
 4     bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);
 5 custom (2):
 6     template <class ForwardIterator, class T, class Compare>
 7     bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
 8 \\ binary_search应用实例
 9 int arr[4] = {1,2,3,4}; // 升序数组
10 bool judge1 = binary_search(arr, arr+4, 1); // judge1结果为true
11 bool judge2 = binary_search(arr, arr+4, 5); // judge2结果为false

本关卡使用的是整型数据,使用默认的模板函数即可。若有兴趣学习自定义数据类型下的二分查找,请参考实训《算法与竞赛(第2章) - C++与Algorithm基础一》第三个关卡对自定义数据类型的相关操作。

编程要求

本关的编程任务是补全右侧代码片段 main 中 Begin 至 End 中间的代码,具体要求如下:

在 main 中,读取N个无序序列,并存储在数组中,然后对无序数组进行排序,最后调用二分查找算法完成 次指定元素的查找任务,并输出查找结果。若在序列中,输出 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行,每行对应查询结果,每行末尾换行!!!


开始你的任务吧,祝你成功!

 

 

头歌 | 数据结构与算法课程设计-算法与竞赛(第3章) - C++与算法基础二
 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 
13 using namespace std;
14 
15 int main(int argc, const char * argv[]) 
16 {
17 
18     // 请在这里补充代码,完成本关任务
19     /********** Begin *********/
20     int n,m;
21     cin>>n;
22     int a[n+10];//需要注意的是,有的编译器支持这种定义方法,有的不支持
23     //可以考虑直接定义一个很大的数组 
24     //如果这样定义的话,顺序不能颠倒,只有有了n之后才可以定义这个数组 
25     
26     for(int i=1;i<=n;i++) cin>>a[i];//依次输入这n个无序序列并储存在数组中 
27     
28     sort(a,a+n+1);//利用sort函数对无序数组进行排序,sort默认使用 < 号 
29     
30     cin>>m;
31     int b[m+10];
32     for(int i=1;i<=m;i++)
33         cin>>b[i];
34         
35     for(int i=1;i<=m;i++){//利用for循环依次对数组中存储的每一个数在有序数组a中进行查找 
36         if(binary_search(a,a+n,b[i])) //binary_search函数题目中有写到,是对有序数组进行查找的 
37             cout<<b[i]<<" in array"<<endl;
38         else cout<<b[i]<<" not in array"<<endl;
39     }
40     /********** End **********/    
41     
42     return 0;
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>
2 bool binary_search (ForwardIterator first, ForwardIterator last, const T& val){
3      first = std::lower_bound(first,last,val);
4      return (first!=last && !(val<*first));
5     //first!=last为true:说明找到一个不小于关键字的元素
6     //!(val<*first) 为true:说明该元素与待查找关键字相等
7 }

模板函数 lower_bound 的基本用途是查找有序区间中第一个 大于或等于 某给定值的元素的位置,由此本关卡的任务可以利用 lower_bound 获取序列中等于待查找关键字的元素的位置。其函数原型及其应用实例如下:

 1 \\ 函数原型
 2 default (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 \\ 应用实例
 9 int arr[5] = {1,2,2,4,5};
10 int a = lower_bound(arr, arr+5, 2) - arr; // a结果为1

模板函数 upper_bound

模板函数 upper_bound 的基本用途与 lower_bound 相对,是查找有序区间中第一个 大于 某给定值的元素的位置,由此本关卡的任务可以利用 upper_bound 获取序列中第一个 大于 待查找关键字的元素的位置,往前移一位就是最后一个等于待查找关键字的元素的位置。其函数原型及其应用实例如下:

 1 \\ 函数原型
 2 default (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 \\ 应用实例
 9 int arr[5] = {1,2,2,4,5};
10 int b = upper_bound(arr, arr+5, 2) - arr; // b结果为3

模板函数 equal_range

模板函数 equal_range 综合了 lower_bound 和 upper_bound 的功能,通过内部调用这两个上下界查找函数,返回两个地址并组成 pair :第一个地址是序列中第一个大于等于待查找关键字的元素位置,而第二个地址是第一个大于待查找关键字的元素位置。因为本关卡的数据保证在序列中存在待查找关键字,所以 equal_range 返回的是一个左闭右开的区间位置。其函数原型及其应用实例如下:

1 default (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);
 6     return std::make_pair ( it, std::upper_bound(it,last,val) );
 7 }
 8 \\ 应用实例
 9 int arr[5] = {1,2,2,4,5};
10 auto bounds = equal_range(arr, arr+5, 2);
11 int a = bounds.first-arr; // a结果为1
12 int b = bounds.second-arr; // b结果为3

编程要求

本关的编程任务是补全右侧代码片段 main 中 Begin 至 End 中间的代码,具体要求如下:

在 main 中,读取 个升序序列,并存储在数组中,基于 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行,每行对应查询结果,每行末尾换行!!!


开始你的任务吧,祝你成功!

 

上一篇:JVM垃圾收集器-Parallel Scavenge收集器


下一篇:《Integer Programming》第二章读书笔记