《程序设计基础(B)Ⅱ》 实验 3 4 难度较大题目记录

说(jiao)明(bian):最近我非常忙,被高数,线性代数,离散数学搞得晕头转向,上次机测还没缓过来,我一时糊涂竟然接了个专题(不是不愿意,是接的不是时候,当时迷迷糊糊的说了有时间,回到宿舍就后悔了,想起还有那么多事情要做...算了,说不定以后更忙呢,现在做专题也好QAQ...),各种因素导致我根本没有时间通过博客记录生活,只能在机测前进行整理与复习。随着下半学期C语言学习告一段落,我想我就能够拿出能多时间做我喜欢的事,并把它们记录下来了。

这将是我近半年来倒数第二次更新的这类博文。下下次一定是有趣的content啦~~

养兔子

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一对成熟的兔子每天能且只能产下一对小兔子,每次都生一公一母,每只小兔子的成熟期是1天,小兔子出生后隔一天才能再生小兔子。第一天某人领养了一对成熟的兔子,一公一母,请问第N天以后,他将会得到多少对兔子。

Input

测试数据包括多组,每组一行,为整数n(1≤n≤90)。
输入以0结束。

Output

对应输出第n天有几对兔子(假设没有兔子死亡现象,而且是一夫一妻制)。

Sample Input

1
2
0

Sample Output

1
2

Hint

数据类型可以用64位整数:long long

Reference Code

