[acm]大整数专题

大整数专题

一、大整数加法

---

(1) 如何输入大整数

用string 类存大整数，之后用数组来存大整数的每一位

vector stl容器 —— 向量

vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []支持下标运算符 

    支持比较运算，按字典序

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

实现的代码

		string a,b;
    vector<int> A;
    vector<int> B;
    
    cin >> a >> b;
    
    for(int i = a.size() - 1; i >= 0 ; i--) A.push_back(a[i] - '0' );
    for(int i = b.size() - 1; i >= 0 ; i--) B.push_back(b[i] - '0' );

(2) 大整数相加的原理

对于每一次加法

1.相加进位

2.相加不进位

模拟手算这个过程

vector<int> add(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    
    int t = 0; ///进位
    for(int i = 0; i < A.size() || i < B.size() ; i++){
        if( i < A.size() ) t += A[i];
        if( i < B.size() ) t += B[i];
        C.push_back(t%10);
        t /= 10;
    }
    if(t) C.push_back(1);
    return C;
}

(3) 完整代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

vector<int> add(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    
    int t = 0; ///进位
    for(int i = 0; i < A.size() || i < B.size() ; i++){
        if( i < A.size() ) t += A[i];
        if( i < B.size() ) t += B[i];
        C.push_back(t%10);
        t /= 10;
    }
    
    if(t) C.push_back(1);
    
    return C;
}

int main(){
    
    string a,b;
    vector<int> A;
    vector<int> B;
    
    cin >> a >> b;
    
    for(int i = a.size() - 1; i >= 0 ; i--) A.push_back(a[i] - '0' );
    for(int i = b.size() - 1; i >= 0 ; i--) B.push_back(b[i] - '0' );
    
    auto C = add(A,B);
    
    for(int i = C.size() - 1; i >=0 ; i --){
        cout << C[i];
    }
    
    cout << endl;
    return 0;
}

c语言版本

#include<stdio.h>
#include<string.h>
 
 
    int i,j,x,y,c[1010],d[1010],e[1010],t=0;
    char a[1010],b[1010];
 
int main()
{
    while(scanf("%s %s",a,b)!=EOF)
    {
        x=strlen(a);
        y=strlen(b);
         
        int cnt1 = 0,cnt2 = 0;
        for(int i = x - 1; i >= 0 ; i--){
            c[cnt1++] = a[i] - '0';
        }
         
        for(int i = y - 1; i >= 0 ; i--){
            d[cnt2++] = b[i] - '0';
        }
        t = 0;
        for(i=0; i<x || i<y; i++)
        {
            if(i<x)
                t+=c[i];
            if(i<y)
                t+=d[i];
            e[i]=t%10;
            t/=10;
        }
         
        int Max = x>y?x:y;
         
        if( t ) {
            e[Max] = 1;
            Max++;
        }
 
        for(i= Max -1; i>=0; i--)
            printf("%d",e[i]);
        printf("
");
 
    }
    return 0;
}

二、大整数相减

---

(1) 判断A，B的大小

从数组的角度分析

bool cmp(vector<int> &A, vector<int> &B)
{
    if( A.size() > B.size() ){
        return true;
    }
    else if(A.size() < B.size()){
        return false;
    }

//    if( A.size() != B.size() ) return A.size() > B.size();

    for(int i = A.size() ; i >= 0; i--){///从最高位开始比较
        if(A[i] != B[i]) return A[i] > B[i];
    }

    return true;
}

(3) 对不同的情况分类

if( cmp(A,B) ) {
        auto C = sub(A,B);
        for(int i = C.size() - 1; i >= 0 ; i--){
            cout << C[i] ;
        }
    }
    else{
        auto C = sub(B,A);
        cout << "-";
        for(int i = C.size() - 1; i >= 0 ; i--){
            cout << C[i] ;
        }
    }

(3) 模拟相减

vector<int> sub(vector<int> &A , vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size() ; i++)///前面的判断确保了A的size肯定>= B的size
    {
        t = A[i] - t  ;
        if(i < B.size() ) t -= B[i];
        C.push_back( (t + 10) % 10 );///确保就算t为负数也可以直接算为C的一位

        if(t < 0) t = 1;
        else t = 0;
    }

    while( C.back() == 0 && C.size() > 1 ) C.pop_back();

    return C;
}

完整代码

#include <bits/stdc++.h>
using namespace std;

bool cmp(vector<int> &A, vector<int> &B)
{
    if( A.size() > B.size() ){
        return true;
    }
    else if(A.size() < B.size()){
        return false;
    }

//    if( A.size() != B.size() ) return A.size() > B.size();

    for(int i = A.size() ; i >= 0; i--){///从最高位开始比较
        if(A[i] != B[i]) return A[i] > B[i];
    }

    return true;
}

vector<int> sub(vector<int> &A , vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size() ; i++)///前面的判断确保了A的size肯定>= B的size
    {
        t = A[i] - t  ;
        if(i < B.size() ) t -= B[i];
        C.push_back( (t + 10) % 10 );///确保就算t为负数也可以直接算为C的一位

        if(t < 0) t = 1;
        else t = 0;
    }

    while( C.back() == 0 && C.size() > 1 ) C.pop_back();

    return C;
}

int main()
{
    string a,b;
    vector<int> A,B;

    cin >> a >> b;
    for(int i = a.size() - 1; i >= 0; i--)  A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--)  B.push_back(b[i] - '0');

    if( cmp(A,B) ) {
        auto C = sub(A,B);
        for(int i = C.size() - 1; i >= 0 ; i--){
            cout << C[i] ;
        }
    }
    else{
        auto C = sub(B,A);
        cout << "-";
        for(int i = C.size() - 1; i >= 0 ; i--){
            cout << C[i] ;
        }
    }

    cout << endl;

    return 0;
}

三、大数相乘

---

模拟手算

完整代码

**#include <bits/stdc++.h>
using namespace std;

vector<int> mul(vector<int> A, int b )
{
    int t = 0;
    vector<int > C;
    for(int i = 0 ; i < A.size() ||  t; i++){ /// ||t的原因就是很可能最后需要进位的数很大，可能不止进一位
        
        if( i < A.size() ) t += A[i] * b;
        C.push_back( t % 10 );
        t /= 10;
    }
    
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    int b;
    vector<int> A;
    
    cin >> a >> b;
    for(int i = a.size() -1 ; i >= 0 ; i--)   A.push_back( a[i] - '0' );
    
    auto C = mul(A,b);
    
    for(int i = C.size() - 1; i >= 0 ; i--)
        cout << C[i];
    cout << endl;
    return 0;
}**

四、大数相除

---

#include <bits/stdc++.h>
using namespace std;

vector<int > div(vector<int> &A,int b ,int &r)
{
    vector<int > C;
    r = 0;
    for(int i = A.size() - 1; i >= 0 ; i--){
        r = r * 10 + A[i];
        C.push_back( r / b );
        r %= b;
    }
    
    reverse(C.begin() , C.end() );
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    int b;
    vector<int> A;
    cin >>a >> b;
    
    for(int i = a.size() -1 ; i >= 0 ; i--) A.push_back(a[i] - '0');
    
    int r;
    
    auto C = div(A,b,r);
    
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    cout << endl << r << endl;
    return 0;
}