CUMTOJ数据结构实验内容1-2

数据结构 C++ 数据结构
发布时间 :
阅读 :
  1. 问题 A: 判断三角形形状
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 代码
  2. 问题 B: 笨鸟先飞
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 代码
  3. 问题 C: 火车出站
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 代码
  4. 问题 D: 最少的交换
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 代码
  5. 问题 E: 欧几里得游戏
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 代码
  6. 问题 F: 取石子游戏
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 代码
  7. 问题 G: 奥运排序问题
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 提示
    7. 代码
  8. 问题 H: 字符串的查找删除
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 提示
    7. 代码
  9. 问题 I: 后缀子串排序
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 代码
  10. 问题 K: 为什么1024是程序员节
    1. 题目描述
    2. 输入
    3. 输出
    4. 样例输入
    5. 样例输出
    6. 代码

问题 A: 判断三角形形状

题目描述

给你三角形的三条边，你能告诉我它是哪种三角形吗？
如果是直角三角形，请输出“good”。如果是等腰三角形，请输出“perfect”。否则，请输出“just a triangle”。
题目保证输入数据合法。

输入

输入的第一行为一个整数t，表示测试样例的数量。
每组样例包含了三个整数a,b,c，代表了三角形的三条边的长度。（0 < a,b,c < 300）

输出

对于每组样例，输出结果，每组结果占一行。

样例输入

4
3 4 5
2 2 3
1 4 4
4 6 3

样例输出

good
perfect
perfect
just a triangle

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if(((a * a) == (b * b + c * c)) || ((b * b) == (a * a + c * c)) || ((c * c) == (a * a + b * b)))
        {
            cout << "good" << endl;
        }
        else if(a == b || a == c || c == b)
        {
            cout << "perfect" << endl;
        }
        else
            cout << "just a triangle" << endl;
    }
    return 0;
}

问题 B: 笨鸟先飞

题目描述

多多是一只小菜鸟，都说笨鸟先飞，多多也想来个菜鸟先飞。于是它从0点出发，一开始的飞行速度为1m/s，每过一个单位时间多多的飞行速度比上一个单位时间的飞行速度快2m/s，问n（0 < n <10^5）个单位时间之后多多飞了多远?

输入

先输入一个整数T表示有几组数据。每组数据输入一个n，表示多多飞行的时间。

输出

输出多多飞行了多远，因为数字很大，所以对10000取模。

样例输入

2
1
2

样例输出

1
4

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
int main()
{
    long long t, n, a = 0, i;
    cin >> t;
    while (cin >> n)
    {
        int sum = 0, d = 1, j;
        for (i = 1; i <= n; i++)
        {
            sum = (sum + d) % 10000;
            d ++;
            d ++;
            if (i == n)
            {
                cout << sum << endl;
                break;
            }
        }
        a ++;
        if (a == t)
            break;
    }
    return 0;
}

问题 C: 火车出站

题目描述

铁路进行列车调度时，常把站台设计成栈式结构的站台，试问：
设有编号为1到n的n辆列车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？

输入

输入包含多组测试数据。每组为一个正整数n（1<=n<=20），表示有n辆列车。

输出

输出可能的出栈序列有多少种。

样例输入

4
3

样例输出

14
5

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main()
{
    int n;
    while(cin >> n)
    {
        long long ans = 1;
        for(int i = 1; i <= n; i++)
            ans = ans * (n + i) / i;
        cout << ans / (n + 1) << endl;
    }
    return 0;
}

问题 D: 最少的交换

题目描述

输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。

输入

输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。

输出

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。

样例输入

1
2
2
8 15
4
21 10 5 39

样例输出

2
2
2
8 15
8 15
15 8
21 10 5 39
5 10 21 39
5 10 39 21

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 1000001;
int N;
long a[MAX], b[MAX];
long cnt;
int main()
{
    void MergeSort(long a[], int Start, int End);
    void Merge(long a[], int Start, int Mid, int End);
    while(cin >> N && N)
    {
        cnt = 0;
        for(int i = 0; i < N; i++)
        {
            scanf("%lld", a + i);
        }
        MergeSort(a, 0, N - 1);
        cout << cnt << endl;
    }
    return 0;
}
void Merge(long a[], int Start, int Mid, int End)
{
    int i = Start, j = Mid + 1, k = Start;
    while(i <= Mid && j <= End)
    {
        if(a[i] <= a[j])
        {
            b[k++] = a[i++];
        }
        else
        {
            cnt += j - k;
            b[k++] = a[j++];
        }
    }
    while(i <= Mid)
    {
        b[k++] = a[i++];
    }
    while(j <= End)
    {
        b[k++] = a[j++];
    }
    for(i = Start; i <= End ; i++)
    {
        a[i] = b[i];
    }
}
void MergeSort(long a[], int Start, int End)
{
    if(Start < End)
    {
        int Mid = (Start + End) / 2;
        MergeSort(a, Start, Mid);
        MergeSort(a, Mid + 1, End);
        Merge(a, Start, Mid, End);
    }
}

