|
算法分析:
由于n的规模比较大，其尾数的个数也会相应地多，所以在这里我们可以用arr数组来存储阶乘的的各位数字，a[0]存储各位，a[1]存储十位，依次类推。
接下来还有个问题需要解决，那就是arr数组的个数。
在这里我们可以利用对数和来统计阶乘的个数m:
累加和: s = lg2 + lg3 + ...... + lgn
m = s + 1
然后设置循环进行累乘，将各个位数存入arr数组中。
i的结果依次为2、3、4、5、6、......、n
g为进位数
各个数的乘积t:
t = arr[j] * i + g;
乘积t的个位数字存于本数组
arr[j] = t %10
乘积t的十位以上数字作为进位数g，即余数。
g = t /10
当把各个位数存入数组后，然后进行判断，如果为0,则零的个数count加一。
编程实现:
package cn.qblank.usual;
import java.util.Scanner;
/**
* 统计n!尾数零
* @author Administrator
*
*/
public class Demo3 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("请输入正整数n:(n<10000):");
int n = input.nextInt();
//统计零的个数
int count = 0;
//统计阶乘的总位数
double s = 0;
for(int i = 2;i <= n;i++){
s += Math.log10(i);
}
//求出总位数
int m = (int) (s + 1);
//创建数组
int[] arr = new int[m];
//初始化进位g=0,初始化数组第一位为1
int g = 0;
arr[0] = 1;
//进行阶乘
for (int i = 2; i <= n; i++) {
for (int j = 0; j < arr.length; j++) {
//算出每次的乘积
int t = arr[j]*i + g;
//将每次乘积的个位数存入数组中
arr[j] = t % 10;
//将十位数作为进位数
g = t / 10;
}
}
System.out.println("数组里面的值:");
//输出数组里面的值 本人亲测最多只能打印1053的阶乘值
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
}
System.out.println();
System.out.println("长度" + arr.length);
//统计连续零的个数
while(arr[count] == 0){
count++;
}
System.out.println(n + "!尾数连续零的共有" + count + "个。");
input.close();
}
}
运行结果:
由此可以看到，数组存储结果是反向存储的，这样方便计算零的个数
打印次数最多是以上结果，当超过以上值，则不能继续往下打印
当超过打印值时，则不打印,由此本次只讨论算法，所以就不在深入研究打印的问题。
算法优化:
通过实践，我们发现，以上的算法有点复杂。我们可以换个角度思考一下:既然要统计零的个数，而一个2的因子和5的因子就能产生一个零，那么我们可以直接通过统计2的因子和5的因子的个数来统计零的个数，但2的因子的个数要远远多于5的个数，于是我们就通过统计5的因子的个数.
5的因子的个数:count = [n/5] + [n/5*5] + *** + [n/5*..5]
编程实现:
package cn.qblank.usual;
import java.util.Scanner;
/**
* 统计5的因子
* @author Administrator
*/
public class Demo4 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("请输入正整数n:");
int n = input.nextInt();
//统计个数
int count = 0;
//统计5
int t = 1;
//统计5的因子
while(t <= n){
t *= 5;
count += n/t;
}
System.out.println(n + "!零的个数是:" + count);
input.close();
}
}
运行结果如下:
| 
转播
