2013
11-10

# Recaman’s Sequence

The Recaman’s sequence is defined by a0 = 0 ; for m > 0, am = am−1 − m if the rsulting am is positive and not already in the sequence, otherwise am = am−1 + m.

The first few numbers in the Recaman’s Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 …

The input consists of several test cases. Each line of the input contains an integer k where 0 <= k <= 500000.

The last line contains an integer −1, which should not be processed.

For each k given in the input, print one line containing ak to the output.

7
10000
-1

20
18658

(1)
import java.util.Scanner;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main{
public static void main(String args[]) throws Exception {
int a[]=new int[500001];
a[0]=0;
HashMap< Integer,Boolean> ha=new HashMap< Integer,Boolean>();
Scanner in=new Scanner(System.in);
for(int i=1;i<=500000;i++){
if(a[i-1]-i>0&&ha.get(a[i-1]-i)==null){
a[i] = a[i-1]-i;
ha.put(a[i],true);
}else{
a[i] = a[i-1]+i;
ha.put(a[i],true);
}
}

String input = new String();
while(!(input=in.nextLine()).equals("-1")) {
int n = Integer.parseInt(input);
System.out.println(a[n]);
}
}

}
(2)

import java.util.Scanner;
public class Main{
public static void main(String args[]) throws Exception {
int a[]=new int[500001];
a[0]=0;
boolean flag[] =new boolean[3012501];
Scanner sc=new Scanner(System.in);
int n=0;
for(int i=1;i<=500000;i++){
if(a[i-1]-i>0&&flag[a[i-1]-i]==false){
a[i] = a[i-1]-i;
flag[a[i-1]-i] = true;
}else{
a[i] = a[i-1]+i;
flag[a[i-1]+i] = true;
}
}

while((n=sc.nextInt())!=-1){
System.out.println(a[n]);

}
}
}

1. m /= i; 是一直在变的。参考这一篇关于质因数的http://www.acmerblog.com/integer-factorization-5124.html

2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

3. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环