202412-Recamán(luogu-B4068)

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

输出 #1

1 2 3 6 7

输入输出样例 #2

输入 #2

输出 #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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

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

最后更新于 2025年9月15日

202409-区间排序(luogu-B4041)202412-字符排序(luogu-B4069)