FOJ 1304 Recaman's Sequence
程序员文章站
2022-03-13 16:45:59
...
一,问题描述
二,问题分析
1.初看题目符合递归的条件,需要注意的是 a(m) 不在序列中的意思是 a(m)的值在 前m-1个序列中不存在
2.输入的整数K的最大范围是500000,采用一个数组记录整个序列即可
3.还需要一个标记数组用来判断得到的a(m) 在前面的序列的是否存在
三,问题解答
#include<iostream>
#include<vector>
using namespace std;
vector<int> vec(500000);
vector<int> visited(4000000, -1); //标记数组
void fun() {
vec[0] = 0;
visited[0] = 1;
vec[1] = 1;
visited[1] = 1;
for (int i = 2; i < 500000; i++) {
if ((vec[i - 1] - i) > 0 && visited[vec[i - 1] - i]==-1 ) {
vec[i] = vec[i - 1] - i;
}
else {
vec[i] = vec[i - 1] + i;
}
visited[vec[i]] = 1; //标记vec[i]已使用
}
}
int main() {
int k;
fun();
while (cin >> k) {
cout << vec[k] << endl;
}
return 0;
}
注意:标记数组开辟的大小一定要足够大,否则会发生越界异常
上一篇: AndroidX引发的“血案”