简答题
偏难
#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
输出样例 1
输入样例 2
输出样例 2
样例解释
对于样例 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 > 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] > 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>
这道题暂未补解析。