千万不要被阶乘吓倒
发布时间:2021-10-06 22:35:45
阶乘(Factorial)是个很有意思的函数,但是不少人都比较怕它,我们来看看两个与阶乘相关的问题:
1、 给定一个整数N,那么N的阶乘N!末尾有多少个0呢?例如:N=10,N!=3 628 800,N!的末尾有两个0。
2、求N!的二进制表示中最低位1的位置。
有些人碰到这样的题目会想:是不是要完整计算出N!的值?如果溢出怎么办?事实上,如果我们从"哪些数相乘能得到10"这个角度来考虑,问题就变得简单了。
首先考虑,如果N!= K×10^M,且K不能被10整除,那么N!末尾有M个0。再考虑对N!进行质因数分解,N!=(2^x)×(3^y)×(5^z)…,由于10 = 2×5,所以M只跟X和Z相关,每一对2和5相乘可以得到一个10,于是M = min(X, Z)。不难看出X大于等于Z,因为能被2整除的数出现的频率比能被5整除的数高得多,所以把公式简化为M = Z。
根据上面的分析,只要计算出Z的值,就可以得到N!末尾0的个数。
【问题1的解法一】
要计算Z,最直接的方法,就是计算i(i =1, 2, …, N)的因式分解中5的指数,然后求和:
ret = 0;
for(i = 1; i <= N; i++)
{
j = i;
while(j % 5 ==0)
{
ret++; //统计N的阶乘中那些能够被5整除的因子的个数
j /= 5;
}
}
【问题1的解法二】
公式:Z = [N/5] +[N/5^2] +[N/5^3] + …(不用担心这会是一个无穷的运算,因为总存在一个K,使得5^K > N,[N/5^K]=0。)
公式中,[N/5]表示不大于N的数中5的倍数贡献一个5,[N/5^2]表示不大于N的数中5^2的倍数再贡献一个5,……代码如下:
ret = 0;
while(N)
{
ret += N / 5;
N /= 5;
}
问题2要求的是N!的二进制表示中最低位1的位置。给定一个整数N,求N!二进制表示的最低位1在第几位?例如:给定N = 3,N!= 6,那么N!的二进制表示(1 010)的最低位1在第二位。
为了得到更好的解法,首先要对题目进行一下转化。
首先来看一下一个二进制数除以2的计算过程和结果是怎样的。
把一个二进制数除以2,实际过程如下:
判断最后一个二进制位是否为0,若为0,则将此二进制数右移一位,即为商值(为什么);反之,若为1,则说明这个二进制数是奇数,无法被2整除(这又是为什么)。
所以,这个问题实际上等同于求N!含有质因数2的个数+1。即答案等于N!含有质因数2的个数加1。 实际上N!都为偶数,因为质因数里面都有一个2,除了1以外,因为1的阶乘是1,是个奇数,其他数的阶乘都是偶数。。
【问题2的解法一】
由于N! 中含有质因数2的个数,等于 N/2 + N/4 + N/8 + N/16 + …[1],
根据上述分析,得到具体算法,如下所示:
/*
可以先求出N!中2的个数(因为每存在一个2,则在数的
最低位多1个0)。因此求1的最低位的位置即为N!中2的个数+1;
*/
int lowestOnePos(int n)
{
int ret = 0; //统计n!中含有质因数2的个数
while(n)
{
n >>= 1;
ret += n;
}
return ret+1;
}
【问题2的解法二】
N!含有质因数2的个数,还等于N减去N的二进制表示中1的数目。我们还可以通过这个规律来求解。
下面对这个规律进行举例说明,假设 N = 11011,那么N!中含有质因数2的个数为 N/2 + N/4 + N/8 + N/16 + …
即: 1101 + 110 + 11 + 1
=(1000 + 100 + 1)
+(100 + 10)
+(10 + 1)
+ 1
=(1000 + 100+ 10 + 1)+(100 + 10 + 1)+ 1
= 1111 + 111 + 1
=(10000 -1)+(1000 - 1)+(10-1)+(1-1)
= 11011-N二进制表示中1的个数
小结
任意一个长度为m的二进制数N可以表示为N = b[1] + b[2] * 2 + b[3] * 22 + … + b[m] * 2(m-1),其中b [ i ]表示此二进制数第i位上的数字(1或0)。所以,若最低位b[1]为1,则说明N为奇数;反之为偶数,将其除以2,即等于将整个二进制数向低位移一位。
相关题目
给定整数n,判断它是否为2的方幂(解答提示:n>0&&((n&(n-1))==0))。
--------------------------------------------------------------------------------
[1] 这个规律请读者自己证明(提示N/k,等于1, 2, 3, …, N中能被k整除的数的个数)。
猜你喜欢
- 这篇文章主要介绍了Spring Batch批处理框架使用解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需
- 背景以springboot为tomcat启动的框架,以angular2为前端页面的框架,最后需要将angular2的代码运行在springb
- 前言最近有个网友问了我一个问题:系统中大事务问题要如何处理?正好前段时间我在公司处理过这个问题,我们当时由于项目初期时间比较紧张,为了快速完
- 本文实例讲述了Java String类简单用法。分享给大家供大家参考,具体如下:一 String类的实例化方式1 代码public clas
- 经常要检测某些IP地址范围段的计算机是否在线。有很多的方法,比如进入到网关的交换机上去查询、使用现成的工具或者编写一个简单的DOS脚本等等,
- 本文实例讲述了C#编程实现获取文件夹中所有文件的文件名。分享给大家供大家参考,具体如下:想实现这样一个功能:批量修改一个目录所有jpg文件的
- 简述mysq5.7之后新增了json类型,但是在使用的过程中,Json数组中的值小于Integer.MAX_VALUE,则反序列化时会转成L
- 需要添加对 System.Management.dll 的引用 using System.Diagnostics; using System
- 本文实例讲述了java中static关键字用法,分享给大家供大家参考。具体分析如下:一、介绍:1、在类中,用static声明的成员变量为静态
- Spring security 重写Filter实现json登录在使用SpringSecurity中,大伙都知道默认的登录数据是通过key/
- c#中通过反射可以方便的动态加载dll程序集,但是如果你需要对dll进行更新,却发现.net类库没有提供卸载dll程序集的方法。在.net
- C#处理猜拳问题的简单实例(非窗体)//猜拳,5局3胜,要求使用公用变量。namespace 结构体复习_公用变量{class Progra
- 骑缝章是用于往来业务合同,以确保合同真实、有效的印章加盖方法,是一种防范风险的重要方式。在Java程序中,可以通过使用工具来辅助加盖这种骑缝
- 页眉位于文档中每个页面的顶部区域,常用于显示文档的附加信息,可以插入时间、图形、公司微标、文档标题、文件名或作者姓名等;页脚位于文档中每个页
- 经过一番搜索发现,java操纵excel文件常用的有jxl和poi两种方式,孰好孰坏看自己需求而定。其中最主要的区别在于jxl不支持.xls
- java函数中的传值和传引用问题一直是个比较“邪门”的问题,其实java函数中的参数都是传递值的,所不同的是对于基本数据类型传递的是参数的一
- 最近项目里面用到了一个日期选择器,实现现在主流的WheelView滑动选择,整理了下,做了个Demo.废话不多说,直接上代码.主布局:act
- 本文实例为大家分享了JavaWeb实现用户登录与注册功能的具体代码,供大家参考,具体内容如下用到的知识客户端:HTML CSS JS (JQ
- 目录1、前提知识2、实现思路:1、前提知识需要知道简单的IO流操作,以及简单的UDP发送数据包的原理。需要用到的类:DatagramSock
- 一、单例模式设计模式:软件设计模式是一套被反复使用、多数人知晓、经过分类编目、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易