13

我试图通过查看 Codility 的前缀和课程中提供的示例来掌握前缀和概念背后的想法（蘑菇选择器问题）

我的理解是，整个概念基于一个简单的属性，其中要找到数组 A 的两个位置 A(pos_left, pos_right) 之间的所有元素的总和，使用第二个数组 P，其中所有元素连续求和，搜索的位置总和计算为
value(P(pos_right + 1)) - value(P(pos_left))。

A 1 2 3 4 5  6
P 0 1 3 6 10 15 21
sum of all elements between A[2] and A[5] = 3+ 4 + 5 = 12
or using the prefix sums"   P[5+1] - P[2] = 15 -3 = 12

问题
非空向量表示的每个地方都有一条蘑菇街。给定拾取器的初始位置及其移动范围，寻找可能收集的最大蘑菇数量。

看这个例子，我不明白循环构造背后的逻辑。任何人都可以澄清这个算法的机制吗？

其次，我发现这个例子中的 positoin 索引非常混乱和麻烦。在开头用零“移位”带有前缀和的向量是常见的做法吗？（在 python 中，向量中的元素计数是从 0 开始的，这一事实已经引起了一些混乱）。

解决方案

def prefix_sums(A):
  n = len(A)
  P = [0] * (n + 1)
  for k in xrange(1, n + 1):
      P[k] = P[k - 1] + A[k - 1]
  return P


def count_total(P, x, y):
    return P[y + 1] - P[x]

# A mushroom picker is at spot number k on the road and should perform m moves
def mushrooms(A, k, m):
    n = len(A)
    result = 0
    pref = prefix_sums(A)
    for p in xrange(min(m, k) + 1):   # going left
        left_pos = k - p
        right_pos = min(n - 1, max(k, k + m - 2 * p))
        result = max(result, count_total(pref, left_pos, right_pos))
    for p in xrange(min(m + 1, n - k)):
        right_pos = k + p
        left_pos = max(0, min(k, k - (m - 2 * p)))
        result = max(result, count_total(pref, left_pos, right_pos))
    return result

我已经为一个小数组运行了一些示例A= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]，选择了位置 k=5 和范围 m = 3。我不明白创建要通过两个循环检查的范围的逻辑。

我得到以下循环参数

(p=, left_pos=, right_pos=)   
loop 1  (0,5,8), (1,4,6),(2,3,5),(3,2,5)
loop 2  (0,2,5), (1,4,6), (2,5,7), (3,5,8)

范围各不相同。为什么？

调试版本

def mushrooms2(A, k, m):
    n = len(A)
    result = 0
    pref = prefix_sums(A)
    l1 =min(m, k) + 1
    print 'loop p in xrange(min(m, k) + 1): %d' % l1
    for p in xrange(min(m, k) + 1):
        print 'p %d' % p
        print 'A= %r' % A
        print 'pref= %r' % pref
        left_pos = k - p
        right_pos = min(n - 1, max(k, k + m - 2 * p))
        result = max(result, count_total(pref, left_pos, right_pos))
        print 'left_pos = k - p= %d' % left_pos
        print 'right_pos= min(n-1,max(k,k+m-2*p))= %d' % right_pos
        print 'max'
        print '(result %d' % result
        print 'count_total(pref, left_pos, right_pos)) %r, %r, %r, %r' % (pref,left_pos, right_pos,count_total(pref, left_pos, right_pos))
        print 'result= %d' % result
        print 'next p'
    l2=min(m + 1, n - k)
    print   'loop xrange(min(m + 1, n - k)): %d' % l2
    for p in xrange(min(m + 1, n - k)):
        print 'p %d' % p
        print 'A= %r' % A
        print 'pref= %r' % pref
        right_pos = k + p
        left_pos = max(0, min(k, k - (m - 2 * p)))
        result = max(result, count_total(pref, left_pos, right_pos))
        print 'right_pos = k + p= %d' % right_pos
        print 'left_pos = max(0, min(k, k - (m - 2 * p)))= %d' % left_pos
        print 'max'
        print '(result %d' % result
        print 'count_total(pref, left_pos, right_pos)) %r, %r, %r, %r' % (pref,left_pos, right_pos,count_total(pref, left_pos, right_pos))
        print 'result= %d' % result
        print 'next p'
    print 'result %d' % result
    return result
4

2 回答 2

20

你并不是唯一一个认为循环构造违反直觉的人，因为我也不得不花几分钟时间。这是我想出来的。

现在，您提供的链接中的解决方案进一步详细说明了最佳策略是以一种仅改变一次方向的方式走在路径上。以这种方式，一个人能够覆盖具有左右端点的范围，这left_pos似乎right_pos代表。

