SDUT-程序设计基础Ⅱ-期末测试

1-1 sdut-C语言实验-递归函数之快速排序

任务描述:

本题要求实现一个快速排序函数。给定 N ( N<= 100000 ) 个 int 范围内的整数,要求用快速排序对数据进行升序排列。

函数接口定义:

void Quick_sort (int array[], int l, int r);

其中 array[]lr 都是用户传入的参数。 array[] 是需要排序的数组,数组长度不会超过100000; lr 是需要进行排序的左端点和右端点。

裁判测试程序样例:

#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;
}
如果对您有帮助的话,能否支持一下博主?
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