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

Jean Francois Clout 发表于 Dev

让·弗朗索瓦·克卢特

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

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

在此示例中，最大分支是1-4-7-8，这给了我们20。为解决此问题，我尝试使用回溯。三角形结构存储在“三角形”类型的数组中：

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。如果需要澄清，请不要犹豫。

潜伏者

您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;