高精度计算

发表于 | 更新于 | 分类于

高精度

(高精度 * int)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> mul(vector<int> a, int b)			//高精度乘法
{
if(b == 0 || (a.size() == 1 && a[0] == 0)) 	//乘积为0的两种特殊情况
        return vector<int> (1, 0);		//返回容器式的 0
    vector<int> c;		//答案(由于从低位开始算，最终答案会是逆序)
    int t = 0;				//每一位上的乘积结果
    for(int i = a.size() - 1; i >= 0; i -- )
    {
        t += a[i] * b;				//模拟人工手算，高精度的每一位乘上b
        c.push_back(t % 10);	//将最低位存入答案，下一位进行计算时需要进位
        t /= 10;			//进位，右移(模拟手算)
    }
    while(t)			//剩下的位继续存入答案
    {
        c.push_back(t % 10);		//取最低位
        t /= 10;			//进位，左移，方便与高位进行运算
    }
    return vector<int> (c.rbegin(), c.rend());		//由于答案是逆序的，再逆序返回
}

高精度 / int

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
vector<int> div(vector<int> a, int b)		//高精度除法
{
    vector<int> res;
    int t = 0;				//进行积累的被除数
    bool first = true; 			//判断第一个没有出现的0为止(前缀会有无用0，这样可以丢弃那些 0)
    for(int i = 0; i < a.size(); i ++ )			//除法，高位往低位移
    {
        t = t * 10 + a[i];			//模拟手工除法，每次向后移一位
        int x = t / b;			//每步的除数
        if(!first || x)		//如果能除数大于0(找到第一个不为0的位置)
        {
            first = false;			//找到第一个不为0的位置，之后的每步计算结果都记录(包括后面的 0)
            res.push_back(x);		//存入答案，这是正序(由于是高位往低位)
        }           
        t %= b;		//取余数继续进行下一次的除
    }
    return res;
}

vector<int> max_vec(vector<int> a, vector<int> b)			//高精度比大小
{				//a, b都是正序
    if(a.size() > b.size())     return a;	//a的位数更多		
    if(a.size() < b.size())     return b;		//b的位数更多
    if(a > b)   return a;		//相同位数直接比字典序
    return b;
}

高精度 + 高精度

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef vector<int> vec;
vec pluss(vec a, vec b, int len)	//都是vec类型相加，答案最大长度为max_len(a, b) + 1
{
    vec ans;
    int t = 0;
    for(int i = 0; i < len; i ++ )		//倒序相加，由于处理时是逆序存入的
    {
        t += a[i] + b[i];		//上一位进来的数 + 本身这位的两位数
        ans.push_back(t % 10);			//取余
        t /= 10;			//进位
    }
    if(t)   ans.push_back(t);		//由于答案 >= max_len
    return vec (ans.rbegin(), ans.rend());				//调整为正序返回
}
char s1[501], s2[501];
int main()
{
    int i, k, len = 0;
    vec a(500), b(500);
    scanf("%s", s1);
    for(i = strlen(s1) - 1, k = 0; i >= 0; i --, k ++ )		//逆序输入处理
        a[k] = s1[i] - '0'; 
    len = max(len, k);
    scanf("%s", s2);
    for(i = strlen(s2) - 1, k = 0; i >= 0; i --, k ++ )
        b[k] = s2[i] - '0';
    len = max(len, k);
    vec res = pluss(a, b, len);
    for(auto x : res)
        cout << x;
    return 0;
}

高精度 - 高精度

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char a[100005], b[100005];
int l1, l2;
bool cmp()
{
    if(l1 > l2)     return true;
    if(l1 < l2)     return false;
    if(strcmp(a, b) >= 0)    return true;
    return false;
}

void print(char a[], int l1)
{
    for(int i = 0; i < l1; i ++ )
    {
        if(a[i] > '0')
        {
            puts(a + i); 
            return;
        }
    }
    puts("0");
}

void work(char a[], int l1, char b[], int l2)
{
    for(int i = l1 - 1, j = l2 - 1; ~i; i -- , j -- )
    { 
        if(j >= 0)  a[i] = a[i] - b[j] + '0';
        if(a[i] < '0')  
            a[i - 1] --, a[i] += 10;
    }
    print(a, l1);
}

int main()
{
    scanf("%s %s", a, b);
    l1 = strlen(a), l2 = strlen(b);
    if(cmp())   work(a, l1, b, l2);
    else    
    {
        printf("-");
        work(b, l2, a, l1);
    }
    return 0;
}

高精度 * 高精度

思想：点阵乘法

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef vector<int> vec;
vec mul(vec a, vec b, int len)
{
    if(a.size() == 1 && a[0] == 0 || (b[0] == 0 && b.size() == 1))	  //被乘数含0，直接返回0
        return vec (1, 0);
    vec ans(len);
    for(int i = 0; i < a.size(); i ++ )
        for(int j = 0; j < b.size(); j ++ )
            ans[len - 2 - i - j] += a[i] * b[j];			//对应位
    for(int i = 0; i < len - 1; i ++ )   
    {
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }
    if(!ans[len - 1])    ans.pop_back();		//pro最大为a + b, 最小为a + b - 1
    return vec (ans.rbegin(), ans.rend());	//还原顺序返回
}
char s1[501], s2[501];
int main()
{
    vec a, b;
    int len = 0;
    scanf("%s", s1);		//处理输入
    for(int i = 0; i < strlen(s1); i ++ )
        a.push_back(s1[i] - '0'); 
    len += strlen(s1);
    scanf("%s", s2);
    len += strlen(s2);
    for(int i = 0; i < strlen(s2); i ++ )
        b.push_back(s2[i] - '0');
    vec res = mul(a, b, len);			//最长可能长度
    for(auto x : res)
        cout << x;
    return 0;
}

高精度 / 高精度

思想: 模拟手工计算，对于前l1 ~ l2位每位判断能减几次(高精度减法)

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
55
56
57
58
59
60
61
#include <stdio.h>
#include <string.h>
char str1[105], str2[105];
int n1[105], n2[105], ans[105];
int check(int a[], int b[], int l1, int l2)
{
	for(int i = l1, j = l2; j >= 1; i --, j -- )
	{
		if(a[i] > b[j]) 	return 1;
		if(a[i] < b[j])		return 0;
	} 
	return 1;
} 

int sub(int a[], int b[], int p, int l2)
{
	for(int i = p - l2 + 1, j = 1; j <= l2; i ++, j ++ )
	{
		a[i] -= b[j];
		if(a[i] < 0)
			a[i] += 10, a[i + 1] --; 
	} 
}

void print(int p)
{
	int f_zero = 0;
	for(int i = 1; i <= p; i ++ )
	{
		if(f_zero || ans[i])
		{
			f_zero = 1;
			printf("%d", ans[i]);
		}
	}
	if(!f_zero)
		printf("0\n");
}
int main()
{
	scanf("%s %s", str1 + 1, str2 + 1);
	int l1 = strlen(str1 + 1), l2 = strlen(str2 + 1);
	for(int i = l1, j = 1; i >= 1; i --, j ++ )
		n1[j] = str1[i] - '0';
	for(int i = l2, j = 1; i >= 1; i --, j ++ )
		n2[j] = str2[i] - '0';
	int cnt, k = 0;
	for(int p = l1; p >= l2; p -- )
	{
		cnt = 0;
		while(check(n1, n2, p, l2))
		{ 
			cnt ++; 
			sub(n1, n2, p, l2);
		} 
		n1[p - 1] += n1[p] * 10;
		ans[ ++ k] = cnt;
	} 
	print(k);
	return 0;
}
0%