Pascal 中的回溯：寻找最大加权分支

Question

我已经学习 Pascal（使用 Free Pascal 编译器）一周了，遇到了一个看似简单的练习。给定如下所示的结构，找到最大加权分支：

分支是任何数字序列，从顶部开始（在本例中为：1），对于每个数字，分支都可以向左下或右下扩展。例如，分支 1-4-0 可以扩展为 1-4-0-8 或 1-4-0-6。所有分支必须从顶部开始到底部结束。

在这个例子中，最大分支是1-4-7-8，这给了我们20。为了解决这个问题，我尝试使用回溯。三角形结构存储在 'triangle':

类型的数组中

type triangle = array[1..MAX_NUM_OF_ROWS, 1..MAX_NUM_OF_ROWS] of integer;

这是我的实现：

function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer;
begin
if i = dim then
    findAux := data[i][j]
else
    if findAux(data, dim, i + 1, j + 1) > findAux(data, dim, i + 1, j) then
        findAux := data[i+1][j+1] + findAux(data, dim, i + 1, j + 1);
    else
        findAux := data[i+1][j] + findAux(data, dim, i + 1, j);
end;

function find_heaviest_path(data: triangle; dim: integer) : integer;
begin
    find_heaviest_path := findAux(data, dim, 1, 1);
end;

如您所见，我使用了一个辅助功能。不幸的是，它似乎没有给出正确的结果。对于上面看到的结构，我得到的结果是 27，减了 7 分。我错过了什么？整体实施情况如何？我应该补充一点，对于这个练习，最大行数是 100。如果需要说明，请随时询问。

Answer 1

您的 findAux 将错误的值添加到递归获得的结果中。另外，您可以使用一些局部变量稍微整理一下代码。 findAux 的更正版本：

uses math;

...

function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer;
var
    left, right: integer;
begin
    if i = dim then
        findAux := data[i][j]
    else begin
        left := findAux(data, dim, i + 1, j);
        right := findAux(data, dim, i + 1, j + 1);
        findAux := data[i][j] + Max(left, right);
    end;
end;

Pascal 中的回溯：寻找最大加权分支

Backtracking in Pascal: finding maximal weighted branch

recursion

pascal

freepascal

backtracking