java - 使用静态 int 数组进行缓存的阶乘

Question

static int count = 0;
static long[] cache = new long[3000];

static {
    cache[0] = 1;
}
public static void main(String args[]) {
    for (int i = 0; i < 100; i++){
        factorial_with_cache(2999);
    }
    System.out.println(count);        
}

public static long factorial_with_cache (int n){
    if (cache[n] != 0){
        return cache[n];
    }
    cache[n] = n * factorial_with_cache(n - 1);
    count++;
    return cache[n];
}

我构建了一个使用缓存计算阶乘的函数(忽略溢出)。

但与非缓存功能相比，它的运行时间并没有好到哪里去，我发现缓存无法正常工作。

因为我预计变量“计数”在循环后为 2999，但我发现它是 293465，远不止于此。 (没有循环，它打印 2999)

这个函数有什么问题？

Answer 1

因为long数据类型的范围:

long 8 bytes (-9,223,372,036,854,775,808 to 9,223,372,036,854,775,807)

在您搜索 25 的阶乘之前，您的阶乘会给出正值。后面的 25 ，计算出的阶乘值为负(这意味着你溢出了很长时间)并且你的计数将按预期工作直到计算出 65 阶乘(直到负值)然后阶乘 66 的值达到 0 ..

只需在下面打印阶乘即可:

for (int i = 0; i < 100; i++) {
          long fact=factorial_with_cache(66);
          System.out.println(fact);
        }
        System.out.println(count);

计数将打印为

(forLoopCount*(number-65))+65 , In your case (100*(2999-65))+65 is 293465

因为它在缓存中追溯的阶乘值不为零，因此是第 65 个元素(在 64 索引处)。