很经典的一道数学题:求n!后面有多少个0。
我的思路:
从"那些数相乘可以得到10"这个角度,问题就变得比较的简单了。
首先考虑,如果N的阶乘为K和10的M次方的乘积,那么N!末尾就有M的0。如果将N的阶乘分解后,那么
N的阶乘可以分解为: 2的X次方,3的Y次方,4的5次Z方,.....的成绩。由于10 = 2 * 5,所以M只能和X和Z有关,每一对2和5相乘就可以得到一个10,于是M = MIN(X,Z),不难看出X大于Z,因为被2整除的频率比被5整除的频率高的多。所以可以把公式简化为M=Z.
由上面的分析可以看出,只要计算处Z的值,就可以得到N!末尾0的个数
搜集了一下网上的资料,发现他们弄的挺麻烦的。。不过逻辑性比较强,大家可以参考一下。。。。
令f(x)表示正整数x末尾所含有的“0”的个数,则有:
当0 < n < 5时,f(n!) = 0;
当n >= 5时,f(n!) = k + f(k!), 其中 k = n / 5(取整)。
显然,对于阶乘这个大数,我们不可能将其结果计算出来,再统计其末尾所含有的“0”的个数。所以必须从其数字特征进行分析。下面我们从因式分解的角度切入分析。
我们先考虑一般的情形。对于任意一个正整数,若对其进行因式分解,那么其末尾的“0”必可以分解为2*5。在这里,每一个“0”必然和一个因子“5”相对应。但请注意,一个数的因式分解中因子“5”不一定对应着一个“0”,因为还需要一个因子“2”,才能实现其一一对应。
我们再回到原先的问题。这里先给出一个结论:
结论1: 对于n的阶乘n!,其因式分解中,如果存在一个因子“5”,那么它必然对应着n!末尾的一个“0”。
下面对这个结论进行证明:
(1)当n < 5时, 结论显然成立。
(2)当n >= 5时,令n!= [5k * 5(k-1) * ... * 10 * 5] * a,其中 n = 5k + r (0 <= r <= 4),a是一个不含因子“5”的整数。
对于序列5k, 5(k-1), ..., 10, 5中每一个数5i(1 <= i <= k),都含有因子“5”,并且在区间(5(i-1),5i)(1 <= i <= k)内存在偶数,也就是说,a中存在一个因子“2”与5i相对应。即,这里的k个因子“5”与n!末尾的k个“0”一一对应。
我们进一步把n!表示为:n!= 5^k * k! * a(公式1),其中5^k表示5的k次方。很容易利用(1)和迭代法,得出结论1。
上面证明了n的阶乘n!末尾的“0”与n!的因式分解中的因子“5”是一一对应的。也就是说,计算n的阶乘n!末尾的“0”的个数,可以转换为计算其因式分解中“5”的个数。
令f(x)表示正整数x末尾所含有的“0”的个数, g(x)表示正整数x的因式分解中因子“5”的个数,则利用上面的的结论1和公式1有:
f(n!) = g(n!) = g(5^k * k! * a) = k + g(k!) = k + f(k!)
所以,最终的计算公式为:
当0 < n < 5时,f(n!) = 0;
当n >= 5时,f(n!) = k + f(k!), 其中 k = n / 5(取整)。
代码如下:
分享到:
相关推荐
求n!数的末尾0的个数.用c语言实现。 简单方便
C语言程序设计-编写程序求无理数e的值并输出;计算公式为:e=1+11!+12!+13!+......+1n!当1n!0.000001时e=2.718282;.c
输入一个正整数n,生成一张阶乘表,输出1! ~n! 的值。要求定义和调用函数fact(n)计算n!,函数类型为double。 【输入形式】 从键盘输入一个正整数n。 【输入输出样例1】(下划线部分表示输入) Enter n: 3 1!=1 2!=2 3...
建一个控制台应用程序,要求输入数字n后,输出1!+2!+…+n!的结果
这是一个非常好的算法,希望大家领会!!!
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以{1, 2, 3, 4, 5}为 例说明如何编写全排列的递归算法。 1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列...
给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个 新的正整数。对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正...
计算几个工作日后的日期,因为VB直接...当我们需要按照工作日来推算的时候就要用到本程序(主要使用一个自制函数),只要知道起始日期, 以及需要推算的工作日数N,本程序即可计算N个工作日后的日期。谢谢大家支持!
每组测试数据输入的第一行有2 个正整数n和k,表示汽车加满油后可行驶n公里,且旅途中有k个加油站。接下来的1 行中,有k+1 个整数,表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地,汽车已加满...
题目描述:输入一个N阶方阵(0<N<10),输出此方阵顺时针旋转M(0<=M<=10000)次后的方阵 题目示例:三阶方阵,围绕方阵中心顺时针旋转 输入描述: (1) 第一行输入一个正整数N (0<N<10) (2) 接下来...
// 向量A目前有elenum个元素,且递增有序,本算法将x插入到向量A中,并保持向量的递增有序。 { int i=0,j; while (i[i]) i++; // 查找插入位置 for (j= elenum-1;j>=i;j--) A[j+1]=A[j];// 向后移动元素 A[i]=x...
下载之后使用轻松汇编打开之后,代码直接保存一下,然后在进行编译,以及后面的运行,输入的数据是0-9的数据,每次只能输入一个数据。如果想要实验多次的话,运行多次,输入不同的结果,然后分别进行截屏!
N后问题 用递归的方法去求解
y(n)= y(n-1)+ y(n-2) +x(n-1) (1) 求出该系统的系统函数,并绘制出零极点分布图,指出其收敛域。 (2) 求系统的冲激响应。 (3) 如果该系统是不稳定系统,则求出其满足稳定系统的冲激响应。 (4) 绘制出系统...
n*n 格的棋盘上放置彼此不受攻击的N个皇后。有回溯法实现N后问题,
第一行输入一个数N(0<N),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符 输出 ...
C语言程序设计-求一个大于10的n位整数的后n-1位的数,并作为函数值返回;
java代码执行hive相关ktr时报错: database type with plugin id [HIVE2] couldn't be found! 解决:kettle-core-7.1.0.0-12.jar适配hive后的包。具体步骤请查看...