-3

10 要素の配列を作成し、各要素にランダムな値を割り当てるプログラムを作成しようとしています。次に、配列がバランスが取れているかどうかをプログラムに知らせたいと思います。つまり、特定の要素で、要素の値の合計がその現在の要素より大きい要素の配列値の合計と等しい配列値のどこかにあるということです。

例

Element (1,2,3,4) Values (2,1,3,0) 次に、プログラムは、要素 1 ～ 2 が要素 3 ～ 4 とバランスが取れていることを表示します。これらは両方とも 4 に等しいからです。

これまでのところ、

import random

size = 10
mean = 0
lists = [0] * size
for i in range(size):
    var = random.randint(0,4)
    lists[i] = var

for i in lists:
    mean += i

avg = (mean)/(size)

要素のバランスをとることができる唯一の方法は、値の平均が2に等しい場合であると考えたので、それが私が始めるべき方法だと考えました.

正しい方向への助けをいただければ幸いです。

4

2 に答える 2

5

質問を理解していれば、最も簡単な解決策は次のようなものです。

def balanced(numbers):
    for pivot in range(len(numbers)):
        left_total = sum(numbers[:pivot])
        right_total = sum(numbers[pivot:])
        if left_total == right_total:
            return pivot
    return None

例えば：

>>> numbers = [2, 1, 3, 0]
>>> balanced(numbers)
2
>>> more_numbers = [2, 1, 3, 4]
>>> balanced(numbers)

(これは を返したため、何も出力しませんでした。これNoneは、リストのバランスをとるためのピボットがないことを意味します。)

これは最も単純な解決策ですが、同じ数値を何度も加算し続けるため、明らかに最も効率的ではありません。

考えてみれば、 と の合計をleft_total1回right_totalだけ呼び出して実行し続ける方法を理解するのは非常に簡単なはずsumです。

def balanced(numbers):
    left_total, right_total = 0, sum(numbers)
    for pivot, value in enumerate(numbers):
        if left_total == right_total:
            return pivot
        left_total += value
        right_total -= value
    return None

最後に、これを中心にプログラムを構築する方法を次に示します。

size = 10
numbers = [random.range(4) for _ in range(size)]
pivot = balanced(numbers)
if pivot is None:
    print('{} is not balanced'.format(numbers))
else:
    print('{} is balanced, because elements 1-{} equal {}-{}'.format(
        numbers, pivot+1, pivot+2, size+1))
于 2013-05-08T00:32:55.960 に答える
0

この種の問題について知っておくとよいデータ構造は、累積和を持つ配列です。元のシリーズのからまでelement[j] - element[i]の合計です。元のシリーズがある場合、累積シリーズはです。元のシリーズの位置までの合計はです。この問題では、0 から始まる合計のみに関心があるため、これは少しやり過ぎですが、他の問題ではより完全に役立ちます。ij[1, 2, 3, 4][0, 1, 3, 6, 10]ielement[i] - element[0]

累積合計を作成するコードは次のとおりです。

def cumulative_sum(series):
    s = [0]
    for element in series:
        s.append(element + s[-1])
    return s

それを考えると、次のコードでピボット ポイントを見つけることができます。

def find_pivot(series):
    cs = cumulative_sum(series)
    total = cs[-1]
    even_total = not (total & 1)
    if even_total:
        target = total // 2
        for i, element in enumerate(cs[1:]):
            if element == target:
                return i + 1
    return -1

系列の合計が奇数になることがわかっている場合は、系列を分割する必要がないことに注意してください。その場合、ピボット ポイントは存在しません。

find_pivotまたは、次のように書くこともできます。

def find_pivot(series):
    cs = cumulative_sum(series)
    total = cs[-1]
    even_total = not (total & 1)
    if even_total:
        target = total // 2
        try:
            return cs.index(target)
        except ValueError:
            return -1
    return -1

ループが Python で明示的に行われるのではなく、標準ライブラリの C コードで行われるという利点があります。

コードを試す:

def test():
    for i in range(1, 30):
        test_values = range(i)
        j = find_pivot(test_values)
        if j >= 0:
            print "{0} == {1}".format(test_values[:j], test_values[j:])

そして、次の出力が得られます。

[0] == []
[0, 1, 2] == [3]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] == [15, 16, 17, 18, 19, 20]
于 2013-05-08T03:17:06.497 に答える