+2 wrote:
> Автор: +2
> +2
> __Rosty__
> Например первое число из 3х единиц равно 7, второе 13, третье 14.
>
>
> Я согласен. С ходу, назовёте 300-е число из 3 единиц?
>

Насколько я понимаю, тут речь идет о том, что если рассматривать числа
подряд, их не нужно сортировать. То, что я назвал упорядоченностью.

Про остальное, если мысль была примерно такая. Нарисую таблицу для
наглядности:

00000 01000 10000 11000
00001 01001 10001 11001
00010 01010 10010 11010
00011 01011 10011 11011
00100 01100 10100 11100
00101 01101 10101 11101
00110 01110 10110 11110
00111 01111 10111 11111

Каждое число можно представить в виде суммы степеней двойки (что
соответствует его представлению в обычных компьютерах). Например, 29 =
16+8+4+1. Чтобы посчитать распределение бит в 16, делим его на две
части - [0..7] и [8..15]. Замечаем, что во втором интервале [8..15]
распределение бит то-же самое, что и в [0..7] плюс фиксированное кол-во
старших бит (здесь - один). То есть, чтобы посчитать распределение для
всего числа (16) нужно узнать распределение половины интервала. Может
продолжать деление пополам до тех пор, пока не дойдём до единицы. Затем,
предположим у нас есть распределение для [0..7]: {1, 3, 3, 1}, то есть,
было встречено одно 0-битное число, три однобитных, три двухбитных, одно
трехбитное.

отсюда найдем распределение для 16 (сдвигая полученное для 8 вправо на
единицу и суммируя):
{1, 3, 3, 1} + {0, 1, 3, 3, 1} = {1, 4, 6, 4, 1}

Теперь переходим ко второму интервалу (+8), для него нам нужно уже
полученное распределение {1, 4, 6, 4, 1}, его собственное (для 8) {1, 3,
3, 1}, и знание того, что для этого интервала у нас два старших бита
неизменны (маска 10xxx):
Из {1, 3, 3, 1} с учетом одно значащего бита имеем {0, 1, 3, 3, 1},
затем, сложим левый и новый интервалы {1, 4, 6, 4, 1} + {0, 1, 3, 3, 1}
= {1, 5, 9, 7, 2}

и т.д - повторяем шаг алгоритма.

Таким образом мы можем просто перебирать интервалы чисел, отслеживая
значение в распределении в нужной позиции до тех пор, пока не увидим,
что вновь рассмотренный интервал перекрывает искомое число. После этого,
мы можем вернуться обратно к предыдущему интервалу, сократить
просматриваемый интервал в два раза (например - в приведенной интерации,
разбивая интервал 8 на два: 4+4), и опять повторить операцию для
сокращенного интервала. Итерации заканчиваются успехом тогда, когда
завиксирован переход, и длина текущего интервала равна 1 (это будет
искомое число), или мы вышли за заданные границы.
Posted via ActualForum NNTP Server 1.4