杭电 OJ2010-2019

写在前面

本文记录了刷杭电 OJ2010-2019 的过程和一些想法，代码仅供参考！

2010 水仙花数

Problem Description

春天是鲜花的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的：
“水仙花数” 是指一个三位数，它的各位数字的立方和等于其本身，比如：153=1^3+5^3+3^3。
现在要求输出所有在 m 和 n 范围内的水仙花数。

Input

输入数据有多组，每组占一行，包括两个整数 m 和 n（100<=m<=n<=999）。

Output

对于每个测试实例，要求输出所有在给定范围内的水仙花数，就是说，输出的水仙花数必须大于等于 m, 并且小于等于 n，如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开；如果给定的范围内不存在水仙花数，则输出 no;
每个测试实例的输出占一行。

Sample Input

100 120
300 380

Sample Output

no
370 371

解题思路

在 m 到 n 的范围内遍历，分别提出百位数，十位数，个位数，并判断各位数字的立方和等于其本身
当然也可以找出 100-999 中所有的水仙花数，之后判断输出即可

参考源码

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() {
    int m, n;
    int a, b, c, count;
    while (cin >> m >> n) {
        count = 0;
        for (int i = m; i <= n; i++) {
            a = i / 100;       //百位
            b = i % 100 / 10;  //十位
            c = i % 10;        //个位
            if (i == a * a * a + b * b * b + c * c * c) {
                count++;
                if (count == 1)  //注意格式
                    cout << i;
                else
                    cout << " " << i;
            }
        }
        if (count == 0)
            cout << "no" << endl;
        else
            cout << endl;
    }
    return 0;
}

2011 多项式求和

Problem Description

多项式的描述如下：
1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + …
现在请你求出该多项式的前 n 项的和。

Input

