0

我希望以通用方式同时递归两个参数。这里有一些解释：

这就是函数调用的样子Func(int a, int b)：

  • 呼叫 0：Func(0, 0)
  • 呼叫 1：Func(0, 1)
  • 呼叫 1：Func(1, 0)
  • 呼叫 1：Func(0, -1)
  • 呼叫 1：Func(-1, 0)

我将如何在代码中实现这一点，以确保以下语句：

  • a INRANGE (-INF, INF)考虑和的所有可能组合b INRANGE (-INF, INF)。
  • 没有开销，我的意思是在递归中不会多次使用相同的函数。

后来我想扩展它以在 7 个参数上做同样的事情。

问候。

4

4 回答 4

1

这是我对螺旋式方法的看法：

// this is your function
static void func(int x, int y)
{
  System.out.println("x = "+x+", y = "+y);
}

// this calls func for all possible combinations of signs of the variables in arr
static void allPossibleSigns(int pos, Integer... arr)
{
  if (pos == arr.length)
  {
     func(arr[0], arr[1]); // not really generic
  }
  else
  {
     allPossibleSigns(pos+1, arr);
     arr[pos] = -arr[pos];
     if (arr[pos] != 0)
        allPossibleSigns(pos+1, arr);
  }
}

static void caller()
{
  for (int t = 0; t < MAX; t++)
  for (int x = 0; x <= t; x++)
  {
     int y = (t-x);
     allPossibleSigns(0, x, y);
  }
}

如果您想要比 更通用的东西func(arr[0], arr[1]);，可以将其替换为：

Method[] methods = NewMain.class.getMethods();
for (Method m: methods)
{
   if (m.getName().equals("func"))
      m.invoke(null, arr);
}

并添加一些错误检查。由于这种方法，我使用Integer...而不是int...in printAllPossibleSigns（以上不适用于int...）。这假设您只有一个名为func. 如果不是这种情况，您将不得不添加一些额外的检查。

对于MAX= 4，它打印：

x = 0, y = 0
x = 0, y = 1
x = 0, y = -1
x = 1, y = 0
x = -1, y = 0
x = 0, y = 2
x = 0, y = -2
x = 1, y = 1
x = 1, y = -1
x = -1, y = -1
x = -1, y = 1
x = 2, y = 0
x = -2, y = 0
x = 0, y = 3
x = 0, y = -3
x = 1, y = 2
x = 1, y = -2
x = -1, y = -2
x = -1, y = 2
x = 2, y = 1
x = 2, y = -1
x = -2, y = -1
x = -2, y = 1
x = 3, y = 0
x = -3, y = 0

这将如何扩展到 3 个变量可能并不完全清楚，所以这里是caller3 个变量：

static void caller()
{
  for (int t = 0; t < MAX; t++)
  for (int x = 0; x <= t; x++)
  for (int y = 0; y <= (t-x); y++)
  {
     int z = (t-x-y);
     printAllPossibleSigns(0, x, y, z);
  }
}

显然，func(arr[0], arr[1]);如果您没有选择通用方法，那么这就是您必须更改的所有内容以及您的功能。

于 2013-08-05T14:11:30.170 回答
1

我提出了一个螺旋式的，非递归的最简单的。为了便于阅读，每一步都会再次选择移动。

int x = 0;
int y = 0;
for (int t = 0; t < 100; ++t) {
    func(x, y);
    if (x <= 0 && y == 0) { // Widen spiral.
        --x;
        ++y; // So next condition takes next.
    } else if (x < 0 && y >= 0) { // Left, upper quadrant.
        ++x;
        ++y;
    } else if (x >= 0 && y > 0) { // Right, upper.
        ++x;
        --y;
    } else if (x >= 0 && y <= 0) { // Right, lower.
        --x;
        --y;
    } else if (x < 0 && y < 0) { // Left, lower.
        --x;
        ++y;
    } else {
        throw new IllegalStateException("x = " + x + ", y = " + y);
    }
}

我没有尝试代码！检查条件。

于 2013-08-05T13:39:35.097 回答
1

也许一些组合学知识会在这里有所帮助。对我来说，这看起来像你有一组从 -N 到 +N 的元素。现在你想为每个长度的变化调用一个函数 == 7 这些元素。

这样的范围可能真的很大。根据您要调用的操作成本，这可能需要比您生活更长的时间。

我会写一个Iterator在每次调用 next() 时提供元素的新变体（这是你的函数参数）。

BigInteger如果您需要大数字，您可以实现这样的迭代器。您可以使用ArrayorList并在每次迭代中更改它的元素。如果您搜索组合算法或排列/变化算法，您可能会找到详细信息，甚至可能是实现。

另一种（类似的）方法（我认为开销更大）是只使用一个数字（例如 BigInteger）来标记当前的变化。在每次迭代中，您将此变体索引号加 1。

要从此数字中获取参数，您必须对此变化索引执行基本转换。基数将是元素集中的元素数量。结果数字的每个数字的范围为 0 到元素的数量 -1。从此，您可以使用每个数字从元素列表中获取函数调用的参数。

我比前一段时间做了，而且效果很好。不能保证比我能找到它。

于 2013-08-05T13:55:16.063 回答
0

对于 n 维：

下面我使用正数作为坐标。对于解决方案中的每个正（大于 0）坐标，使坐标为负也是一个解决方案（几乎是 2^n 个解决方案的因子）。（使用正数可以简化解的解读。）

这是维数为 n 的坐标向量的解。选择坐标时，“半径”=坐标总和。

static void func(int[] x) {
    System.out.printf("%s%n", Arrays.toString(x));
}

/**
 * Call many funcs with several coordinates.
 * @param x n-dimensional coordinates.
 * @param fromI starting index for variable coordinates.
 * @param r radius, equal to the sum of x[>= fromIndex].
 * @param t downward counter limiting the number of calls.
 * @return new value of t.
 */
static int callFuncsForRadius(int[] x, int fromIndex, int r, int t) {
    if (t <= 0) {
        return t;
    }
    if (fromIndex >= x.length) { // Nothing more to vary.
        if (r == 0) { // Read radius sum.
            func(x);
            --t;
        }
        return t;
    }
    for (int rNext = r; rNext >= 0; --rNext) {
        x[fromIndex] = rNext;
        t = callFuncsForRadius(x, fromIndex + 1, r - rNext, t);
        if (t <= 0) {
            break;
        }
    }
    return t;
}

static int callFuncs(int[] x, int t) {
    int r = 0;
    while (t > 0) {
        t = callFuncsForRadius(x, 0, r, t);
        ++r;
    }
    return t;
}

public static void main(String[] args) {
    int n = 3;
    int[] x = new int[n];
    int t = 10; // N^n, where N = 2^31.
    callFuncs(x, t);
}
于 2013-08-06T15:01:28.060 回答