大连网站建设lccm,嘉祥网站seo,网站的建设心得,2021年中国关键词在上文中我们进行了排序算法的判断题、选择题的专项练习#xff0c;在这一篇中我们将进行排序算法中编程题的练习。 目录 编程题R7-1 字符串的冒泡排序R7-1 抢红包R7-1 PAT排名汇总R7-2 统计工龄R7-1 插入排序还是堆排序R7-2 龙龙送外卖R7-3 家谱处理 编程题
R7-1 字符串的冒… 在上文中我们进行了排序算法的判断题、选择题的专项练习在这一篇中我们将进行排序算法中编程题的练习。 目录 编程题R7-1 字符串的冒泡排序R7-1 抢红包R7-1 PAT排名汇总R7-2 统计工龄R7-1 插入排序还是堆排序R7-2 龙龙送外卖R7-3 家谱处理 编程题
R7-1 字符串的冒泡排序
我们已经知道了将N个整数按从小到大排序的冒泡排序法。本题要求将此方法用于字符串序列并对任意给定的KN输出扫描完第K遍后的中间结果序列。
输入格式
输入在第1行中给出N和K1≤KN≤100此后N行每行包含一个长度不超过10的、仅由小写英文字母组成的非空字符串。
输出格式
输出冒泡排序法扫描完第K遍后的中间结果序列每行包含一个字符串。
输入样例
6 2
best
cat
east
a
free
day输出样例
best
a
cat
day
east
free这里要知道一个知识点先比较两个字符串的第一个字符的ASCII码值如果第一个字符串的第一个字符大于第二个字符串的第一个字符则返回1反之则返回-1若两个字符相等则进行下一对字符的比较下面的比较均是ASCII码值的比较直到出现有一对字符不同则返回相应的值1或-1。若两个字符串所有的字符都相同则返回数字0。
#include stdio.h
#include string.h
int main()
{int n,k;scanf(%d%d,n,k);char a[100][11]{0},x[11];for(int i0;in;i)//用二维数组存储{scanf(%s,a[i]);}for(int i0;ik;i)//对于每个元素而言{for(int j0;jn-i-1;j)//每个元素都比较n-i-1次{if(strcmp(a[j],a[j1])0)//交换{strcpy(x,a[j]);strcpy(a[j],a[j1]);strcpy(a[j1],x);}}}for(int i0;in;i)printf(%s\n,a[i]);}R7-1 抢红包
没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录请你统计一下他们抢红包的收获。
输入格式
输入第一行给出一个正整数N≤104即参与发红包和抢红包的总人数则这些人从1到N编号。随后N行第i行给出编号为i的人发红包的记录格式如下
K N1 P1 ⋯ NK PK
其中K0≤K≤20是发出去的红包个数Ni是抢到红包的人的编号Pi0是其抢到的红包金额以分为单位。注意对于同一个人发出的红包每人最多只能抢1次不能重复抢。
输出格式
按照收入金额从高到低的递减顺序输出每个人的编号和收入金额以元为单位输出小数点后2位。每个人的信息占一行两数字间有1个空格。如果收入金额有并列则按抢到红包的个数递减输出如果还有并列则按个人编号递增输出。
输入样例
10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10输出样例
1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32#include iostream
#include algorithm
#include cstdiousing namespace std;// 定义结构体redbag用于存储每个人的红包信息
struct redbag{int id; // 编号int count 0; // 收到红包的个数int money 0; // 最终收到的金额
};// 自定义比较函数cmp用于sort排序时指定排序规则
bool cmp(redbag r1, redbag r2){if(r1.money ! r2.money){ // 按照最终收到的金额从大到小排序return r1.money r2.money;}else if(r1.count ! r2.count){ // 如果最终收到金额相等则按照收到红包的个数从大到小排序return r1.count r2.count;}else{ // 如果最终收到金额和收到红包的个数都相等则按照编号从小到大排序return r1.id r2.id;}
}int main(){int n; // 总人数cin n;redbag red[n1]; // 定义数组red用于存储每个人的信息int k, card, mon; // k表示某个人发出的红包数card表示发红包的人的编号mon表示红包金额for(int i 1; i n; i){cin k;red[i].id i;for(int j 1; j k; j){cin card mon;red[i].money - mon; // 发出红包的人需要减掉红包金额red[card].money mon; // 收到红包的人需要加上红包金额red[card].count; // 收到红包的人收到红包数加1}}sort(red1, redn1, cmp); // 使用sort排序按照指定的cmp规则排序for(int i 1; i n; i){printf(%d %.2lf\n, red[i].id, red[i].money / 100.0); // 输出每个人最终获得的金额需要将单位从分转换为元并保留两位小数}return 0;
}R7-1 PAT排名汇总
计算机程序设计能力考试Programming Ability Test简称PAT旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力科学的评价计算机程序设计人才为企业选拔人才提供参考标准。
每次考试会在若干个不同的考点同时举行每个考点用局域网产生本考点的成绩。考试结束后各个考点的成绩将即刻汇总成一张总的排名表。
现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。
输入格式:
输入的第一行给出一个正整数N≤100代表考点总数。随后给出N个考点的成绩格式为首先一行给出正整数K≤300代表该考点的考生总数随后K行每行给出1个考生的信息包括考号由13位整数字组成和得分为[0,100]区间内的整数中间用空格分隔。
输出格式:
首先在第一行里输出考生总数。随后输出汇总的排名表每个考生的信息占一行顺序为考号、最终排名、考点编号、在该考点的排名。其中考点按输入给出的顺序从1到N编号。考生的输出须按最终排名的非递减顺序输出获得相同分数的考生应有相同名次并按考号的递增顺序输出。
输入样例:
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85输出样例:
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4#includebits/stdc.h
using namespace std;struct student {string s; // 考生姓名int score; // 考生成绩int id; // 考场编号int rank; // 考场内排名int zrank; // 总体排名} a[30000]; // 存储考生信息的数组bool cmp(student x,student y)
{if(x.score ! y.score) return x.score y.score; // 根据成绩从高到低排序elsereturn x.s y.s; // 成绩相同时按照姓名的字典序排序}int main() {int n, cnt 0, k; // n为考生人数cnt为考生总数k为每个考场的考生人数cin n; // 输入考生人数for(int i 0; i n; i){cin k; // 输入每个考场的考生人数for(int j 0; j k; j) {cin a[j cnt].s a[j cnt].score; // 输入考生姓名和成绩a[j cnt].id i 1; // 设置考场编号}sort(a cnt, a cnt k, cmp); // 对当前考场的考生按照成绩从高到低排序a[cnt].rank 1; // 第一名考生的排名为1for(int j 1; j k; j) {if(a[cnt j - 1].score a[cnt j].score)a[cnt j].rank a[cnt j - 1].rank; // 成绩相同的考生排名相同elsea[cnt j].rank j 1; // 不同成绩的考生排名递增}cnt cnt k; // 更新考生总数}sort(a, a cnt, cmp); // 对所有考生按照成绩从高到低排序a[0].zrank 1; // 总体排名第一名考生的排名为1for(int j 1; j cnt; j){if(a[j - 1].score a[j].score)a[j].zrank a[j - 1].zrank; // 成绩相同的考生总体排名相同elsea[j].zrank j 1; // 不同成绩的考生总体排名递增}cout cnt endl; // 输出考生总数for(int i 0; i cnt; i) cout a[i].s a[i].zrank a[i].id a[i].rank endl; // 输出每个考生的姓名、总体排名、考场编号和考场排名return 0;
}R7-2 统计工龄
给定公司N名员工的工龄要求按工龄增序输出每个工龄段有多少员工。
输入格式:
输入首先给出正整数N≤105即员工总人数随后给出N个整数即每个员工的工龄范围在[0, 50]。
输出格式:
按工龄的递增顺序输出每个工龄的员工个数格式为“工龄:人数”。每项占一行。如果人数为0则不输出该项。
输入样例:
8
10 2 0 5 7 2 5 2输出样例:
0:1
2:3
5:2
7:1
10:1#include stdio.h // 包含标准输入输出头文件int main()
{int n;scanf(%d, n); // 输入待排序数字的个数int a[51] {0}; // 初始化一个长度为 51 的整型数组并初始化所有元素为 0// 循环读入待排序的数字统计各个年龄出现的次数for (int i 0; i n; i){int age;scanf(%d, age); // 输入当前数字a[age]; // 对应年龄出现次数加一}// 输出统计结果for (int i 0; i 50; i){if (a[i] ! 0) // 如果该年龄出现次数不为 0printf(%d:%d\n, i, a[i]); // 输出该年龄及其出现次数}
}
R7-1 插入排序还是堆排序
根据维基百科的定义
插入排序是迭代算法逐一获得输入数据逐步产生有序的输出序列。每步迭代中算法从输入序列中取出一元素将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
堆排序也是将输入分为有序和无序两部分迭代地从无序部分找出最大元素放入有序部分。它利用了大根堆的堆顶元素最大这一特征使得在当前无序区中选取最大元素变得简单。
现给定原始序列和由某排序算法产生的中间序列请你判断该算法究竟是哪种排序算法
输入格式
输入在第一行给出正整数 N (≤100)随后一行给出原始序列的 N 个整数最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出格式
首先在第 1 行中输出Insertion Sort表示插入排序、或Heap Sort表示堆排序然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔且行首尾不得有多余空格。
输入样例 1
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0输出样例 1
Insertion Sort
1 2 3 5 7 8 9 4 6 0输入样例 2
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9输出样例 2
Heap Sort
5 4 3 1 0 2 6 7 8 9#includestdio.h// 插入排序函数
void insert_sort(int *am,int n)
{int i,j;// 找到第一个逆序的元素位置for(i2; inam[i-1]am[i]; i);// 将该元素插入到合适的位置int keyam[i];for(ji-1;j1;j--){if(am[j]key) am[j1]am[j];else break;}am[j1]key;
}// 交换两个数的值
void swap(int *a,int *b)
{int t*a;*a*b;*bt;
}// 最大堆调整函数
void maxheapify(int *am,int i,int n)
{int l,r,max;while(1){li1;ri1|1;// 找到左右子节点中的最大值if(lnam[l]am[i]) maxl;else maxi;if(rnam[r]am[max]) maxr;// 如果最大值是当前节点则满足最大堆性质结束循环if(maxi) return;// 否则交换当前节点与最大值节点的值并继续调整swap(am[i],am[max]);imax;}
}// 堆排序函数
void heap_sort(int *am,int n)
{int i,size;// 找到第一个逆序的元素位置for(in;i1am[i]am[i-1];i--);// 交换第一个元素与最后一个元素并调整堆sizei-1;swap(am[1],am[i]);maxheapify(am,1,size);
}int main(void)
{int n;scanf(%d,n);int num[120]{0};int am[120]{0};// 输入数字序列for(int i1;in;i)scanf(%d,numi);// 输入比较的数字序列for(int i1;in;i)scanf(%d,ami);// 根据第一个数字的大小选择排序算法if(am[1]am[2]){printf(Insertion Sort\n);// 使用插入排序算法进行排序insert_sort(am,n);// 输出排序结果for(int i1;in;i){if(i!n) printf(%d ,am[i]);else printf(%d\n,am[i]);}}else{printf(Heap Sort\n);// 使用堆排序算法进行排序heap_sort(am,n);// 输出排序结果for(int i1;in;i){if(i!n) printf(%d ,am[i]);else printf(%d\n,am[i]);}}return 0;
}
R7-2 龙龙送外卖
龙龙是“饱了呀”外卖软件的注册骑手负责送帕特小区的外卖。帕特小区的构造非常特别都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树根结点是外卖站树上的结点就是要送餐的地址。
每到中午 12 点帕特小区就进入了点餐高峰。一开始只有一两个地方点外卖龙龙简单就送好了但随着大数据的分析龙龙被派了更多的单子也就送得越来越累……
看着一大堆订单龙龙想知道从外卖站出发访问所有点了外卖的地方至少一次这样才能把外卖送到所需的最短路程的距离到底是多少每次新增一个点外卖的地址他就想估算一遍整体工作量这样他就可以搞明白新增一个地址给他带来了多少负担。
输入格式:
输入第一行是两个数 N 和 M (2≤N≤105, 1≤M≤105)分别对应树上节点的个数包括外卖站以及新增的送餐地址的个数。
接下来首先是一行 N 个数第 i 个数表示第 i 个点的双亲节点的编号。节点编号从 1 到 N外卖站的双亲编号定义为 −1。
接下来有 M 行每行给出一个新增的送餐地点的编号 Xi。保证送餐地点中不会有外卖站但地点有可能会重复。
为了方便计算我们可以假设龙龙一开始一个地址的外卖都不用送两个相邻的地点之间的路径长度统一设为 1且从外卖站出发可以访问到所有地点。
注意所有送餐地址可以按任意顺序访问且完成送餐后无需返回外卖站。
输出格式:
对于每个新增的地点在一行内输出题目需要求的最短路程的距离。
输入样例:
7 4
-1 1 1 1 2 2 3
5
6
2
4输出样例:
2
4
4
6#includebits/stdc.h
using namespace std;
const int N1e55;
int n,m,t,a[N],maxx,dis[N],sum,k,vis[N],s;
vectorinte[N];// DFS函数用于计算每个节点到根节点的距离
void dfs(int x,int d){dis[x]d; // 记录节点x到根节点的距离为dfor(int i0;ie[x].size();i) dfs(e[x][i],d1); // 递归计算子节点到根节点的距离
}int main(){cinnm;for(int i1;in;i){scanf(%d,a[i]); // 输入每个节点的父节点编号if(a[i]-1) si; // 找到根节点的编号else e[a[i]].push_back(i); // 将节点i加入到其父节点a[i]的子节点列表中}dfs(s,0); // 从根节点开始进行DFS计算每个节点到根节点的距离vis[s]1; // 标记根节点已经访问过for(int i0;im;i){scanf(%d,t),kt;while(!vis[k]) vis[k]1,ka[k]; // 从节点t一直向上找直到找到已经访问过的节点maxxmax(maxx,dis[t]); // 更新最大距禝sumdis[t]-dis[k]; // 累加每次找到的路径长度printf(%d\n,sum*2-maxx); // 输出结果}return 0;
}
R7-3 家谱处理
人类学研究对于家族很感兴趣于是研究人员搜集了一些家族的家谱进行研究。实验中使用计算机处理家谱。为了实现这个目的研究人员将家谱转换为文本文件。下面为家谱文本文件的实例
JohnRobertFrankAndrewNancyDavid家谱文本文件中每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例John这个家族最早的祖先他有两个子女Robert和NancyRobert有两个子女Frank和AndrewNancy只有一个子女David。
在实验中研究人员还收集了家庭文件并提取了家谱中有关两个人关系的陈述语句。下面为家谱中关系的陈述语句实例
John is the parent of Robert
Robert is a sibling of Nancy
David is a descendant of Robert研究人员需要判断每个陈述语句是真还是假请编写程序帮助研究人员判断。
输入格式:
输入首先给出2个正整数N2≤N≤100和M≤100其中N为家谱中名字的数量M为家谱中陈述语句的数量输入的每行不超过70个字符。
名字的字符串由不超过10个英文字母组成。在家谱中的第一行给出的名字前没有缩进空格。家谱中的其他名字至少缩进2个空格即他们是家谱中最早祖先第一行给出的名字的后代且如果家谱中一个名字前缩进k个空格则下一行中名字至多缩进k2个空格。
在一个家谱中同样的名字不会出现两次且家谱中没有出现的名字不会出现在陈述语句中。每句陈述语句格式如下其中X和Y为家谱中的不同名字
X is a child of Y
X is the parent of Y
X is a sibling of Y
X is a descendant of Y
X is an ancestor of Y输出格式:
对于测试用例中的每句陈述语句在一行中输出True如果陈述为真或False如果陈述为假。
输入样例:
6 5
JohnRobertFrankAndrewNancyDavid
Robert is a child of John
Robert is an ancestor of Andrew
Robert is a sibling of Nancy
Nancy is the parent of Frank
John is a descendant of Andrew输出样例:
True
True
True
False
False#includeiostream
#includevector
#includemap
#includealgorithm
using namespace std;
const int MAX105;
vectorstringname(MAX); // 存储每个人的姓名
mapstring,stringparent; // 存储每个人与其父母的关系
string ancanc; // 用于表示祖先节点的字符串int main(){int N,M;cinNM;getchar(); // 读取换行符string s;while(N--){getline(cin,s); // 逐行读取输入int count1count(s.begin(),s.end(), ); // 统计该行中空格的个数ss.substr(count1); // 截取出姓名if(count10){parent[s]anc; // 如果没有空格说明是祖先节点name[0]s; // 将祖先节点的姓名存入name[0]}else{parent[s]name[count1/2-1]; // 否则将该节点与其父母的关系存入parent中name[count1/2]s; // 将该节点的姓名存入name中}}while(M--){string a,b,c,d;cinaddbdc; // 依次读取查询的条件if(bchild){ // 如果查询条件是childif(parent[a]c)coutTrueendl; // 如果a的父亲是c则输出Trueelse coutFalseendl; // 否则输出False}if(bancestor){ // 如果查询条件是ancestorwhile(parent[c]!aparent[c]!anc)cparent[c]; // 从c开始向上查找直到找到a或者祖先节点if(parent[c]anc)coutFalseendl; // 如果找到祖先节点则输出Falseelse coutTrueendl; // 否则输出True}if(bsibling){ // 如果查询条件是siblingif(parent[a]parent[c])coutTrueendl; // 如果a和c的父母相同则输出Trueelse coutFalseendl; // 否则输出False}if(bparent){ // 如果查询条件是parentif(parent[c]a)coutTrueendl; // 如果c的父亲是a则输出Trueelse coutFalseendl; // 否则输出False}if(bdescendant){ // 如果查询条件是descendantwhile(parent[a]!cparent[a]!anc)aparent[a]; // 从a开始向上查找直到找到c或者祖先节点if(parent[a]anc)coutFalseendl; // 如果找到祖先节点则输出Falseelse coutTrueendl; // 否则输出True}} return 0;
}
以上就是排序算法编程题的专项练习在下一篇文章中我们将介绍树的相关知识点。
