大数乘法 阶乘

比如50的阶乘结果是65位, 而 int 的范围是 10 ^ 9, long long 的范围是 10 ^ 18

  • 由于运算结果已经远远超出计算机能表达的范围了,因此衍生出模拟笔算乘法, 并且使用数组, 来保存运算结果的方法

    大数乘法

    思路

    模拟笔算乘法, 如图
    大数乘法 阶乘 - 图1
    由于我们对笔算乘法已经了然于心, 因此几乎不用思考就能算出结果, 但是如果我们慢下来一步一步思考, 我们可以发现一些规律
  1. 计算乘法时, 每次都是拿 23 的一位数, 与 123 相乘, 相乘次数是 2 次, 即 23 的位数;
  2. 而拿3 或 2 与 123 相乘时, 相乘次数是3, 即123的位数;
  3. 计算加法时, 每次都需要向左偏移一位

发现这些规律后, 可以发现

  • 第 1 步是一个大循环, 循环次数为 23 即第二个数的位数
  • 第 2 步和第 3 步, 是内部的小循环, 循环次数分别是, 123 即第一个数的位数, 和 23 的位数减一

开始动手

代码实现

模拟笔算乘法
为了方便, 我从下标 0 开始处理数据, 读取后需要逆转一下数据, 所以我先使用字符数组(即字符串)读取数据, 处理后在转移到整形数组

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstring>
  4. using namespace std;
  5. #define Int(x)     (x - '0')
  7. int main() {
  8.     int num1[105] = {0}, num2[105] = {0}, ret[205] = {0};
  9.     char n1[105], n2[105];
  10.     scanf("%s%s", n1, n2);
  12.     //这几步只是单纯方便读取及逆序处理 
  13.     int len1 = strlen(n1), len2 = strlen(n2); 
  14.     reverse(n1, n1 + len1);
  15.     reverse(n2, n2 + len2);
  16.     for (int i = 0; i < len1; i++) {
  17.         num1[i] = Int(n1[i]);
  18.     }
  19.     for (int i = 0; i < len2; i++) {
  20.         num2[i] = Int(n2[i]);
  21.     }
  22.     //模拟笔算乘法
  23.     int carry;
  24.     int t[100], temp;
  25.     int tlen, offset = 0, rlen;
  26.     for (int i = 0; i < len2; i++) { //笔算乘法 次数为第二个数的位数 
  27.         carry = 0; //此处为乘法进位 
  28.         memset(t, 0, sizeof(t)); //临时数组每次使用前都需要清零 
  29.         tlen = 0;
  30.         for (int j = 0; j < len1; j++) {  
  31.         //每次拿出第二个数的一个数 与 第一个数相乘 次数为第一个数的位数 
  32.             temp = num1[j] * num2[i] + carry;
  33.             t[tlen++] = temp % 10;
  34.             carry = temp / 10;
  35.         }
  36.         if (carry) {
  37.             t[tlen++] = carry;
  38.         }
  39.         carry = 0;  //此处为加法进位 
  40.         rlen = offset; //偏移位 笔算中每次向左偏移一位 因为在这里逆序保存 所以变成向右偏移一位 
  41.         for (int i = 0; i < tlen; i++) {
  42.             temp = ret[i + offset] + t[i] + carry;
  43.             ret[i + offset] = temp % 10;
  44.             carry = temp / 10;
  45.             rlen++;
  46.         }
  47.         if (carry) {
  48.             ret[rlen++] = carry;
  49.         }
  50.         offset++;
  51.     }
  52.     for (int i = rlen - 1; i >= 0; i--) {
  53.         cout << ret[i];
  54.     }
  55.     cout << endl;
  57.     return 0;
  58. }

运行结果

大数乘法 阶乘 - 图2

大数阶乘

思路

既然大数乘法我们都解决, 那么大数阶乘也是相同思路, 每次都是两个数相乘, 不过要注意的是, 我这里输入的数据是在 int 范围内的, 所以就不用使用字符串来保存乘数, 只需要一个数据来保存结果即可

代码实现

  1. #include <iostream>
  2. using namespace std;
  3. int main() {
  4.     int a[20001];//储存每一位所得到的数 
  5.     int temp,digit,n;//temp每次的得数   digit每次得数的位数 
  6.     int carry; 
  7.     cin >> n;
  8.     a[0] = 1;//从1开始乘 
  9.     digit = 1;//位数从第一位开始 
  10.     for (int i = 2; i <= n; i++) {
  11.         carry = 0;
  12.         for (int j = 0; j < digit; j++) {
  13.             temp = a[j] * i + carry;//将一个数的每一位数都分别乘以i， 
  14.             a[j] = temp % 10;
  15.             carry = temp/10;
  16.         }
  17.         //处理进位
  18.         //此时由于不像大数乘法那样两个数都是个位数相乘
  19.         //有可能是多位数乘单位数, 所以进位不止一位
  20.         //需要循环处理进位, 一直到进位为0
  21.         while (carry) {
  22.             a[digit] = carry % 10; 
  23.             carry = carry / 10;
  24.             digit++;
  25.         }
  26.     }
  27.     for (int i = digit-1; i >= 0; i--)//倒序输出每一位 
  28.         printf("%d", a[i]);
  29.     printf("\n");
  30.     return 0;
  31. }

运行结果

大数乘法 阶乘 - 图3

最最最重要的总结部分