时间戳

首页 > 解决方案 > 向下滑动金字塔时位移以决定左或右方向

java - 向下滑动金字塔时位移以决定左或右方向

问题描述

我正在解决“金字塔下滑”问题（https://www.mathblog.dk/project-euler-18/），我需要帮助更直观地理解更新索引变量的解决方案背后的逻辑内循环。

算法：

int posSolutions = (int)Math.Pow(2, inputTriangle.GetLength(0) - 1);
int largestSum = 0;
int tempSum, index;
 
for (int i = 0; i <= posSolutions; i++) {
    tempSum = inputTriangle[0, 0];
    index = 0;
    for (int j = 0; j < inputTriangle.GetLength(0) - 1; j++) {
        index = index + (i >> j & 1);
        tempSum += inputTriangle[j + 1, index];
    }
    if (tempSum > largestSum) {
        largestSum = tempSum;
    }
}

我一直在尝试了解index变量是如何更新的以及它的用途。据我了解index，我们使用了金字塔中的所有可能路径（正如解决它的人所说“它用于决定是向右还是向左走”）。但是我很难理解这个表达式中发生了什么：

index = index + (i >> j & 1);

所以，这就是我所在的位置：

内循环循环的次数与金字塔的楼层一样多（-1 因为顶层）。我们必须确保在每次迭代中，从我们的出发点开始，我们必须覆盖所有可能的左右组合，一直到底层——这就是我们index的用途。但我不知道我怎么会想出这种表达方式。我已经尝试通过不同的金字塔楼层，记录不同的变量等，但我无法围绕表达式。

非常感谢任何人的任何输入、建议或解释。谢谢！

标签： javaalgorithmbit-manipulation

解决方案

以下是该算法的工作原理：

for (int i = 0; i <= posSolutions; i++) {

该循环旨在检查所有可能的解决方案。正在检查的解决方案由 表示i。它本质上是一个长度与三角形深度相同的位图。对于每一位，0 表示向左，1 表示向右，因此每个值唯一地表示从三角形顶部到底部的路径。

index = 0;

该index变量表示要在“当前”级别中查找的值。它从 0 开始，因为顶层只有 1 个值。然后必须为每个后续级别增加 0（如果向左）或 1（如果向右），以确保为当前解决方案添加正确的值i。例如，如果您在一个级别中的位置 6，那么您需要移动到下一级中的位置 6 或位置 7，具体取决于相应位是否设置在 中i。

for (int j = 0; j < inputTriangle.GetLength(0) - 1; j++) {

正如你所指出的，j是金字塔的层次，从顶部开始。

    index = index + (i >> j & 1);

这是根据当前解决方案是要向左还是向右向索引添加 0 或 1 的表达式。将当前层的i >> j位移到最右边的位置（即技术上的最低有效位）。然后清除除最右边之外的所有位，留下 0 或 1。然后将此值添加到索引中以指向当前级别的正确值。ij& 1

例如，如果正在查看的解决方案 ( i) 是 12（或二进制 1100）并且我们正在考虑第三级，那么index将是 0 和j2。因此i >> j将i右移 2 位以产生 11（二进制）。& 1将清除除最右边之外的所有位以产生 1。现在将其添加到index，我们知道要查看第 2 行中的位置 1。

    tempSum += inputTriangle[j + 1, index];

这会将当前级别的值添加到总和。

if (tempSum > largestSum) {
    largestSum = tempSum;
}

一旦您获得了当前可能解决方案的总数i，就会将其与之前找到的最大总数进行比较。

最后几点：首先，您发布的代码中的变量命名不直观。更好的命名会使这个算法更容易理解。其次，有比你发布的蛮力算法更好的算法来解决这个问题。它们从底部向上工作，并且具有更易于理解的额外优势（在我看来）。

推荐阅读