【GESP】C++四级真题 luogu-B4068 [GESP202412 四级] Recamán

GESP C++四级2024年12月真题。本题主要考查排序和递推思想的应用。排序使用内置函数sort难度不大，整体难度⭐⭐★☆☆。本题在洛谷评定为普及-。

luogu-B4068 [GESP202412 四级] Recamán

题目要求

题目描述

小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的：

• 数列的第一项 $a_1$ 是 $1$；
• 如果 $a_{k-1}-k$ 是正整数并且没有在数列中出现过，那么数列的第 $k$ 项 $a_k$ 为 $a_{k-1}-k$，否则为 $a_{k-1}+k$。

小杨想知道 Recamán 数列的前 $n$ 项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。

输入格式

第一行，一个正整数 $n$。

输出格式

一行，$n$ 个空格分隔的整数，表示 Recamán 数列的前 $n$ 项从小到大排序后的结果。

输入输出样例 #1

输入 #1

5

输出 #1

1 2 3 6 7

输入输出样例 #2

输入 #2

8

输出 #2

1 2 3 6 7 12 13 20

说明/提示

样例解释

对于样例 1，$n=5$：

• $a_1=1$；
• $a_1-2=-1$，不是正整数，因此 $a_2=a_1+2=3$；
• $a_2-3=0$，不是正整数，因此 $a_3=a_2+3=6$；
• $a_3-4=2$，是正整数，且没有在数列中出现过，因此 $a_4=a_3-4=2$；
• $a_4-5=-3$，不是正整数，因此 $a_5=a_4+5=7$。

$a_1,a_2,a_3,a_4,a_5$ 从小到大排序的结果为 $1,2,3,6,7$。

数据范围

对于所有数据点，保证 $1\le n\le 3\, 000$。

---

题目分析

本题的解题思路如下：

1. 题目要求

生成 Recamán 数列并对前 n 项进行排序。Recamán 数列的生成规则是：

• 第一项 $a_1 = 1$
• 对于第 k 项，如果 $a_{k-1}-k$ 是正整数且未在数列中出现过，则 $a_k = a_{k-1}-k$
• 否则 $a_k = a_{k-1}+k$

2. 解题关键点

• 需要判断一个数是否已经在数列中出现过
• 数列生成过程中需要记录已有的数字
• 最后需要对生成的数列进行排序
• 数据范围 $n \leq 3000$，可以使用数组存储

3. 具体实现步骤

• 读入数列长度 n
• 初始化第一项为 1
• 循环生成后续数字：
  • 计算 $a_{k-1}-k$
  • 判断是否为正数且未出现过
  • 根据判断结果确定第 $k$ 项的值
• 对整个数列排序并输出

4. 时间复杂度分析

• 生成数列时每次需要遍历已有数字判断是否存在，复杂度 $O(n^2)$
• 最后排序的复杂度为 $O(n\log n)$
• 总体时间复杂度为 $O(n^2)$
• 由于 $n \leq 3000$，此复杂度可以接受

5. 注意事项

• 数组下标从 1 开始更方便处理
• 判断数字是否存在时需要遍历到当前位置
• 输出数字间需要用空格分隔
• 最后一个数字后也需要输出空格

这道题目主要考察对数组和排序的应用，排序使用 C++ 的 sort 函数可以方便地实现最后的排序操作。

关于sort的用法，前面文章【GESP】C++四级真题 luogu-B3851 [GESP202306 四级] 图像压缩已经介绍过。

---

示例代码

#include <iostream>
#include <algorithm>

// 定义数组存储 Recamán 数列
int ary[3005];

/**
 * 判断一个数字是否已经在数列中存在
 * @param num 要判断的数字
 * @param n 当前数列长度
 * @return true 表示数字已存在，false 表示数字不存在
 */
bool is_exist(int num, int n) {
    for (int i = 1; i <= n; i++) {
        if (ary[i] == num) {
            return true;
        }
    }
    return false;
}

int main() {
    // 读入数列长度
    int n;
    std::cin >>n;
    
    // 初始化第一项为1
    ary[1] = 1;
    
    // 生成 Recamán 数列
    for (int i = 2; i <= n; i++) {
        // 计算 a[k-1]-k
        int tmp_num = ary[i - 1] - i;
        
        // 如果 tmp_num 为正且未在数列中出现过，则取 tmp_num
        // 否则取 a[k-1]+k
        if (tmp_num > 0 && !is_exist(tmp_num, i)) {
            ary[i] = tmp_num;
        } else {
            ary[i] = ary[i - 1] + i;
        }
    }
    
    // 对前n项进行升序排序
    std::sort(ary + 1, ary + n + 1);
    
    // 输出排序后的结果
    for (int i = 1; i <= n; i++) {
        std::cout << ary[i] << " ";
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号