主页 / 问题 / 1072139
Accepted
KotFind
Asked:2020-01-20 22:40:03 +0000 UTC2020-01-20 22:40:03 +0000 UTC

多个整数值的无限迭代

  • 772

假设我想无限循环遍历多个整数值，直到找到合适的组合。如果只有一个值，那么这很容易：我们只需使用 while 循环遍历该值。如果有多个这些值怎么办？PS我认为它可以用BFS完成，但没有更简单的方法吗？

UPD：例如，我有一个整数变量 a 和一个 check(int a) 函数，如果该值匹配则返回 true。在这种情况下，您可以像这样遍历所有值：

int a = 0;
while(!check(a) && !check(-a)) {
    ++a;
}

如果我有整数变量 a、b 和函数 check(int a, int b) 怎么办？如何迭代？

алгоритм

3 个回答

  1. Best Answer

    伪代码：

    M = 0

Повторять:
    для a от 0 до M:
        b = M
        Проверить (a, b)
    для b от 0 до (M-1)
        a = M
        Проверить (a, b)
    M = M + 1

    也就是说，它类似于您编写的内容：

    Т.е. (для двух значений) мы предполагаем, что находимся на клетчатом поле в клетке (0, 0) потом рассматриваем соседние для этой клетки клетки, потом соседние для соседей и т.д. Но этот способ мне не очень нравится. Ему нужно достаточно много дополнительной памяти, да и код некрасивым будет.

    只有在我的版本中，没有必要存储单元列表并查找它们的邻居，因为邻居的每次迭代都将是正方形上方和右侧的一条单元格，每次迭代都会增加 1。

    对于两个以上的变量，原理相同，只是代码稍微复杂一些。

    UPD：我意识到你可以让它变得更容易：

    S = 0
Повторять:
    для a от 0 до S:
        b = S - a
        Проверить (a, b)
    S = S + 1
    • 3

  2. 当您迭代一个变量的值时，您只需沿着 OX 轴从零向正值移动到无穷大。而且这个没有问题，拿去整理一下。

    现在您需要遍历两个数字。那些。以某种方式同时沿两个坐标轴“绘制”整个检查区域。如何在其上绘画取决于您，但如果您需要简单枚举“前额”中的所有选项，那么仅沿一个轴移动是行不通的：它是无限的。因此，您可以尝试通过填充从角度 0,0 到角度 + infinity_in_X、+ infinity_in_Y 的所有内容来沿对角线移动。

    您的算法将采用的路径如下图所示：

    解决方案的图形表示

    例如，代码本身（我在 php 中的示例）可以是这样的（在 dir 变量中 - 运动方向 - 朝向轴a或朝向轴b，其余部分很清楚等等）：

    const DIR_A = 0;
const DIR_B = 1;

$a = 0;
$b = 0;
$dir = DIR_A;

$dots = [];
while (count($dots) < 16) {
    $dots[] = [$a, $b];
    if ($dir === DIR_A) {
        if ($b > 0) {
            $b--;
            $a++;
        } else {
            $a++;
            $dir = DIR_B;
        }
    } else {
        if ($a > 0) {
            $a--;
            $b++;
        } else {
            $b++;
            $dir = DIR_A;
        }
    }
}

foreach ($dots as $dot) {
    echo "[{$dot[0]}, {$dot[1]}], ";
}
echo "...\n";

    结果，这是输出：

    [0, 0], [1, 0], [0, 1], [0, 2], [1, 1], [2, 0], [3, 0], [2, 1], [1, 2], [0, 3], [0, 4], [1, 3], [2, 2], [3, 1], [4, 0], [5, 0], ...
    • 2

  3. 好吧，如果你想迭代几个值以寻找它们的合适组合，那么......呃......你可以在循环中做一个循环吗？！

    bool isFound = false;

for (int a = start; a < end; a++) {
  for (int b = start; b < end; b++) {
    ...
      if (check(a, b, ..., n)) {
        // Сохрани найденные значения
        isFound = true;
        break;
      }
    ...
    if (isFound) break;
  }
  if (isFound) break;
}

    只是不要去无穷大！有点长。。。

    • 0

相关问题