至于循环的细节，而不是根据循环变量（即p）来考虑循环，更容易弄清楚循环过程中发生了什么变化，以及如何p使用。否则，一开始就弄清楚那些 min 和 max 表达式中的内容似乎有点太奇怪了。

例如，在第一个循环中，不是弄清楚该范围代表什么，而是尝试left_pos不同的值如何影响p获取。经过一番思考，人们注意到left_pos变化的方式符合可能的左端点。

具体来说，当 时，左端点p == 0是起始索引（即 在前一种情况下，这是左端点可以走的最远，因为它会超出道路上的有效位置范围。在后一种情况下，移动的数量禁止任何小于的解决方案，因为不可能从m 移动中的那些索引。kpmin(m, k)k < m(k - m)left_pos(k - m)k

right_pos在第一个循环中进行的分配可以类似地解释。min 语句包括(n-1)，这是可以到达的最右边的合法索引，它用于将正确的端点保持在允许的范围内。内部 max 语句的特点k，因为它是right_pos. （即由于k是起点）它也有一个表达式(k + m - 2 * p)。此表达式表示以下过程：

  • 向左走 p 步。
  • 改变方向，向右走 p 步到达起点。
  • 用剩下的(m - 2p)动作向右走。

第二个循环只是第一个循环的反映，你可以简单地通过改编我对第一个循环的解释来解释它。

至于你的第二个问题，我认为移动前缀和数组的索引不是常见的做法。我通常在在线编程竞赛中使用这种方法，我在 Python 中使用的前缀和数组的实现如下。

def prefix_sums(A):
    n = len(A)
    P = [0] * n
    P[0] = A[0]
    for k in xrange(1, n):
        P[k] = P[k - 1] + A[k]
    return P

def count_total(P, x, y):
    return (P[y] - P[x - 1] if x > 0 else P[y])

上述实现背后的基本思想是，在 处P[x]，我们有 sum A[0] + A[1] + ... + A[x]。

于 2016-10-31T10:57:31.793 回答
2

在阅读了这个主题之后，仍然很难理解这个想法，直到我实现了幼稚的解决方案（这是第一个在codility 文档中）

难以理解的解决方案 #2 只是模仿左右移动，所有这些看起来很奇怪的计算只是为了获得区域的左右限制（因为你真的会在里面移动）。所以每次迭代意味着一个完整的循环使用 6 个步骤。

如果您向左移动，然后向右移动 (p=0...M)，您有

  • 左 0 步，右 6 步（实际上 0 和 2 步导致超出数组边界），因此区域的左边界在索引 4 处，右边界在索引 6 处
  • 向左 1 步，向右 5 步（实际上是 1 和 3），所以左边界在索引 3，右边界在索引 6
  • 向左 2 步，向右 4 步（真的是 2 和 4）...继续计算

这是我的 PHP 版本，其中包含过度简化的代码和附加变量，以便于理解

function prefix_sums(array $a)
{
    $n = count($a);
    $p = array_fill(0, $n + 1, 0);
    for ($i = 1; $i <= $n; $i++) {
        $p[$i] = $p[$i - 1] + $a[$i - 1];
    }
    return $p;
}

function count_total($p, $x, $y)
{
    return $p[$y + 1] - $p[$x];
}

function mushrooms(array $a, int $k, int $m)
{
    $n = count($a) - 1;
    $max = 0;
    $sums = prefix_sums($a);
    //start  moving to the left and then the right
    for ($p = 0; $p < $m; $p++) {
        $stepsLeft = $p;
        $realStepsLeft = min($k, $stepsLeft);
        $leftBorder = $k - $realStepsLeft;

        $stepsRight = $m - $stepsLeft;
        $realStepsRight = min($n - $leftBorder, $stepsRight);
        $rightBorder = $leftBorder + $realStepsRight;

        $max = max($max, count_total($sums, $leftBorder, $rightBorder));
    }
    //moving to the right and then the left
    for ($p = 0; $p < $m; $p++) {
        $stepsRight = $p;
        $realStepsRight = min($p, $n - $k);
        $rightBorder = $k + $realStepsRight;

        $stepsLeft = $m - $stepsRight;
        $realStepsLeft = min(($k + $realStepsRight), $stepsLeft);
        $leftBorder = $rightBorder - $realStepsLeft;

        $max = max($max, count_total($sums, $leftBorder, $rightBorder));
    }
    return $max;
}

assert(ASSERT_EXCEPTION, 1);
assert(mushrooms([2, 3, 7, 5, 1, 3, 9], 4, 6) == 25);

echo 'Success';
于 2019-09-25T12:33:40.013 回答