|
|
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Penkov VladimirМетод МайороваКороче тут два критерия, с памятью допустим можно чтото придумать. Но нужно придумать чтото с эвристикой. Например если элементов будет 1 млн. то решение перебором будет (1млн * на пробежаться по 1 млн) тоесть уже миллиард. А это недопустимо. ну не миллиард а все-то то лишь количество делителей*N нет, длина группы может быть любой. Если последняя группа будет не полной, ничего страшного ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:36 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Penkov VladimirМетод МайороваКороче тут два критерия, с памятью допустим можно чтото придумать. Но нужно придумать чтото с эвристикой. Например если элементов будет 1 млн. то решение перебором будет (1млн * на пробежаться по 1 млн) тоесть уже миллиард. А это недопустимо. ну не миллиард а все-то то лишь количество делителей*N да, вот эвристика - очевидно, что длина группы не более длины максимальной последовательности серых элементов. то есть ограничение сверху, какое никакое ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:36 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Penkov Vladimirда, вот эвристика - очевидно, что длина группы не более длины максимальной последовательности серых элементов. то есть ограничение сверху, какое никакое да, ето одно из условий может быть. Еще что можно придумать ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:38 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Метод МайороваPenkov Vladimirда, вот эвристика - очевидно, что длина группы не более длины максимальной последовательности серых элементов. то есть ограничение сверху, какое никакое да, ето одно из условий может быть. Еще что можно придумать ? можно свести задачу к сети и поискать максимальный путь. алгоритмы есть ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:40 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Penkov VladimirМетод Майоровапропущено... да, ето одно из условий может быть. Еще что можно придумать ? можно свести задачу к сети и поискать максимальный путь. алгоритмы есть собственно это ж и есть NP задача. в худшем случае только перебором ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:40 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
про эту задачу я знаю, просто не вижу явной связи с этой задачей. Если найдете связь опишите алгоритм. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:43 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
связать можно так (в общем случае): узлы - это множество разбиений (умное слово есть для него, но я забыл. фактор-множество что ли) последовательности вес ребра - вес узла, в который мы идем. найти максимальный путь причем, в данном случае множество узлов сильно ограничено, так как есть условие на одинаковость длины подпоследовательностей это что я сходу придумал. наверно можно покрасивше придумать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:47 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
но мы же не можем представить множество разбиений, оно велико ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:51 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Метод Майоровано мы же не можем представить множество разбиений, оно велико поэтому я изначально не связывался с графами. проще побегать в цикле по массиву ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:52 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Penkov VladimirМетод Майоровано мы же не можем представить множество разбиений, оно велико поэтому я изначально не связывался с графами. проще побегать в цикле по массиву но такая прикидка на графы показывает что задача сводится с NP, собственно дальше чо уж думать то... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:54 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
пока приходит на ум, пробежаться по последовательности и найти "островки". Тоесть элементы которые друг к другу максимально приближены. Получается последовательность "островков". Теперь с каждого "островка" взять первое число, остальные выбросить и сформировать новую последовательность чисел, повторить операцию по сворачиванию в "островки" наиболее близких по расположению элементов. И так до тех пор пока последовательность не будет свернута в один элемент. Наиболее удачный делитель при всех этих операциях сворачивания и будет искомой длиной группы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:57 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
я думал в качестве делителей брать длины серых последовательностей. но это бьет по памяти ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 18:58 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Penkov Vladimirя думал в качестве делителей брать длины серых последовательностей. но это бьет по памяти да здесь может быть два подхода, или плясать от серых или от заполненых. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 19:00 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Почему-то никто не задал пару главных вопросов: - а как строится последовательность "серых" значений? - а исходная последовательность строго монотонно возрастающая? Нет, умозрительно по примеру мы допёрли, что это все натуральные от min(A) до max(A), но это ведь для данного конкретного примера... Или нам, действительно, считать это за известное ограничение - "рассматриваем подмножество из некоторого количества последовальных натуральных (целые к ним приводятся элементарным нормированием) чисел"? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 19:15 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
AndreTMПочему-то никто не задал пару главных вопросов: - а как строится последовательность "серых" значений? Последовательность серых не строится. Строится обычная последовательность в возрастающем порядке целых чисел. Среди этих целых могут быть "пропущены" многие промежуточные числа. Физический смысл всего этого - представить в памяти компьютера последовательность чисел равными блоками, часть из которых будут виртуальные ( тоесть серые ) и не будут требовать доп. выделения памяти ОЗУ. AndreTM- а исходная последовательность строго монотонно возрастающая? да, последовательность сортирована в возрастающем порядке. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 19:20 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Уважаемый ТС, я где-то сказал, что собираюсь эту последовательность представлять целиком "внутрях компа" и физически? Я просто попытался получить ответ на понятном мне языке, ибо задача к компьютерам имеет такое же отношение, как Дэцл к балету. Да, она нынче решаема вычислительными средствами; но ведь и мат.методы никто не отменял. Что вам и пытаются рассказать почти все присутствующие. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 19:26 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
AndreTMУважаемый ТС, я где-то сказал, что собираюсь эту последовательность представлять целиком "внутрях компа" и физически? Я просто попытался получить ответ на понятном мне языке, ибо задача к компьютерам имеет такое же отношение, как Дэцл к балету. Да, она нынче решаема вычислительными средствами; но ведь и мат.методы никто не отменял. Что вам и пытаются рассказать почти все присутствующие. Зачем вы нервничаете ? Задача имеет к компьютерам самое прямое отношение. Последовательность я вам ответил - случайна и в возрастающем порядке. Числами в этой последовательности могут быть например хешами строк. Тоесть "серых" участков может быть существенно больше чем "белых" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 19:33 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Метод МайороваКритерий есть. Все полностью серые группы можно принять как 0. Все остальные группы как длина группы. Таким образом лучшее решение с самим меньшем коэфициентом. Например. Период: 5. Количество групп: 10 Количество полностью серых групп: 3 Не серых: 7 Таким образом 3*0+7*5 = 35Тогда оптимальный период ревен единице. Оценка получается равна количеству чисел. Меньше никак не получится. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 19:42 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
У меня появилась идея: 1. Пробежаться по последовательности пометив каждый элемент числом Х. Число Х - расстояние до следующего элемента в ряде. 2. Последовательно удалять все элементы из ряда. Тоесть в первой итерации удалить из ряда все элементы где расстояние до следующего элемента 1, потом 2, потом 3 и тд вплоть до Хmax. 3. Построить график зависимости Х от N*X, где N количество удаленных элементов в итерации, максимум этого графика и будет по идее наилучшим периодом. Но нужно еще подумать. Короче курс на апроксимацию ряда и уже потом его анализ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 19:46 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
?Метод МайороваКритерий есть. Все полностью серые группы можно принять как 0. Все остальные группы как длина группы. Таким образом лучшее решение с самим меньшем коэфициентом. Например. Период: 5. Количество групп: 10 Количество полностью серых групп: 3 Не серых: 7 Таким образом 3*0+7*5 = 35Тогда оптимальный период ревен единице. Оценка получается равна количеству чисел. Меньше никак не получится. да, тут слегхка лажа. Физический смысл здесь такой, что хранение одной серой или белой группы в памяти это уже как минимум 3 единицы, а не 0. Поэтому расчет будет таким 1 Серая группа = -3 1 Белая группа = длина группы-3 таким образом 3*(-3)+(7*5)-(7*3) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 19:55 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Не заводитесь на коэффициенты - для констант всё равно "на всякий газ будет..." Ну а так - я и не нервничаю... Сформулируем условие примерно так (расчет от промежутков): Пусть имеется некий массив A, целых чисел. Отсортируем его, Приведем значения к натуральным, начиная с единицы. (Для ТС - имелся массив {191,-7,250,-32,10,77,14}, стал {1,25,43,47,110,224,283}, N=len(A)=7) Представим себе последовательность N` всех натуральных от 1 до 2*(A(N)-1) Нужно разбить эту последовательность на G>1 (кстати, ИМХО, G будет одним из делителей числа 2*(A(N)-1)) групп, так, чтобы: - Длина группы (разность между последним и первым значениями в группе; здесь учитываем, что и включая "виртуальные" значения) была максимальной - "Промежутки" между группами содержали минимальное количество "пустых (виртуальных)" групп; а здесь учитываем, что это количество легко находится, если известны окончание предыдущей "реальной" группы и начало следующей... По первому впечатлению - легко реализуемый перебор, но мы же желаем уйти от O(N), так что будем думать... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 20:33 |
|
||
|
Задачка
|
|||
|---|---|---|---|
|
#18+
Метод МайороваЕсть последовательность чисел. Допустим 1,5,6,8,12,14,18,20 Развернем ее в чистый числовой ряд 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 Нужно разбить эту последовательность на группы чисел, одинаковой длины так, чтобы А) Было как можно больше групп в которых все числа серые Б) Самих групп было бы как можно меньше Вообщемто нужно найти длину такой оптимальной группы чисел. Для примера - длина группы равна 5. 1,2,3,4,5 | 6,7,8,9,10 | 11,12,13,14,15 | 16,17,18,19,20 Несколько мыслей. Ты привёл очень неудачный пример. Условие (А) совершенно не выполняется. Так и было задумано? Если немного разобраться с характером этой последовательности (есть или нет периода) то можно было-бы сильно ускорить поиск решения. Вообще, к числовым рядам в такой общей постановке не приходят. Если это (к примеру) последовательность решета Эратосфена или Дирихле или SecuredRandon sequence то поиск решения закончистя фейлом. Я гарантирую это! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.06.2011, 23:46 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=37316541&tid=1342874]: |
0ms |
get settings: |
8ms |
get forum list: |
21ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
192ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
73ms |
get tp. blocked users: |
2ms |
| others: | 244ms |
| total: | 560ms |

| 0 / 0 |
