SDUT-程序设计基础Ⅱ-单元测试2

1-1 数据结构实验之排序八:快速排序

任务描述:

本题要求实现一个快速排序函数。给定 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 删数问题

任务描述:

 键盘输入一个高精度的正整数n(≤100位),去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s,寻找一种方案,使得剩下的数字组成的新数最小。

输入格式:

输入两个数字,分别为原始数n,要去掉的数字数s (s < n);

输出格式:

输出去掉s个数后最小的数。

输入样例:

178543 4

输出样例:

13

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
#include
int main()
{
    char num[200]={'\0'};
    int s,i,j;
    scanf("%s %d",num,&s);
    while(s>0)
    {
        i=0;
        while(num[i]!='\0'&&num[i]<=num[i+1])
            i++;
        for(j=i;j<strlen(num);j++)
        {
            num[j]=num[j+1];
        }
        s--;
    }
    i=0;
    while(num[i]=='0')
        i++;
    if(num[i]=='\0')
        printf("0\n");
    else
        printf("%s\n",&num[i]);
    return 0;
}

1-3 母牛的故事

任务描述:

有一对夫妇买了一头母牛,它从第2年起每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?

输入格式:

输入为一个整数n(0< n< 55)

输出格式:

输出在第n年的时候母牛的数量。

输入样例:

在这里给出一组输入。例如:

5

输出样例:

在这里给出相应的输出。例如:

6

相关限制:

代码长度限制16KB            时间限制400ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
#include
int main()
{
   int n,i;
   long long int f[100];
   scanf("%d",&n);
   f[1]=1;
   f[2]=2;
   f[3]=3;
   f[4]=4;
   for(i=5;i<=n;i++)
   {
       f[i]=f[i-1]+f[i-3];
   }
   printf("%d\n",f[n]);
    return 0;
}

1-4 骨牌铺方格

任务描述:

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.例如n=3时,为2× 3方格,骨牌的铺放方案有三种。

输入格式:

输入包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0< n<=50)。

输出格式:

输出铺放方案的总数。

输入样例:

在这里给出一组输入。例如:

3

输出样例:

在这里给出相应的输出。例如:

3

相关限制:

代码长度限制16KB            时间限制400ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
#include
int main()
{
   int n,i;
   long long int f[100];
   scanf("%d",&n);
   f[1]=1;
   f[2]=2;
   for(i=3;i<=n;i++)
   {
       f[i]=f[i-1]+f[i-2];
   }
   printf("%lld\n",f[n]);
    return 0;
}

1-5 青蛙过河

任务描述:

1)一条小溪尺寸不大,青蛙可以从左岸跳到右岸,在左岸有一石柱L,石柱L面积只容得下一只青蛙落脚,同样右岸也有一石柱R,石柱R面积也只容得下一只青蛙落脚。

2)有一队青蛙从小到大编号:1,2,…,n。

3)初始时:青蛙只能趴在左岸的石头 L 上,按编号一个落一个,小的落在大的上面—–不允许大的在小的上面。

4)在小溪中有S个石柱、有y片荷叶。

5)规定:溪中的每个石柱上如果有多只青蛙也是大在下、小在上,每个荷叶只允许一只青蛙落脚。

6)对于右岸的石柱R,与左岸的石柱L一样允许多个青蛙落脚,但须一个落一个,小的在上,大的在下。

7)当青蛙从左岸的L上跳走后就不允许再跳回来;同样,从左岸L上跳至右岸R,或从溪中荷叶、溪中石柱跳至右岸R上的青蛙也不允许再离开。

问题:在已知小溪中有 s 根石柱和 y 片荷叶的情况下,最多能跳过多少只青蛙?

输入格式:

第一行输入一个整数 t, 代表有 t 组数据。(1 <= t <= 15)

每组占一行,每行包含2个数s(s是小溪中的石柱数目)、y(y是小溪中的荷叶数目)。(0 <= s <= 10 , 0 <= y <= 10)

输出格式:

对每组输入,输出有一行,输出最多能跳过的青蛙数目。

输入样例:

在这里给出一组输入。例如:

2
0 2
1 2

输出样例:

在这里给出相应的输出。例如:

3
6

相关限制:

代码长度限制16KB            时间限制400ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
int f(int n,int m);
int main()
{
	int t,s,y,c;
	scanf("%d",&t);
	while(t--)
    {
        scanf("%d%d",&s,&y);
        c=f(s,y);
        printf("%d\n",c);
    }
	return 0;
 }
int f(int n,int m)
{
    int t;
    if(n==0)
        t=m+1;
    else
        t=2*f(n-1,m);
    return t;
}

1-6 数字三角形问题

任务描述:

给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。对于给定的由n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和的最大值。

输入格式:

输入数据的第1行是数字三角形的行数n,1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。

输出格式:

输出数据只有一个整数,表示计算出的最大值。

输入样例:

在这里给出一组输入。例如:

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例:

在这里给出相应的输出。例如:

30

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
int main ()
{
    int a[120][120],b[120][120],n,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        for(j=0;j<=i;j++)
        {
            scanf("%d",&b[i][j]);
        }
    }
    for(i=0;i<n;i++) { a[n][i]=b[n][i]; } for(i=n-1;i>=0;i--)
    {
        for(j=0;j<=i;j++) { if(a[i+1][j]>a[i+1][j+1])
            {
                a[i][j]=a[i+1][j]+b[i][j];
            }
            else
                a[i][j]=a[i+1][j+1]+b[i][j];
        }
    }
    printf("%d\n",a[0][0]);
    return 0;
}

1-7 蟠桃记

任务描述:

孙悟空在大闹蟠桃园的时候,第一天吃掉了所有桃子总数一半多一个,第二天又将剩下的桃子吃掉一半多一个,以后每天吃掉前一天剩下的一半多一个,到第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("%d\n",f[1]);
    return 0;
}

1-8 汉诺塔

任务描述:

汉诺塔(又称河内塔)问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒A、B和C,A上面套着n个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从A棒搬到C棒上,规定可利用中间的一根B棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。僧侣们搬得汗流满面,可惜当n很大时这辈子恐怕就很搬完了。聪明的你还有计算机帮你完成,你能写一个程序帮助僧侣们完成这辈子的夙愿吗?

输入格式:

输入金片的个数n (1 <= n <= 10)。

输出格式:

输出搬动金片的全过程。格式见样例。

输入样例:

在这里给出一组输入。例如:

2

输出样例:

在这里给出相应的输出。例如:

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

相关限制:

代码长度限制16KB            时间限制400ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
void move(int,char,char,char);
int main()
{
    int n;
    scanf("%d",&n);
    move(n,'A','B','C');
    return 0;
}
void move(int m,char p,char q,char r)
{
    if(m==1)
    {
        printf("Move disk %d from %c to %c\n",m,p,r);
    }
    else
    {
        move(m-1,p,r,q);
        printf("Move disk %d from %c to %c\n",m,p,r);
        move(m-1,q,p,r);
    }
}
如果对您有帮助的话,能否支持一下博主?
暂无评论

发送评论 编辑评论


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