TUZ_2-07 Поиск точки опоры физических весов_Разбор

TUZ_2-07* Поиск точки опоры физических весов
Разбор различных способов решения.
Пусть SL_i - сумма "моментов весов" слева от перекладины, а SR_i справа от перекладины при положении перекладины в позиции i.
Тогда возможны следующие алгоритмы:

1. Перебор всех позиций i, "прямое" вычисление  SL_i, SR_i и их сравнение. 

• Достоинство - простота кода, надежность решения
• Недостаток - сложность O(N²), где N - длина списка

2. Перебор позиций i, то тех пор, пока SL-SR <= 0 ( "прямое" вычисление  SL_i, SR_{i )}. 

• Достоинство - простота кода, надежность решения, примерно в два раза быстрее алгоритми I
• Недостаток - сложность O(N²), где N - длина списка

3. Исследование структур и взаимосвязи SLi и SRi и попытка упрощения алгоритма до сложности O(N), где  Т - длина списка.
   Это и будет рассмотрено в тетради

Описание I можно посмотреть в тетради

 

TUZ_2-07 Поиск точки опоры физических весов
2.7. Поиск точки опоры физических весов
Под «точкой опоры» подразумевается точка равновесия в списке весов, где общий вес на левой стороне равен общему весу на правой стороне.
Эта задача требует определить позицию в непустом списке числовых значений, которая может служить опорой и сбалансировать вес обеих сторон.
Согласно принципам физики, перекладина весов достигает равновесия, когда силы, действующие на оба ее конца, равны.
Ваша задача: написать функцию, которая принимает список чисел и возвращает положение точки опоры, уравновешивающей веса.
Это должно быть целое или рациональное число. (рациональное число задается числителем и знаменателем)
В табл. 2.7 показаны ожидаемые результаты для некоторых входных данных.

Таблица 2.7. Некоторые ожидаемые результаты для разных входных значений в задаче поиска точки опоры
Веса	Ожидаемый результат
6, 6, 9	(15, 7)
43, 51, 35, 4	2
19, 25, 5, 42, 38, 8, 34, 16, 14, 8, 47, 42, 4, 20, 23	8
7, 24, 3, 38	3

Пояснение - нумерация позиций начинается с 1

Алгоритм
Будем считать, что есть список масс W=[w₁, w₂,...,w_n], крторые расположены в точках с координатами 1,2,..., n.
Рассмотрим расположение "перекладины! в точке с номером j и определим SLj, SRj (веса слева и справа), положив:

• \(SL_j=w_1\cdot|j-1|+\cdots+w_{j-1}\cdot|j-(j-1)|\) - сумма весов (моментов масс) элементов "слева" от перекладины;
• \(SR_j=w_{j+1}\cdot|(j+1)-j|+\cdots+w_{j-1}\cdot|n-j|\) - сумма весов (моментов масс) элементов "справа" от перекладины;

Также определим S, Sj- и Sj+, положив:

• \(S=w_1+\cdots+w_{n} \) - сумма всех элементов 
• \(S_{j-}=w_1+\cdots+w_{j-1} \) - префиксная сумма элементов "до j"
• \(S_{j+}=w_{j}+w_{j+1}+\cdots+w_{n} \) - префиксная сумма элементов "от j" 

Нетрудно заметить, что:

• \(S_{j+}=S-S_{j-}\)
• \(SL_{i}=SL_{i-1}+S_{i-}\)
• \(SR_{i}=SR_{i-1}-S_{i+}=SR_{i-1}-S+S_{i-} \)

Таким образом, получаем, что:

• \(SR_{i}-SL_{i}=SR_{i-1}-SL_{i-1}-S=\cdots=SR_{0}-SL_0 - i\cdot S \)
• где \(SL_0=0;\ SR_0=1\cdot w_1+2\cdot w_2+\cdots+n\cdot w_n \)
• значит решения для перекладины есть \(j=\frac{SR_0}{S}=\frac{\Sigma\ j\cdot w_j}{\Sigma\ w_j}\) или средневзвешенное значений позиций массами в этих позициях.
  Нетрудно заметить, что позицию центра тяжести системы на прямой и это значение будет целым, если SR₀ кратно S

Сложность нахождения SR₀ и S составляет O(n)
 

Понять, что достаточно найти центр тяжести можно было и без таких больших выкладок. 
Однако, если рассмотреть задачу для поиска j -места сбора всех элементов, со стоимостью перевозки равной \(w_i\cdot |j-i|\) 
мы поймем, что надо миминизировать значение SL_j+SR_j и для этого нам могут пригодиться преобразования, сделанные выши.
Более подробно рассмотрим это в тетради