找到雷卡曼序列的第 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索引超出边界异常： 104

at P2J2.recaman（P2J2.java：78）

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

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

Answer 1

检查[减去瓦尔]是正确的方法。public static int recaman(int n)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int[] seq = new int[n];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; boolean[] check = new boolean[10 * n];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; seq[0] = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; check[0] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int k = 1; k < n; k++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int minusVal = seq[k - 1] - k;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int plusVal = seq[k - 1] + k;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ((minusVal > 0) && (!check[minusVal]))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; seq[k] = minusVal;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; check[minusVal] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; seq[k] = plusVal;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; check[plusVal] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return seq[n - 1];&nbsp; &nbsp; &nbsp; &nbsp; }

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 {&nbsp; &nbsp; public static int recaman(int n){&nbsp; &nbsp; &nbsp; &nbsp; int[] seq = new int[n * 10];&nbsp; &nbsp; &nbsp; &nbsp; boolean[] check = new boolean[10 * n];&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; seq[0]=0;&nbsp; &nbsp; &nbsp; &nbsp; check[0]=true;&nbsp; &nbsp; &nbsp; &nbsp; for(int k=1;k<=n;k++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int minusVal = seq[k-1]-k;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int plusVal = seq[k-1] + k;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if((minusVal>0)&&(!check[minusVal])){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; seq[k]= minusVal;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; check[minusVal] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; seq[k] = plusVal;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; check[plusVal]=true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return seq[n];&nbsp; &nbsp;}&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Hello World!");&nbsp; &nbsp; &nbsp; &nbsp; recaman(100000);&nbsp; &nbsp; }}