60分求助

AKkkk_TIX @ 2024-08-07 18:57:49

//大整数存储：    0下标存储个位数，
//      实现： 以字符串方式输入大整数，转换字符数组为数字数组，逆置数字数组
#include<iostream>
#include<cstring>
using namespace std;
char c1[101],c2[101];
int x[100],y[100],z[101];

int main()
{
    freopen("bignumber.in","r",stdin);
    //freopen("bignumber.out","w",stdin);

    //输入大整数到字符数组 
    cin>>c1>>c2;

    //字符转换数字 
    int len1=strlen(c1);
    int len2=strlen(c2);
    //cout<<len1; 
    for(int i=0;i<len1;i++)
        x[i]=c1[i]-'0';
    for(int i=0;i<len2;i++)
        y[i]=c2[i]-'0';
    //for(int i=0;i<len1;i++)
    //  cout<<a[i]<<" ";

    //逆置 
    for(int i=0;i<len1/2;i++)
        swap(x[i],x[len1-1-i]);
    for(int i=0;i<len2/2;i++)
        swap(y[i],y[len2-1-i]);
    //for(int i=0;i<len2;i++)
    //  cout<<y[i]<<" ";
    //cout<<endl;

    //消除前导零
    for(int i=len1-1; i>0&&x[i]==0; len1--,i--);
    for(int i=len2-1; i>0&&y[i]==0; len2--,i--); 

    if(len1==1&&x[0]==0||len2==1&&y[0]==0)
    {
        cout<<0;
        return 0;
    }

    //a*b
    for(int i=0;i<len1;i++)
        for(int j=0;j<len2;j++)
        {
            z[i+j]+=x[i]*y[j];
            z[i+j+1]+=z[i+j]/10;
            z[i+j]=z[i+j]%10;
        }

    //位数判断 
    int len=len1+len2;
    if(z[len-1]==0)
        len--;

    //输出大整数 
    for(int i=len-1;i>=0;i--)
        cout<<z[i]; 
}

by AKkkk_TIX @ 2024-08-07 18:58:34

请忽略freopen:)

by All_Wrong_Answer @ 2024-08-07 19:01:38

@a_programmer

数组开大点，有2000位

by AKkkk_TIX @ 2024-08-07 19:05:01

@jury01 80分了又

#include<iostream>
#include<cstring>
using namespace std;
char c1[2001],c2[2001];
int x[2000],y[2000],z[2001];

int main(){
    cin >> c1 >> c2;

    int len1 = strlen(c1);
    int len2 = strlen(c2);

    for(int i = 0;i < len1;i++)
        x[i] = c1[i] - '0';
    for(int i = 0;i < len2;i++)
        y[i] = c2[i] - '0';

    for(int i = 0;i < len1 / 2;i++)
        swap(x[i], x[len1 - 1 - i]);
    for(int i = 0;i < len2 / 2;i++)
        swap(y[i], y[len2 - 1 - i]);

    for(int i = len1 - 1;i > 0 && x[i] == 0;len1--,i--);
    for(int i = len2 - 1;i > 0 && y[i] == 0;len2--, i--); 

    if(len1 == 1 && x[0] == 0 || len2 == 1 && y[0] == 0){
        cout << 0;
        return 0;
    }

    for(int i = 0;i < len1;i++)
        for(int j = 0;j < len2;j++){
            z[i + j] += x[i] * y[j];
            z[i + j + 1] += z[i + j] / 10;
            z[i + j] = z[i + j] % 10;
        }

    int len = len1 + len2;
    if(z[len - 1] == 0)
        len--;

    for(int i = len - 1;i >= 0;i--)
        cout << z[i];   
    return 0;
}

测评记录

by All_Wrong_Answer @ 2024-08-07 19:06:07

@a_programmer

我用你代码开到10000就过了

记录： https://www.luogu.com.cn/record/171222987

by bcdmwSjy @ 2024-08-07 19:08:49

@a_programmer 要开到 4000+

by AKkkk_TIX @ 2024-08-07 19:12:18

@jury01 @bcdmwSjy 确实，谢谢大佬

by pmkmzfuzsotqotmzs @ 2024-08-08 13:41:47

#include <iostream>
#include <string>
using namespace std;
#define MAX_N 10010

struct BigInt {
    int data[MAX_N];        // 数据
    bool is_negative;       // 是否为负数。true: 是负数; false: 不是负数
    int len;                // 数的长度
};

