组合算法中的循环

Question

我想执行特定类型的搜索。我不知道它是否有名称，但我可以描述它，并有执行它的工作代码。

对于二维矩阵，从点 0,0 开始并向右下方工作，搜索生成将如下所示：

• 1, 4, 9, 16,
• ... ; 2、 3、8、15、...
• 5、 6、7、14、...
• 10、11、12 , 13, ...
• ...

所以第一个搜索循环将检查 1，第二个循环检查 2, 3, 4，第三个循环检查 5, 6, 7, 8, 9 等。

生成此搜索的代码是：

$row_search = 0;
$point_not_found = true;

while ($point_not_found && $row_search < $matrix_height/2)
{
    $current = array(0, $row_search);

    while ($current[0] < $row_search)
    {
        if (searchForPoint( $matrix, $current ) !== false)
            $point_not_found = false;

        ++$current[0];
    }

    if (!$anchor_not_found)
        break;

    while ($current[1] >= 0)
    {
        if (searchForPoint( $matrix, $current ) !== false)
            $point_not_found = false;

        --$current[1];
    }

    ++$row_search;
}

我对搜索被分成两个循环的方式不满意，因为循环内的代码几乎相同。您能否建议一种组合或嵌套循环并消除对 searchForPoint 的冗余调用的方法？

Answer 1

像这样的事情怎么样

$pointFound = false;
$row = 0;

while(!$pointFound && $row < $matrixSize)
{
    $y = $row;
    $x = 0;
    while($y >= 0)
    {
        if (searchForPoint($matrix,$x,$y) !== false)
        {
            $pointFound = true;
            break;
        }

        // If we reached the right column, start moving upwards (decreasing y)
        if($x == $row)
            $y--;
        // Else move right
        else
            $x++;
    }
    // EDIT (forgot the next line)
    $row++;
}

Answer 2

存在一种嵌套循环的方法，但是将问题分解为两个循环的方法非常直观，而且最重要的是，已经可以工作了。

假设我们正在计算数学表达式 ln(x^2 + 1) - sqrt(x^2 + 1)。写成f(x) = ln(g(x)) - sqrt(g(x)), g(x) = x^2 + 1不是很方便吗？这似乎是你问题的本质，这个类比的要点是你应该考虑两个函数。

您有一种从左上到右下迭代的方法。给这个策略一个名称并将其抽象为迭代器。如果您愿意，请使用 OOP。然后，您就有了对迭代器提供给您的每件事做一些事情的概念。给那个东西一个名字并让它使用你的迭代器。额外的好处：您可以在找到匹配项后立即中止搜索，而不是过了一段时间。

伪代码：

$iterator = new MatrixRippleIterator($matrix);
$needle = 1337;
$found_match = false;
while ($iterator->hasNext()) {
    $current = $iterator->next();
    if ($current == $needle) {
        $found_match = true;
        break;
    }
}