【前排提醒】
这3道编程题都是送分题，难度类似23年，都很低，所有人都应该能够迅速写出代码。20、22年难度稍大一些，不过难度也没超过算法基础课，不会写代码也尽量写上算法思想，能写多少算多少，判卷尺度较松。

1. 马鞍点

原题链接

给定一个 n×m 的整数矩阵，行的编号为 1∼n，列的编号为 1∼m，求矩阵中的所有鞍点。

鞍点，即该位置上的元素在该行上最大，在该列上最小。

有可能有多个鞍点，也可能没有鞍点。

输入格式
第一行包含两个整数 n,m。

接下来 n 行，每行包含 m 个整数。

输出格式
输出所有鞍点的坐标和值。

输出优先级，整体从上到下，同行从左到右。

如果不存在鞍点，则输出 NO。

数据范围
1≤n,m<10

矩阵元素取值范围 [1,9]。

输入样例：

3 4
1 2 3 4
1 2 3 4
1 2 3 4

输出样例：

1 4 4
2 4 4
3 4 4

#include <iostream>

using namespace std;

const int N = 15;
int g[N][N], n, m;

// 判断是否为鞍点
bool is_saddle_point(int a, int b)
{
    int x = a, y = b;
    for (int i = 1; i <= n; i++)
        if (g[i][b] < g[a][b]) // 在该列不是最小
            return false;
    for (int j = 1; j <= m; j++)
        if (g[a][j] > g[a][b]) // 在该行不是最大
            return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);

    bool flag = false;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (is_saddle_point(i, j))
            {
                printf("%d %d %d\n", i, j, g[i][j]);
                flag = true;
            }

    if (!flag)
        puts("NO");

    return 0;
}

该程序通过遍历矩阵，对于每个元素检查是否为鞍点，如果是则输出鞍点的坐标和值，否则输出”NO”。

二、完美数

问题描述

完美数的定义——如果一个大于$1$ 的正整数的所有因子之和等于它的本身，则称这个数是完美数，比如 $6$，$28$ 都是完数：$6=1+2+3$；$28=1+2+4+7+14$。同时完全数也满足$2^{p-1}$·$(2^p-1)$的形式，其中$p$为素数，例如：6=$2^1$·$(2^2-1)$

输入说明

给定一个正整数$n$

输出说明

输出两行，如果 $n$ 是完美数，返回 $true$，否则返回 $false$，并在第二行按照从小到大的顺输出 $10000$ 内的完全数（以空格分隔）。

输入：

6

输出：

true
6 28 496 8128

算法思想：
1. is_perfect: 判断一个数是否为完美数，即因子之和等于自身。
2. is_prime: 判断一个数是否为质数。
3. 在 main 函数中，根据输入的数判断是否为完美数，并输出结果。
4. 输出 1 到 10000 范围内的梅森素数，梅森素数的形式为 $2^{p-1} * (2^p - 1)$，其中 p 是素数。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

// 判断一个数是否为完美数
bool is_perfect(int n)
{
    int res = 0;
    for (int i = 1; i < n; i++)
        if (n % i == 0)
            res += i;
    return res == n;
}

// 判断一个数是否为质数
bool is_prime(int x)
{
    if (x < 2)
        return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0)
            return false;
    return true;
}

int main()
{
    int n;
    cin >> n;

    // 输出判断结果
    if (is_perfect(n))
        puts("true");
    else
        puts("false");


    for (int i = 1; i <= 1000; i++)
        if (is_prime(i))
        {
            int res = pow(2, i - 1) * (pow(2, i) - 1);
            // 输出 1 到 10000 范围内的梅森素数
            if (res > 10000) break;
            cout << res << ' ';
        }

    return 0;
}

三、机器人的复制

问题描述

虚拟机器人复制，第一天生产一个成熟机器人，成熟机器人每天可生产一个新机器人，新机器人 $3$ 天可变成成熟机器人，机器人个数和天数的关系如下：

输入描述

第 $n$ 天（$n<=100$ 的自然数）

输出描述

第 $n$ 天时机器人总数

算法思想：

1. 使用数组 f 存储每一天的机器人数量。
2. 初始化前四天的机器人数量。对于前四天（1 到 3 天），机器人数量等于天数。
3. 利用递推关系 $f[i] = f[i - 3] + f[i - 1]$ 计算第 n 天的机器人总数。对于第四天及以后的每一天，机器人数量等于前三天和前一天机器人数量之和，因为新的机器人在第四天之后的三天内变成成熟机器人。
4. 输出结果。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int n, f[N];

int main()
{
    // 输入天数
    cin >> n;

    // 初始化前四天的机器人数量
    for (int i = 0; i <= 3; i++)
        f[i] = i;

    // 计算第 n 天的机器人总数
    for (int i = 4; i <= n; i++)
        f[i] = f[i - 3] + f[i - 1];

    // 输出结果
    cout << f[n] << endl;

    return 0;
}