输入数据由 2 行组成，首先是一个正整数 m（m<100），表示测试实例的个数，第二行包含 m 个正整数，对于每一个整数 (不妨设为 n,n<1000），求该多项式的前 n 项的和。

Output

对于每个测试实例 n，要求输出多项式前 n 项的和。每个测试实例的输出占一行，结果保留 2 位小数。

Sample Input

2
1 2

Sample Output

1.00
0.50

解题思路

简单题，通过 flag 控制加减，for 循环进行前 n 项求和
另外也可以通过迭代

f(n)={0，n=0f(n−1)+1/n，n为奇数f(n−1)−1/n，n为偶数\text{f}\left( \text{n} \right) =\left\{ \begin{array}{c} \text{0，n}=0\\ \text{f}\left( \text{n}-1 \right) +\text{1/n，n为奇数}\\ \text{f}\left( \text{n}-1 \right) -\text{1/n，n为偶数}\\ \end{array} \right.

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main() {
    int m, n, flag;
    double ans;
    cin >> m;
    while (m--) {
        cin >> n;
        ans = 0;
        flag = 1;
        for (int i = 1; i <= n; i++) {
            ans += flag * 1.0 / i;//计算前 n 项的和
            flag *= -1;  //控制加减
        }
        printf("%.2f\n", ans);
    }
    return 0;
}

2012 素数判定

Problem Description

对于表达式 n^2+n+41，当 n 在（x,y）范围内取整数值时（包括 x,y）(-39<=x<y<=50)，判定该表达式的值是否都为素数。

Input

输入数据有多组，每组占一行，由两个整数 x，y 组成，当 x=0,y=0 时，表示输入结束，该行不做处理。

Output

对于每个给定范围内的取值，如果表达式的值都为素数，则输出 “OK”, 否则请输出 “Sorry”, 每组输出占一行。

Sample Input

0 1
0 0

Sample Output

OK

解题思路

根据输入范围计算表达式的所有值，判断是否为素数
或者也可以把范围里的全部计算出来，数字不大也不多，直接打表

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cmath>
#include <iostream>
using namespace std;
bool isPrime(int a) {
    if (a == 2 || a == 3) return true;
    for (int i = 2; i <= sqrt(a); i++) {
        if (a % i == 0) return false;
    }
    return true;
}
int main() {
    int x, y;
    while (cin >> x >> y && (x || y)) {
        int flag = 1;
        for (int i = x; i <= y; i++) {
            if (!isPrime(i * i + i + 41)) flag = 0;
        }
        if (flag)
            cout << "OK" << endl;
        else
            cout << "Sorry" << endl;
    }
    return 0;
}

2013 蟠桃记

Problem Description

喜欢西游记的同学肯定都知道悟空偷吃蟠桃的故事，你们一定都觉得这猴子太闹腾了，其实你们是有所不知：悟空是在研究一个数学问题！
什么问题？他研究的问题是蟠桃一共有多少个！不过，到最后，他还是没能解决这个难题，呵呵 ^-^
当时的情况是这样的：
第一天悟空吃掉桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第 n 天准备吃的时候只剩下一个桃子。聪明的你，请帮悟空算一下，他第一天开始吃的时候桃子一共有多少个呢？

Input

输入数据有多组，每组占一行，包含一个正整数 n（1<n<30），表示只剩下一个桃子的时候是在第 n 天发生的。

Output

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

Sample Input

2
4

Sample Output

4
22

解题思路

简单计算题，总数加 1 再乘 2，循环 n-1 次

参考源码

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

2014 青年歌手大奖赛_评委会打分

Problem Description

青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。

Input

输入数据有多组，每组占一行，每行的第一个数是 n (2<n<=100)，表示评委的人数，然后是 n 个评委的打分。

Output

对于每组输入数据，输出选手的得分，结果保留 2 位小数，每组输出占一行。

Sample Input

3 99 98 97
4 100 99 98 97

Sample Output

98.00
98.50

解题思路

找到最高分和最低分，计算平均得分，这里我直接用了 sort()，当然也可以遍历一次，寻找 max 和 min

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
    int n, s[100], sum;
    while (cin >> n) {
        sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> s[i];
            sum += s[i];
        }
        sort(s, s + n);
        printf("%.2f\n", 1.0 * (sum - s[0] - s[n - 1]) / (n - 2));
    }
    return 0;
}

2015 偶数求和

Problem Description

有一个长度为 n (n<=100) 的数列，该数列定义为从 2 开始的递增有序偶数，现在要求你按照顺序每 m 个数求出一个平均值，如果最后不足 m 个，则以实际数量求平均值。编程输出该平均值序列。

Input

输入数据有多组，每组占一行，包含两个正整数 n 和 m，n 和 m 的含义如上所述。

Output

对于每组输入数据，输出一个平均值序列，每组输出占一行。

Sample Input

3 2
4 2

Sample Output

3 6
3 7

解题思路

等差数列求和，第一个数是 X 时，下一组的第一个数就是 X + 2 × m
从 X 开始连续 m 个偶数的和就是:

X+(X+2×(m−1))2×m=(X+m−1)×m\frac{\text{X}+\left( \text{X}+2\times \left( \text{m}-1 \right) \right)}{2}\times \text{m}=\left( \text{X}+\text{m}-1 \right) \times \text{m}

所以平均数就是 X + m - 1
若不满 m 个数:

\frac{\text{X}+\left( \text{X}+2\times \left( \text{n%m}-1 \right) \right)}{2}\times \text{n%m}=\left( \text{X}+\text{n%m}-1 \right) \times \text{n%m}

所以平均数就是 X + n % m - 1

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main() {
    int n, m;
    while (cin >> n >> m) {
        int count = 0, a = 2;
        for (int i = 0; i < n / m; i++) {  //每m个数求平均值
            count++;
            if (count == 1)  //输出格式
                cout << a + m - 1;
            else
                cout << " " << a + m - 1;
            a += 2 * m;  //更新下一组的第一个数
        }
        if (n % m == 0)  //没有剩下的数
            cout << endl;
        else
            cout << " " << a + n % m - 1 << endl;  //不满m个数求平均值
    }
    return 0;
}

2016 数据的交换输出

Problem Description

输入 n (n<100) 个数，找出其中最小的数，将它与最前面的数交换后输出这些数。

Input

输入数据有多组，每组占一行，每行的开始是一个整数 n，表示这个测试实例的数值的个数，跟着就是 n 个整数。n=0 表示输入的结束，不做处理。

Output

对于每组输入数据，输出交换后的数列，每组输出占一行。

Sample Input

4 2 1 3 4
5 5 4 3 2 1
0

Sample Output

1 2 3 4
1 4 3 2 5

解题思路

遍历数组找最小数，与第一个数交换

参考源码

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 <algorithm>
#include <iostream>
#define INF 0x3fffffff
using namespace std;
int main() {
    int n, num[100], min, pos;
    while (cin >> n && n) {  // n为0时退出
        min = INF;
        for (int i = 0; i < n; i++) {
            cin >> num[i];
            if (min > num[i]) {
                pos = i;  //记录位置
                min = num[i];
            }
        }
        swap(num[0], num[pos]);  //交换
        for (int i = 0; i < n; i++) {
            if (i == 0)
                cout << num[i];
            else
                cout << " " << num[i];
        }
        cout << endl;
    }
    return 0;
}

2017 字符串统计

Problem Description

对于给定的一个字符串，统计其中数字字符出现的次数。

Input

输入数据有多行，第一行是一个整数 n，表示测试实例的个数，后面跟着 n 行，每行包括一个由字母和数字组成的字符串。

Output

对于每个测试实例，输出该串中数值的个数，每个输出占一行。

Sample Input

2
asdfasdf123123asdfasdf
asdf111111111asdfasdfasdf

Sample Output

6
9

解题思路

读取字符串，isdigit()判断是否为数字
注：

  • cin 不能读取空格
  • gets() 接收一串字符，可以读取空格
  • getline() 读取一行字符串，通过回车键来确定输入的结尾

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int n;
    string str;
    cin >> n;
    while (n--) {
        cin >> str;
        int count = 0;
        for (int i = 0; i < str.length(); i++)  //遍历字符串
            if (isdigit(str[i])) count++;       //统计数字
        cout << count << endl;
    }
    return 0;
}

