大整数的四则运算.txt

大整数的四则运算,搞ACM时丰常常用,我当时是屡试不爽,传上来大家分享

//20、大数运算处理基本函数
#include<string.h>
#include <iostream.h>
#include<stdio.h>
const int N = 1100;
struct big_num{
    int ele[N];
    int front;
};
typedef struct big_num bigNum;
void print_bigNum(const bigNum& num)
{
    for(int i = num.front; i < N; ++i)
        printf("%d", num.ele[i]);
}
void println_bigNum(const bigNum& num)
{
    for(int i = num.front; i < N; ++i)
        printf("%d", num.ele[i]);
    printf("\n");
}
bigNum multi_bigNum(const bigNum& num1, const bigNum& num2)
{
    bigNum temp;
    bigNum num3;
    int i, j, carry;
    int temp_int;
    num3.front = num1.front + num2.front - N;
    for(i = num3.front; i < N; ++i)
        num3.ele[i] = 0;
    for(i = N - 1; i >= num1.front; --i)
    {
        carry = 0;
        for(j = N - 1; j >= num2.front; --j)
        {
            temp_int = num2.ele[j] * num1.ele[i] + carry;
            temp.ele[j] = temp_int % 10;
            carry = temp_int / 10;
        }
        temp.front = num2.front;
        if(carry != 0)
            temp.ele[--temp.front] = carry;
        carry = 0;
        for(j = N - 1; j >= temp.front; --j)
        {
            temp_int = num3.ele[i + j + 1 - N] + temp.ele[j] + carry;
            if(temp_int >= 10)
            {
                num3.ele[i + j + 1 - N] = temp_int - 10;
                carry = 1;
            }
            else
            {
                num3.ele[i + j + 1 - N] = temp_int;
                carry = 0;
            }
        }
        while(carry == 1)
        {
            temp_int = num3.ele[i + j + 1 - N] + carry;
            if(temp_int >= 10)
            {
                num3.ele[i + (j--) + 1 - N] = temp_int - 10;
                carry = 1;
            }
            else
            {
                num3.ele[i + (j--) + 1 - N] = temp_int;
                carry = 0;
            }
        }
    }
    while(num3.ele[num3.front] == 0 && num3.front < N - 1)
        ++num3.front;
    return num3;
}
bigNum add_bigNum(const bigNum& num1, const bigNum& num2)
{
    bigNum num3;
    num3.front = num1.front;
    if(num3.front < num2.front)
        num3.front = num2.front;
    int carry = 0;
    int i;
    for(i = N - 1; i >= num3.front; --i)
    {
        num3.ele[i] = num2.ele[i] + num1.ele[i] + carry;
        carry = num3.ele[i] / 10;
        num3.ele[i] %= 10;
    }
    if(num3.front == num2.front)
    {
        num3.front = num1.front;
        for(; i >= num3.front; --i)
        {
            num3.ele[i] = num1.ele[i] + carry;
            carry = num3.ele[i] / 10;
            num3.ele[i] %= 10;
        }
        if(carry == 1)
        {
            --num3.front;
            num3.ele[num3.front] = 1;
        }
    }
    else
    {
        num3.front = num2.front;
        for(; i >= num3.front; --i)
        {
            num3.ele[i] = num2.ele[i] + carry;
            carry = num3.ele[i] / 10;
            num3.ele[i] %= 10;
        }
        if(carry == 1)
        {
            --num3.front;
            num3.ele[num3.front] = 1;
        }
    }
    return num3;
}
void string_to_bigNum(bigNum& num, const char s[])
{
    num.front = N - strlen(s);
    for(int i = num.front; i < N; ++i)
        num.ele[i] =s[i-num.front]-'0'; 
}
// 0 <= a <= 10
void muti_by_one(const bigNum& num1, int a, bigNum& num2)
{
    int temp;
    int carry = 0;
    int i;
    if(a == 0)
    {
        num2.ele[N - 1] = 0;
        num2.front = N - 1;
        return;
    }
    if(a == 10)
    {
        for(i = num1.front; i < N; ++i)
            num2.ele[i - 1] = num1.ele[i];
        num2.ele[N - 1] = 0;
        num2.front = num1.front - 1;
    }
    for(i = N - 1; i >= num1.front; --i)
    {
        temp = a * num1.ele[i] + carry;
        num2.ele[i] = temp % 10;
        carry = temp / 10;
    }
    if(carry == 0)
        num2.front = num1.front;
    else
    {
        num2.front = num1.front - 1;
        num2.ele[i] = carry;
    }
}
int comp_bigNum(const bigNum& num1, const bigNum& num2)
{
    int i;
    if(num1.front != num2.front)
    {
        if(num1.front < num2.front)
            return 1;
        else
            return -1;
    }
    for(i = num1.front; i < N; ++i)
        if(num1.ele[i] != num2.ele[i])
        {
            if(num1.ele[i] > num2.ele[i])
                return 1;
            else
                return -1;
        }
    return 0;
}
bool comp_bigNum_0(const bigNum& num1)
{
    return (num1.ele[N - 1] == 0) && (num1.front == N - 1);
}
//这里只能让大数减小数，如果num1 < num2 则交换num1 和 num2 的顺序
bigNum minus_bigNum(const bigNum& num1, const bigNum& num2)
{
    bigNum num3;
    int temp;
    int i;
    temp = comp_bigNum(num1, num2);
    if(temp < 0)
    {
        num3 = minus_bigNum(num2, num1);
        return num3;
    }
    if(temp == 0)
    {
        num3.front = N - 1;
        num3.ele[N - 1] = 0;
        return num3;
    }
    int carry = 0;
    for(i = N - 1; i >= num2.front; --i)
    {
        temp = num1.ele[i] - num2.ele[i] - carry;
        if(temp < 0)
        {
            temp += 10;
            carry = 1;
        }
        else
            carry = 0;
        num3.ele[i] = temp;
    }
    while(i >= num1.front)
    {
        temp = num1.ele[i] - carry;
        if(temp < 0)
        {
            temp += 10;
            carry = 1;
        }
        else
            carry = 0;
        num3.ele[i] = temp;
        --i;
    }
    num3.front = num1.front;
    while(num3.ele[num3.front] == 0)
        ++num3.front;
    return num3;
}
//需要再调用前检查num2是否为0
bigNum div_bigNum(const bigNum& num1, const bigNum& num2, bigNum& num4)
{
    bigNum num3;
    if(comp_bigNum(num1, num2) < 0)
    {
        num4 = num1;
        num3.front = N - 1;
        num3.ele[N - 1] = 0;
        return num3;
    }
    int num[N];
    int num_end = 0;
    int num1_cur = num1.front + N - 1 - num2.front;
    int i;
    bigNum temp_bigNum;
    bigNum cut_bigNum;
    bigNum pre_bigNum;
    cut_bigNum.front = num2.front + 1;
    for(i = num1.front; i < num1_cur; ++i)
        cut_bigNum.ele[cut_bigNum.front + i - num1.front] = num1.ele[i];
    while(num1_cur < N)
    {
        if(!comp_bigNum_0(cut_bigNum))
        {
            for(i = cut_bigNum.front; i < N; ++i)
                cut_bigNum.ele[i - 1] = cut_bigNum.ele[i];
            --cut_bigNum.front;
        }
        cut_bigNum.ele[N - 1] = num1.ele[num1_cur++];
        temp_bigNum.front = N - 1;
        temp_bigNum.ele[N - 1] = 0;
        for(i = 1; i <= 10; ++i)
        {
            pre_bigNum = temp_bigNum;
            muti_by_one(num2, i, temp_bigNum);
            if(comp_bigNum(temp_bigNum, cut_bigNum) > 0)
                break;
        }
        num[num_end++] = i - 1;
        cut_bigNum = minus_bigNum(cut_bigNum, pre_bigNum);
    }
    num4 = cut_bigNum;
    num3.front = N;
    for(i = num_end - 1; i >= 0; --i)
        num3.ele[--num3.front] = num[i];
    while(num3.ele[num3.front] == 0)
        ++num3.front;
    return num3;
}/*
void print_bigNum(const bigNum&);
void println_bigNum(const bigNum& num);
bigNum multi_bigNum(const bigNum& num1, const bigNum& num2);
bigNum add_bigNum(const bigNum& num1, const bigNum& num2);
void string_to_bigNum(bigNum& num, const char s[]);
void muti_by_one(const bigNum& num1, int a, bigNum& num2);
int comp_bigNum(const bigNum& num1, const bigNum& num2);
bool comp_bigNum_0(const bigNum& num1);
bigNum minus_bigNum(const bigNum& num1, const bigNum& num2);
bigNum div_bigNum(const bigNum& num1, const bigNum& num2, bigNum& num4);*/
int main()
{
    bigNum num1, num2, num3, num4;
    char s[550];
    while(cin >> s)
    {
        string_to_bigNum(num1, s);
        cin >> s;
        string_to_bigNum(num2, s);
        num3 = minus_bigNum(num1, num2);
        println_bigNum(num3);
    }
    return 0;
}