查找数组是否平衡的算法 [英] Algorithm for finding if an array is balanced

问题描述

我正在尝试创建一个程序，该程序将创建10个元素的数组，然后为每个元素分配随机值。然后，我希望程序判断数组是否平衡。所谓平衡，是指数组值中某处某个元素的值之和等于该元素中数组值之和大于当前元素。

I'm trying to create a program that will create a 10 element array and then assign random values to each element. I then want the program to tell if the array is balanced. By balanced I mean, is there anywhere in the array values that at a certain element the sum of the values in the elements are equal to the sum of the array values in the elements greater than that current element.

示例

元素（1,2,3,4）值（2,1,3,0 ）
然后程序将显示元素1-2与元素3-4平衡，因为它们都等于4。

Element (1,2,3,4) Values (2,1,3,0) The program would then display that elements 1-2 are balanced to elemtns 3-4, because they both equal 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，那么我想这就是开始的方法。

I figured the only way the elements could be balanced is if the values average is equal to 2, so I figured that's how I should start.

推荐答案

如果我理解这个问题，最简单的解决方案是这样的：

If I understand the question, the simplest solution is something like this:

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)

（那没有打印任何内容，因为它返回了无，这意味着没有平衡列表的要点。）

(That didn't print anything, because it returned None, meaning there is no pivot to balance the list around.)

这是最简单的解决方案，它显然不是最有效的，因为您不断将相同的数字一遍又一遍地加起来。

While this is the simplest solution, it's obviously not the most efficient, because you keep adding the same numbers up over and over.

，很容易弄清楚如何保持 left_total 和 right_total 的运行总计，仅调用 sum 一次。

If you think about it, it should be pretty easy to figure out how to keep running totals for left_total and right_total, only calling sum once.

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

---

最后，这是围绕它构建程序的方法：

---

Finally, here's how you can build a program around it:

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))

这篇关于查找数组是否平衡的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！