2021-2022学年上学期《算法设计与分析》期中小测

2021-2022学年上学期《算法设计与分析》期中小测

文章目录

• A 院庆抽奖（分治法）
• • 题目描述
  • 基本思路
  • 参考代码
  • 拓展
• B 程序设计竞赛之路（分治）
• • 题目描述
  • 基本思路
  • 参考代码
  • 拓展
• C 回忆之路（动态规划）
• • 题目描述
  • 基本思路
  • 参考代码
  • 拓展
• D 校友调查（动态规划）
• • 题目描述
  • 基本思路
  • 参考代码
  • 拓展

A 院庆抽奖（分治法） 题目描述

Description
为了庆祝信息学院成立20周年，学院举行了网络抽奖活动，每个信息学院的校友和教师都分配一个不重复号码，随机进行抽奖。请你设计一个高效的算法，根据获奖号码找到获奖者的姓名。如果该号码不存在，则输出none。请用分治法实现，禁止调用库函数，否则没有分数。要求算法的最坏时间复杂度为O(logn)
Input
第一行一个数字n，表示共有多少人参与抽奖， 1<=n<10^6
下面n行，每行包含号码和姓名，以空格分隔，已按号码升序进行了排序
下面一行，获奖号码，以空格分隔，表示获奖者的编号，号码为0时表示结束
Output
输出获奖者的姓名，姓名以空格分隔
Sample Input 1

5
1 乔布斯
3 扎克伯格
8 李开复
9 雷军
11 马化腾
11 3 7 0

Sample Output 1

马化腾 扎克伯格 none

基本思路

主要方法为二分搜索函数的实现，难点在于数字与人名的对应，参考代码中使用map函数进行处理

参考代码

