Форум: "Прочее";
Текущий архив: 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.07 c