首页 > 代码库 > 编程之美2.2 不要被阶乘吓倒
编程之美2.2 不要被阶乘吓倒
开始看到这道题目的时候,我还以为是利用字符串表示整型数的思想,后来一看,由于是一个数的阶乘,那么,如果这个数本身就很大,那么,即使是利用字符串表示也是不合理的,所以,看了下这道题的解释,书中给出了一个公式之后就明白了题目的意思。
首先,我先把函数声明和题目要求贴出来:
/*2.2 不要被阶乘吓倒*/ /*2.2.1 N!的末尾有多少个0*/ int DutCountOf0InFactorialN(int); /*2.2.2 N!的二进制表示中最低位1的位置*/ int DutPositionOf1InFactorialN(int);
我们想这样一个问题,有一个数N,那么1-N中存在多少个c(c >= 1 && c <= 9)呢?我们可以利用这个公式计算:
1-N中存在x的个数的计算公式为:N/x + N/x2 + N/x3 +...,且这个公式最后一定是收敛的
所以,可以写出如下的代码:
/*2.2.1 N!的末尾有多少个0*/ /*这道题目的解题思想是:2 * 5 = 10,所以,我们只要确定1—N中存在几个5就可以了(因为2有很多)*/ int DutCountOf0InFactorialN(int n) { if (n <= 0) return 0; int count = 0; /*1-N中存在x的个数的计算公式为:N/x + N/x2 + N/x3 +...,且这个公式最后一定是收敛的*/ while (n) { n += n / 5; n /= 5; } /*返回末尾0的个数*/ return count; } /*2.2.2 N!的二进制表示中最低位1的位置*/ /*二进制中最低位1,所以,需要知道后面存在多少个0,由此,我们只要确定有多少个2就可以了*/ int DutPositionOf1InFactorialN(int n) { if (n <= 0) return 0; int count = 0; /*1-N中存在x的个数的计算公式为:N/x + N/x2 + N/x3 +...,且这个公式最后一定是收敛的*/ while (n) { count += n / 2; n /= 2; } return count + 1; }
编程之美2.2 不要被阶乘吓倒
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。