数据结构大整数加法有待改正，请大家能够帮帮忙。,萌新交流区,萌新训练营,鱼C论坛

白砂糖 发表于 2020-12-28 10:34:56

数据结构大整数加法有待改正，请大家能够帮帮忙。

大整数加法运算
窗体底端
【问题描述】
给定测试数据若干组，每组有两个100位以内的正整数，要求程序给出这两个正整数相乘的结果。

【输入格式】
第一行为数据的组数 N，后面有N组测试数据，每组测试数据占一行，每行有两个100位以内的十进制整数。

【输出格式】

输出每一组测试数据的运算结果，每行一个结果。

【示例】
[输入]
6
47858628539074 212821064467
51357484452396 62369401380260
41972493335 769524402008059
16223931314069 936153278101
11775956124 981003321643
4648312830247 63220212506777
[输出]
10185324269616473782483558
3203135561691948572664102960
32298857834403116993786765
15188086483351158930902969
11552252073166227591732
293867324926193383538083919

我用的是vs2019

#include<iostream>
#include<string>
using namespace std;
const int MAX = 100;
class bigint
{
public:
bigint() { length = 0; }
bigint(int a[],int n);
~bigint() {};
friend bigint addition(bigint a, bigint b);
void Printlist();
private:
int data;
int length;
};
bigint::bigint(int a[],int n)
{
length = n;
if (length > MAX)throw"yichu";
n--;
for (int i = 0; i < length; i++)
data = a;

}
bigint addition(bigint A, bigint B)
{
int flag = 0, i = 0;
int n, m,len;

bigint C;
n = A.length;
m = B.length;
len = n > m ? n : m;
for (i = 0; i < len; i++)
{
C.data = A.data + B.data;
if (C.data > 9)
{
C.data -= 10;
C.data += 1;
}
}
if (C.data != 0)
len++;
return C;
}
void bigint::Printlist()
{
for (int i = length - 1; i >= 0; i--)
cout << data << endl;
}
int main()
{
string a, b;
int a1, b1;

cout << "请输入1个大数：";

cin >> a;
cout << endl;
cout << "请输入第二个大数：";
cin >> b;
int lena, lenb;
lena = a.size();
lenb = b.size();
for (int i = 0; i < lena; i++)
{
a1 = a - '48';
}
for (int i = 0; i < lenb; i++)
{
b1 = b - '48';
}
bigint A(a1, lena), B(b1, lenb);
bigint C;
C = addition(A, B);

cout << "结果：";
C.Printlist();
return 0;
}

xieglt 发表于 2020-12-28 10:34:57

fft算法，最快的乘法了，如果再不行，我也没办法。

#include <iostream>
#include <math.h>
#include <string>

#define PI (3.1415926535897932)

typedef struct tagComplex
{
double X;
double Y;

tagComplex()
{
X = 0;
Y = 0;
}

tagComplex(const struct tagComplex & c)
{
X = c.X;
Y = c.Y;
}

tagComplex(double x,double y = 0.0)
{
X = x;
Y = y;
}

struct tagComplex & operator = (double x)
{
X = x;
Y = 0;
return * this;
}

struct tagComplex & operator = (const tagComplex & c)
{
X = c.X;
Y = c.Y;
return * this;
}

struct tagComplex & operator += (const tagComplex & c)
{
X += c.X;
Y += c.Y;
return * this;
}

struct tagComplex & operator -= (const tagComplex & c)
{
X -= c.X;
Y -= c.Y;
return * this;
}

struct tagComplex & operator *= (const tagComplex & c)
{
COMPLEX t = * this;
X = t.X * c.X - t.Y * c.Y;
Y = t.X * c.Y + t.Y * c.X;
return * this;
}

struct tagComplex & operator /= (double n)
{
X /= n;
Y /= n;
return * this;
}

void Mul(const tagComplex & a,const tagComplex & b)
{
* this = a;
* this *= b;
}

operator double()
{
return sqrt(X*X + Y*Y);
}

operator long()
{
return (long)(X + 0.4);
}

}COMPLEX, *LPCOMPLEX;

