(笔试题)N!尾部连续0的个数
个数 笔试 连续 尾部
2023-09-14 08:59:06 时间
题目:
对任意输入的正整数N,编写C程序求N!的尾部连续0的个数,并指出计算复杂度。如:18!=6402373705728000,尾部连续0的个数是3。
(不用考虑数值超出计算机整数界限的问题)
思路:
1、直接计算N!的值,然后统计尾部0的个数,时间复杂度O(n);
2、发散思维,想想尾部为0的数是怎么得到的?
很容易想到2*5即可得到0,则N!可以表示为k*(2^m)*(5^n),由于在N!中m>>n,因此N!=k'*(2*5)^n,即n为尾部为0的个数。
由此,我们只要考虑N!中包含多少个5的倍数就可以了,如25,含有5,10,15,20,25,包含6个5的倍数,即25!尾部有6个0。
n=N/5+N/(5^2)+N/(5^3)....+N/(5^k) (k<=N/5)
时间复杂度:O(log5N)
代码:
#include <iostream> using namespace std; long long NumOfZero(long long n){ long long count=0; while(n>0){ count+=n/5; n=n/5; } return count; } long long factorial(long long n){ if(n==1) return 1; return n*factorial(n-1); /* int fac=1; while(n>0){ fac*=n; n--; } return fac; */ } int main() { long long n=20; cout<<NumOfZero(n)<<endl; cout<<factorial(n)<<endl; return 0; }
相关文章
- 2022-11-26:给定一个字符串s,只含有0~9这些字符 你可以使用来自s中的数字,目的是拼出一个最大的回文数 使用数字的个数,不能超过s里含有的个数 比如
- Excel公式技巧:获取最后5个数值中3个数的平均值
- 图的连通分量个数
- linux 下统计一个文件夹下文件的个数
- 【集合论】集合概念与关系 ( 真子集 | 空集 | 全集 | 幂集 | 集合元素个数 | 求幂集步骤 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
- 使用 jQuery 统计用户选中的复选框的个数
- 操作系统查看LINUX操作系统中CPU个数(cpu个数linux)
- MySQL数据统计如何统计特定列的数量(mysql下统计某列个数)
- Redis中的桶个数默认16383个(redis默认有多少个桶)
- Redis提升服务性能的长连接持续优化(redis长连接个数)
- c#n个数排序实现代码
- javascript中的=等号个数问题两个跟三个有什么区别
- python实现从字符串中找出字符1的位置以及个数的方法