high-precision-algorithm

高精度

​ 在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加、减、乘、除、乘方、阶乘、开方等运算。 对于一个很大的数字N >= 10^ 100，很显然这样的数字无法在计算机中正常存储。于是， 我们想到了办法，将这个数字拆开，拆成一位一位的或者是四位四位的存储到一个数组中，用一个数组去表示一个数字。这样这个数字就被称谓是高精度数。 对于高精度数，也要像平常数一样做加减乘除以及乘方的运算，于是就有了高精度算法。

1.高精度加法

void high_precision_add(string num1, string num2, string& res) {
    int l1 = num1.size(), l2 = num2.size();
    int len = l1 > l2 ? l1 : l2;
    int a[N] = {0}, b[N] = {0};
    for (int i = l1 - 1; i >= 0; i--)
        a[l1 - i - 1] = num1.at(i) - '0';
    for (int i = l2 - 1; i >= 0; i--)
        b[l2 - i - 1] = num2.at(i) - '0';
    for (int i = 0; i < len; i++) {
        a[i] += b[i];
        a[i + 1] += a[i] / 10;
        a[i] %= 10;
    }
    if (a[len])
        len++;
    while (!a[len - 1] && len > 1)
        len--;
    for (int i = len - 1; i >= 0; i--) {
        res += (a[i] + '0');
    }
}

2.高精度乘法

void high_precision_multiply(string num1, string num2, string& res) {
    int l1 = num1.size(), l2 = num2.size();
    int a[N] = {0}, b[N] = {0}, c[N] = {0};
    for (int i = l1 - 1; i >= 0; i--)
        a[l1 - i - 1] = num1.at(i) - '0';
    for (int i = l2 - 1; i >= 0; i--)
        b[l2 - i - 1] = num2.at(i) - '0';
    for (int i = 0; i < l1; i++) {
        for (int j = 0; j < l2; j++) {
            c[i + j] += a[i] * b[j];
            if (a[i] > 9) {
                a[i + 1] += a[i] / 10;
                a[i] %= 10;
            }
        }
    }
    int len = l1 + l2;
    for (int i = 0; i < len; i++) {
        if (c[i] > 9) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }
    while (!c[len - 1] && len > 1)
        len--;
    for (int i = len - 1; i >= 0; i--) {
        res += (c[i] + '0');
    }
}

3.高精度减法

void high_precision_sub(string num1, string num2, string& res) {
    int l1 = num1.size(), l2 = num2.size(), flag = 0;
    if (l1 < l2 || num1.compare(num2) < 0 && l1 == l2) {
        flag = 1;
    }
    int a[N] = {0}, b[N] = {0};
    if (!flag) {
        for (int i = l1 - 1; i >= 0; i--)
            a[l1 - i - 1] = num1.at(i) - '0';
        for (int i = l2 - 1; i >= 0; i--)
            b[l2 - i - 1] = num2.at(i) - '0';
    } else {
        for (int i = l2 - 1; i >= 0; i--)
            a[l2 - i - 1] = num2.at(i) - '0';
        for (int i = l1 - 1; i >= 0; i--)
            b[l1 - i - 1] = num1.at(i) - '0';
    }
    int len = l1 > l2 ? l1 : l2;
    for (int i = 0; i < len; i++) {
        a[i] -= b[i];
        if (a[i] < 0) {
            a[i + 1] -= 1;
            a[i] += 10;
        }
    }
    while (!a[len - 1] && len > 1)
        len--;
    if (flag) {
        res += '-';
    }
    for (int i = len - 1; i >= 0; i--) {
        res += (a[i] + '0');
    }
}

4.高精度除法

void sub(string& num1, string& num2) {
    int l2 = num2.size();
    int low = 0;
    while (num1.at(low) == '0')
        low++;
    for (int i = low; i < l2; i++)
        num1.at(i) = num1.at(i) - num2.at(i) + '0';
    for (int i = l2 - 1; i > low; i--)
        if (num1.at(i) < '0') {
            num1.at(i) += 10;
            num1.at(i - 1)--;
        }
}
void high_precision_div(string num1, string num2, string& res) {
    int p = 0, re[N] = {0};
    int l1 = num1.size();
    int l2 = num2.size();
    if (l1 < l2 || (l1 == l2 && num1.compare(num2) < 0))
        res = "0";
    else {
        while (1) {
            re[p] = 0;
            while (num1.compare(num2) >= 0) {
                sub(num1, num2);
                re[p]++;
            }
            p++;
            if (l1 == l2)
                break;
            num2 = "0" + num2;
            l2++;
        }
        int low = 0;
        while (!re[low])
            low++;
        for (int i = low; i < p; i++)
            res += (re[i] + '0');
    }
}

模板题

阶乘之和

[NOIP1998 普及组] 阶乘之和

题目描述

用高精度计算出 $S = 1! + 2! + 3! + \cdots + n!$（$n \le 50$）。

其中 ! 表示阶乘，定义为 $n!=n\times (n-1)\times (n-2)\times \cdots \times 1$。例如，$5! = 5 \times 4 \times 3 \times 2 \times 1=120$。

输入格式

一个正整数 $n$。

输出格式

一个正整数 $S$，表示计算结果。

样例 #1

样例输入 #1

3

样例输出 #1

9

提示

【数据范围】

对于 $100 %$ 的数据，$1 \le n \le 50$。

【其他说明】

注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 $n \le 20$，使用书中的代码无法通过本题。

如果希望通过本题，请继续学习第八章高精度的知识。

AC代码

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <limits.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define M 100007
#define ll long long
int a[1005],b[1005],n;
int main() {
	int i,j;
	scanf("%d", &n);
	a[0]=b[0]=1;
	for (i=2; i<=n; i++) {
		for (j=0; j<100; j++) {
			b[j]*=i;
		}
		for (j=0; j<100; j++) {
			if (b[j]>9) {
				b[j+1] += b[j]/10;
				b[j]%=10;
			}
		}
		for (j=0; j<100; j++) {
			a[j]+=b[j];
			if (a[j]>9) {
				a[j+1] += a[j]/10;
				a[j]%=10;
			}
		}
	}
	for (i=100; i>=0&&a[i]==0; i--);
	for (j=i; j>=0; j--) printf("%d", a[j]);
	return 0;
}