时间戳

首页 > 解决方案 > 求 Recamán 数列的第 n 个值

java - 求 Recamán 数列的第 n 个值

问题描述

我的一个实验问题是编写一段代码来计算 Recamán 序列的第 n 个值。

我给出的测试用例达到了 Recamán 序列的第 100,000 个值，而确定值本身的算法不是我的问题，我的问题是以一种不需要太长时间运行的方式编写程序. 为了做到这一点，我的教授给了我们使用足够大的大小为 n*10 的 Boolean[] 的提示，并使用它来跟踪哪些整数值已经是生成序列的一部分，而不是遍历整个先前生成的值.

我有我认为应该可以很好地执行此操作的代码，但是我的数组索引用完了。查看我们提供的自动测试仪，它随机要求从 1 到 100,000 的第 n 个值。但是，我遇到了 Boolean[] 中空间不足的问题，以检查是否已生成数字。

我的代码如下

   public static int recaman(int n){
        int[] seq = new int[n];
        boolean[] check = new boolean[10 * n]; 

        seq[0]=0;
        check[0]=true;
        for(int k=1;k<=n;k++){
            int minusVal = seq[k-1]-k;
            int plusVal = seq[k-1] + k;
            if((minusVal>0)&&(!check[seq[minusVal]])){
                seq[k]= minusVal;
                check[minusVal] = true;
            }else{
                seq[k] = plusVal;
                check[plusVal]=true;
            }
        }
        return seq[n];
   }

并运行 recaman(100) 会导致以下错误

Java.lang.ArrayIndexOutOfBoundsException ：104
在 P2J2.recaman（P2J2.java:78）

奇怪的是，对于小数字，错误并非每次都出现，但对于任何高于 ~400 的数字，几乎总是发生。

我似乎无法弄清楚我做错了什么，如果有人能指出我正确的方向，我将不胜感激。

标签： java

解决方案

!check[minusVal] 是正确的方法。

public static int recaman(int n)
        {
            int[] seq = new int[n];
            boolean[] check = new boolean[10 * n];

            seq[0] = 0;
            check[0] = true;
            for (int k = 1; k < n; k++)
            {
                int minusVal = seq[k - 1] - k;
                int plusVal = seq[k - 1] + k;
                if ((minusVal > 0) && (!check[minusVal]))
                {
                    seq[k] = minusVal;
                    check[minusVal] = true;
                } else
                {
                    seq[k] = plusVal;
                    check[plusVal] = true;
                }
            }
            return seq[n - 1];
        }

推荐阅读