Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2013.03.22;
Скачать: CL | DM;

Вниз

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

 
DevilDevil ©   (2012-07-10 11:56) [0]

Здравствуйте, уважаемые форумчане

Существует ряд упорядоченных чисел. (дробных, но для простоты берём целые)
Например
5 18 19 41 44 67 69 69 70 71 78 85 87 96 115 121 144 541 834 999 1001

Необходимо подобрать 8 равноудалённых "столбиков" (чисел) чтобы с их помощью закодировать числовой ряд с наименьшими потерями

Например такими "столбиками" могут быть:
 44.5    175    305.5    436    566,5    697    827,5    1058

Т.е. результат кодируется "стартом" (44.5) и "приращением" (130.5)
Все "столбики" могут выходить за диапазоны ряда
Но существуют границы возможных значений. Например от 0 до 10 000.
Все числа положительные


 
Компромисс ©   (2012-07-10 12:04) [1]

Очень похоже на интерполяцию полиномом 1-ой степени, метод наименьших квадратов тебе в помощь...


 
Дмитрий С ©   (2012-07-10 12:36) [2]


> с их помощью закодировать числовой ряд с наименьшими потерями

Еще бы вот это знать что значит


 
БарЛог ©   (2012-07-10 12:51) [3]

А ты уверен, что такие "столбики" всегда будут существовать?

1,2,5,10,999,1000


 
DevilDevil ©   (2012-07-10 13:02) [4]

Еще бы вот это знать что значит

"потеря" между числом ряда и "столбиком" = | Ч - С |
"столбик числа" - столбик максимально близкий к числу (или минимальной потерей)

"потеря" по решению = сумме потерь между (числами и их столбиками)

А ты уверен, что такие "столбики" всегда будут существовать?
1,2,5,10,999,1000


Набор чисел всегда больше восьми

Очень похоже на интерполяцию полиномом 1-ой степени, метод наименьших квадратов тебе в помощь...

а может как-то попроще ?


 
Омлет ©   (2012-07-10 13:07) [5]

Выкинь слово "столбик". Это просто точки на числовой прямой.


 
Компромисс ©   (2012-07-10 13:21) [6]


> а может как-то попроще ?


Куда уж проще...

http://helpstat.ru/2012/01/metod-naimenshix-kvadratov/


 
DevilDevil ©   (2012-07-10 13:53) [7]

Куда уж проще...

ересь какая-то
ты можешь по-человечески объяснить ?
и у меня здесь не двумерное пространство


 
Плохиш ©   (2012-07-10 14:14) [8]

Так и представляется план выпуска книг редакции:
2012 - "Метод наименьших квадратов для полных идиотов"
2013 - "Умножение и деление для полных идиотов"
2014 - "Сложение и вычитание для полных идиотов"
2015 - "Что-такое числа? Для полных идиотов"


 
Думкин ©   (2012-07-10 14:16) [9]


> 2016 - "Как правильно задавать вопросы? Для полных идиотов"


 
DevilDevil ©   (2012-07-10 14:21) [10]

Удалено модератором


 
Думкин ©   (2012-07-10 14:25) [11]

А вопроса в нормальной постановке просто нет. Есть нечто, на что можно только делать попытки угадать, что же именно хотел автор. В такие игры играть - интереса мало.


 
DevilDevil ©   (2012-07-10 14:29) [12]

Удалено модератором


 
Компромисс ©   (2012-07-10 14:30) [13]

DevilDevil ©   (10.07.12 13:53) [7]

Двумерное. Xi=i, 1<=i<=N

ЗЫ. Посмотрел анкету, в 26 лет незаконченное высшее. Зря не закончил, тут как раз высшая математика. Объяснять дальше не буду, слишком много объяснять придется, тем более, что я уже забыл детали, только самое важное помню.


 
Думкин ©   (2012-07-10 14:33) [14]


> что не понятно в вопросе ?

В первоначальной формулировке? Ну, вообще говоря все.

с пояснением в [4] уже получше. Но с кодировкой все-равно вопросы.


 
DevilDevil ©   (2012-07-10 14:37) [15]

> Компромисс ©   (10.07.12 14:30) [13]

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

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


 
Компромисс ©   (2012-07-10 14:42) [16]


> что не понятно в вопросе ?


Есть набор чисел: Y1=3, Y2=7, Y3=11
Нужно его интерполировать двумя точками (в данном случае ответ должен быть 5 и 9)
Значит, нужно найти функцию Y=AX+B
X1=1, X2=2, X3=3 и найти ее значения для X=1.5 и X=2.5.

Ответом будет Y=4X-1 при X=1.5 и X=2.5, то есть 5 и 9, как и ожидалось.
Я правильно понял вопрос? :-)


 
DevilDevil ©   (2012-07-10 14:42) [17]

