java - 在java中使用递归方法进行内存

Question

我正在做家庭作业，我已经筋疲力尽了。我是编程新手，这是我的第一堂编程课。

问题是:

考虑以下 Collat​​z.java 中的递归函数，它与数论中著名的未解决问题有关，称为 Collat​​z 问题或 3n + 1 问题。

public static void collatz(int n) {
StdOut.print(n + " ");
if (n == 1) return;
if (n % 2 == 0) collatz(n / 2);
else            collatz(3*n + 1);}

例如，调用 collat​​z(7) 打印序列7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1作为 17 次递归调用的结果。编写一个程序，它接受一个命令行参数 N 并返回 n < N 的值，使 collat​​z(n) 的递归调用次数最大化。提示:使用内存。 Unresolved 问题是，没有人知道函数是否针对 n 的所有正值终止(数学归纳法无济于事，因为递归调用之一是针对参数的更大值)。

我尝试了几种方法:使用 for 循环，尝试计算每次方法执行时递增的变量的执行次数，以及数小时的苦差事。

显然，我应该以某种方式在内存中使用数组。但是，当必须在启动时指定数组的长度时，我不明白如何使用数组。

我做错了什么吗？我是不是误读了问题？

到目前为止，这是我的代码。它反射(reflect)了尝试创建整数数组的尝试:

public class Collatz2 {
public static int collatz2(int n)
{

    StdOut.print(n + " ");
    if (n==1) {return 1;}
    else if (n==2) {return 1;}
    else if (n%2==0) {return collatz2(n/2);}
    else {return collatz2(3*n+1);}

}



public static void main(String[] args)
{
    int N = Integer.parseInt(args[0]);
    StdOut.println(collatz2(N));

}
}

编辑:

我写了一个单独的程序

public class Count {
   public static void main(String[] args) { 
        int count = 0;       

        while (!StdIn.isEmpty()) {
            int value = StdIn.readInt();
            count++;
        }

        StdOut.println("count is " + count);
    }
}

然后我使用管道:%java Collat​​z2 6 | Java 计数

而且效果很好。

Answer 1

由于您对最大序列大小感兴趣而不一定是序列本身，因此最好让 collat​​z 返回序列的大小。

private static final Map<Integer,Integer> previousResults = new HashMap<>();

private static int collatz(int n) {
    int result = 1;
    if(previousResults.containsKey(n)) {
        return previousResults.get(n);
    } else {
        if(n==1) result = 1;
        else if(n%2==0) result += collatz(n/2);
        else result += collatz(3*n + 1);
        previousResults.put(n, result);
        return result;
    }
}

内存是通过在 Map previousResults 中存储 n 的先前值的序列大小来实现的。

可以在main函数中寻找最大值:

public static void main(String[] args) {
    int N = Integer.parseInt(args[0]);
    int maxn=0, maxSize=0;
    for(int n=N; n>0; n--) {
        int size = collatz(n);
        if(size>maxSize) {
            maxn = n;
            maxSize = size;
        }
    }
    System.out.println(maxn + " - " + maxSize);
}