-3

如果有一定的数 x 0和 x n+1，如果 x i是整数 0 <= i <= n+1，如何用 JAVA 计算数字的总和？

总和表示它对 (x 1 ,x 2 ,...x n ) 的每个可能组合取 f(x 1 , x 2 , ... x n )的总和，使得不等式成立。不等式是x 0 < x 1 < x 2 < ... < x n+1

我有一个解决方案的想法，但它是一种使用二进制的非常无效的算法，它是 O(2 n )。当然，我不能使用“for”，因为它必须用于 n（非特定）次。

例如，

如果给定的是 x 1 = 1，并且 x n+1是 x 3 = 5，那么可能的组合是

  • x 1 =1, x 2 =2, x 3 =5
  • x 1 =1, x 2 =3, x 3 =5
  • x 1 =1, x 2 =4, x 3 =5

总和应该计算所有这 3 个可能值集的总和。

有没有人知道更有效的算法？

4

1 回答 1

2

解决这个问题的方法是将其视为尝试找到 和 之间的所有数字n组合。随时添加它们minmax

您可以想象在和n之间的数字线上的石头，然后移动最右边的石头直到它达到最大值，当它是时，您将下一个最右边的石头向上移动一个位置并将所有石头移动到它的右边。minmax

请参阅此示例，其中 n=4、min=2 和 max=11

在此处输入图像描述

该算法将确保您获得所有组合。

因此，考虑到该算法，您可以编写函数

boolean[] getNextCombinations(boolean[] currentCombination) //which would advance to the next value (and probably return null when there are no more combinations)

和

int scoreCombinations(boolean[] currentCombination, int min, int max) //which would add up a particular combination
于 2013-09-30T11:29:29.420 回答