← All posts tagged algorithms

Есть значение, изменяющееся со временем. Нужно измерить его среднее значение за некоторый промежуток времени (несколько секунд). Измерения будут происходить раз в некоторый промежуток времени (можно менять).
Мог бы просто копить сумму замеров и их количество, а в конце тупо посчитать среднее (с помощью технологии вещественного деления) но боюсь, что аккумулятор переполниться может, вернее в конце он начнет принимать большие значения и нормально прибавлять к нему замеры уже не получится (без большой потери точности).
Как такое большие дядьки делают?

Есть у нас произвольный направленный взвешенный граф. Задача: разложить его оси (на одном измерении, тобиш) так, чтобы сумма квадратов разностей междц весом дуг и их реальными длинами была минимальна
То есть, для простейшего графа из двух вершин имеем:
первая точка — кордината = 0
вторая точка — кордината = x
вес дуги = 1
направление дуги от первой точки ко второй
Тогда:
квадрат разности у нас будет (1 — (x — 0))^2 = (1-x)^2
Тут мы дифференцируем по x и все зашибись, решаем уравненице линейное.
Но когда у нас 3 и более вершины, то все сложнее, там вылезают произведения вида x1*x2 + x2*x3 и так далее

В связи с этим вопрос: есть ли готовые решение по подобному раскладыванию графа, ну не первый же я решаю такое? И второе: если такого нет, то как решать многочлены вида
A*x1^2 + B*x1*x2 + C*x2*x3 + D*x2^2 ..... = 0
?

Вот смотри, жуик, есть задача генерации файлов определенного формата. Формат я уже разгадал, с этим проблем нет, осталось придумать алгоритм генерации случайных данных.
Данные представляют из себя 4 потока цифр — показания датчиков на некотором участке длины. Нужно сформировать случайные данные "похожие на правду".
Правда заключается в следующем: на всем участке датчики обычно показывают прямую линию, в которую подмешан некоторый шум, но шум не просто белый, а как-бы кгадкий, чем-то похожий на графики цен акций, или типа того, то есть, есть некоторое блуждание. Также, встречаются "деффекты", заключающиеся в резких скачках-впадинах, также обладающих определенным паттерном. Есть еще обрывы, в которых датчик непрерывно показывает 0xFFFF. Все это должно генерироваться случайным образом в большом количестве и быть "похожи на правду". Вобщем, какие есть идеи, может на эту тему есть статейки/паперы, она ведь наверно давно изучена? Прозреваю, что генерация карт и окружений для игор имеет много общего с этим.
Сделать мне это надо за выхи.