0

所以这是我在 UVa 上的 3n+1 问题的代码。它在 Eclipse AFAIK 中在我的 PC 上完美运行，但是，我不断收到针对 UVa 判断的运行时错误。不幸的是，法官没有告诉我它使用了哪些输入，也没有在失败时提供“RuntimeException”之外的任何信息。出于好奇，这与ACM 的 ICPC结构相同。

我很确定递归不会溢出堆栈，因为从 1 到 1000000 的所有数字的最大循环长度仅为 525。此外，1000000 个整数的缓存应该只有 4Mb 大。

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 回答