考虑 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;
}
}
最佳答案
无需执行整个乘法,您只需要跟踪 2 和 5 的因数。如果一个数字可以写成 N = 2^a * 5^b *(除 2 或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)
因此,我们可以把这个问题看成两个Fibonacci sequences .您从 s(0)
和 s(1)
中 2 和 5 的数量开始,计算 s(2) 中 2 和 5 的数量, 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)
的值显然是一样的。诀窍是memoize the recursion通过记住先前计算的结果,以避免重新计算。或者,您可以使用循环计算类似斐波那契的序列:
// 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];
这是一种比内存递归更简单的方法,至少对于这个问题而言。
关于java - 计算序列中尾随零的数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50549007/