问题 E: 欧几里得游戏

题目描述

小明和小红在玩欧几里得游戏。他们从两个自然数开始，第一个玩家小明，从两个数的较大数中减去较小数的尽可能大的正整数倍，只要差为非负即可。然后，第二个玩家小红，对得到的两个数进行同样的操作，然后又是小明。就这样轮流进行游戏，直至某个玩家将较大数减去较小数的某个倍数之后差为0为止，此时游戏结束，该玩家就是胜利者。

输入

输入包含多组测试数据。每组输入两个正整数，表示游戏一开始的两个数，游戏总是小明先开始。
当输入两个0的时候，输入结束。

输出

对于每组输入，输出最后的胜者，我们认为他们两个都是顶尖高手，每一步游戏都做出了最佳的选择。
具体输出格式见输出样例。

样例输入

34 12
15 24
0 0

样例输出

xiaoming wins
xiaohong wins

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
int main() {
    int a, b, k, t;
    while(cin >> a, cin >> b, a != 0 || b != 0)
    {
        k = 1;
        if(a == b)
        {
            cout << "xiaoming wins" << endl;    
        }
        else
        {
            while(a != b)
            {
                if(a < b)
                {
                    t = a;
                    a = b;
                    b = t;
                }
                k++;
                if(a / b != 1)
                {
                    break;
                } 
                a = a % b;
            }
            if(k % 2 == 1)
                cout << "xiaohong wins" << endl;
            else
                cout << "xiaoming wins" << endl;
        }
    }
    return 0;
}

问题 F: 取石子游戏

题目描述

一天小明和小红在玩取石子游戏，游戏规则是这样的：
（1）本游戏是一个二人游戏；
（2）有一堆石子，共有n个；
（3）两人轮流进行；
（4）每走一步可以取走1 ~ m个石子；
（5）最先取光石子的一方为胜。
如果游戏的双方使用的都是最优策略，请输出哪个人能赢。

输入

输入的第一行是一个正整数C（C<=100），表示有C组测试数据。
每组输入两个整数n和m（1<=n,m<=1000），n和m的含义见题目描述。

输出

对于每组输入，如果先走的人能赢，请输出“first”，否则请输出“second”。

样例输入

2
23 2
4 3

样例输出

first
second

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main()
{
    int c, n, m;
    cin >> c;
    while(c--)
    {
        cin >> n >> m;
        if(n % (m + 1))
            cout << "first" << endl;
        else
            cout<<"second"<<endl;
    }
   return 0;
}

问题 G: 奥运排序问题

题目描述

按要求，给国家进行排名。

输入

有多组数据。
第一行给出国家数N，要求排名的国家数M，国家号从0到N-1。
第二行开始的N行给定国家或地区的奥运金牌数，奖牌数，人口数（百万）。
接下来一行给出M个国家号。

输出

排序有4种方式: 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例
对每个国家给出最佳排名排名方式 和 最终排名
格式为: 排名:排名方式
如果有相同的最终排名，则输出排名方式最小的那种排名，对于排名方式，金牌总数 < 奖牌总数 < 金牌人口比例 < 奖牌人口比例
如果有并列排名的情况，即如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4.
每组数据后加一个空行。

样例输入

4 4
4 8 1
6 6 2
4 8 2
2 12 4
0 1 2 3
4 2
8 10 1
8 11 2
8 12 3
8 13 4
0 3

样例输出

1:3
1:1
2:1
1:2

1:1
1:1

提示

本题需要解决的是奥运会中各国家最有利的排名方式以及名次。只要进行五次排序即可。首先读入各国家信息，写好国家编号，计算和存储排名所需要的数据。然后按四种排名方式分别对需要排名的国家进行排名，并记录名次。最后使用国家编号对国家进行排名。这样就可以输出结果了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <algorithm>
using namespace std;
const int size = 1005;
class Country
{
    public:
        double g, j, p;
        int id;
} c[size];

bool cmpg(Country x, Country y)
{
    return x.g > y.g;
}
bool cmpj(Country x, Country y)
{
    return x.j > y.j;
}
bool cmpgp(Country x, Country y)
{
    return x.g / x.p > y.g / y.p;
}
bool cmpjp(Country x, Country y)
{
    return x.j / x.p > y.j / y.p;
}

