洛谷 B4068 [GESP202412 四级] Recamán：从规则到代码的完整解析

洛谷 B4068 [GESP202412 四级] Recamán 这道题，要求我们生成 Recamán 数列的前 n 项，然后将这些项按从小到大的顺序排序并输出。这道题的核心在于理解 Recamán 数列的生成规则，并用代码准确实现。因为 a 是全局数组，默认初始化为 0。生成第 1 项时，a [0] = 0，正好符合规则（a [1] = 0 + 1 = 1）。理解 Recamán 数列的生成规则

2501_91189146

1557人浏览 · 2025-07-23 16:40:47

2501_91189146 · 2025-07-23 16:40:47 发布

洛谷 B4068 [GESP202412 四级] Recamán：从规则到代码的完整解析

有错提醒改正。。。

恩师：hnjzsyjyj

一、题目介绍

洛谷 B4068 [GESP202412 四级] Recamán 这道题，要求我们生成 Recamán 数列的前 n 项，然后将这些项按从小到大的顺序排序并输出。这道题的核心在于理解 Recamán 数列的生成规则，并用代码准确实现。

二、Recamán 数列是什么？—— 用例子说清楚

Recamán 数列是一种特殊的整数数列，它的生成方式有点像 “走迷宫”，每一步都要根据前一步的位置决定下一步的方向。我们用具体例子来理解：

比如生成前 5 项：

第 1 项：固定是 1（这是数列的起点）
第 2 项：看前一项（1）减 2 的结果。1-2=-1，这个数不大于 0，所以第 2 项是 1+2=3
第 3 项：前一项是 3，3-3=0，不大于 0，所以第 3 项是 3+3=6
第 4 项：前一项是 6，6-4=2，这个数大于 0 且没出现过，所以第 4 项是 2
第 5 项：前一项是 2，2-5=-3，不大于 0，所以第 5 项是 2+5=7

这样就得到数列 [1,3,6,2,7]，排序后是 [1,2,3,6,7]。是不是很简单？

三、题目分析：我们要做什么？

这道题的任务可以拆成三步：

输入一个整数 n（比如 5、10）
按照规则生成 Recamán 数列的前 n 项
把这 n 项从小到大排序后输出

看起来不难，但关键是要把数列的生成规则转化成代码逻辑。这道题考察的是对循环、条件判断和数组运用的掌握，是 GESP 四级中的典型题目。

四、核心规则：Recamán 数列的生成秘诀

Recamán 数列的生成规则用 “说人话” 总结：

第 1 项 a [1] = 1（固定起点）
生成第 i 项（i≥2）时：
- 先算 “前一项减 i”：a [i-1] - i
- 如果这个结果是正数，而且之前没出现过，就用这个结果当第 i 项
- 否则，就用 “前一项加 i” 当第 i 项
每个数只能出现一次（用标记数组记录）

记住这个规则，写代码就像按菜谱做菜一样简单。

五、代码逐行解读：每一句都讲透

我们来一句一句分析代码，看看它是怎么实现上面的规则的。

代码全文

cpp

#include <bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int n,a[N],s[N*4];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        if(a[i-1]-i>0&&!s[a[i-1]-i])a[i]=a[i-1]-i;
        else a[i]=a[i-1]+i;
        s[a[i]]=1;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    return 0;
}

第一部分：头文件和变量

cpp

#include <bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int n,a[N],s[N*4];

#include <bits/stdc++.h>：万能头文件，包含了所有常用库（比如输入输出、排序函数）
using namespace std;：简化代码，不用每次写std::cin之类的
const int N=3e3+5;：定义常量 N=3005，因为题目中 n 最大不超过 3000
变量：
- n：存储输入的数列长度
- a[N]：存储生成的 Recamán 数列（下标 1 到 n）
- s[N*4]：标记数组，记录哪些数已经出现过（防止重复）

第二部分：输入 n

cpp

int main() {
    cin>>n;

int main()：程序入口
cin>>n：从键盘输入 n（比如输入 5，就生成前 5 项）

第三部分：生成数列（核心循环）

cpp

for(int i=1;i<=n;i++){
    if(a[i-1]-i>0&&!s[a[i-1]-i])a[i]=a[i-1]-i;
    else a[i]=a[i-1]+i;
    s[a[i]]=1;
}

这是最关键的部分，我们拆开来理解：

for(int i=1;i<=n;i++)：循环 n 次，生成第 1 到第 n 项
if(a[i-1]-i>0&&!s[a[i-1]-i])：两个条件
- a[i-1]-i>0：前一项减 i 的结果是正数
- !s[a[i-1]-i]：这个结果之前没出现过（s 数组里是 0）
满足条件就执行a[i]=a[i-1]-i，否则执行a[i]=a[i-1]+i
s[a[i]]=1：标记刚生成的数，防止以后重复出现

举个例子（i=4 时）：

前一项 a [3]=6，i=4
算 6-4=2，是正数，且 s [2] 是 0（没出现过）
所以 a [4]=2，然后 s [2]=1（标记为已出现）

第四部分：排序数列

cpp

sort(a+1,a+n+1);

用 sort 函数排序，范围是从 a [1] 到 a [n]（因为数列存在这部分）
排序后数列从小到大排列（比如 [1,3,6,2,7] 变成 [1,2,3,6,7]）

第五部分：输出结果

cpp

for(int i=1;i<=n;i++)cout<<a[i]<<" ";
return 0;
}

循环输出排序后的数列，每个数后加空格
return 0：程序正常结束

六、代码运行全过程：以 n=5 为例

我们一步一步看代码怎么生成数列：

初始状态

a 数组全是 0（全局数组默认值），s 数组全是 0
n=5（输入的数）

生成第 1 项（i=1）

a [0] 是 0（默认值），算 0-1=-1（不满足条件）
所以 a [1]=0+1=1
s [1]=1（标记 1 已出现）
现在 a=[0,1,0,0,0,0]

生成第 2 项（i=2）

a [1]=1，算 1-2=-1（不满足条件）
所以 a [2]=1+2=3
s[3]=1
现在 a=[0,1,3,0,0,0]

生成第 3 项（i=3）

a [2]=3，算 3-3=0（不满足正数条件）
所以 a [3]=3+3=6
s[6]=1
现在 a=[0,1,3,6,0,0]

生成第 4 项（i=4）

a [3]=6，算 6-4=2（正数，且 s [2]=0）
所以 a [4]=2
s[2]=1
现在 a=[0,1,3,6,2,0]

生成第 5 项（i=5）

a [4]=2，算 2-5=-3（不满足条件）
所以 a [5]=2+5=7
s[7]=1
现在 a=[0,1,3,6,2,7]

排序后

调用 sort (a+1,a+6)，数组变成 [0,1,2,3,6,7]

输出

循环输出 a [1] 到 a [5]：1 2 3 6 7

七、为什么代码能跑通？

规则准确实现：严格按照 “前项减 i” 和 “前项加 i” 的条件生成数列
去重机制：用 s 数组标记已出现的数，确保每个数只出现一次
排序正确：用标准库的 sort 函数，保证排序结果正确
数组够用：N=3005 和 s [N*4] 的大小，足够应对 n≤3000 的情况

八、常见问题解答

1. 为什么 s 数组要开 N*4 这么大？

因为数列里的数可能比 n 大很多。比如 n=3000 时，后面的数可能达到几万，N*4=12020 足够用，防止数组越界。

2. a [0] 为什么是 0？

因为 a 是全局数组，默认初始化为 0。生成第 1 项时，a [0] = 0，正好符合规则（a [1] = 0 + 1 = 1）。

3. 排序为什么从 a+1 开始？

因为数列存在 a [1] 到 a [n] 里，a [0] 是没用的 0，不用排序。

九、代码优化小技巧

虽然代码已经能解决问题，但可以让它更易读：

给变量起个好名字：比如 a 改成 recaman，s 改成 isUsed
加注释说明每一步的作用：

cpp

// 生成Recamán数列
for(int i=1;i<=n;i++){
    int prev = recaman[i-1]; // 前一项
    int candidate = prev - i; // 候选值
    if(candidate > 0 && !isUsed[candidate]){
        recaman[i] = candidate;
    }else{
        recaman[i] = prev + i;
    }
    isUsed[recaman[i]] = 1; // 标记已出现
}