class CFFT
{
private:
CFFT(const CFFT &);
CFFT & operator = (const CFFT &);

private:
unsigned int BinaryRev(unsigned int ul,int len)
{
unsigned int nRet = 0;

for(int i = 0 ; i < len ; i ++)
{
nRet <<= 1;
nRet |= (ul & 1);
ul >>= 1;
}

return nRet;
}

public:
CFFT(){};
~CFFT(){};

void FFT(LPCOMPLEX fft,long n,bool flag = false)
{
long i,j;
long log2n = (long)(log(n)/log(2) + 0.4);
COMPLEX omegaTemp;

for(i = 0 ; i < n ; i ++)
{
j = BinaryRev(i,log2n);

if(i < j)
{
omegaTemp = fft;
fft = fft;
fft = omegaTemp;
}
}

for(i = 1 ; i <= log2n ; i++)
{
long m = (1 << i);
COMPLEX omega_m(cos(2*PI/m),sin(2*PI/m));

if(flag)
{
omega_m.Y = -omega_m.Y;
}

for(j = 0 ; j < n ; j += m)
{
COMPLEX omegaBase(1,0);

for(long k = 0 ; k < m / 2 ; k ++)
{
long loc = j + k + m / 2;

omegaTemp = omegaBase;
omegaTemp *= fft;

fft = fft;
fft += omegaTemp;
fft -= omegaTemp;

omegaBase *= omega_m;
}
}
}

if(flag)
{
for(i = 0 ; i < n ; i++)
{
fft /= n;
}
}
}

void Mul(std::string a,std::string b,std::string & out)
{
long len = 1;
long i = a.length() > b.length() ? a.length() : b.length();
long j = 0;

while(i > len)
{
len <<= 1;
}

len <<= 1;

char * buffer = new char[(len * sizeof(COMPLEX) * 3)];
memset(buffer,0,(len * sizeof(COMPLEX) * 3));
LPCOMPLEX f1 = (LPCOMPLEX)buffer;
LPCOMPLEX f2 = f1 + len;
LPCOMPLEX f3 = f2 + len;

for(i = a.length()-1; i >= 0 ; i--)
{
f1 = a - 0X30;
}

for(j = 0, i = b.length()-1 ; i >= 0 ; i--)
{
f2 = b - 0X30;
}

FFT(f1,len);
FFT(f2,len);

for(i = 0 ; i < len ; i++)
{
f3.Mul(f1,f2);
}

FFT(f3,len,true);

out = "";
typedef std::string::iterator SI;
SI si = out.begin();

long num = 0;

for(i = 0 ; i < len ; i ++)
{
long n = f3;
num += n;
out.insert(si,(num % 10 + 0X30));
num /= 10;
}

while(out == 0X30 && out.length() > 1)
{
out.erase(si);
}

delete [] buffer;
}
};

int main()
{
std::string a,b,c;
//输入两个大整数
std::cin >> a >> b;

CFFT fft;
fft.Mul(a,b,c);
std::cout << c;

return 0;
}

xieglt 发表于 2020-12-28 21:32:37

题目是求两数的积,不是和

#include <iostream>
#include <string.h>

#define _BASE_SIZE (1024)

class CBigInt
{
public:
CBigInt()
{
_num = new char;
memset(_num,0,_BASE_SIZE);
_size = _BASE_SIZE;
_len = 0;
}

CBigInt(const CBigInt & n)
{
_num = new char;
memset(_num,0,_BASE_SIZE);
_size = _BASE_SIZE;
*this = n;
}

~CBigInt()
{
if(_num != NULL)
{
delete [] _num;
}
}

CBigInt & operator = (const CBigInt & n)
{
memcpy(_num,n._num,_size);
_len = n._len;
return * this;
}

friend CBigInt operator + (const CBigInt & a,const CBigInt b)
{
CBigInt n = a;
n += b;
return n;
}

friend CBigInt operator * (const CBigInt & a,const CBigInt b)
{
CBigInt n = a;
n *= b;
return n;
}

friend std::istream & operator >> (std::istream & in, CBigInt & n)
{
char buffer = {0};

std::cin >> buffer;

int len = strlen(buffer);

for(int i=len-1,j=0 ; i>=0 ; i--)
{
n._num = buffer - '0';
}

n._len = len;

return in;
}

friend std::ostream & operator << (std::ostream & out,const CBigInt & n)
{
for(int i=n._len- 1 ; i>=0 ; i--)
{
char ch = (n._num + '0');
std::cout << ch;
}

return out;
}
private:

CBigInt & operator += (const CBigInt & n)
{
char value = 0;
char carry = 0;
int len = _len >= n._len ? _len : n._len;

for(int i=0 ; i<len ; i++)
{
value = carry;

if(i<_len)
{
value += _num;
}

if(i<n._len)
{
value += n._num;
}
carry = value / 10;
_num = value % 10;
}

if(carry > 0 && i+1 < n._size)
{
_num =carry;
}

_len = i;
return * this;
}

CBigInt & operator *= (char n)
{
char value = 0;
char carry = 0;

for(int i=0 ; i<_len ; i++)
{
value = carry;
value += n * _num;
carry = value / 10;
_num = value % 10;
}

if(carry > 0 && i+1 < _size)
{
_num = carry;
}

_len = i;

return * this;
}

CBigInt & operator *= (const CBigInt & n)
{
CBigInt tempnum;
CBigInt addnum;

for(int i=0; i<n._len; i++)
{
tempnum = *this;
tempnum *= n._num;
tempnum <<= i;
addnum += tempnum;
}
*this = addnum;

return * this;
}

CBigInt & operator <<= (int i)
{
if(i + _len + 1 < _size)
{
memcpy(_num+i,_num,_len);
memset(_num,0,i);
_len += i;
}

return * this;
}

private:
char * _num;
int _size;
int _len;
};

