找到雷卡曼序列的第 n 个值

Question

我的一个实验问题是编写一段代码来计算 Recamán 序列的第 n 个值。我得到的测试用例最高可达Recamán序列的第100，000个值，用于确定值本身的算法不是我的问题，我的问题是以一种不需要太长时间运行的方式编写程序。为了实现这一点，我的教授给了我们一个提示，使用大小为n*10的足够大的布尔值[]，并用它来跟踪哪些整数值已经是生成的序列的一部分，而不是遍历整个先前生成的值。我有一些代码，我认为应该可以很好地做到这一点，但问题是我用完了数组指示。通过向我们提供的自动测试仪，它会随机要求1-100，000之间的第n个值。但是，我遇到了布尔值[]中空间不足的问题，以检查是否已生成该数字。我的代码如下   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.Array索引超出边界异常： 104at P2J2.recaman（P2J2.java：78）奇怪的是，对于小数字，错误并不是每次都出现，但对于任何高于~400的数字，几乎总是会发生。我似乎无法弄清楚我做错了什么，如果有人能给我指出正确的方向，我将不胜感激。

Answer 1

检查[减去瓦尔]是正确的方法。

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

        }

Answer 2

对于 和 你检查 .这是错误的原因。似乎你也需要制作。希望它有帮助！k=16minusVal = 104!check[seq[minusVal]]int[] seq = new int[n * 10];

PS.我测试了它，但仍然有相同的错误。一般来说，这种情况是错误的，并可能导致错误的结果。您应该将其替换为，因为您要检查以前是否存在，而不是 。int[] seq = new int[n * 10];!check[seq[minusVal]]!check[minusVal]MinusValseq[minusVal]

此代码对我来说没有错误：

public class HelloWorld {

    public static int recaman(int n){

        int[] seq = new int[n * 10];

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

   }

    public static void main(String[] args) {

        System.out.println("Hello World!");

        recaman(100000);

    }

}