返回不同的结果以找到阶乘尾随零 [英] return different result to find Factorial Trailing Zero
问题描述
我有以下两个版本的实现,为什么它们返回不同的结果?
问题语句,
给出一个整数n,返回尾数
Java源代码,
public class TrailingZero {
public static int TrailingZeroes(int n){
int result = 0;
int base = 5;
而(n / base> 0){
结果+ = n / base;
基数* = 5;
}
返回结果;
}
public static int TrailingZeroesV2(int n){
return n == 0? 0:n / 5 +尾随零(n / 5);
}
public static void main(String [] args){
// TODO自动生成的方法存根
System.out.println(trailingZeroes(1808548329) );
System.out.println(trailingZeroesV2(1808548329));
}
}
基数
乘以5在第二个版本中丢失了。
public static int TrailingZeroesV2(n,5){
return TrailingZeroesV2(n,5);
}
private static int TrailingZeroesRec(int n,int base){
return n == 0? 0:n /基数+ TrailingZeroesRec(n / 5,基数* 5);
}
(通常,递归函数使用额外的参数)
两个版本的正确性都由您来提供。
它显然使用了阶乘中5个因子的数量至少具有相同的2个因子。因此,可以这样确定10个因子。
但是我会考虑%5
,取模5。但是我不会认真研究您的算法。
I have below two versions of implementation, why they return different results?
Problem statement,
Given an integer n, return the number of trailing zeroes in n!.
Source code in Java,
public class TrailingZero {
public static int trailingZeroes(int n) {
int result = 0;
int base = 5;
while (n/base > 0) {
result += n/base;
base *= 5;
}
return result;
}
public static int trailingZeroesV2(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(trailingZeroes(1808548329));
System.out.println(trailingZeroesV2(1808548329));
}
}
base
becoming multiplied by 5 got lost in the second version.
public static int trailingZeroesV2(int n) {
return trailingZeroesV2(n, 5);
}
private static int trailingZeroesRec(int n, int base) {
return n == 0 ? 0 : n / base + trailingZeroesRec(n / 5, base * 5);
}
(Typically a recursive function uses an extra parameter,)
The correctness of both versions I leave to your ingenuity. It obviously uses that the number of factors of 5 in the factorial has at least the same number of factor 2. So the factors of 10 can be determined as such.
I would however consider % 5
, modulo 5. But I will not seriously delve into your algorithm.
这篇关于返回不同的结果以找到阶乘尾随零的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!