递归函数g(n)

Question

我有一个g(n)可以给出的功能g(n)=f(n,n) .这是由递归定义的

f(i, j) = 1/3
(f(i?1, j) + f(i?1, j ?1) + f(i, j ?1))

with f(0,0) = 0;  f(i,0) = 1,i > 0; f(0, j) = 1, j > 0

我编写了一个java程序来计算10-15的值.快速处理前几个值,但是在值结束时,程序变得非常慢并且需要很长时间来处理结果.我的代码有问题还是只是一个冗长的计算？

public class javaapplication4 {
    private static double f(double i, double j) {
        if (i == 0.0 && j == 0.0) return 0.0;
        if (i == 0.0 || j == 0.0) return 1.0;
        return (f(i - 1, j) + f(i - 1, j - 1) + f(i, j - 1));
    }

    private static double g(double n) {
        return f(n, n);
    }

    public static void main (String[] args) {
        for (int n = 10; n < 16; n ++) {
            System.out.println("g(" + (int) n + "): " + g(n));
        }
    }
}

Answer 1

首先,你似乎忘记了1.0 / 3这一行:

return(f(i - 1,j)+ f(i - 1,j - 1)+ f(i,j - 1));

其次,您的程序很慢,因为多次计算相同的值.例如,f(i - 1, j)将调用f(i - 1, j - 1),也称为调用f(i, j).

要解决此问题,请在矩阵中计算递归关系:

 f(0,0) = 0; f(i,0) = 1,i > 0; f(0, j) = 1, j > 0
 for i = 1 to n:
   for j = 1 to n:
     f[i, j] = 0.33*(f[i - 1, j] + f[i, j - 1] + f[i - 1, j - 1])

或者保持递归实现,但使用memoization来加速它:

记忆功能"记住"与某些特定输入相对应的结果.使用记忆输入的后续调用将返回记住的结果而不是重新计算结果,从而消除了除了使用这些参数对函数进行的第一次调用之外的所有参数的调用的主要成本.

基本上,您仍然可以使用矩阵来存储结果,并执行以下操作:

private static double f(double i, double j) { // make i and j ints, they do not need to be doubles here.
    if (i == 0.0 && j == 0.0) return 0.0;
    if (i == 0.0 || j == 0.0) return 1.0;
    if (storageMatrix[i, j] != -1) {
      return storageMatrix[i, j];
    }

    storageMatrix[i, j] = (1.0 / 3) * (f(i - 1, j) + f(i - 1, j - 1) + f(i, j - 1));
    return storageMatrix[i, j];
}

您可以通过注意到如果您实现迭代解决方案我为上面提供了伪代码来进一步优化,您只需要使用矩阵的当前行和前一行.所以你可以使用两个长度数组n而不是方形n x n矩阵来计算你的函数.