найти n-е число Фибоначчи, где n может варьироваться до 10 ^ 9 - PullRequest
Новая
       13

найти n-е число Фибоначчи, где n может варьироваться до 10 ^ 9

0 голосов
/ 22 сентября 2019

// я пытался найти (n ^ n)% 1000000007, где n - это n-й член Фибоначчи ряда.пример: n = 3 и 4 (2 ^ 2) 

 public class Sol_Big {
 public static void main(String args[])
{  
       int n =10000000;
       BigInteger a = BigInteger.ZERO;
       BigInteger b = BigInteger.ONE;
       BigInteger c = BigInteger.valueOf(1);
       BigInteger MOD = BigInteger.valueOf(1000000007);

       for (int j=2 ; j<=n ; j++)
       {
           c =  a.add(b);
           c=c.mod( MOD);
           a = b.mod(MOD);
           b = c.mod(MOD);
       }
        System.out.println(c);
        BigInteger result = BigInteger.valueOf(1);
        result = c.modPow(c, MOD);
        int intval = result.intValue();
        System.out.println( intval);

      }
}

// мой код работает для ввода 10 ^ 7, но для 10 ^ 8 и далее он превышает ограничение по времени ....

1 Ответ

2 голосов
/ 22 сентября 2019

Хитрость в том, чтобы заметить, что вы можете вычислить числа Фибоначчи с помощью умножения матриц: 

| 0 1 |   | a |   | b     |
| 1 1 | * | b | = | a + b |

С этим знанием мы можем вычислить n-е число Фибоначчи: 

| 0 1 |^n   | 0 |
| 1 1 |   * | 1 |

Поскольку матричное умножение ассоциативно, мы можем эффективно вычислить m ^ n.

  • Если n четное, m^n = m^(n/2) * m^(n/2)
  • Если n нечетное, m^n = m^((n-1)/2)) * m^((n-1)/2)) * m

Обратите внимание, что нам нужно одно и то же дважды, но мы должны вычислить его только один раз.
Это позволяет вычислить n-е число Фибоначчи в O(log n).

Я оставляю вам право писать код.

...