#include 
using namespace std;
int b[1000005]={0};
bool bin_search(int a[],int l,int r,int x)
{
	while(l<=r){
		int mid=(l+r)/2;
	if(x==a[mid]) return true;
	else{
		if(x>a[mid])
		{
			l=mid+1;
			//bin_search(a,l,r,x);
		}
		else{
			r=mid-1;
			//bin_search(a,l,r,x);
		}
	}
	}
	return false;
}
int main()
{
	int n;
	cin>>n;
	string ss;
	map mp;
	for(int i=1;i<=n;i++)
	{
		cin>>b[i]>>ss;
		mp[b[i]]=ss;
	}
	int each;
	while(cin>>each)//!!!!!!!!!
	{
      	if(each==0) break;
//		if(binary_search(b,b+n+1,each))
		if(bin_search(b,0,n,each)) cout< 
拓展 
二分查找函数的实现：
 方法一：运用递归
 
int biSearch(int x, int a[],  int left, int right) {
  if (left > right) //当数组中没有元素时
      return -1;
  count++;
  int middle = (left + right) / 2;
  if (a[middle] == x) //如果找到，直接返回位置
     return middle;
  else if (a[middle] > x) //如果中间的数字大于x，在数组左半部分递归查找
     return biSearch(x, a, left, middle - 1);
  else //否则在数组右半部分递归查找
    return biSearch(x, a, middle + 1, right);
}
 
方法二：非递归
 
bool bi_search(int a[],int n,int q)
{
	int l=0,r=n-1;
	int mid=(l+r)/2;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(q==a[mid]) return true;
		if(q>a[mid]) l=mid+1;
		else r=mid-1;
	}
	return false;
}
 
方法三：
 
 
 
stl中的binary_search()函数实现二分查找
 binary_search(arr[],arr[]+size , indx)
 详细介绍参考：
 stl中binary_search()函数等介绍
 
 
map（）函数的运用
 c++map（）函数
 
对于连续输入直到输入为零时停止的处理
 
int each;
while(cin>>each)//!!!!!!!!!
{
  	if(each==0) break;
  	}
 
本来用的是
 
int each;
cin>>each;
while(each!=0)
{
.....
cin>>each;
}
 
但在判题系统中出现Runtime Error的错误，虽然后来又判对了，保险起见还是用第一种吧。
 
B 程序设计竞赛之路（分治） 
题目描述 
Description
 院庆时总是让人禁不住回忆学院从无到有的点点滴滴。学院组队参加第一次大学生程序设计比赛区域赛是2008年的合肥站，初次参赛经验不足，没有任何收获。后面经过若干次大赛的洗礼，终于在2013年长沙站首次获得了铜牌，2014年广州站首次获得了银牌，2020年南京站首次获得了金牌。这些成绩的取得都离不开队员刻苦的训练。如果你热爱编程，希望你也能刻苦学习，继续创造学院的辉煌。学院从2008年开始每年都会参加几场大学生程序设计比赛区域赛，请你帮忙找出如果按照时间排序，参加的第k场比赛是在哪一天。注意：直接用排序算法不得分，可以参考快速排序的思路，要求算法的平均时间复杂度为O(n)
 Input
 第一行一个数字n，表示共有多少场比赛
 第二行n个数字以空格分隔，表示每场比赛的比赛的日期，日期格式为YYYYMMDD
 下面一行一个数字k，表示查询的是第k场比赛的时间。
 Output
 第k场比赛的时间
 Sample Input 1
 
5
20081117
20180901
20101203
20101111
20191105
3
 
Sample Output 1
 
20101203
 
基本思路 
快速排序的函数实现，排序后选出第k天即可
 
参考代码 
#include 
using namespace std;
int a[10005];
int partition(int a[],int l,int r)
{
	int i=l,j=r+1;
	int x=a[l];
	while(true)
	{
		while(a[++i]x);
		if(i>=j) break;
		swap(a[i],a[j]);
	}
//	swap(a[l],a[j]);
a[l]=a[j];
a[j]=x;
	return j;
}
void QuickSort(int a[],int l,int r){
	if(l>n;
	for(int i=0;i>a[i];
	}
	QuickSort(a,0,n-1);
	int res;
	cin>>res;
	cout< 
拓展 
快速排序的函数实现：
 
int partition(int a[],int l,int r)
{
	int i=l,j=r+1;
	int x=a[l];
	while(true)
	{
		while(a[++i]x);
		if(i>=j) break;
		swap(a[i],a[j]);
	}
//	swap(a[l],a[j]);
a[l]=a[j];
a[j]=x;
	return j;
}
void QuickSort(int a[],int l,int r){
	if(l 
c++中的sort（）函数
 C++ sort()排序详解
 
C 回忆之路（动态规划） 
题目描述 
Description
 学院举办院庆时会邀请校友返校。校友返校后，经常会漫步校园，参观教学楼、实验室、图书馆，回忆他曾经学习和生活的点点滴滴。学校的形状为三角形高为n，景点的坐标表示为（i，j），每个景点都有一个回忆值。校友从曾经居住的13栋，坐标为（0, 0），出发，一直走到体育馆，坐标为（n-1, n-1）。由于时间比较紧张，所以只能向下走，或者向右走。请你帮忙计算参观路线的最大回忆值。要求算法的时间复杂度为O(n^2)
 Input
 第一行一个数字n，表示三角形的行数。2<=n<100
 第二行一个数字m，表示景点数
 接下来m行，每行3个数字，以空格分隔，表示景点的坐标（i, j）和回忆值v，0<=i<=n-1, 0<=j<=n-1, 1<=v<=100
 Output
 参观路线的最大回忆值
 Sample Input 1
 
5
6
0 0 6
1 1 3
2 0 2
3 0 2
3 2 7
4 4 8
 
Sample Output 1
 
25
 
Hint 校园地图为
 
6
*3
2 * *
2 * 7
** *8
 
最优路线为6->2->2->7->8，回忆值为25
 
基本思路 
 
 
运用动态规划填表就可解决问题 设定两二维数组
 v[i][j]:表示第i行第j列处的回忆值
 sum[i][j]:表示第i行第j列处总的最大回忆值(初始化为v[i][j]的值）
 状态转移方程： sum[i][j]=max(sum[i-1][j]+v[i][j],sum[i][j-1]+v[i][j]) 
 
 
参考代码 
#include 
using namespace std;
int main()
{
	int n;
	cin>>n;
	int m;
	cin>>m;
	int vl[n+1][n+1];
	memset(vl,0,sizeof(vl));
	int sum[n+1][n+1];
	memset(sum,0,sizeof(vl));
	int a,b,c;
	for(int i=0;i>a>>b>>c;
		vl[a+1][b+1]=c;
		sum[a+1][b+1]=c;
		
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			sum[i][j]=max(sum[i-1][j]+vl[i][j],sum[i][j-1]+vl[i][j]);
		}
	}
	cout< 
拓展 
 
 
注意二维数组的初始化要用memset函数
 memset（）函数介绍：
 老生常谈，正确使用memset
 C++中memset()函数的用法详解
 
 
在遍历数组时要注意i,j的边界与从0还是1开始的问题
 
D 校友调查（动态规划） 
题目描述 
Description
 校友返校后，算法老师想知道是不是在校时算法学得越好，毕业后的薪酬越高。于是算法老师找出了校友们在校时算法的成绩单，并且询问了每位校友的薪酬。算法老师希望找出最长校友的序列，满足算法成绩是严格递增的，同时薪酬也是严格递增的。要求算法的时间复杂度为O(nlogn)
 Input
 第一行一个数字n，表示调查的校友总数， 1<=n<=100
 下面n行，每行2个正整数用空格分隔，表示校友的算法成绩grade和薪酬salary, 0<=grade<=100, 0
 Output
 满足递增条件的校友序列最长的长度
 Sample Input 1
 
5
76 300000
82 500000
93 900000
89 200000
65 100000
 
Sample Output 1
 
4
 
 
 
Hint
 校友序列为
 （65，100000）、（76，300000）、（82，500000）、（93，900000）
 
 
基本思路 
与求最长的单调递增子序列类似，但有两个变量
 参考求最长单调递增子序列问题的状态转移方程：
 
 
 
 
 
本题中我用结构体保存分数与工资两个变量
 而本题中有两个条件，即需
 fris[i].sco>fris[j].sco&&fris[i].money>fris[j].money时更新动态规划数组
 len[i]=max(len[i],len[j]+1);
 注意需要对数据进行预处理，即对两结构体变量按照若两者分数不同，按分数从小到大排序，当两者分数相同则按两结构体变量按照工资从小到大排序，便于后续的遍历更新数组。
 代码中体现在对结构体数组排序的cmp函数：
 
bool cmp(fri a,fri b)
{
	if(a.sco!=b.sco) return a.sco 
最后len数组中的最大值即为题目所需的最大满足条件的递增序列长度
 
参考代码 
#include 
using namespace std;
struct fri{
	int sco;
	int money;
};
bool cmp(fri a,fri b)
{
	if(a.sco!=b.sco) return a.sco>n;
	fri fris[n+1];
	int len[n+1];
	for(int i=1;i<=n;i++)
	{
		cin>>fris[i].sco>>fris[i].money;
		len[i]=1;
	}
	sort(fris+1,fris+n+1,cmp);//结构体数组排序 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i-1;j++)
		{
			if(fris[i].sco>fris[j].sco&&fris[i].money>fris[j].money)
			{
				len[i]=max(len[i],len[j]+1);
			}
		}
	}
	int max_res=0;
	for(int i=1;i<=n;i++)
	{
		max_res=max(max_res,len[i]);
	}
	cout< 
拓展 
结构体的相关用法：
 C/C++结构体语法总结
 
cmp函数介绍：
 C++中cmp（）用法
 C++排序函数中cmp()比较函数详解
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5155553.html