Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];

Вниз

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

 
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;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.56 MB
Время: 0.065 c
15-1343728350
Miau
2012-07-31 13:52
2013.03.22
Delphi+1C


15-1354048202
Юрий
2012-11-28 00:30
2013.03.22
С днем рождения ! 28 ноября 2012 среда


3-1280093798
Alexkont
2010-07-26 01:36
2013.03.22
Запрос с датами и временем к Access


2-1338391814
Serge Petrov
2012-05-30 19:30
2013.03.22
TWebBrowser и обновление элемента веб-страницы


2-1333633351
Jimmy
2012-04-05 17:42
2013.03.22
Как правильно отобразить картинку с полупрозрачными пикселями?





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский