модульная арифметика c задач - PullRequest
Новая
       20

модульная арифметика c задач

0 голосов
/ 15 апреля 2020

Я столкнулся с проблемой из простого алгоритма. Вопрос ниже:

Описание проблемы Рекурсивная формула последовательности Фибоначчи: Fn = Fn-1 + Fn-2, где F1 = F2 = 1.

Когда n большое, Fn также очень большой, и теперь мы хотим знать, что является остатком Fn после 10007.

Формат ввода

Вход содержит целое число n.

Формат вывода

Выходная строка содержит целое число, представляющее остаток от Fn, деленный на 10007.

Пример ввода 10 Пример вывода

55

Пример ввода 22 Пример вывода

7704

Размер данных и условные обозначения 1 <= n <= 1 000 000. </p>

Мое решение приведено ниже: 

import java.util.Scanner;

/ ** * * / publi c class Main {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    System.out.println(recurrence(n));
    in.close();

}


/**
 *
 * @param n
 * @return
 */
public static int recurrence(int n) {
    int f1 = 1;
    int f2 = 1;
    int temp = f1;
    for (int i = 1; i <= n - 2; i++) {
        temp = (f1 + f2)%10007;
        f1 = f2;
        f2 = temp;
    }
    return temp;
}

}

Решение выше верное. Но я хочу сказать, что в следующем решении есть проблема. 

public static int recurrence(int n) {
    int f1 = 1;
    int f2 = 1;
    int temp = f1;
    for (int i = 1; i <= n - 2; i++) {
        f1 %= 10007;
        f2 %= 10007;
        temp = f1 + f2;
        f1 = f2;
        f2 = temp;
    }
    return temp;
}

- это не temp = (f1+f2)%10007 так же, как f1 %= 10007; f2 %= 10007; temp = f1 + f2;？

Мой английский sh беден, надеюсь, вы, ребята, могу понять, что я имею в виду Спасибо!

1 Ответ

0 голосов
/ 15 апреля 2020

Существуют определенные свойства для перезаписи результата по модулю. Википедия показывает некоторые из них. Здесь уместно следующее: 

(a + b) % n = ((a % n) + (b % n)) % n

Так что если вы измените

F n = F n-1 + F n-2

до

F n = (F n-1 + F n-2 )% 10007

вы получаете то, что хотите, поскольку F n-1 и F n-2 уже применили % 10007. 

static int fibMod(int n, int mod) {
    if (n < 0 || mod < 2)
        throw new IllegalArgumentException();
    if (n <= 1)
        return n;
    int prev = 1, fib = 1;
    for (int i = 3; i <= n; i++)
        fib = (prev + (prev = fib)) % mod;
    return fib;
}

Тест 

System.out.println(fibMod(10, 10007));
System.out.println(fibMod(22, 10007));
System.out.println(fibMod(1_000_000, 10007));

Выход 

55
7704
114
...