#include<stdio.h>
int main()
{
    int i,n;
    while (~scanf("%d",&n))
    {
        long long int f[92];
        if (n==0) break;
        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;
}

爬楼梯

Time Limit: 1000 msMemory Limit: 65536 KiB

Problem Description

小明是个非常无聊的人,他每天都会思考一些奇怪的问题,比如爬楼梯的时候,他就会想,如果每次可以上一级台阶或者两级台阶,那么上 n 级台阶一共有多少种方案?

Input

输入包含多组测试数据,对于每组测试数据:
输入只有一行为一个正整数 n(1 ≤ n ≤ 50)。

Output

对于每组测试数据,输出符合条件的方案数。
注意:64-bit 整型请使用 long long 来定义,并且使用 %lld 或 cin、cout 来输入输出,请不要使用 __int64 和 %I64d。

Sample Input

2
4

Sample Output

2
5

Reference Code

#include<stdio.h>
int main()
{
    int n,i;
    while (~scanf("%d",&n))
    {
        long long int f[52];
        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;
}

三国佚事——巴蜀之危

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

话说天下大势,分久必合,合久必分。。。却道那魏蜀吴三国鼎力之时,多少英雄豪杰以热血谱写那千古之绝唱。古人诚不我欺,确是应了那句“一将功成万骨枯”。
是夜,明月高悬。诸葛丞相轻摇羽扇,一脸愁苦。原来是日前蜀国战事吃紧,丞相彻夜未眠,奋笔急书,于每个烽火台写下安排书信。可想,这战事多变,丞相运筹 帷幄,给诸多烽火台定下不同计策,却也实属不易。
谁成想这送信小厮竟投靠曹操,给诸葛丞相暗中使坏。这小厮将每封书信都投错了烽火台,居然没有一封是对的。不多时小厮便被抓住,前后之事却也明朗。这可急坏了诸葛丞相,这书信传错,势必会让蜀军自乱阵脚,不攻自破啊! 诸葛丞相现在想知道被这小厮一乱,这书信传错共有多少种情况。

Input

​ 题目有多组数据,处理到文件结尾,丞相共写了n(1 <= n <= 20)封书信,输入一个正数n。

Output

​ 输出书信传错的情况数。

Sample Input

1
3
6

Sample Output

0
2
265

Reference Code

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

C语言实验——拍皮球

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 小瑜3岁了,很喜欢玩皮球,看来今后喜欢打篮球的^_^。最近她发现球从手中落下时,每次落地后反跳回原高度的一半,再落下,每次球落地时数球跳了几次,数到n次时爸爸在边上喊停,问小瑜现在球到底总共走了多少距离,小瑜故作沉思状,爸爸又问接下来小球能跳多高啊,小瑜摇摇头,心想还没跳我怎么知道啊,难道爸爸是神啊!这时的你在边上出主意想给小瑜写个程序计算一下,因此任务就交给你啦!假设球的初始高度为h,计算第n次落地时球经过的距离,以及落地后反弹能有多高。

Input

​ 输入数据有多组,第一行为数据的组数t,下面t行为t组数据,每行有两个数h和n,分别用空格分隔。

Output

​ 输出第n次反弹时球经过的距离和球最后的高度,保留小数点后2位。

Sample Input

2
100 1
100.0 2

Sample Output

100.00 50.00
200.00 25.00

Reference Code

#include<stdio.h>
int main()
{
    int n,i,x;
    while (~scanf("%d",&x))
    {
        double h,num,ans;
        while (x--)
        {
            scanf("%lf %d",&h,&n);
            num = h;
            ans = h;
            for (i=0;i<n;i++)
            {
                ans /= 2;
                if (i < n-1)
                {
                    num += 2*ans;
                }
            }
             ("%.2f %.2f\n",num,ans);
        }
    }
    return 0;
}

蟠桃记

Time Limit: 1000 msMemory Limit: 65536 KiB

Problem Description

​ 孙悟空在大闹蟠桃园的时候,第一天吃掉了所有桃子总数一半多一个,第二天又将剩下的桃子吃掉一半多一个,以后每天吃掉前一天剩下的一半多一个,到第n天准备吃的时候只剩下一个桃子。这下可把神仙们心疼坏了,请帮忙计算一下,第一天开始吃的时候一共有多少个桃子?

Input

​ 输入数据有多组,每组占一行,包含一个正整数n(1≤n≤30),表示只剩下一个桃子的时候是在第n天发生的。
输入以0结束。

Output

​ 对于每组输入数据,输出第一天开始吃的时候桃子的总数,每个测试实例占一行。

Sample Input

2
4
0

Sample Output

4
22

Reference Code

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

马拦过河卒

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

​ 棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示,A点(0,0)、B点(n,m)(n,m为不超过15的整数),同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

Input

​ 一行四个数据,用空格分隔,分别表示B点的坐标和马的坐标。

Output

​ 一个数据,表示所有的路径条数。

Sample Input

6 6 3 3

Sample Output

6

Referance Code

#include<stdio.h>
int main()
{
    int x,y,m,n,i,j;
    int dx[9]={0,-2,-1,1,2,2,1,-1,-2};
    int dy[9]={0,1,2,2,1,-1,-2,-2,-1};
    long long int f[20][20]={0};
    int g[20][20] = {0};
    scanf("%d %d %d %d",&n,&m,&x,&y);
    g[x][y]=1;
    for (i=1;i<=8;i++)
    {
        if ((x+dx[i]>=0)&&(x+dx[i]<=n)&&(y+dy[i]>=0)&&(y+dy[i]<=m))
            g[x+dx[i]][y+dy[i]] = 1;
    }
    for (i=1;i<=n;i++)
    {
        if (g[i][0]!=1) f[i][0]=1;
        else
        {
            for(;i<=n;i++)
            {
                f[i][0]=0;
            }
        }
    }
    for (j=1;j<=m;j++)
    {
        if (g[0][j]!=1) f[0][j]=1;
        else
        {
            for(;j<=m;j++)
            {
                f[0][j]=0;
            }
        }
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            if (g[i][j]==1) f[i][j]=0;
            else f[i][j] = f[i][j-1] + f[i-1][j];
        }
    }
    printf ("%d\n",f[n][m]);
    return 0;
}

汉诺塔

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 汉诺塔(又称河内塔)问题是印度的一个古老的传说。

开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒A、B和C,A上面套着n个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从A棒搬到C棒上,规定可利用中间的一根B棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。

僧侣们搬得汗流满面,可惜当n很大时这辈子恐怕就很搬完了。

聪明的你还有计算机帮你完成,你能写一个程序帮助僧侣们完成这辈子的夙愿吗?

Input

​ 输入金片的个数n。这里的n<=10。

Output

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

Sample Input

2

Sample Output

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

Hint

可以用递归算法实现。

Reference Code

#include<stdio.h>
void move(int m,char a,char b,char c)
{
    if (m == 1)
    {
        printf("Move disk %d from %c to %c\n",m,a,c);
    }
    else
    {
        move(m-1,a,c,b);
        printf("Move disk %d from %c to %c\n",m,a,c);
        move(m-1,b,a,c);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    move(n,'A','B','C');
    return 0;
}

青蛙过河

“Too young, too simple, sometimes naive”,你们啊,naive!

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 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 片荷叶的情况下,最多能跳过多少只青蛙?

Input

​ 输入数据有多组,每组占一行,每行包含2个数s(s是小溪中的石柱数目)、y(y是小溪中的荷叶数目)。(0 <= s <= 10,0 <= y <= 10),输入文件直到EOF为止!

Output

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

Sample Input

0 2
1 2

Sample Output

3
6

Reference Code

#include<stdio.h>

int naive(int s,int y)
{
    int bignews;
    if (s == 0)
    {
        bignews = y + 1;
    }
    else
    {
        bignews = 2*naive(s-1,y);
    }
    return bignews;
}

int main()
{
    int s,y,nothingtosay;
    while(~scanf("%d %d",&s,&y))
    {
        nothingtosay = naive(s,y);
        printf("%d\n",nothingtosay);
    }
    return 0;
}

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定N(N≤10^5)个整数,要求用快速排序对数据进行升序排列,注意不得使用STL。

Input

​ 连续输入多组数据,每组输入数据第一行给出正整数N(≤10^5),随后给出N个整数,数字间以空格分隔。

Output

​ 输出排序后的结果,数字间以一个空格间隔,行末不得有多余空格。

Sample Input

8
49 38 65 97 76 13 27 49

Sample Output

13 27 38 49 49 65 76 97

Reference Code

#include<stdio.h>

void qsort(int a[],int l,int r)
{
    int x=a[l],i=l,j=r;
    if (l>=r) return;
    while (i<j)
    {
        while (i<j&&a[j]>=x) j--;
        a[i]=a[j];
        while (i<j&&a[i]<=x) i++;
        a[j]=a[i];
    }
    a[i]=x;
    qsort(a,l,i-1);
    qsort(a,i+1,r);
}

int main()
{
    int n,i;
    while(~scanf("%d",&n))
    {
        int a[100001];
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        qsort(a,0,n-1);
        for (i=0;i<n;i++)
        {
            if (i==n-1) printf("%d\n",a[i]);
            else printf("%d ",a[i]);
        }
    }
    return 0;
}

第X大的数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

X最近爱上了区间查询问题,给出N (N <= 100000) 个数,然后进行M (M <= 50) 次询问,每次询问时,输入一个数X (1 <= X <= N),输出N个数中第X大的数。

Input

多组输入。

每组首先输入一个整数N,代表有N个数,下面一行包含N个整数,用空格隔开。然后为一个整数M,代表有M次询问,下面的M行,每行一个整数X。

Output

输出N个数中第X大的数。

Sample Input

4
1 2 2 3
4
1
2
3
4

Sample Output

3
2
2
1

Reference Code

#include<stdio.h>

int find(int a[],int l,int r,int x)
{
    int i=l,j=r,t=a[l];
    while (i<j)
    {
        while (i<j&&a[j]<=t) j--;
        a[i]=a[j];
        while (i<j&&a[i]>=t) i++;
        a[j]=a[i];
    }
    a[i]=t;
    if (i==x)
    {
        return a[i];
    }
    else if (i<x)
    {
        return find(a,i+1,r,x);
    }
    else
    {
        return find(a,l,i-1,x);
    }
}

int main()
{
    int n,m,x,i,ans;
    while (~scanf("%d",&n))
    {
        int a[100001];
        for (i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        scanf("%d",&m);
        for (i=1;i<=m;i++)
        {
            scanf("%d",&x);
            ans=find(a,1,n,x);
            printf("%d\n",ans);
        }
    }
    return 0;
}

M--二分查找

Time Limit: 600 ms Memory Limit: 65536 KiB

Problem Description

给出含有n个数的升序序列,保证序列中的数两两不相等,这n个数编号从1 到n。

然后给出q次询问,每次询问给出一个数x,若x存在于此序列中,则输出其编号,否则输出-1。

Input

单组输入。首先输入一个整数n(1 <= n && n <= 3000000),接下的一行包含n个数。

再接下来的一行包含一个正整数q(1 <= q && q <= 10000),表示有q次询问。

再接下来的q行,每行包含一个正整数x。

Output

对于每次询问,输出一个整数代表答案。

Sample Input

5
1 3 5 7 9
3
1
5
8

Sample Output

1
3
-1

Reference Code

#include<stdio.h>

int a[3123456];

int find(int a[],int left,int right,int x)
{
    if (left>right) return -1;
    int mid=(left+right)/2;
    if (a[mid]>x) return find(a,left,mid-1,x);
    else if (a[mid]<x) return find(a,mid+1,right,x);
    else return mid;
}

int main()
{
    int n,q,i,x,ans;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&q);
    for (i=0;i<q;i++)
    {
        scanf("%d",&x);
        ans=find(a,1,n,x);
        printf("%d\n",ans);
    }
    return 0;
}

全排列问题

Time Limit: 10000 ms Memory Limit: 65536 KiB

Problem Description

从n个不同元素任取m(m<=n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列,当m=n时所有的排列情况叫全排列。现输入n个递增的数,请你输出这n个数的全排列。全排列输出顺序如样例所示。

Input

多组输入。

首先输入一个数据组数T(1<=T<=100)

接下来是T组数据。

每组数据有两行。

第一行先输入一个整数n(1<=n<=10)。

接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000)。

Output

对于每组数据,每一种排列占一行,各元素间用逗号隔开。

Sample Input

1
3
1 2 3

Sample Output

1,2,3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2

Hint

注意题目数据及题面有更新。

Reference Code

#include<stdio.h>

void rank(int a[],int left,int right)
{
    int i,t;
    if (left==right)
    {
        for (i=1;i<right;i++)
        {
            printf("%d,",a[i]);
        }
        printf("%d\n",a[right]);
    }
    else
    {
        for (i=left;i<=right;i++)
        {
            t=a[left],a[left]=a[i],a[i]=t;
            rank(a,left+1,right);
            t=a[left],a[left]=a[i],a[i]=t;
        }
    }
}

int main()
{
    int t,n,a[90002],i;
    while (~scanf("%d",&t))
    {
        while (t--)
        {
            scanf("%d",&n);
            for (i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            rank(a,1,n);
        }
    }
    return 0;
}
Tags:none
上一篇
下一篇