7, 11, 13, 14, 19, 21, 22, 25, …., Небольшая последовательность Опции

[Cheburashka]

В общем дана последовательность 7, 11, 13, 14, 19, 21, 22, 25, ….
Нужно по заданному N найти N-ый член.
В общем-то задача является олимпиадной, хотелось бы узнать как ее можно решить
Что это за последовательность я нашел:
Это числа которые содержат 3 единицы в двоичной записи числа, числа по возрастанию идут.
7 - 111
11 - 1011
13 - 1101
14 - 1110
19 - 10011 и т.д.

Вот мой код

program N468;
  var n, i, k, q : longint;
      Number     : longint;
      res        : int64;
      a          : array [1..10000] of byte;

begin
  Readln (n);
  a[1] := 1;
  a[2] := 1;
  a[3] := 1;
  number := 1;
  k := 3;
  While Number <> n do
    begin
      If ((a[1] = a[2]) and (a[2] = a[3]))
        then begin
               For i := 1 to k do a[i] := 0;
               inc (k);
               a[1] := 1;
               a[k] := 1;
               a[k - 1] := 1;
               Inc (number);
             end; {Переход в следующий разряд}
      For i := k downto 3 do
        If a[i] = 1 then
          If a[i - 1] <> a[i]
            then begin
                   a[i - 1] := 1;
                   a[i] := 0;
                   Inc (number);
                   break;
                 end
            else begin
                   a[i - 1] := 0;
                   a[i] := 0;
                   a[i-2] := 1;
                   a[k] := 1;
                   inc (number);
                   break;
                 end;
    end;
  q := 1;
  res := 0;
  For i := k downto 1 do
    begin
       res := res + (a[i] * q);
       q := q * 2;
    end;
  Write (res);
end.

Но к сожалению данный алгоритм не является быстрым( Где-то начиная с 32,000,000-го члена программа начинает долго очень работать, при том что 1 <= N <= 2,147,483,647. И это еще при том, что я не реализовал длинную арифметику.

Подскажите какой-нибудь алгоритм или сами подскажите, как можно находить данные числа намного быстрее.

Сообщение отредактировано: Lapp - 17.06.2010 22:11

[Lapp]

Подскажите какой-нибудь алгоритм или сами подскажите, как можно находить данные числа намного быстрее.

Здесь нужен совсем другой подход, мне кажется..
Комбинаторику знаешь? Плясать нужно от количества расстановок: три единицы по N местам. Подробнее ниже..

Разряды в числе заполняются справа налево. Число способов размещения трех единиц по k разрядам равно:

m_k = k!/(6*(k-3)!)

Эти числа образуют последовательность:

0, 0, 1, 4, 10, ...

- первые два члена я положил нулями, но это неважно, поскольку они не нужны. С этой последовательностью тебе следует сравнить данное число n. Нужно найти такое k, при котором выполняется двойное неравенство:

m_k-1 < n <= m_k

Оно находится либо последовательным сравнением, либо дихотомией - второе быстрее, но я думаю, это уже неважно. Найденное k - это позиция самой левой из тех трех единиц. Если справа осуществляется равенство, то поиск прекращается, и все остальные единицы просто приписываются за первой. Если нет, то ..

.. после этого задача трансформируется в задачу о такой же последовательности, только не для трех единиц, а для двух, при этом ищем ее n-m_k-1 член. Так мы определим позицию второй единицы. Затем продолжим процесс с одной единицей..

Если что-то неясно - спрашивай ).

Добавлено через 1 мин.
Немного я опоздал )).
TarasBer'у респект и +1.