4

I am working on a homework assignment, and I have completely exhausted myself. I'm new to programming, and this is my first programming class.

this is the problem:

Consider the following recursive function in Collatz.java, which is related to a famous unsolved problem in number theory, known as the Collatz problem or the 3n + 1 problem.

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);}

For example, a call to collatz(7) prints the sequence 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 as a consequence of 17 recursive calls. Write a program that takes a command-line argument N and returns the value of n < N for which the number of recursive calls for collatz(n) is maximized. Hint: use memoization. The unsolved problem is that no one knows whether the function terminates for all positive values of n (mathematical induction is no help because one of the recursive calls is for a larger value of the argument).

I have tried several things: using a for loop, trying to count the number of executions with a variable incremented each time the method executed, and hours of drudgery.

Apparently, I'm supposed to use an array somehow with the memoization. However, I don't understand how I could use an array when an array's length must be specified upon initiation.

Am I doing something completely wrong? Am I misreading the question?

Here is my code so far. It reflects an attempt at trying to create an integer array:

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

}
}

EDIT:

I wrote a separate program 

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);
    }
}

I then used piping: %java Collatz2 6 | java Count

and it worked just fine.

4

2 回答 2

4

由于您对最大序列大小感兴趣而不一定对序列本身感兴趣，因此最好让 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);
}
于 2014-02-22T10:00:49.920 回答
0

这里的技巧是编写一个递归方法，其中一个参数是你想要“记忆”的值。例如，这是一个方法的一个版本，它将返回达到 1 所需的步数（n当然，它假设大于或等于 1）：

public int countSteps(final int n)
{
    return doCollatz(0, n);
}

public static int doCollatz(final int nrSteps, final int n)
{
    if (n == 1)
        return nrSteps;

    final int next = n % 2 == 0 ? n / 2 : 3 * n + 1;
    return doCollatz(nrSteps + 1, next);
}

如果您要记录不同的步骤，则将 aList<Integer>作为参数传递.add()给它，并在您经历时传递给它，等等。

于 2014-02-22T09:20:13.880 回答