Как сделать вместо 40 циклов 1?

Question

Мой код складывает два соседних числа и делит на 2, в результате чего список каждый раз уменьшается на 1. Как сделать вместо 40 циклов один?

array = '1101111011010101110101010010011010100100'
array = [i + 1 for i in range(len(array)) if array[i] == '1']
count0, count1, count = 0, 1, []
print(len(array))
for i in array:
    count.append((array[count0] + array[count1]) / 2)
    count0 += 1
    print(count0)
    if count0 == len(array) - 1:
        break
    else:
        count1 += 1

Вот на простом примере:

a = [1, 2, 4, 5, 6]
a = [1.5, 3, 4.5, 5.5]
a = [2.25, 3.75, 5]
a = [3, 4.375]
a = [3.6875]

Это не среднее число списка - должно получиться 3.6

Answer 1

В списке длиной N+1 (заметьте +1) нужно сложить числа с коэффициентами для K-го числа (нумерация с нуля) С(N, K) / 2^(N), т.е.

Result = Sum(k=0..N){A[K]*C(N,K)/2^N} = 1/2^N * Sum(k=0..N){C(N,K)*A[K]}

где С(N, K) - биномиальные коэффициенты

Например, для списка длиной 5 будут коэффициенты из 4-го ряда треугольника Паскаля 1,4,6,4,1, разделённые на 16

def cnk(n, k):
    k = min(k, n - k)
    if k <= 0:
        return 1 if k == 0 else 0
    res = 1
    for i in range(k):
        res = res * (n - i) // (i + 1)
    return res

def freaksum(a):
    n = len(a) - 1
    return sum([a[k] * cnk(n, k) for k in range(n+1)]) / 2**n

l = [1, 2, 4, 5, 6]
print(freaksum(l))

>>> 3.6875

Здесь коэффициенты рассчитываются по ходу дела, но, имея предрасчитанный треугольник Паскаля, результаты для набора списков можно получать более оптимально.

P.S. Между прочим, всё это действие по большому счёту эквивалентно наложению Гауссова фильтра

для проверки:

def repsum(a):
    while len(a) > 1:
        b = []
        for i in range(len(a) - 1):
            b.append((a[i] + a[i + 1]) / 2)
        a = b[:]
    return a[0]

l = [1,2,3,4,8,9,10,13,14,15,19]
print(freaksum(l))
print(repsum(l))

БЛОГ НА HUSL

Как сделать вместо 40 циклов 1?

Ответы (1 шт):