简答题 偏难
#18052

Recamán 时间限制:2.0 s 内存限制:512.0 MB 题目描述 小杨最近发现了有趣的 Recamán 数列,这个数列是这样生成的: 数列的第一项a…

Recamán

时间限制:2.0 s

内存限制:512.0 MB

题目描述

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

数列的第一项a1是 1;

如果ak−1−k 是正整数并且没有在数列中出现过,那么数列的第 k  项ak为ak−1−k,否则为ak−1+k。

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

输入格式

第一行,一个正整数 n 。

输出格式

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


输入样例 1

5
1

输出样例 1

1 2 3 6 7
1

输入样例 2

8
1

输出样例 2

1 2 3 6 7 12 13 20
1

样例解释

对于样例 1,n=5;

a1−2=−1,不是正整数,因a2=a1+2=3;

a2−3=0,不是正整数,因此a3=a2+3=6;

a3−4=2,是正整数,且没有在数列中出现过,因此a4=2;

a4−5=−3,不是正整数,因此a5=a4+5=7;

a1,a2,a3,a4,a5从小到大排序后的结果为 1 2 3 6 7 。

数据范围

对于所有数据点,保证1≤n≤3000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">n = int(input()) a = [1] for i in range(2, n + 1): a.append(a[-1] - i if a[-1] - i &gt; 0 and a[-1] - i not in a else a[-1] + i) def bubble_sort(a): n, flag = len(a), True while flag: flag = False for i in range(n - 1): if a[i] &gt; a[i + 1]: flag = True a[i], a[i + 1] = a[i + 1], a[i] bubble_sort(a) for i in range(n): a[i] = str(a[i]) print(' '.join(a))</pre>
这道题暂未补解析。