算法笔记-第五章-大整数运算

大整数运算

一：使用数组存储整数的时候，整数的高位存储在数组的高位，整数的低位存储
在数组的低位
二：把整数按照字符串读入的时候，实际是逆序存储的，就是在读入数组的首需要翻转一下

比如说12345存储在数组当中应该是54321

#include<stdio.h>
#include<string.h>
struct bign
{
   
    int d[100];//这里需要获取大整数的长度，设置一个结构通
    int len;

    bign()
    {
   
        memset(d, 0, sizeof(d));//在定义结构体之后，就需要初始化结构体
        int len = 0;
    }
};
bign change(char str[])//将字符串转化成bign
{
   
    bign a;
    a.len = strlen(str);
    for (int i = 0; i < a.len; i++)
    {
   
        a.d[i] = str[a.len - i - 1] - '0';
    }
    return a;
}
bign add(bign a, bign b)
{
   
    bign c;
    int carry = 0;//这个是进位
    for (int i = 0; i < a.len || i < b.len; i++)
    {
   
        int t = a.d[i] + b.d[i] + carry;
        a.d[c.len++] = t % 10;
        carry = t / 10;
    }
    if (carry != 0)
    {
   
        c.d[c.len++] = carry;
    }
    return c;
}
void print(bign a)


{
   
    for (int i = a.len - 1; i > +0; i--)
    {
   
        printf("%d", a.d[i]);
    }
}
int main()
{
   
    char str1[1000], str2[1000];
    scanf_s("%s%s", str1, str2);
    bign a = change(str1);
    bign b = change(str2);
    print(add(a, b));
    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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

大整数比较

vector简单模拟大整数
typedef vector Bigint;
使用容器来存储
一个vector便可以模拟一个大整数，每位数字倒序储存在vector中
把大整数当作string输入

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

typedef vector<int> BigInt;

BigInt toBigInt(string nums) {
   
    BigInt result;
    for (int i = (int)nums.length() - 1; i >= 0; i--) {
   
        result.push_back(nums[i] - '0');
    }
    return result;
}
int compare(BigInt a, BigInt b) {
   
    if (a.size() > b.size()) {
   
        return 1;
    }
    else if (a.size() < b.size()) {
   
        return -1;
    }
    else {
   
        for (int i = 
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