2018 母牛的故事

Problem Description

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第 n 年的时候，共有多少头母牛？

Input

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数 n (0<n<55)，n 的含义如题目中描述。
n=0 表示输入数据的结束，不做处理。

Output

对于每个测试实例，输出在第 n 年的时候母牛的数量。
每个输出占一行。

Sample Input

2
4
5
0

Sample Output

2
4
6

解题思路

简单的递推问题
f(n) = f(n-1) + f(n-3) (n > 3)
f(n) = n (n <= 3)

参考源码

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
using namespace std;
int main(){
    int n, i, sum[55] = {1,2,3,4};
    for(i = 4; i < 55; i++)
        sum[i] = sum[i - 1] + sum[i - 3];
    while(cin >> n && n){
        cout << sum[n - 1] << endl;
    }
    return 0;
}

2019 数列有序!

Problem Description

有 n (n<=100) 个整数，已经按照从小到大顺序排列好，现在另外给一个整数 x，请将该数插入到序列中，并使新的序列仍然有序。

Input

输入数据包含多个测试实例，每组数据由两行组成，第一行是 n 和 m，第二行是已经有序的 n 个数的数列。n 和 m 同时为 0 标示输入数据的结束，本行不做处理。

Output

对于每个测试实例，输出插入新的元素后的数列。

Sample Input

3 3
1 2 4
0 0

Sample Output

1 2 3 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
#include <iostream>
using namespace std;
int main() {
    int n, m, num[101];
    while (cin >> n >> m && (n || m)) {
        int pos = 0;
        for (int i = 0; i < n; i++) {
            cin >> num[i];
            if (m > num[i]) pos = i + 1;  //插入位置
        }
        for (int i = n; i > pos; i--) {
            num[i] = num[i - 1];  //从后向前移动元素
        }
        num[pos] = m;  //插入
        for (int i = 0; i < n + 1; i++) {
            if (i == 0)
                cout << num[i];
            else
                cout << " " << num[i];
        }
        cout << endl;
    }
    return 0;
}

相关内容