需要优化递归函数

Question

我想优化这个功能,以便它可以快速输出输入值
(x = 300,y = 120,z = 10).
我想过在连续计算后将值存储在3D数组中,但无法实现.

请帮忙.递归太难理解了!

double P(int x, int y, int z) {

    double final;
    if (x >= 0 && (y <= 0 || z <= 0))
        return  0;

    else if (x <= 0 && (y >= 0 || z >= 0) )
        return 1;

    else {     
        final = 0.1 * (P(x,y-1,z)
                       + P(x-1,y-1,z)
                       +  P(x-2,y-1,z)
                       +  P(x-3,y-1,z)
                       +  P(x-4,y-1,z)
                       +  P(x-5,y-1,z)
                       +  P(x-6,y-1,z)
                       +  P(x-1,y,z)
                       +  P(x-1,y,z)
                       +  P(x,y-1,z-1));
        return final;
    }
}

为了计算P (300, 120, 10)该函数必须计算的x,y和z的所有可能的组合,使得0 <= x <= 300,0 <= y <= 120,0 <= z <= 10.我想过要先创建一个3D数组.如果相应的arr [x] [y] [z]为空,我将调用该函数,否则我将从arr [x] [y] [z]中取值.

Answer 1

您需要构建函数的memoized版本.即包括缓存:

double P_memoized (int x, int y, int z, double ***cache) {

    if (x >= 0 && (y <= 0 || z <= 0))
        return  0;

    else if (x <= 0 && (y >= 0 || z >= 0) )
        return 1;

    else {
        if (cache[x][y][z] < 0.0) /* Negative => uncached.  */
          cache[x][y][z] = 0.1 * (P_memoized(x,y-1,z, cache)
                                  +  P_memoized(x-1,y-1,z, cache)
                                  +  P_memoized(x-2,y-1,z, cache)
                                  +  P_memoized(x-3,y-1,z, cache)
                                  +  P_memoized(x-4,y-1,z, cache)
                                  +  P_memoized(x-5,y-1,z, cache)
                                  +  P_memoized(x-6,y-1,z, cache)
                                  +  P_memoized(x-1,y,z, cache)
                                  +  P_memoized(x-1,y,z, cache)
                                  +  P_memoized(x,y-1,z-1, cache));
        return cache[x][y][z];
    }
}

但是调用者P_memoized将不得不分配(以及后来取消分配)cache.这对调用者来说是一个不必要的麻烦,所以你将memoized函数包装在一个包装器中,然后调用它P(就像你之前做的那样).下面的代码执行此操作,但请记住它不会检查是否malloc失败(请阅读malloc 此处):

#include <stdlib.h>
double P(int x, int y, int z) {

    double ***cache, final;
    int i, j, k;

    /* Create a cache.  */
    cache = malloc (sizeof (double **) * (x+1));
    for (i = 0; i <= x; i++)
      {
        cache[i] = malloc (sizeof (double *) * (y+1));
        for (j = 0; j <= y; j++)
          {
            cache[i][j] = malloc (sizeof (double) * (z+1));
            for (k = 0; k <= z; k++)
              cache[i][j][k] = -1.0; /* Negative => uncached.  */
          }
      }

    final = P_memoized (x, y, z, cache);

    /* Delete the cache.  */
    for (i = 0; i < x; i++)
      {
        for (j = 0; j < y; j++)
          free (cache[i][j]);
        free (cache[i]);
      }
    free (cache);
    return final;
}

然后你可以像以前一样使用它,只是这次,它更快:

#include <stdio.h>
int main (void)
{
  printf ("%f\n", P (10, 5, 3));
  return 0;
}

花哨的缓存

如果要进行多次调用P,则cache每次创建和删除可能不是最好的主意.那你应该考虑做以下事情:

1. 使缓存成为一个static变量,使其在调用时生效P
2. 用于realloc在需要时动态调整缓存大小
3. 不要free在最后的缓存P(因为它将被重用)

为什么需要动态调整缓存大小？因为,比方说,第一次打电话P是用来做的x==10.然后该函数将创建一个宽度为10的缓存.下一次,如果P使用x==20旧缓存调用,则不再宽泛.但其中包含的旧值仍然有用.

这个问题及其答案谈论了realloc一个二维阵列.您应该能够将其扩展到3D版本.

一旦你这样做,你可能想要考虑一个新问题:缓存永远不会得到freed.所以它一直保留在程序退出之前分配的内存.然后,您可能希望拥有全局缓存,而不是本地静态缓存,并free最终为其提供单独的功能.