0

これがUVa の 3n+1 問題に対する私のコードです。Eclipse AFAIKのPCで完全に動作しますが、UVaジャッジに対してランタイムエラーが発生し続けます。残念ながら、ジャッジは使用する入力を教えてくれませんし、失敗した場合に「RuntimeException」以外の情報も提供しません。これはACM の ICPCと同じ構造です。

1 から 1000000 までのすべての数値の最大サイクル長はわずか 525 であるため、再帰によってスタックがオーバーフローすることはないと確信しています。

package Collatz;

import java.util.Arrays;
import java.util.Scanner;

class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] cache = buildCache(1000000);
        while (in.hasNextLine()) {
            Scanner line = new Scanner(in.nextLine());
            if (!line.hasNextInt()) continue;
            int a = line.nextInt();
            int b = line.nextInt();
            int c = a;
            int d = b;
            if (c > d) {
                int temp = c;
                c = d;
                d = temp;
            }
            int max = 0;
            for (int i = c - 1; i <= d - 1; i++) {
                max = Math.max(max, cache[i]);
            }
            System.out.format("%d %d %d\n", a, b, max);
            line.close();
        }
        in.close();
    }

    public static int[] buildCache(int n) {
        int[] cache = new int[n];
        Arrays.fill(cache, 0);
        cache[0] = 1;
        for (int i = 1; i < n; i++) {
            search(i + 1, cache);
        }
        return cache;
    }

    public static int search(long i, int[] cache) {
        int n = cache.length;
        if (i == 1) {
            return 1;
        } else if (i <= n && cache[(int)(i - 1)] > 0) {
            return cache[(int)(i - 1)];
        } else {
            long j = (i % 2 == 1) ? (3 * i + 1) : (i / 2);
            int result = search(j, cache) + 1;
            if (i <= n) {
                cache[(int)(i - 1)] = result;
            }
            return result;
        }
    }
}
4

2 に答える 2

1

わかった。私はついに問題を見つけました。パッケージ明細書です。プログラムは削除後に受け入れられます... IDE から送信フォームにコードをコピーして貼り付けるときのちょっとした間違い..しかし、ここには興味深い議論がいくつかあります。

于 2014-01-24T00:54:11.500 に答える
0

ここでのロジックはスタックをオーバーフローさせます。現在の関数の結果をキャッシュする前に、シーケンス内の次の番号を検索します。

    int result = search(j, cache) + 1;
    if (i <= n) {
        cache[(int)(i - 1)] = result;
    }
    return result;
于 2014-01-23T23:13:17.197 に答える