> с пояснением в [4] уже получше. Но с кодировкой все-равно
> вопросы.


давай я тебе по детсадовски объясню

- есть ряд чисел
- у нас есть "палитра" из 8ми равномерных значений
- необходимо определить наиболее эффективную "палитру" с помощью которой можно представить этот ряд чисел

эффективность здесь определяется минимизацией суммы отклонений


 
DevilDevil ©   (2012-07-10 14:48) [18]

> X1=1, X2=2, X3=3 и найти ее значения для X=1.5 и X=2.5.

ээ.. вопрос то правильно..
X у нас от одного до 8 ?
и зачем нам значения X=1.5 и X=2.5 ?

B по твоей формуле - это как раз стартовая точка
а A - это коэфициент приращения


 
БарЛог ©   (2012-07-10 14:50) [19]

DevilDevil ©   (10.07.12 13:02) [4]

> Набор чисел всегда больше восьми

Ну предоставь решение для:
1,2,5,10,999,1000,1001,1002,1003

> "палитру"

Тут без паллитры и не разберёсся :)


 
DevilDevil ©   (2012-07-10 15:02) [20]

> Ну предоставь решение для:

Ну точного решения я не знаю

Но будет оно близким к:

5.00 147.29 289.57 431.86 574.14 716.43 858.71 1001.00


 
Компромисс ©   (2012-07-10 15:07) [21]


> и зачем нам значения X=1.5 и X=2.5 ?


Откуда я знаю :)

У тебя есть 50 значений, а ты хочешь на их основе 8 посчитать, вот и найди A и B из Y=AX+B, а потом посчитай Y для X=1, X=8+1/7,X=15+2/7/,X=22+3/7,X=29+4/7,X=35+5/7,X=42+6/7, X=50


 
DevilDevil ©   (2012-07-10 15:13) [22]

:))

т.е. брать вот эту формулу? http://helpstat.ru/wp-content/ql-cache/quicklatex.com-611eab674823fc6f8e5d92b2b2b259ee_l3.gif

Ты уверен что здесь X = i ?


 
Компромисс ©   (2012-07-10 15:17) [23]


> т.е. брать вот эту формулу?


А вот детали я не помню, последний раз применял этот метод больше 10 лет назад :)


> Ты уверен что здесь X = i ?


Конечно. Ты же сам написал, что есть ряд чисел, а у каждого члена ряда чисел есть порядковый номер. То есть ты привел Y(1), Y(2), ... Y(N)


 
DevilDevil ©   (2012-07-10 15:34) [24]

> Компромисс ©   (10.07.12 15:17) [23]

чёт мне кажется не подходит эта формула


 
Jeer ©   (2012-07-10 16:19) [25]

"Гадание на кофейной гуще, когда изначально был заварен чай" (С)


 
Думкин_   (2012-07-10 16:59) [26]


> DevilDevil ©  

Вот смотри. Не будем 8 точек, а рассмотрим 2 как и предлагает Компромисс. Для начала.

Как я могу понять то, что ты описал и что из этого выходит.

1. При условии наличия "столбиков" числа из набора разбиваются на непересекающиеся множества, по принципу - какой столбик ближе (в случае равенства прибиваем к любому, но одному).

2. Для всех чисел в группе считается расстояние до столбика и потом их сумма.

3. потом сумма по всем группам.

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

----------

Теперь есть группа - 3,7, 11 что предложил Компромисс. Какие будут столбики? Что ты ожидаешь увидеть?

Минимизировать тут будут такие наборы столбиков

1. Первый - 3, второй число из отрезка 7-11.
2. Первый - 11, второй число из отрезка 3-7.

В обоих случаях суммарное отклонение 4. Но скорее всего, тебе бы понравилось решение (5,9). Но в этом случае отклонение будет 6.

---------

Собственно и возникает вопрос - а что минимизируем? Может при заданном наборе столбцов считаем максимальное отклонение и потом ищем набор который имеет минимум по этому максимуму?

В такой постановке, учитывая п.1. задача становится сложнее. Но главное в другом - тебе что надо то? Правильная постановка задача - зачастую 75% ее решения.
-----------

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


 
БарЛог ©   (2012-07-10 17:15) [27]

> Правильная постановка задача - зачастую 75% ее решения.

Сейчас пойдет разговор о том, что на Мастерах одни тролли, и помочь не могут :)


 
DevilDevil ©   (2012-07-10 19:35) [28]

1. Первый - 3, второй число из отрезка 7-11.
2. Первый - 11, второй число из отрезка 3-7.