int main()
{
CBigInt a,b;

//输入两个大整数
std::cin >> a >> b;

//输出两数之和
std::cout << a + b;
//输出两数之积
std::cout << a * b;

return 0;
}

白砂糖 发表于 2020-12-29 08:45:43

请问，为什么提示i未定义呢？

xieglt 发表于 2020-12-29 08:49:13

白砂糖发表于 2020-12-29 08:45
请问，为什么提示i未定义呢？

c++支持变量即用即定义啊，你用的什么编译器？

xieglt 发表于 2020-12-29 08:59:44

白砂糖发表于 2020-12-29 08:45
请问，为什么提示i未定义呢？

实在不行，就把变量先定义吧
#include <iostream>
#include <string.h>

#define    _BASE_SIZE    (1024)

class CBigInt
{
public:
   CBigInt()
   {
            _num = new char;
            memset(_num,0,_BASE_SIZE);
            _size = _BASE_SIZE;
            _len = 0;
   }

   CBigInt(const CBigInt & n)
   {
            _num = new char;
            memset(_num,0,_BASE_SIZE);
            _size = _BASE_SIZE;
            *this = n;
   }

   ~CBigInt()
   {
            if(_num != NULL)
            {
                     delete [] _num;
            }
   }

   CBigInt & operator = (const CBigInt & n)
   {
            memcpy(_num,n._num,_size);
            _len = n._len;
            return * this;
   }

   friend CBigInt operator + (const CBigInt & a,const CBigInt b)
   {
            CBigInt n = a;
            n += b;
            return n;
   }

   friend CBigInt operator * (const CBigInt & a,const CBigInt b)
   {
            CBigInt n = a;
            n *= b;
            return n;
   }

   friend std::istream & operator >> (std::istream & in, CBigInt & n)
   {
            char buffer = {0};
int i,j;
int len;

            std::cin >> buffer;

            len = strlen(buffer);

            for(i=len-1,j=0 ; i>=0 ; i--)
            {
                     n._num = buffer - '0';
            }

            n._len = len;

            return in;
   }

   friend std::ostream & operator << (std::ostream & out,const CBigInt & n)
   {
int i;
char ch;

            for(i=n._len- 1 ; i>=0 ; i--)
            {
                     ch = (n._num + '0');
                     std::cout << ch;
            }

            return out;
   }
private:

   CBigInt & operator += (const CBigInt & n)
   {
int i;
            char value = 0;
            char carry = 0;
            int len = _len >= n._len ? _len : n._len;

            for(i=0 ; i<len ; i++)
            {
                     value = carry;

                     if(i<_len)
                     {
                           value += _num;
                     }

                     if(i<n._len)
                     {
                           value += n._num;
                     }
                     carry = value / 10;
                     _num = value % 10;
            }

            if(carry > 0 && i+1 < n._size)
            {
                     _num =carry;
            }

            _len = i;
            return * this;
   }

   CBigInt & operator *= (char n)
   {
int i;
            char value = 0;
            char carry = 0;

            for(i=0 ; i<_len ; i++)
            {
                     value = carry;
                     value += n * _num;
                     carry = value / 10;
                     _num = value % 10;
            }

            if(carry > 0 && i+1 < _size)
            {
                     _num = carry;
            }

            _len = i;

            return * this;
   }

   CBigInt & operator *= (const CBigInt & n)
   {
            CBigInt tempnum;
            CBigInt addnum;
int i;

            for(i=0; i<n._len; i++)
            {
                     tempnum = *this;
                     tempnum *= n._num;
                     tempnum <<= i;
                     addnum += tempnum;
            }
            *this = addnum;

            return * this;
   }

   CBigInt & operator <<= (int i)
   {
            if(i + _len + 1 < _size)
            {
                     memcpy(_num+i,_num,_len);
                     memset(_num,0,i);
                     _len += i;
            }

            return * this;
   }

private:
   char * _num;
   int _size;
   int _len;
};

int main()
{
   CBigInt a,b;

   //输入两个大整数
   std::cin >> a >> b;

   //输出两数之和
   std::cout << a + b;
   //输出两数之积
   std::cout << a * b;

   return 0;
}

白砂糖 发表于 2020-12-29 10:21:54

因为是在题库上提交，要求要在10000毫秒内完成，应该怎么办呢？

白砂糖 发表于 2020-12-29 11:13:03

谢谢你，

白砂糖 发表于 2020-12-29 11:13:41

我用的是vs2019，运行不出来

xieglt 发表于 2020-12-29 11:13:53

白砂糖发表于 2020-12-29 10:21
因为是在题库上提交，要求要在10000毫秒内完成，应该怎么办呢？

100位数的乘法，怎么也要不了10秒钟吧，你在什么平台上提交的？

qiaoqiaoqq 发表于 2020-12-29 14:12:20

感谢大佬

白砂糖 发表于 2020-12-30 17:13:04

数据结构课程设计在线平台

页: [1]

鱼C论坛's Archiver

数据结构 大整数加法有待改正，请大家能够帮帮忙。

数据结构大整数加法有待改正，请大家能够帮帮忙。