ifLab·iOS组2015秋季招新问卷-阶乘位数问题题解及拓展思考

【题目】

iOS组有一个异于其他组的习惯。每年进入组内的同学都将获得一个编码,但是为了凸显iOS组的高大上属性,编码并不是顺序的,而是需要通过一个特别的计算方法得到的,描述如下。

  1. 先由同学自己说出一个喜欢的数,要求大于50(即不会太小)。
  2. 计算由这个同学制定的数的阶乘,将末尾0的个数记录下来。
  3. 编码的长度为8位,结果不足8位的需要用0在前面补齐。

例如制定的数是1024,其阶乘末尾有253个0,则这名同学的编号为00000253。

需要解决的问题:

  1. 这个编码方式在实际操作的时候出现了两名同学虽然指定了不同的数却得到了相同的编号的情况,请简述原因。
  2. 请描述计算编号的解决方案。(你可以在伪代码、高级语言或自然语言中任选,能表示清楚思路即可)

在面试过程当中,我尝试询问遇到这道题的面试者在看题之后的思路。在预定情况下,这道题是为有NOIP经验的同学准备的。对于这类同学,这道题的难度并不大,但是思路决定代码的复杂程度。可惜大部分面试者对这道题的考虑只停留在如何求得阶乘以及对阶乘的处理上,这样的解法甚至不能完成样例中1024这个数据。

【解题思路】

可以肯定的是,对于1024这样的数,这个阶乘已经很大了,再去处理一个这么庞大的数的尾数问题,从时间和空间上都不划算。所以,我们可以转而思考这个数末尾的0是怎么来的。

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120

  1. 末尾的0和阶乘中能够构造出的10的个数相关。
  2. 10是由2和5构造出来的。
  3. 2的个数应该远多于5的个数,所以只需要讨论5的个数。

由此,我们把这个问题转化成了在n之前的数分解质因数后有多少个5的问题。

接下来,更进一步地思考可以发现,25分解之后可以得到2个5。在这个问题中还需要同时考虑5的n次方及其倍数包含多个5。

下面可以分为两种思路:

  1. 从1循环到n,对每个数分解质因数,求出5的个数。(必须指出这种算法比算阶乘再处理的时间复杂度高,但是空间复杂度大大降低了,至少针对大数是可以算的)
  2. 每5个数出现一个5,每25个数出现2个5……如果我们已经每5个数筛一次的情况下,25个数也只出现1个5了,这时候我们可以选择不断地整除5的n次方,并把结果相加。
【示例代码】


 C++ Code 
#include <stdio.h>



int main(int argc, const char * argv[]) {

    
int right = 5, sum = 0, n;

    scanf(
"%d", &n);

    
while(right <= n) {

        sum += n / right;

        right *= 
5;

    }

    printf(
"%08d\n", sum);

    
return 0;

}

【思路拓展】

因为之前的算法一下子把一个数字减小了将近5倍,我们研究了一种新的计算方法。

依然由同学指定一个数,这一次我们先对其求阶乘,然后把10进制数变为2进制,最后求这个2进制数从末尾数有多少个连续的0,并编为编号。

乍一看这道题比刚才的题目更加复杂了,不仅涉及阶乘和末尾0的问题,还发生了一次进制转换。但是如果你对进制有一定的了解的话,就会发现,这个问题的本质是探求n之前的数分解质因数有多少个2。

让我来详细地说明一下吧:在二进制的条件下,末尾的0代表2的n次方没有出现,即存在更高位的数。这时,从末尾看的第一个1其实就是其位数所在的权。(如果不好想象可以尝试完成几个数的二进制和十进制互换,这时你将会对这里提到的内容有更深的理解)

具体代码留给读者,和上面的示例代码大同小异。

需要提示读者的是,在面对和数学有关的问题时,一般都不应该暴力模拟,而是尝试从数学本质理解问题,找到好的解决方案。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

89 + = 98