蓝桥杯|蓝桥杯——阶乘计算编程语言|面试|列表|java

蓝桥杯——阶乘计算

0.前言
1.解题思路
- 1.1原题
- - 1.1.1题目描述
  - 1.1.2输入
  - 1.1.3输出
- 1.2解答
- - 1.2.1思路一(BigInteger)
  - 1.2.2思路二(整型数组模拟)
  - - 1.2.2.1方案概要
    - 1.2.2.2细节问题
    - 1.2.2.3代码
    - 1.2.2.4说明
    - - 1.2.2.4.1`BigInteger`中的`multiplyByInt(int[] x, int y, int sign)`源码分析
      - 1.2.2.4.2分析
      - 1.2.2.4.2.1上来就判断2进制下1的个数
        
        1.2.2.4.2.2大数每9位划分一次
        
        1.2.2.4.2.3结果的数组rmag最多比原大数多1位
        
        1.2.2.4.2.4用 `& LONG_MASK`的方式转换成long
        
        1.2.2.4.2.5`product >>> 32`的意义
        
        1.2.2.4.2.6为啥整个方法的效率这么高
2.总结

0.前言免费的基础练习做完了，尝试一下VIP题目，推荐一个蓝桥杯一些特殊题目的网站，有需要可以在这里搜索，里面有很多题目，也可以在线提交评测。C语言网。这道题思路很简单，递归即可，找到公式 n ! = n × ( n ? 1 ) ! n!=n×(n-1)! n!=n×(n?1)!，即 F a c t o r i a l ( n ) = n × F a c t o r i a l ( n ? 1 ) Factorial(n)=n×Factorial(n-1) Factorial(n)=n×Factorial(n?1)。但这道题目问题在于，n会很大，如果用传统的Long型无法表示这么大的数字。对于这个问题也是有两种做法，第一种就是最简单的使用BigInteger类，第二张就是用整型数组模拟。
1.解题思路 1.1原题 1.1.1题目描述
输入一个正整数n，输出n!的值。其中n!=123*…*n。
1.1.2输入
输入包含一个正整数n，n< =1000。将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。
1.1.3输出
输出n!的准确值
1.2解答 1.2.1思路一(BigInteger)
简单的调用BigInteger类即可

import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] agrs) { Scanner sc = new Scanner(System.in); //传入的参数要是一个字符串 BigInteger nBigInteger=new BigInteger(sc.next()); System.out.println(factorial(nBigInteger).toString()); sc.close(); } public static BigInteger factorial(BigInteger n) { if (n.intValue()==1) { return n; } //multiply表示乘法，subtract表示减法 return n.multiply(factorial(n.subtract(new BigInteger("1")))); } }

1.2.2思路二(整型数组模拟)
这个思路不难想到，但实现起来稍微费点事，需要考虑清楚。
1.2.2.1方案概要把一个数值比较大的整数，从个位开始依次赋值到整型数组arr中，因为n的范围是1-1000，所以n可以用一个int表示。当需要乘n的时候，可以把让n依次与数组中的各位数相乘，有需要进位就进位。简单来看，就是模拟人类处理乘法的过程。
1.2.2.2细节问题如果需要最高位需要进位的时候，需要把数组动态增加一定的位数，此时需要把数组转化为列表，但如果是int[]的数组是没法转化为List的，原因很简单，所以声明的时候最好是Integer[]，但不用担心代码别的地方有太多变动，int和Integer的转化有自动拆箱和装箱操作，无需考虑，把它当int就可以。如果非要用int[]数组的话，转化的时候就需要用Stream流式操作了，这个是Java8的新特性，我也不熟，有机会单独学习一下。最后还需要把列表转化为数组，当然如果声明的时候用的就是列表就无需这一步了。
1.2.2.3代码

import java.util.Arrays; import java.util.List; import java.util.Scanner; import java.util.stream.Collectors; public class Main { public static void main(String[] agrs) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //构造了一个静态类Num Num num = factorial(n); //获取数组 int[] arr = num.getArr(); //倒序遍历输出 for (int i = arr.length - 1; i >= 0; i--) { System.out.print(arr[i]); } sc.close(); }public static Num factorial(int n) { if (n == 1) { int[] arr = {1}; return new Num(arr); } return factorial(n - 1).mul(n); }/** * 静态类Num */ static class Num { /** * 表示Num的数组 */ private int[] arr; /** * 构造器 * * @param arr 表示Num的数组 */ public Num(int[] arr) { super(); this.arr = arr; }public int[] getArr() { return arr; }public void setArr(int[] arr) { this.arr = arr; }/** * 乘法 * * @param another 需要乘的数 * @return 经过乘法运算的数 */ public Num mul(int another) { //需要进位的数字 int remain = 0; //arr[i]*another的结果 int result; for (int i = 0; i < arr.length; i++) { //arr[i]*another的结果 result = arr[i] * another + remain; //模10 arr[i] = result % 10; //进位数 remain = (result - arr[i]) / 10; } //当最高位需要进位时 if (remain != 0) { //转化为列表 List newList = Arrays.stream(arr).boxed().collect(Collectors.toList()); //在这里写while,而不在if那里,避免重复把数组转化为列表 while (remain != 0) { //新增一位模10 newList.add(remain % 10); remain = remain / 10; } //列表转化为数组 arr = newList.stream().mapToInt(Integer::valueOf).toArray(); } return new Num(arr); } } }

1.2.2.4说明虽然自己手动模拟了过程，但效率相比BigInteger内置的乘法差了很多。对比如下：

文章图片
上面的是思路二，下面的是思路一。
为啥BigInteger的效率会那么高呢，带着这个疑问，我去看了一下BigInteger的multiply()方法，发现问题在于，BigInteger对于大数乘法，用了别的算法，而不是这种简单手算。首先思路二本质上是一个大数乘一个不是特别大的数，对应BigInteger中的multiplyByInt(int[] x, int y, int sign)方法。更详细的分析可参考如何得出数组里最大_支付宝面试官问我如何偷偷扣钱给自己，我用这知识点怼翻他…
1.2.2.4.1BigInteger中的multiplyByInt(int[] x, int y, int sign)源码分析源码如下，加了部分注释，有一些问题可见后续分析

/** * 大数乘非大数 * * @param x大数每9位划分一次,从高到低的数组,如18927348347389543834934878, *x[0]保存 18927348 *x[1]保存 347389543 *x[2]保存 834934878 * @param y非大数 * @param sign 正负号 * @return 返回的大数 */ private static BigInteger multiplyByInt(int[] x, int y, int sign) { //如果把y转化成二进制后只有一个1 if (Integer.bitCount(y) == 1) { //只需要根据1后0的个数决定左移的位数,计算机组成原理的知识点 return new BigInteger(shiftLeft(x, Integer.numberOfTrailingZeros(y)), sign); } //x的长度 int xlen = x.length; //新数值的数组 int[] rmag = new int[xlen + 1]; //进位 long carry = 0; //把y转化成long long yl = y & LONG_MASK; //末位 int rstart = rmag.length - 1; //逐位相乘 for (int i = xlen - 1; i >= 0; i--) { long product = (x[i] & LONG_MASK) * yl + carry; rmag[rstart--] = (int) product; //右移32位(二进制下) carry = product >>> 32; } //进位是否为0 if (carry == 0L) { rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length); } else { rmag[rstart] = (int) carry; } return new BigInteger(rmag, sign); }

1.2.2.4.2分析关键地方都有代码注释，可以对照注释看，有几个问题考虑一下。
1.2.2.4.2.1上来就判断2进制下1的个数在计算机组成原理中我们了解过，计算机内部二进制乘的时候，乘二进制的1（也可写作10），相当于把整个数字左移一位，最后一位补0，如果不理解，可以类别十进制下的， 55 ? 10 = 550 55*10=550 55?10=550。具体移动的位数，需要看后面0的个数，如果只有一个0，左移一位，两个0，左移两位，以此类推。
1.2.2.4.2.2大数每9位划分一次 mag是int[]，众所周知int最多由32bit表示，因为有一位符号位，所以最大数值为 2 31 ? 1 2^{31}-1 231?1，转换成10进制是10位（2147483647），如果10位一划分的话，如果出现比2147483647大的数字，比如3147483647，就无法用int表示了。
1.2.2.4.2.3结果的数组rmag最多比原大数多1位整个确定思路和上面的差不多，非大数也是int类型的，最大值是0x7fffffff，也就是左移31位，正好可以在一个int的表示范围内。因此看来，代码层层相扣，非常巧妙。
1.2.2.4.2.4用 & LONG_MASK的方式转换成long 首先弄清楚LONG_MASK是什么。

/** * This mask is used to obtain the value of an int as if it were unsigned. */ final static long LONG_MASK = 0xffffffffL;

这是源码，可以看到这是8个十六进制的f，也就是32个1。根据计算机网络中掩码的知识，掩码一般是用来计算子网划分的。为啥要用在这？
又涉及计算机组成原理的知识了，与运算是最基础的门电路，所以运算速度非常快，而且一般编程语言对其还有优化。虽然也可以直接强制类型转换或者用Long.valueOf()，但都要经过多于的步骤，甚至底层调用的也是与运算。
1.2.2.4.2.5product >>> 32的意义和1.2.2.4.2.1思路相似，也是用到计算机组成原理中乘法运算的知识，这里模拟的是计算机计算乘法的过程，直接相乘，最后在进行移位操作，移动32位原因也是product 最大是32位的。
1.2.2.4.2.6为啥整个方法的效率这么高看了源码之后，可以发现，思路二模拟的是人工运算的过程，源码中模拟的是真实的计算机计算的过程，用到了大量的位运算，无论是速度还是空间都比思路二好很多。
2.总结 【蓝桥杯|蓝桥杯——阶乘计算】虽然这是一道简单的题目，但仔细思考能得出这么多有用的知识。整个源码我读了很久，查了很久的资料才明白的，理解之后才发觉写出这种代码的人是真的厉害。另一方面我也深刻明白了，计算机的408课程（数据结构，计算机网络，计算机组成原理，操作系统）是多么有用。我大二下学组原的时候，因为疫情在家上的，而且组原本来就很难，我真的没咋学明白，全靠老师给的重点考前突击的。感觉组原太接近硬件底层，我学软件的应该用不上整个高深的知识，而且还这么难。我今天才发现，组原很有用，因为软件运行的最高效的方式就是按照底层硬件的方式运行，如果想写成高性能的软件，必然需要了解硬件知识，从计算机硬件的角度去编写代码。