Версия для печати темы

Автор: Сергей Меркурьев 17.06.2010 22:36

В общем дана последовательность 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. И это еще при том, что я не реализовал длинную арифметику.

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

Автор: TarasBer 18.06.2010 13:53

Надо найти N-ю записть из 3х единиц...
Значит, надо найти какую-то закономерность.
Ага, вот.
Ищем, на какой позиции находится 1я единица, то есть скольки-значное число под номером N.
Записи до 1й включительно - 3 значные.
до 4й - 4 значные
до 10й - 5 значные
до 20й - 6 значные.
до C(2, 2) + C(2, 3) + ... + C(2, K) - (K+1) - значные
где C(n, k) = fact(n)/(fact(k)*fact(n-k))

Далее, C(2, 2) + C(2, 3) + ... + C(2, K) = (2*(2-1)/2 + 3*(3-1)/2 + ... + K*(K-1)/2) = (K*K*K-K)/6

То есть надо найти минимальное такое K, что N<=(K*K*K-K)/6
Вводим N1 := ((K-1)*(K-1)*(K-1)-(K-1))/6
Ну типа кубическое уравнение решить... Я бы дихотомил, наверное.
Для второй единицы смотрим, где она может быть
до N1+1 - она на 2 месте
до N1+3 - на 3
до N1+6 - на 4
итд
до N1+(L*L-L)/2 - на L

То есть находим минимальное L, что N <= N1+(L*L-L)/2
Вводим N2 := N1 + ((L-1)*(L-1)-(L-1))/2
Далее, тогда 3я единица находится на N-N2+1 позиции, это видно сразу.

Автор: Lapp 18.06.2010 13:59

Здесь нужен совсем другой подход, мне кажется..
Комбинаторику знаешь? Плясать нужно от количества расстановок: три единицы по 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.