В обоих случаях суммарное отклонение 4. Но скорее всего, тебе бы понравилось решение (5,9). Но в этом случае отклонение будет 6.


Хороший пример
Исходя из постановки задачи и 7-11 и 3-7 будут оптимальными решениями. Потому что считаем разницу по модулю

Решение (5,9) наверное подойдёт если считать отклонением сумму квадратов. 16 против 12

В целом мне интересны оба способа решения. Но если найти хотя бы один - уже было бы не плохо


 
Думкин_   (2012-07-10 20:10) [29]


> Решение (5,9) наверное подойдёт если считать отклонением
> сумму квадратов. 16 против 12

Тут не понял. Это решение можно формализовать в требовании

>  Может при заданном наборе столбцов считаем максимальное
> отклонение и потом ищем набор который имеет минимум по этому
> максимуму?


И с оговоркой еще по выбору столбца и разбиением. Т.к. в этом случае надо, чтобы 7 работало на два фронта - вправо и влево. Иначе оптимальным будет или (3,9) или (11,5).
----------

С первым подходом понятно тогда в постановке. Но как с ходу искать ответ для 8 и произвольной группы - не скажу сейчас, т.к. не знаю.


 
DevilDevil ©   (2012-07-15 20:49) [30]

По поводу метода наименьших квадратов ?

Метод не подходит, потому что количество X совпадает с количеством Y

У нас по другому. Палитра из 8 элементов, а массив поступающих данных - больше


 
картман ©   (2012-07-15 23:49) [31]


> DevilDevil ©   (15.07.12 20:49) [30]


>  Палитра из 8 элементов,

любой алгоритм кластеризации, среде-арифметические кластеров будут "столбиками"


 
DevilDevil ©   (2012-07-17 17:10) [32]

> любой алгоритм кластеризации, среде-арифметические кластеров
> будут "столбиками"


Я не уверен, что алгоритм кластеризации в точности подойдёт
Потому что наши "столбики" идут друг за другом, на равном отдалении друг от друга
кроме того как быть с начальной точкой a ?
(т.е. в какой точке начинается первый столбик)


 
картман ©   (2012-07-17 17:47) [33]


> кроме того как быть с начальной точкой a ?
> (т.е. в какой точке начинается первый столбик)

метод к-средних - начальные центры могут быть случайными


 
DevilDevil ©   (2012-07-17 20:44) [34]

опиши схематично что в какой последовательности "такой" алгоритм должен сделать


 
картман ©   (2012-07-17 22:21) [35]

есть шеть чисел: 1,2,3,7,11,13 разбить на два "столбика", выбираем случайно два, например, х1=7 и  х2=16, потом считаешь отклонения(в одномерном пр-ве просто разность) е1=abs(1-7) и т .д., в первом столбике будут w1=1,2,3,7,11 во-втором w2=13, пересчитываешь "столбики" с1=(1+2+3+7+11)/5=4.8 , с2=13/1 перемещаешь числа
w1=1,2,3,7; w2=11,13 и т.д. пока числа бегают


 
DevilDevil ©   (2012-07-18 00:52) [36]

завтра обдумаю
спасибо !


 
Студент   (2012-07-18 01:04) [37]

Сортировка слиянием? Когда до меньшего деления доходишь вместе массив не собираешь?


 
DevilDevil ©   (2012-07-18 01:36) [38]

> картман © (17.07.12 22:21) [35]

Опиши ещё раз.. Если чисел допустим 8, а столбиков 4. Потому что с двумя - принцип не ясен

> Студент   (18.07.12 01:04) [37]

что ты имеешь ввиду ?
давай цифрами что ли )


 
Студент   (2012-07-18 03:20) [39]

DevilDevil ©   (18.07.12 01:36) [38]

http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC


 
DevilDevil ©   (2012-07-18 09:25) [40]

> Студент   (18.07.12 03:20) [39]

а почему не быстрой сортировкой ? )))))))))))))))



Страницы: 1 2 вся ветка

Текущий архив: 2013.03.22;
Скачать: CL | DM;

Наверх




Память: 0.57 MB
Время: 0.06 c
2-1338803238
rioko
2012-06-04 13:47
2013.03.22
Работа с нетипизированными файлами более 2 гигабайт


2-1342945485
Ярослав
2012-07-22 12:24
2013.03.22
Склейка формы


2-1332009690
теркин
2012-03-17 22:41
2013.03.22
Использование полиморфных объектов


2-1341126507
Pcrepair
2012-07-01 11:08
2013.03.22
ПОчему ДЕЛФИ без спроса создает-уничтожает TStringList?


15-1347609677
Dmitry87
2012-09-14 12:01
2013.03.22
Запуск программы от имени текущего пользователя