java - 找到 Recamán 序列的第 n 个值

Question

我的一个实验问题是编写一段代码来计算 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
at P2J2.recaman(P2J2.java:78)

奇怪的是，错误并不是每次都出现在小数字上，而是几乎一直发生在 ~400 以上的任何数字上。

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

Answer 1

!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];
        }