// 比较两个BigInt的绝对值大小
int abs_compare(BigInt &a, BigInt &b)
{
    /*
    如果a > b，return 1
    如果a == b，return 0
    如果a < b，return -1
    */

    // 如果a的长度大于b的长度
    if (a.len > b.len) return 1;
    // 如果b的长度大于a的长度
    else if (a.len < b.len) return -1;
    else
    {
        // 长度相同，由高至低比较
        for (int i = a.len-1; i >= 0; i--)
        {
            if (a.data[i] > b.data[i]) return 1;
            else if (a.data[i] < b.data[i]) return -1;
        }
        return 0;
    }
}

// 将一个BigInt清空，将这个BigInt设置为零。
void clear(BigInt &a)
{
    a.is_negative = false;
    a.len = 0;
}

// 将两个BigInt相加，返回相加的结果
BigInt add(BigInt &a, BigInt &b)
{
    BigInt res;
    clear(res);

    if (a.is_negative == b.is_negative)
    {
        // 两个数的符号相同，直接相加
        res.is_negative = a.is_negative;
        int len = max(a.len, b.len);

        // 进位
        int carry = 0;
        for (int i = 0; i < len; i++)
        {
            int temp = a.data[i] + b.data[i] + carry;
            res.data[res.len++] = temp % 10;
            carry = temp / 10;
        }

        // 进位
        if (carry != 0)
            res.data[res.len++] = carry;
    }
    else
    {
        // 两个数的符号不同，则需要先比较两个数的绝对值大小
        int cmp = abs_compare(a, b);
        if (cmp == 0)
        {
            // 绝对值相等
            res.is_negative = false;
            res.len = 1;
            res.data[0] = 0;
        }
        else
        {
            // 两个数的绝对值不相等，用绝对值大的减去绝对值小的
            // 运算结果的正负，取决于绝对值大的正负
            if (cmp == 1)
                res.is_negative = a.is_negative;
            else
                res.is_negative = b.is_negative;

            int len = max(a.len, b.len);

            if (cmp == 1)
            {
                int carry = 0;
                for (int i = 0; i < len; i++)
                {
                    int temp = a.data[i] - b.data[i] - carry;
                    if (temp < 0)
                    {
                        temp += 10;
                        carry = 1;
                    }
                    else
                        carry = 0;
                    res.data[res.len++] = temp;
                }
            }
            else
            {
                int carry = 0;
                for (int i = 0; i < len; i++)
                {
                    int temp = b.data[i] - a.data[i] - carry;
                    if (temp < 0)
                    {
                        temp += 10;
                        carry = 1;
                    }
                    else
                        carry = 0;
                    res.data[res.len++] = temp;
                }
            }
            while (res.data[res.len - 1] == 0 && res.len > 1)
            {
                res.len--;
            }
        }
    }
    return res;
}

// 将两个BigInt相减
BigInt sub(BigInt &a, BigInt &b)
{
    BigInt temp = b;
    temp.is_negative = !temp.is_negative;
    return add(a, temp);
}

// 将两个BigInt相乘
BigInt mul(BigInt &a, BigInt &b)
{
    BigInt res;
    clear(res);

    // 竖式乘法
    // TODO
    int len=a.len+b.len;
    for(int i=0;i<a.len;i++)
    {
        for(int j=0;j<b.len;j++)
        {
            res.data[i+j]+=a.data[i]*b.data[j];
        } 
    }
    for(int i=0;i<len;i++)
    {
        res.data[i+1]+=res.data[i]/10;
        res.data[i]%=10;
    } 
    while(res.data[len-1]==0&&len>1)
        len--;
    res.len=len;
    res.is_negative=a.is_negative^b.is_negative;
    return res;
}

// 输出一个BigInt
void output(BigInt &a)
{
    // 是负数，则输出负号
    if (a.is_negative)
        cout << "-";

    // 从后往前输出
    for (int i = a.len - 1; i >= 0; i--)
        cout << a.data[i];
    cout << endl;
}

// 读入一个BigInt
void read_my_bigint(BigInt &a)
{
    string str;
    cin >> str;

    if (str[0] == '-')
    {
        a.is_negative = true;
        str.erase(0, 1);        // 将'-'从字符串中删除
    }
    else
        a.is_negative = false;

    a.len = str.size();

    for (int i = a.len - 1; i >= 0; i--)
        a.data[i] = str[a.len-1-i] - '0';
}

int main()
{
    BigInt a, b;
    // 读入两个BigInt
    read_my_bigint(a);
    read_my_bigint(b);

    // output(a);
    // output(b);
    // 执行乘法操作
    BigInt res = mul(a, b);

    // 相减
    output(res);
    return 0;
}