首页 > 数据结构 > Hash表 > POJ 2081 Recaman’s Sequence [解题报告] Java
2013
11-10

POJ 2081 Recaman’s Sequence [解题报告] Java

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 …

Given k, your task is to calculate ak.

输入:

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
    会陷入死循环