1-1 sdut-C语言实验-递归函数之快速排序
任务描述:
本题要求实现一个快速排序函数。给定 N ( N<= 100000 ) 个 int 范围内的整数,要求用快速排序对数据进行升序排列。
函数接口定义:
void Quick_sort (int array[], int l, int r);
其中 array[]
、 l
、r
都是用户传入的参数。 array[]
是需要排序的数组,数组长度不会超过100000; l
和 r
是需要进行排序的左端点和右端点。
裁判测试程序样例:
#include <stdio.h> void Quick_sort (int array[], int l, int r); int main() { int N, array[100000]; scanf("%d", &N); for(int i=0; i<N; i++) { scanf("%d", &array[i]); } Quick_sort(array, 0, N-1); for(int i=0; i<N; i++) { printf("%d ", array[i]); } printf("\n"); return 0; } /* 请在这里填写答案 */
输入样例:
8 49 38 65 97 76 13 27 49
输出样例:
13 27 38 49 49 65 76 97
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> void Quick_sort(int array[],int l,int r) { int k = array[l],i=l,j=r; if(l>=r)return; while(i<j) { while(i<j&&array[j]>=k) j--; array[i] = array[j]; while(i<j&&array[i]<=k) i++; array[j] = array[i]; } array[i]=k; Quick_sort(array,l,i-1); Quick_sort(array,i+1,r); }
1-2 sdut-C语言实验-逆序建立单链表
任务描述:
输入N个整数,按照输入的相反顺序建立单链表存储,并遍历所建立的单链表,输出这些数据。
函数接口定义:
struct NODE *creat_node(int n);
参数n 为建立链表结点的个数。函数须返回单链表的地址。
void printf_node(struct NODE *head);
参数head为链表的头指针。函数不需返回。
裁判测试程序样例:
#include <stdio.h> 在这里给出函数被调用进行测试的例子。例如: #include #include struct NODE{ int data; struct NODE *next; }; struct NODE *creat_node(int n); void printf_node(struct NODE *head); int main() { int n; scanf("%d",&n); struct NODE *p=creat_node(n); printf_node(p); return 0; } /* 请在这里填写答案 */
输入样例:
8 12 56 4 6 55 15 33 62
输出样例:
62 33 15 55 6 4 56 12
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> struct NODE *creat_node(int n) { int i; struct NODE *head,*p,*q; head=(struct NODE *)malloc(sizeof(struct NODE)); head->next=NULL; q=head; for(i=1;i<=n;i++) { p=(struct NODE *)malloc(sizeof(struct NODE)); scanf("%d",&p->data); p->next=NULL; q->next=p; q=p; } return (head); } void printf_node(struct NODE *head) { struct NODE *p; p=head->next; while(p) { if(p->next) { printf("%d ",p->data); } else printf("%d\n",p->data); p=p->next; } }
1-3 sdut-C语言实验-英文金曲大赛
任务描述:
学校英语俱乐部举办了一个叫做“英文金曲大赛”的节目。评分规则是:有7个评委,每个评委都要给选手打分,最后要求去掉一个最高分和去掉一个最低分,再算出平均分。结果精确到小数点后两位。由于参赛人数太多,怎么快速给出成绩成了问题。大家都知道虎子是位热心的同学,他主动要求承担这份工作,发挥他计算机专业的特长,赛前根据规则先设计好程序,等分数一出,他这边就可以用程序计算出成绩了。你也是学计算机的吧?也一起来试试吧?
输入格式:
测试数据包括多个实例。每组数据包括7个实数,代表评委们对该选手的评分。紧接着是选手的名字,名字的长度不超过30个字符,且没有空格。输入直到文件结束。
输出格式:
算出每位选手名字和最终得分,结果保留两位小数。
输入样例:
10 10 10 10 10 10 9 tiger 0 0 0 0 0 0 0 beast
输出样例:
tiger 10.00 beast 0.00
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> struct count { int a,b,c,d,e,f,g; double ave; char name[300]; }s[1000]; int main () { int n,i; while(~scanf("%d%d%d%d%d%d%d %s",&s[i].a,&s[i].b,&s[i].c,&s[i].d,&s[i].e,&s[i].f,&s[i].g,s[i].name)) { s[i].ave=(s[i].b+s[i].c+s[i].d+s[i].e+s[i].f)/5.0; printf("%s %.2lf\n",s[i].name,s[i].ave); } return 0; }
1-4 sdut-C语言实验-敢死队问题
任务描述:
中国人民自古具有不怕死的精神,尤其在保家卫国的战场上,为了保卫祖国和人民,总是有人勇敢加入“敢死队”,不怕困难,勇于牺牲。大家不要以为我来介绍电影了,因为数据结构里真有这么道程序设计题目,原题如下:淄博市马鞍山保卫战中,有M个敢死队员要炸掉敌人的一个碉堡,谁都抢着想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到5时,对应的战士就去执行任务,且此战士不再参加下一轮计数。如果此战士没完成任务,再从下一个战士开始数数,被数到第5时,此战士接着去执行任务。以此类推,直到任务完成为止。今天大家就要完成这道敢死队问题。我们假设排长是1号,按照上面介绍,从一号开始数,数到5的那名战士去执行任务,那么排长是第几个去执行任务的?
输入格式:
输入包括多组数据,每行一个整数M(0<=M<=10000)(敢死队人数),若M=0,输入结束,不做处理。
输出格式:
输出一个整数n,代表排长是第n个去执行任务。
输入样例:
在这里给出一组输入。例如:
9 6 223 0
输出样例:
在这里给出相应的输出。例如:
2 6 132
相关限制:
代码长度限制16KB 时间限制1000ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> int main () { int n; while(~scanf("%d",&n)&&n!=0) { int a[10000],t=0,count=0,i,j; for(i=1;i<=n;i++) a[i]=i; for(i=1;i<=n;i++) { if(a[i]!=-1) { count++; if(count==5) { if(i!=1) { a[i]=-1; t++; count=0; } else if(i==1) { printf("%d\n",t+1); break; } } } if(i==n) i=0; } } return 0; }
1-5 神奇的函数
任务描述:
神奇的函数是这样被定义的:
F(n, m) = { if(n == 1 || m == 1) F(n, m) = 1; else F(n, m) = F(n-1, m) + F(n, m-1); }
输入格式:
第一行是正整数N (1 <= N<= 30),表示有N组数据。接下来N行,每行两个整数n,m (1 <= n, m <= 10)。
输出格式:
输出N行。每行输出一个整数表示F(n,m)。
输入样例:
在这里给出一组输入。例如:
1 1 2
输出样例:
在这里给出相应的输出。例如:
1
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> int f(int n,int m) { int t; if(n==1||m==1) t=1; else t=f(n-1,m)+f(n,m-1); return t; } int main () { int t,n,m,c; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); c=f(n,m); printf("%d\n",c); } return 0; }
1-6 sdut-C语言实验-王奶奶分茶叶蛋
任务描述:
由于新闻的封闭和局限,导致我国台湾省某教授认为中国大陆目前仍然很贫穷,老百姓尤其是河南的老百姓仍然吃不起茶叶蛋。热情的虎子邀请台湾网友前去河南游玩,王奶奶煮了一大锅茶叶蛋来招待他们,茶叶蛋太多了,第一天吃掉了所有茶叶蛋总数一半多一个,第二天又将剩下的茶叶蛋吃掉一半多一个,以后每天吃掉前一天剩下的一半多一个,到第n天准备吃的时候只剩下一个茶叶蛋。这下可把台湾同胞们难为坏了。
请帮忙计算一下,第一天开始吃的时候一共有多少个茶叶蛋?
输入格式:
输入包含一个正整数n(1≤n≤30),表示只剩下一个茶叶蛋的时候是在第n天发生的。
输出格式:
输出第一天开始吃的时候茶叶蛋的总数。
输入样例:
在这里给出一组输入。例如:
2
输出样例:
在这里给出相应的输出。例如:
4
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> int main () { int n,i; long long int f[100]; scanf("%d",&n); f[n]=1; f[n-1]=4; for(i=n-1;i>=1;i--) f[i-1]=2*(f[i]+1); printf("%lld\n",f[1]); return 0; }
1-7 sdut-虎子的会议安排
任务描述:
学校的礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办。虎子的工作就是安排学校礼堂的活动,每个时间最多安排一个活动。现在虎子有一些活动计划的时间表,他想尽可能的安排更多的活动,请问他该如何安排。
输入格式:
第一行是一个整型数m(m<100)表示共有m组测试数据。每组测试数据的第一行是一个整数n(1<n<100)表示该测试数据共有n个活动。随后的n行,每行有两个正整数Bi,Ei(0<=Bi,Ei<24),分别表示第i个活动的起始与结束时间(Bi<=Ei)
输出格式:
对于每一组输入,输出最多能够安排的活动数量。每组的输出占一行
输入样例:
在这里给出一组输入。例如:
2 2 1 10 10 11 3 1 10 9 11 11 20
输出样例:
在这里给出相应的输出。例如:
2 2
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> struct count { int begin,end,dight; }a[100],b[100]; void st(struct count a[],int n) { int i,j; struct count t; for(i=0;i<n-1;i++) { for(j=0;j<n-1-i;j++) { if(a[j].end>a[j+1].end) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } } int main () { int t,n,i,k; scanf("%d",&t); while(t--) { k=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&a[i].begin,&a[i].end); a[i].dight=i+1; } st(a,n); for(i=0;i<n;i++) { if(a[i].begin>=b[k].end) { k++; b[k]=a[i]; } } printf("%d\n",k); } return 0; }
1-8 sdut-C语言实验-最长上升子序列的和
任务描述:
一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1<= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)。你的任务,就是对于给定的序列,求出最长上升子序列的长度以及最长上升子序列的长度的和。
注意:
1、最长上升子序列的长度的和不一定是序列和最大的,比如(100 1 2 3),最长上升子序列的长度的和是6而不是100;
2、(1, 7, 3, 5, 9, 4, 8)的最长上升子序列为(1, 3, 5, 9)和(1, 3, 5, 8),最长上升子序列的长度的和是18。
输入格式:
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。
输出格式:
最长上升子序列的长度和最长上升子序列的长度之和。
输入样例:
在这里给出一组输入。例如:
7 1 7 3 5 9 4 8
输出样例:
在这里给出相应的输出。例如:
4 18
相关限制:
代码长度限制16KB 时间限制400ms 内存限制64MB 栈限制8192KB
答案:
#include <stdio.h> int main () { int a[1001],b[1001],n,i,k,max,m,t=0; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); b[1]=a[1]; for(k=2;k<=n;k++) { m=0; for(i=1;i<k;i++) { if(a[k]>a[i]&&b[i]>m) m=b[i]; } b[k]=a[i]+m; } max=-1; for(i=1;i<=n;i++) { if(b[i]>max) { max=b[i]; t++; } } printf("%d %d\n",t,max); return 0; }