int main()
{
    int n, m, i, t, j;
    int need[size];
    int rank[size][5];
    while(cin >> n >> m)
    {
        for(i = 0; i < n; i++)
        {
            cin >> c[i].g >> c[i].j >> c[i].p;
            c[i].id = i;
        }
        for(i = 0; i < m; i++)
        {
            cin >> need[i];
        }
        sort(c, c + n, cmpg);
        rank[c[0].id][1] = 1;
        for(i = 1; i < n; i++)
        {
            if(c[i].g == c[i - 1].g)
                rank[c[i].id][1] = rank[c[i - 1].id][1];
            else
                rank[c[i].id][1] = i + 1;
        }
        
        sort(c, c + n, cmpj);
        rank[c[0].id][2] = 1;
        for(i = 1; i < n; i++)
        {
            if(c[i].j == c[i - 1].j)
                rank[c[i].id][2] = rank[c[i - 1].id][2];
            else
                rank[c[i].id][2] = i + 1;
        }
        
        sort(c, c + n, cmpgp);
        rank[c[0].id][3] = 1;
        for(i = 1; i < n; i++)
        {
            if(c[i].g / c[i].p == c[i - 1].g / c[i - 1].p)
                rank[c[i].id][3] = rank[c[i - 1].id][3];
            else
                rank[c[i].id][3] = i + 1;
        }
        
        sort(c, c + n, cmpjp);
        rank[c[0].id][4] = 1;
        for(i = 1; i < n; i++)
        {
            if(c[i].j / c[i].p == c[i - 1].j / c[i - 1].p)
                rank[c[i].id][4] = rank[c[i - 1].id][4];
            else
                rank[c[i].id][4] = i + 1;
        }
        
        for(i = 0; i < m; i++)
        {
            int min = n + 1, type = 5;
            for(t = 1; t <= 4; t++)
            {
                int tmp = 1;
                for(j = 0; j < m; j++)
                {
                    if(i != j)
                    {
                        if(rank[need[i]][t] > rank[need[j]][t])
                        {
                            tmp++;
                        }
                    }
                }
                if(min > tmp)
                {
                    min = tmp;
                    type = t;
                }
            }
            cout << min << ":" << type << endl;
        }
        cout << endl;
    }
    return 0;
}

问题 H: 字符串的查找删除

题目描述

给定一个短字符串（不含空格），再给定若干字符串，在这些字符串中删除所含有的短字符串。

输入

输入只有1组数据。
输入一个短字符串（不含空格），再输入若干字符串直到文件结束为止。

输出

删除输入的短字符串(不区分大小写)并去掉空格,输出。

样例输入

in
#include
int main()
{

printf(“ Hi “);
}

样例输出

#clude
tma()
{

prtf(“Hi”);
}

提示

注:将字符串中的In、IN、iN、in删除。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <string.h>
using namespace std;
int main()
{
    int k = 0;
    char a[10000] , ans[10000];
    char temp[10000];
    gets(temp);
    for(int i=0; i < strlen(temp); i++)
        if(temp[i] >= 'A' && temp[i] <= 'Z')
            temp[i] += 32;
    int len = strlen(temp);
    while(scanf("%c" , &a[k]) != EOF)
    {
        ans[k] = a[k];
        if(a[k] >= 'A' && a[k] <= 'Z')
            a[k] += 32;
        if(a[k] == temp[len-1])
        {
            int i = 0 , t = 0;
            for(i = k - len + 1; i <= k; i++)
            {
                if(temp[t++] != a[i])
                    break;
            }
            if(i == k+1)
                k = k - len + 1;
            else
                k++;
        }
        else
            k++;
    }
    for(int i = 0; i < k; i++)
    {
        if(ans[i] != ' ')
            cout << ans[i];
    }
    cout << endl;
    return 0;
}

问题 I: 后缀子串排序

题目描述

对于一个字符串，将其后缀子串进行排序，例如grain
其子串有：
grain
rain
ain
in
n
然后对各子串按字典顺序排序，即：
ain,grain,in,n,rain

输入

每个案例为一行字符串。

输出

将子串排序输出

样例输入

grain
banana

样例输出

ain
grain
in
n
rain
a
ana
anana
banana
na
nana

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<string> v;
int main()
{
    string str;
    int i;
    while(~scanf("s", str))
    {
        v.clear();
        for(i = 0; i < str.size(); i++)
        {
            string temp = str.substr(i, str.size() - i);
            v.push_back(temp);
        }
        sort(v.begin(), v.end());
        for(i = 0; i < str.length(); i++)
        {
            cout << v[i] << endl;
        }
    }
    return 0;
}

问题 K: 为什么1024是程序员节

题目描述

小雏鸟正在看剧。突然被插播的广告吓了一跳。
只见广告上说 1024你懂的
小雏鸟不懂， 问身边的大白。大白说，这个1024是2的10次方，程序员把10月24日作为程序猿日。
现在给你一个整数N，让你求2的N次方有多大。

输入

一个整数N，N<30

输出

一个整数，2的N次方的结果

样例输入

10

样例输出

1024

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main()
{
    long long num, tmp, result = 1;
    cin >> num;
    for(tmp = 0; tmp < num; tmp++)
    {
        result *= 2;
    }
    cout << result << endl;
    return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 xingshuaikun@163.com。

赏

©2016-2020 Yelog

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