Рассчитать количество конечных нулей в последовательности

Question

Рассмотрим последовательность, в которой s(0) и s(1) являются входами, а s(n) = s(n-1) * s(n-2) для всех n >= 2.Я хочу найти число конечных нулей в s(n).Мы можем предположить следующее:

• n, s(0) и s(1) заданы в качестве входных данных
• n <= 40
• s(0) <= 20
• s(1) <= 20

Ниже приведена моя попытка кода.Он не работает, если n больше 30 (он работает очень долго).Есть ли другой способ рассчитать количество конечных нулей?

public class Soroco {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BigInteger n = new BigInteger(br.readLine());
    BigInteger s0 = new BigInteger(br.readLine());
    BigInteger s1 = new BigInteger(br.readLine());
    BigInteger num = s(n, s0, s1);
    System.out.println(num);
    System.out.println(countTrailingZeroes(num));
  }

  static BigInteger s(BigInteger n, BigInteger s0, BigInteger s1) {
    if (n.equals(new BigInteger("0")))
        return s0;
    else if (n.equals(new BigInteger("1")))
        return s1;
    else {
        BigInteger n1=n.subtract(new BigInteger("1"));
        BigInteger n2=n.subtract(new BigInteger("2"));
        BigInteger n3=s(n1, s0, s1).multiply(s(n2, s0, s1));
        return n3;
    }
  }

  static int countTrailingZeroes(BigInteger num) {
    String str = String.valueOf(num);
    int count = 0;
    for (int i = 0; i < str.length(); i++)
        if (str.charAt(i) == '0')
            count++;
    return count;
  }
}

Answer 1

public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());

    int s0 = Integer.parseInt(br.readLine());

    int s1 = Integer.parseInt(br.readLine());

    int num21 = findNumberOf2s(s0);

    int num22 = findNumberOf2s(s1);

    int num51 = findNumberOf5s(s0);

    int num52 = findNumberOf5s(s1);

    int arr2[] = new int[n + 1];
    arr2[0] = num21;
    arr2[1] = num22;
    for (int i = 2; i <= n; i++)
        arr2[i] = arr2[i - 1] + arr2[i - 2];

    int arr5[] = new int[n + 1];
    arr5[0] = num51;
    arr5[1] = num52;
    for (int i = 2; i <= n; i++)
        arr5[i] = arr5[i - 1] + arr5[i - 2];

    System.out.println(Math.min(arr2[n], arr5[n]));

}

static int findNumberOf2s(int num) {
    int num2 = 0;
    while (num % 2 == 0) {
        num = num / 2;
        num2++;
    }
    return num2;
}

static int findNumberOf5s(int num) {
    int num5 = 0;
    while (num % 5 == 0) {
        num = num / 5;
        num5++;
    }
    return num5;
}

Answer 2

Вместо выполнения полного умножения необходимо отслеживать только коэффициенты 2 и 5. Если число можно записать как N = 2^a * 5^b * (factors other than 2 or 5), то число конечных нулей в N равно min(a, b).(Это потому, что конечный ноль - это просто множитель 10, для которого требуется одно 2 и одно 5).

Обратите внимание, что умножение складывает вместе экспоненты факторов.Итак, если вы можете написать:

s(n-2) = 2^a * 5^b * (factors other than 2 or 5)
s(n-1) = 2^c * 5^d * (factors other than 2 or 5)

Тогда у нас будет:

s(n) = s(n-1) * s(n-2)
     = 2^(a+c) * 5^(b+d) * (factors other than 2 or 5)

Следовательно, мы можем рассматривать эту проблему как две последовательности Фибоначчи .Вы начинаете с числа 2 и 5 в s(0) и s(1) и вычисляете число 2 и 5 в s(2), s(3), ..., s(n) в последовательности Фибоначчи:

#2s in s(n) = (#2s in s(n-1)) + (#2s in s(n-2))
#5s in s(n) = (#5s in s(n-1)) + (#5s in s(n-2))

Наконец, числоконечных нулей составляет min(#2s in s(n), #5s in s(n)).

---

Вышеприведенный алгоритм (если реализован с помощью цикла или запомненной рекурсии) равен O(n).Ваша попытка была экспоненциальной в n, поэтому даже для n = 30 требуется много времени.Я не хочу разбивать вашу попытку, но хорошо понимать эти ошибки - ваш код работает медленно по двум основным причинам:

Во-первых, умножение очень больших целых чисел с полной точностью (как вы делаете сBigInteger) очень медленно, так как количество цифр может удваиваться с каждым умножением.Если вас волнует только число конечных нулей, полная точность не требуется.

Во-вторых, игнорируя стоимость умножения, ваша рекурсивная реализация s по-прежнему экспоненциально, но это не такдолжен быть.Обратите внимание, что вы вычисляете одни и те же значения много раз - s(n-2) вычисляется отдельно для s(n) и s(n-1), но значение s(n-2) явно одно и то же.Хитрость заключается в том, чтобы запомнить рекурсию , запоминая ранее вычисленные результаты, чтобы избежать повторного вычисления.Кроме того, вы можете вычислять последовательности, подобные Фибоначчи, с помощью цикла:

// Computes the n-th Fibonacci number in O(n) time
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++)
    fib[i] = fib[i-1] + fib[i-2];
return fib[n];

Это гораздо более простой подход, чем запомненная рекурсия, по крайней мере для этой проблемы.