2.2 不要被阶乘吓倒

本文主要是介绍2.2 不要被阶乘吓倒，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

1、给定一个整数N，阶乘N！末尾有多少个0

2、求N！的二进制表示中最低位1的位置

1、给定一个整数N，阶乘N！末尾有多少个0

举例：10！＝3 628 800，则 N！的末尾有两个0

思路：

 

即，知道 Z ，就知道N！中含有0的个数

方法一：求出1~N中每一个数被5整除的因子的个数，比较笨

代码：

int FindZeroNum(int n) {int ret = 0;for(int i = 1; i <= n; ++i) {int j = i;while(j % 5 == 0) {ret ++;j /= 5;}}return ret;
}

方法二：

举例：N = 25 ，即1~25

5的倍数(5,10,15,20,25)贡献一个5

25的倍数贡献一个5

虽然25可以贡献两个5，但是已经在5的倍数中贡献一次了，所以这里就统计一次

也就是说，对于每一个5 ^{^M},N只统计一次5，虽然它本身有多个5的质因数，但是已经在前面M-1计算过，所以只需统计一次即可

代码

int FindZeroNum(int n) {int ret = 0;while(n) {ret += n / 5;n /= 5;}return ret;
}

2、求N!的二进制表示中最低位1的位置

举例：N = 3，N！ = 6，6的 二进制1010 最低位1在第二位

问题分析

方法一：

代码

int FindZeroNum(int n) {int ret = 0;while(n) {n >>= 1;ret += n;}return ret;
}

代码说明：

假设是8! 有1 2 3 4 5 6 7 8

第一次循环： 则它有 2 4 6 8四个具有2的质因数

第二次循环： 2 4 6 8变为 1 2 3 4 则只有 2 4具有2的质因数

第三次循环：2 4 变为 1 2 则只有2 具有2的质因数

方法二：

代码

思考题

给定正整数N，判断其是否为2的方幂

问题等价于：判断 N 的二进制表示中是否只有一位为1

方法：

这篇关于2.2 不要被阶乘吓倒的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---