ряды

← →
ТНЕ картман (2014-04-09 17:28) [0]

есть массив: 1, 2, 12, 24, 30, 36, 47
из него нужно получить массив(ы) чисел, с примерно одинаковой разностью смежных элементов: (a[i+1] - a[i]) <= (some_const)

Что об этом можно почитать?

← →
brother © (2014-04-09 17:39) [1]

> с примерно

в программистике такого нет...

← →
ТНЕ картман (2014-04-09 17:42) [2]

> brother © (09.04.14 17:39) [1]
>
> > с примерно
>
> в программистике такого нет...

тогда так:
(a[i+1] - a[i]) <= some_func(some_params)

← →
brother © (2014-04-09 17:51) [3]

задача не понятна, из массива получить массивы?
на примере бы показали...

← →
ТНЕ картман (2014-04-09 18:24) [4]

[1, 2, 12, 24, 30, 36, 47]
два решения:
[1, 12, 24, 36, 47]
и
[24, 30, 36]

← →
й (2014-04-09 19:10) [5]

1) пройтись 1 раз по сортированному массиву, составляя список всех возможных разностей, содержащий в каждом члене количество встретившихся с этой разностью случаев
(этот список, отсортированный по разностям, можно рассматривать как гистограмму)
2) осталось найти требуемое количество максимумов сумм соседних членов требуемой ширины и объема

← →
Павиа (2014-04-09 19:44) [6]

Передискретизация:
1) Аппроксимация
2) Фильтрация

Думаю вам больше через сплайн аппроксимацию подойдёт.

← →
R. (2014-04-09 21:15) [7]

Ну какая аппроксимация? Из примера видно: сделать выборку из имеющегося при критерии равенства промежутков между элементами ряда.
ИМХО, смотреть надо в сторону динамического программирования сначала. А может пройдет и простое: построить массивы разностей соседних элементов, черезх один и т.д. , а потом взять и упорядочить по их элементам по возрастанию (с запоминанием номера массива). Останется выбрать ряд, различающийся не более чем на 1-2.

← →
Romkin © (2014-04-09 21:23) [8]

Э. В обсчем, я хотел сказать что строим матрицу, строки - разности. Первая - соседних элементов, вторая - через один и т.д. Далее выбираем ряд по одному элементу из каждого столбца.
[1,2,12,24,30,36,47]

01,10,12,06,06,11 -> 24,30,36 это (6,6) дают
11,18,17
23,23
из подбора (11,10, 12, 11) еще собрать по столбцам. Еслия не ошибся в арифметике, то это 1, 12, 24, 36, 47 должно быть.
Все, я по пиву.

← →
Romkin © (2014-04-09 21:26) [9]

А, ну да, (23,23) - это 1,24,47 которых в [4] нет, почему?

← →
картман © (2014-04-09 21:44) [10]

> Romkin ©

шикарно

> нет, почему?

вай! не заметил))

← →
Romkin © (2014-04-10 11:46) [11]

На самом деле не так все просто, как мне кажется. Лучше взять ряд два раза и строить ряды разностей смещая второй ряд на 1 элемент относительно первого в цикле.
Вот тогда все разности будут, остается сделать их записями вида (разность, элемент, смещение), упорядочить в этом порядке полей и пройти по массиву ища почти одинаковые разности подряд.
Сложность O(n^2), не слишком хорошо, но сойдет для небольших рядов.

← →
ТНЕ картман (2014-04-10 11:53) [12]

> Romkin © (10.04.14 11:46) [11]

это понятно - подумал, ты упростил для наглядности))

Не, это у меня автопилот так работает :D

> из него нужно получить массив(ы) чисел, с примерно одинаковой
> разностью смежных элементов

получишь кучу массивов из 2-х элементов ))))))))))))))))

> oldman © (11.04.14 13:37) [14]
>
>
> > из него нужно получить массив(ы) чисел, с примерно одинаковой
> > разностью смежных элементов
>
>
> получишь кучу массивов из 2-х элементов

шо ж делать? Введу всякие эвристики, отсеивающие ненужное. А вот что делать, если интересующий меня элемент будет в единственном экземпляре - вопрос...

> На самом деле не так все просто, как мне кажется

Всё проще, чем кажется.
Надо строить матрицу МОДУЛЕЙ разностей, это я согласен, НО она получится диагональная!
первая строка состоит из разностей всех элементов и первого, вторая из всех элементов - второй и т.д. Каждая строка получится короче предыдущей на один элемент и последняя строка будет из одного элемента (последний-предпоследний).
Пример: 1, 2, 12, 24, 30, 36, 47
матрица:
2 12 24 30 36 47
1 1 11 23 29 35 46
2 0 10 22 28 34 45
12 0 0 12 18 24 35
24 0 0 0 6 12 23
30 0 0 0 0 6 17
36 0 0 0 0 0 11
Дальше собираем полученные разницы в один массив, сортируем и наслаждаемся:
1 6 6 10 11 11 12 12 17 18 22 23 23 24 28 29 34 35 35 45 46

Получаем решения для точного равенства
6 6 (24,30)(30,36)
11 11 (12,1)(47,36)
12 12 (12,24)(24,36)
23 23 (1,24)(24,47)
35 35 (1,36)(12,47)
Выбираем из решений те пары, в которых элементы повторяются и получаем
6 6 (24,30)(30,36) = (24,30,36)
12 12 (12,24)(24,36) = (12,24,36)
23 23 (1,24)(24,47) = (1,24,47)
Вот так вот и никаких O(n^2) (наверное) :)

Блин, некрасиво матрица в посте получилась, надо нолики добавить, может красивше станет и понятнее:
00 2 12 24 30 36 47
01 1 11 23 29 35 46
02 0 10 22 28 34 45
12 0 0 12 18 24 35
24 0 0 0 06 12 23
30 0 0 0 0 06 17
36 0 0 0 0 0 11

АЙ, ШАЙТАН!!!
00 02 12 24 30 36 47
01 01 11 23 29 35 46
02 00 10 22 28 34 45
12 00 00 12 18 24 35
24 00 00 00 06 12 23
30 00 00 00 00 06 17
36 00 00 00 00 00 11

ряды Найти похожие ветки