算法学习（16）阶乘求解（考虑大数组的阶乘求解）_用数组求阶乘的思路

1.前言

这一篇博客的价值，在于使用了一种处理非常大的数字乘积的方法，这些数字是存储在数组中的，这样，理论上，处理多大的数相乘，都不会有任何问题。（然而实际测试过程中，发现Python内部处理乘法的逻辑，已经采用类似的方法了，于是，理论上对阶乘的大小是没有限制的了……）

2.问题

求输入给定整数的阶乘。

2.1 名词解释

阶乘，给定一个整数$n$，$n!=n\times (n-1)\times (n-2)\times ...\times 1$

3.编程解决

3.1 递归求解

3.1.1 编程思路

对于 $n!$，其实可以看成 $n\times (n-1)!$，根据这个递推公式，既可以直接写出递归求解的程序

3.1.2 实现代码

# 算阶乘,递归的方法
def factorial(n):
    if n == 1:  # 递归结束条件
        return 1
    else:
        return n*factorial(n-1)
1
2
3
4
5
6

3.1.3 运行效果

3.1.4 代码分析

1.注意一定要有递归结束的条件：if n==1
2.对于每一种编程语言来说，都有默认的递归调用深度，对于Python,测试后是998层，具体为什么是998，不得而知，可能跟程序的规模大小有关。可能程序越复杂，能递归调用的层数也会相应减少吧。
3. 递归调用的程序，看起来简洁，但不一定高效，如求解斐波那契数列，用递归解决很简单，但该方法却什么低效，之后会具体介绍。

3.2 循环求解

3.2.1 编程思路

能用递归调用解决的方法，都能用循环解决。对于阶乘，无非就是建立一个for循环，根据定义，依次把数字乘起来即可。

3.2.2 实现代码

