4

私は宿題に取り組んでおり、完全に疲れ果てています。私はプログラミングが初めてで、これが私の最初のプログラミングクラスです。

これが問題です：

Collat​​z.java の次の再帰関数について考えてみましょう。これは、コラッツ問題または 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) への呼び出しは、17 回の再帰呼び出しの結果として、シーケンス 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 を出力します。コマンド ライン引数 N を取り、collat​​z(n) の再帰呼び出しの数が最大になる n < N の値を返すプログラムを作成します。ヒント: メモ化を使用します。未解決の問題は、n のすべての正の値に対して関数が終了するかどうかを誰も知らないことです (再帰呼び出しの 1 つが引数のより大きな値に対するものであるため、数学的帰納法は役に立ちません)。

私はいくつかのことを試しました: for ループを使用する、メソッドが実行されるたびにインクリメントされる変数を使用して実行回数をカウントしようとする、および何時間もの単調な作業。

どうやら、メモ化で何らかの形で配列を使用することになっています。ただし、開始時に配列の長さを指定する必要がある場合に、配列を使用する方法がわかりません。

私は何か完全に間違っていますか？私は質問を誤解していますか？

これまでの私のコードは次のとおりです。これは、整数配列を作成しようとする試みを反映しています。

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 カウント

そしてそれはうまくいきました。

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

メモ化は、n の前の値のシーケンス サイズを Map previousResults に格納することによって実装されます。

メイン関数で最大値を探すことができます:

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 に答える