Модели числовых последовательностей

[niko-a8]

Друзья, хочу обратиться за консультацией по следующему вопросу:

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

Пример, который решается просто: Поиск наличия общего итога в числовой последовательности.
Исходные данные, могут содержать общий итог, который может быть как первым, так и последним элементом последовательности.
Решение:
- находим $MaxValue = \max(FirstValue{set} | LastValue{set})$
- рассчитываем сумму всех элементов кроме без $Total = \sum({set}) - MaxValue$
- если $MaxValue = Total$, то считаем что есть вероятность наличия общего итога

Пример, который не получается решить: Поиск наличия подитогов в числовой последовательности.

Прошу помощи, в какую сторону копать чтобы понять, как можно определить, есть ли в последовательности чисел вероятность наличия подитогов?

[mihaild]

Непонятно, причем тут язык. Вы хотите проверить, верно ли, что последовательность разбивается на части, в каждой из которых первый или последний элемент является суммой остальных? Или что?

[niko-a8]

mihaild в сообщении #1480492 писал(а):

Непонятно, причем тут язык. Вы хотите проверить, верно ли, что последовательность разбивается на части, в каждой из которых первый или последний элемент является суммой остальных? Или что?

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

Да, верно, необходимо проверять, разбивается ли последовательность на части, для которых первый или последний элемент является суммой всех остальных. Какие математические (статистические) формулы/выражения могут это проверить. Или тут нужны не формулы/выражения, а что-то совсем другое?

[mihaild]

Если точное равенство - то это алгоритмическая задача. Решается, например, динамикой (для каждого отрезка смотрим, удовлетворяет ли он сам нужному свойству, или разбивается ли на удовлетворяющие).

[niko-a8]

mihaild в сообщении #1480508 писал(а):

Если точное равенство - то это алгоритмическая задача. Решается, например, динамикой (для каждого отрезка смотрим, удовлетворяет ли он сам нужному свойству, или разбивается ли на удовлетворяющие).

Важное дополнение, что числовая последовательность может быть длиной от 10 тыс до 100 млн значений.
Перебирать все варианты отрезков проблематично по ресурсам сервера и времени таких обработок.

[mihaild]

Ага, то есть квадрат не подходит, хотим быстрее.
Могут ли некоторые подитоги идти до соответствующего им отрезка, а некоторые после? Могут ли значения быть отрицательными? Если нет - то просто проверяем два варианта (сумма слева/справа), два прохода с доп. памятью на один элемент.

[Pphantom]

Тема перемещена из форума «Экономика и Финансовая математика» в форум «Computer Science»
Причина переноса: связь этого с экономикой, если и имеется, для решения задачи явно несущественна.

[niko-a8]

Приношу извинения, что недостаточно подробно описал задачу.

Принимаем следующие соглашения:
1. Последовательность состоит из положительных или отрицательных чисел имеющих точность 4 знака после запятой.
Могут принимать значения от -1 * 10^12 до 1 * 10^12
2. Числовая последовательность может иметь от 10 тыс до 100 млн значений
3. Подитоги групп чисел для всей последовательности могут быть указаны только в конце группы

[mihaild]

Если числа были указаны точно (или известны правила округления - т.е. можно детерменированно восстановить сумму), то решается в один проход с линейной доп. памятью - бежим по последовательности, и запоминаем какие суммы префиксов возможны.

[niko-a8]

mihaild в сообщении #1480650 писал(а):

Если числа были указаны точно (или известны правила округления - т.е. можно детерменированно восстановить сумму), то решается в один проход с линейной доп. памятью - бежим по последовательности, и запоминаем какие суммы префиксов возможны.

А можно для "школьников" подробнее описать проход по пунктам?

[mihaild]

По пунктам - запрещено правилами.
Пусть $k$-й отрезок заканчивается в позиции $i$, $k-1$-й - в позиции $j$, и сумма элементов от начала до $i$-го равна $s$. Чему равна сумма элементов от начала до $j$-го?