0

我正在研究数论中的一个问题，该问题需要我解决一个相当复杂的丢番图方程。我们称这个方程为 f(r1, r2, ..., rk)。等式中的变量数量本身是可变的。这就是我被编程绊倒的地方。

我希望编写一个签名如下所示的 java 方法：

int[] getExponents(int n, int k, int max);

在这里，参数k等于丢番图方程f(r1, ... , rk)中的参数数量。

此方法应评估r1, ..., rk的所有组合的f(r1, ... , rk)使得0 < r1 < r2 < ... < rk < max，其中max是我们方法中给出的参数签名。

如果我们发现r满足n = f(r1, ... , rk)那么我们希望将r1, ... , rk作为整数数组返回。（值n在我们的方法签名中给出。）

我怀疑这种方法会使用递归。不幸的是，无论是我的编程技能还是我的耐心都不足以找到它。

我将感谢任何能够为我概述这种方法的人。

4

2 回答 2

1

f(int r[])假设是评估方程的函数的签名，基本函数可能看起来像这样。

  int[] getExponents( int n, int k, int max ){
    int[] result = new int[k];
    for(int i=0; i<k; i++)
      result[i]=i+1;
    do{
      if(f(result)==n)
        return result;
    }while(updateExponents(result,max));          
    return null;
  }

然后，您需要一个函数来迭代和boolean updateExponents(result,max)之间递增的整数序列。像这样的东西：0max

  private boolean updateExponents(int[] result, int max) {
    int k = result.length;
    for(int i=k-1; i>=0; i--){
      if(result[i]< max-(k-i))
      {
        result[i]++;
        for(int j=i+1; j<k; k++)
          result[j]=result[j-1]+1;
        return true;
      }
    }
    return false;
  }

免责声明：此代码可能包含错误，我尚未对其进行测试甚至运行它，但至少它应该是一个很好的起点。

于 2013-10-01T20:50:57.133 回答
0

以下是如何考虑处理递归。（这不是丢番图方程所特有的；这将适用于您需要找到所有此类整数序列的其他情况。）

问题是找到所有k整数序列 r 使得 0 < r1 < r2 < ... < rk < max。

好吧，从选择 r1 开始。可能性是 1, 2, ..., max - 1（实际上您可以在之前停止max - 1。您将循环进行并尝试每一个。

对于每个r1，您已将其简化为一个新问题：找到k-1整数 r2、r3、...、rk 的所有序列，使得 r1 [fixed] < r2 < r3 < ... < rk < max。这看起来很像原来的问题吗？好吧，这就是你的递归。唯一不同的是，下限是除 0 之外的其他值。因此，您的递归例程将需要一个下限参数（第一次调用时为 0），以及第一次调用时的k参数k，那么k-1, k-2, 等等

现在你只需要弄清楚当你到达底部时该怎么做。如果k为 1，则无需再次调用递归例程。你只需要对你收集的所有数字做点什么。因此，为此目的，您需要维护一个整数数组。这个数组一开始是空的。但是当第一级递归找到一个 integerr1时，您将添加r1到数组中。然后第二级需要追加 r2到数组；这意味着您的递归方法将需要一个参数来保存迄今为止找到的整数数组。该方法的每次调用都将获得一个“迄今为止找到的整数”数组，并在递归调用自身时使用该数组并附加一个新整数。当你到达底层时，你将拥有一个完整的整数数组，然后你可以测试你的丢番图方程来做任何你想做的整数。

希望这会让你开始。

于 2013-10-01T20:53:05.633 回答