Как найти двоичное представление для n-го числа Фибоначчи - PullRequest
Новая
       14

Как найти двоичное представление для n-го числа Фибоначчи

1 голос
/ 25 марта 2012

Это мой первый пост здесь, поэтому, если я совершу какую-то ошибку, пожалуйста, дайте мне знать.

Мне дали задание, и для его части требуется двоичное представление n-го числа Фибоначчи. Ограничения -

  1. ) C ++ должен использоваться как прога. язык.
  2. ) n фиб. число должно быть рассчитано в lg (n) времени.

У меня есть функция, но она работает с целыми числами. Но максимальное значение, для которого я должен сделать вычисления, составляет около 10 ^ 6. Итак, я сильно застрял здесь. Что бы я ни знал, я не могу применить в этом сценарии, потому что я могу генерировать n'th выдумку. используя строки, но это будет иметь линейную сложность по времени. следующая функция, 

void multiply(long int F[2][2], long int M[2][2]);
void power(long int F[2][2], long int n);

// Function to Calculate n'th fibonacci in log(n) time
long int fib(long int n)
{
    long int F[2][2] = {{1,1},{1,0}};
    if(n == 0)
        return 0;
    power(F, n-1);
    return F[0][0];
}

void power(long int F[2][2], long int n)
{
    if( n == 0 || n == 1)
        return;
    long int M[2][2] = {{1,1},{1,0}};

    power(F, n/2);
    multiply(F, F);

    if( n%2 != 0 )
        multiply(F, M);
}

void multiply(long int F[2][2], long int M[2][2])
{
    long int x =  (F[0][0]*M[0][0])%mod + (F[0][1]*M[1][0])%mod;
    long int y =  (F[0][0]*M[0][1])%mod + (F[0][1]*M[1][1])%mod;
    long int z =  (F[1][0]*M[0][0])%mod + (F[1][1]*M[1][0])%mod;
    long int w =  (F[1][0]*M[0][1])%mod + (F[1][1]*M[1][1])%mod;  
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

int main(){
    int n; cin >> n; cout << fib(n)<<endl; getchar();
}

Как видно, в этой функции могут использоваться только предопределенные типы данных.

Ответы [ 2 ]

0 голосов
/ 23 мая 2013

Лучшим методом было бы использовать матричное экспонирование, которое вычисляло бы n-й фиб. в LG время (полезно для различных онлайн-конкурсов по кодированию) См. Метод 4 из Эта запись.

0 голосов
/ 25 марта 2012

Так как это домашнее задание, я дам только маленькие подсказки.

Две проблемы не связаны, поэтому вам нужно два метода: toBinary и fib.toBinary (fib (n)); будет вашим решением.

Для решения задачи toBinary деление и модуль являются полезными и могут вызываться рекурсивно.

Если вы вычисляете fib (n) как fib (n-1) + fib (n-2), возникает ловушка, в которую вы можете перейти, когда вычисляете fib (n-1) как fib (n)-2) + fib (n-3), вы в итоге вычисляете fib (n-2) дважды, fib (n-3) три раза и так далее.

Вместо этого вы должны начать с (0 + 1) и идти вверх, пропуская уже рассчитанный вперед.

После короткого теста я вижу, как быстро растут числа Фибоначчи.У вас есть доступ к Ints произвольного размера, или вы собираетесь использовать предварительно выделенные массивы?

Тогда вам понадобится метод add, который принимает младшее и большее число в виде массива целых или логических значений и создает сумму в нижнем массиве, который затем становится верхним массивом.

обновление:

Поскольку вы решили проблему, я не стесняюсь опубликовать мое решение для справки, написанное на Scala: 

import annotation._
/**
  add two arrays recursively. carry the position pos and the overrun 
   overrun=0   = 1      0      1      0      1
   Sum    low        | next        |  Sum
          0 1        | overrun     |  %2
  high 0| 0 1   1 2  | 0 0    0 1  | 0 1    1 0 
       1| 1 2   2 3  | 0 1    1 1  | 1 0    0 1
*/
@tailrec 
def add (low: Array[Int], high: Array[Int], pos: Int = 0, overrun: Int = 0): Array[Int] = {
  if (pos == higher.size) {
    if (overrun == 0) low else sys.error ("overrun!")
  } else {
    val sum = low (pos) + high (pos) + overrun
    low (pos) = (sum % 2)
    add (low, high, pos + 1, if (sum > 1) 1 else 0)
  }
}

/** call cnt (example: 5) steps of 
   fib (5, 0, 1), 
   fib (4, 1, 1), 
   fib (3, 1, 2), 
   fib (2, 2, 3), 
   fib (1, 3, 5), 
   fib (0, 5, 8) */
@tailrec 
def fib (cnt: Int, low: Array[Int], high: Array[Int]): Array[Int] = {
  if (cnt == 0) low else fib (cnt - 1, high, add (low, high)) }

/** generate 2 Arrays, size dependent on n of about 0.7*n + 1, big enough to
    hold values and result. Result has to be printed in reverse order, from the highest bit
*/
def fibonacci (n: Int) = {
  val lower =  Array.fill (n * 7 / 10 + 1)(0) // [...000]
  val higher = Array.fill (n * 7 / 10 + 1)(0) // [...000]
  higher (0) = 1 // [...001]
  val res = fib (n, lower, higher)
  res.reverse.foreach (print)
  println ()
  res
}

fibonacci (n)

Для Фибоначчи (10000) Я получаю результат почти 7000 двоичных цифр, и отношение 10/7 является постоянным, поэтому миллионная цифра Фибоначчи будет иметь около 1,4 млн цифр.

...