我的一个实验问题是编写一段代码来计算 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 以上的任何数字上。
我似乎无法弄清楚我做错了什么,如果有人能指出我正确的方向,我将不胜感激。
最佳答案
!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];
}
关于java - 找到 Recamán 序列的第 n 个值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55464013/