[devel] вопрос про числа

[Vladislav Zavjalov]

On Sat, Nov 07, 2009 at 10:34:02PM +0300, Alexey Tourbin wrote:
> Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их
> по возрастанию.  Для примера m=32, n порядка 10^3.
> 
> Вычислить энтропию и предложить оптимальную процедуру кодирования
> (сжатия) последовательности.  Сколько битов на число можно получить?

То есть, задача: есть n m-битных чисел, нужно проверить, что данное число
находится среди них. Хранить хочется меньше, чем n*m бит.

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

Но это так, первая идея без обоснования :)

Слава