# 用循环来解决
def factorial_loop(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result
1
2
3
4
5
6

3.2.3 运行效果

3.2.4 代码分析

注意range(n),并不包括 $n$, 因此循环的终点要设为$n+1$

3.3 上述方法小结

3.3.1 潜在问题

阶乘的结果增长很快，一般计算机用于存储整数最大去到64位，对应于十进制数是 $1.84467441\times 10^{19}$, 也就是说没如果阶乘结果的位数超过19，计算机会溢出，所谓的溢出，就是数值的高位被舍去，结果反而变小了。下面是教材演示的溢出现象。

3.3.2 现象

教材用的是 int 型数据，对应32位，最大的整数值是 $2,147,483,647$, 而下面 $13!=6,227,020,800$, 结果是存不进去的。

不过，我直接用Python测试，发现Python已经解决了这样的问题。在我算到$998!$的时候，递归算法才因为超过递归深度而无法计算，而没有出现溢出的显现。

3.3.3 测试

经过测试，Python是优化过大数的乘法运算的，下面多个测试，完全无障碍。

$500!$ 毫无问题

$997!$ 这是递归算法能hold住的最后一个数，对于循环求解算法，唯一的限制或许就是计算机本身的存储能力了吧。

$998!$, 递归溢出。对于递归算法，使用的时候，必须记得测试最大递归深度是多少，使用递归的快排算法，也会面临递归深度溢出的问题。

3.4 针对大数相乘的编程思路

3.4.1 编程思路

1. 利用数组来存储一个大数的每一位，这样，100位的大数字，就建立一个100长度的数组，每个位置，只需要储存$0$到$9$，非常巧妙的思路，这里的核心是，我们自己给数组的每一位脑补“个十百千”的权重 。
2. 处理进位，这是这个方法的难点。
3. 乘法的过程，就跟我们手算乘法很类似。每一个数组位的数，都跟乘数相乘，结果放在原数组位中。然后因为是十进制，所以，每个数组位，保留数字的个位部分（取余10），多的部分，当作进位（整除10），加到下一数组位的数字上即可，参考下图。（特别是右下的示意图）
   

3.4.2 代码实现

# 用教材的方法，使用数组存储
# 这里有两个部分，第一个函数，处理进位的函数，是最重要的一个；第二个，处理遍历各位的信息，
# 但依赖于函数一
def carryHandle(listOfNum, numOfBit):  # 参数1是存储乘积结果的矩阵，参数2是存储乘积的倍数
    carry = 0
    for i in range(numOfBit+1):
        listOfNum[i] += carry  # carry是进位
        if listOfNum[i] <= 9:
            carry = 0  # 表明不用进位
        elif i < numOfBit:  # numOfBit 记录的也是索引
            carry = listOfNum[i] // 10  # 因为是十进制，多的进位
            listOfNum[i] = listOfNum[i] % 10  # 一个数组位，保留一位就好
        else:
            # 正常能进来这里，就是 listOfNum[i] > 9, 并且是最高位
            while listOfNum[i] > 9:
                carry = listOfNum[i] // 10
                listOfNum[i] = listOfNum[i] % 10
                i += 1
                listOfNum[i] = carry  # 把上面的进位，继续加上去
            # 此处传的是数组，所以不用返回


def factorial_LargeNumber(num):  #
    # 确定结果的位数，建立相应的数组
    sumOfBits = 0
    for i in range(1, num+1):
        sumOfBits += math.log10(i)  # log2则是求比特的位数，因为是10进制，所以对10求log；此时是实数
    digit = int(sumOfBits)+1  # 最长的结果
    # 建数组
    listOfNum = [0]*(digit+1)  # 装每一次相乘的结果,预设的数组多一位，防止越界
    # 数组开始应为1
    listOfNum[0] = 1
    # 开始正式的乘法，让前一位数，乘以新的乘数
    for num_j in range(2, num+1):
        # 确定目前的最高位
        for k in range(digit, -1, -1):  # 找最高位
            if listOfNum[k] != 0:
                highBit = k  # 最高位所在的索引
                break
        for i in range(highBit+1):  # 已知最高位的索引后，从第一个数开始乘乘数
            listOfNum[i] *= num_j  # 相乘的结果，还是直接存在数组里，先处理进位
        # 等所有为乘完，才处理进位
        carryHandle(listOfNum, highBit)
    # 等大for循环结束，结果也就出来了
    # 打印结果
    # 确定最高位，方便打印
    for k in range(digit, -1, -1):
        if listOfNum[k] != 0:
            highBit = k
            break
    print('拆解算法：', num, '! = ', end='')
    for i in range(highBit, -1, -1):
        print(listOfNum[i], end='')
    print()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

3.4.3 运行效果

第三个输出~这里的输出，是把数组从最高位输出到最低位，跟第一、二种方法直接数字输出，是有本质不同的。

3.4.4 代码分析

1. def carryHandle(listOfNum, numOfBit):,这个函数最为关键，输入储存乘积结果的数组和此时数字的位数
2. 函数的处理思想很简单，根据下面三步来，对应 if语句的三个判断
   1）先把上一位的进位 carry 加到目前正在处理的这一位
   2）判断现在这一位，是否大于10（因为是十进制）
   3）小于10，没有进位，处理下一位
   4）大于10，这时就要判断是不是最高位了，不是最高位，只需要正常取余保留这一数组位的数字，整除10 算出进位 carry传给下一位
   5）或是最高位了，就依次把carry位往前推，算到每个数组位都是小于10为止
3. 在主函数，完成的操作是
   1）预先估计乘积的位数，创建相应长度的数组
   2）类似循环方法求阶乘一样，依次把数字累乘，唯一区别是，每乘一次，就调用carryHandle(listOfNum, numOfBit): 处理进位
   3）把数组逆序输出，看起来就跟一整个大数字一样
4. 重点理解

for i in range(1, num+1):
      sumOfBits += math.log10(i)  # log2则是求比特的位数，因为是10进制，所以对10求log；此时是实数
  digit = int(sumOfBits)+1  # 最长的结果
1
2
3

对10求 log， 是因为我们这里是10进制，用二进制求位数的方法理解这里即可。同时，思考为什么这里是加~确实很巧妙
5. 关于Python 3 print() 函数的小知识。在Python 3中，print() 已经变成了一个语句，默认输出是换行，而我们这里需要的，恰恰就是不换行。于是，在print()函数的参数中，增加 end=’’, 这样输出一个数字后，不会有空格或是换行，而是接着输出。原函数缺省的默认参数是 end=’\n’，这就不难理解为什么每次输出后，都是自动换行了。
(print()输出的控制，参考了这篇文章，很有帮助，非常感谢~ 传送门)

3. 注意range() 函数的边界，要遍历到索引为 0 的位置，终点一定记得是 -1。

4. 总结

对于方法三，采用数组来表达一个大数，何尝不是又一次空间策略的精彩应用呢~ 这里体现了化整为零的思想。虽然Python 3 已经内置了处理非常大数相乘的逻辑，可是，掌握背后的思想，真的挺有趣的，当然，方法三运行肯定很慢，只是，它设计的初衷在于能算而不是为了快啊，理论上只有计算机内存允许，多大的数，都能算。