ここで、Codility による Prefix Sum レッスンで示されている例を参照して、Prefix Sum の概念の背後にあるアイデアを把握しようとしています(マッシュルーム ピッカーの問題) 。
私の理解では、概念全体が単純なプロパティに基づいており、配列 A の 2 つの位置 A(pos_left, pos_right) 間のすべての要素の合計を見つけるために、すべての要素が連続して合計され、検索された場所で 2 番目の配列 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
問題
空でないベクトルで表されるすべての場所にキノコのある通りがあります。ピッカーの初期位置とその移動範囲を考慮して、収集できる最大数のキノコを探します。
例を見ると、ループの構築の背後にあるロジックがわかりません。このアルゴリズムの仕組みを説明できる人はいますか?
第 2 に、この例のポジショインのインデックス付けが非常にわかりにくく、扱いにくいことがわかりました。接頭辞の合計でベクトルを最初にゼロで「シフト」するのは一般的な方法ですか? (ベクター内の要素のカウントは、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 を選択しました。2 つのループでチェックする範囲を作成するロジックがわかりません。
ループの次のパラメーターを取得します
(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