Сообщение Re: Наиболее плотный диапазон чисел от 20.10.2014 21:57
Изменено 20.10.2014 22:04 vpchelko
Здравствуйте, Kerk, Вы писали:
K>Я подозреваю, эта задача элементарно решается статистическими методами, но что-то не соображу как...
K>Суть вот в чем.
K>Есть набор чисел. Можно считать, что случайных. Без повторов.
K>И есть некое число N.
K>Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
1. Очевидно, что X будет принадлежать набору чисел, любые другие числа будут непрактичны.
2. Если набор чисел отсортирован, то просто считаем плотность для каждого числа из набора чисел -> профит
3. Если набор чисел не отсортирован, то сортируем / либо используем промежуточный результат сортировки. Например: если для набора чисел применима сортировка подсчетом — то достаточно массива подсчёта совпадающих элементов. -> считаем плотность для каждого числа из набора чисел -> профит.
K>Я подозреваю, эта задача элементарно решается статистическими методами, но что-то не соображу как...
K>Суть вот в чем.
K>Есть набор чисел. Можно считать, что случайных. Без повторов.
K>И есть некое число N.
K>Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
1. Очевидно, что X будет принадлежать набору чисел, любые другие числа будут непрактичны.
2. Если набор чисел отсортирован, то просто считаем плотность для каждого числа из набора чисел -> профит
3. Если набор чисел не отсортирован, то сортируем / либо используем промежуточный результат сортировки. Например: если для набора чисел применима сортировка подсчетом — то достаточно массива подсчёта совпадающих элементов. -> считаем плотность для каждого числа из набора чисел -> профит.
Re: Наиболее плотный диапазон чисел
Здравствуйте, Kerk, Вы писали:
K>Я подозреваю, эта задача элементарно решается статистическими методами, но что-то не соображу как...
K>Суть вот в чем.
K>Есть набор чисел. Можно считать, что случайных. Без повторов.
K>И есть некое число N.
K>Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
1. Очевидно, что X будет принадлежать набору чисел, любые другие числа будут непрактичны, ибо для них всегда можно найти число из набора, которое даст большую оценку (плотность).
2. Если набор чисел отсортирован, то просто считаем плотность для каждого числа из набора чисел -> профит.
3. Если набор чисел не отсортирован, то сортируем / либо используем промежуточный результат сортировки. Например: если для набора чисел применима сортировка подсчетом — то достаточно массива подсчета совпадающих элементов. -> считаем плотность для каждого числа из набора чисел -> профит.
K>Я подозреваю, эта задача элементарно решается статистическими методами, но что-то не соображу как...
K>Суть вот в чем.
K>Есть набор чисел. Можно считать, что случайных. Без повторов.
K>И есть некое число N.
K>Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
1. Очевидно, что X будет принадлежать набору чисел, любые другие числа будут непрактичны, ибо для них всегда можно найти число из набора, которое даст большую оценку (плотность).
2. Если набор чисел отсортирован, то просто считаем плотность для каждого числа из набора чисел -> профит.
3. Если набор чисел не отсортирован, то сортируем / либо используем промежуточный результат сортировки. Например: если для набора чисел применима сортировка подсчетом — то достаточно массива подсчета совпадающих элементов. -> считаем плотность для каждого числа из набора чисел -> профит.