c++大数运算考虑正负
2016-07-18 07:49:10 Martind 阅读数 249

大数加法

string add(string s1,string s2)
{
    if(s1.length()<s2.length()){
        string temp=s1;
        s1=s2;
        s2=temp;
    }
    int i,j;
    for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--){
        s1[i]=s1[i]+(j>=0?s2[j]-'0':0);
        if(s1[i]-'0'>=10){
            s1[i]=(s1[i]-'0')%10+'0';
            if(i) s1[i-1]++;
            else s1='1'+s1;
        }
    }
    return s1;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100000000;
char a[maxn],b[maxn];
string add(string s1,string s2)
{
    if(s1.length()<s2.length()){
        string temp=s1;
        s1=s2;
        s2=temp;
    }
    int i,j;
    for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--){
        s1[i]=s1[i]+(j>=0?s2[j]-'0':0);
        if(s1[i]-'0'>=10){
            s1[i]=(s1[i]-'0')%10+'0';
            if(i) s1[i-1]++;
            else s1='1'+s1;
        }
    }
    return s1;
}
int main()
{
    while(scanf("%s%s",&a,&b)){
        cout<<add(a,b)<<endl;
    }
}


2016-08-03 22:55:01 qq_16398189 阅读数 241

大数就是指十几位,几十位或者几百位的数字,反正对于这样的数,任何计算机本身的变量类型(int,double,甚至long long)都表示不了。怎么存?最常用的就是用字符串string或者向量vector,然后的问题自然是要实现大数的四则运算。

大数加法

加法的实现很简单,就是从低位开始,模拟加法的计算过程,需要注意的就是计算过程中产生的进位。
string实现大数加法:

string BigIntPlus(string s1, string s2)
{
    //把较长的数给s1,方便写程序
    if (s1.size() < s2.size())
    {
        string tmp = s2;
        s2 = s1;
        s1 = tmp;
    }
    //从低位开始,模拟加法的过程,注意每次加法的进位即可
    for (int i = s1.size()-1, j = s2.size()-1; i >= 0; i--, j--)
    {
        s1[i] = s1[i] + (j >= 0 ? s2[j] - '0' : 0);
        if (s1[i] > '9')//表示有进位
        {
            s1[i] -= 10;
            if (i) s1[i - 1]++;
            else s1 = '1' + s1;//i=-1,表示超过了原来的长度,利用字符串加法
        }
    }
    return s1;
}

大数减法

大数减法虽然看起来也就是模拟做减法的过程,但实际上比加法复杂的多。网上很多所谓的大数减法的程序,要么只能计算结果为正数的情况,要么2225-2227算下来结果显示-0002,什么鬼嘛,等于-2呀。
1.string实现大数减法:

//用来清除数字字符串前多余的0
string eraseZero(string s)
{
    if (s.size() <= 1) return s;
    if (*s.begin() != '0') return s;
    s.erase(s.begin());
    return eraseZero(s);
}
//返回s1-s2的值
//为了方便写程序,我们先保证计算的结果是正数,最后看情况是否需要转负数
string BigIntMinus(string s1, string s2)
{
    bool tag = false;//用来标记s1 s2是否发生了交换
    if (s1.size() < s2.size() || (s1.size()==s2.size() && s1 < s2))
    {
        tag = true;
        string tmp = s2;
        s2 = s1;
        s1 = tmp;
    }
    for (int i = s1.size()-1, j = s2.size()-1; i >= 0; i--, j--)
    {
        if (j>=0){
            if (s1[i] < '0' || s1[i] < s2[j])//需要借位
            {
                s1[i] = s1[i] + 10 - ((j < 0) ? 0 : s2[j] - '0');
                s1[i - 1]--;
                continue;
            }
        }
        s1[i] = s1[i] - ((j<0) ? 0 : s2[j] - '0');
    }
    //处理计算结果字符串前面多余的0,比如0005应该显示5
    string result = eraseZero(s1);
    if (tag) result = '-' + result;
    return result;
}

虽然我们用string可以实现大数减法,但写程序的过程总是很不舒服的。因为我们从头到尾都要记得我们处理的是字符’0’…..’9’,而不是真正的数字0,1……9。

大数乘法

大数的乘法就有多种算法思想。主要有分治法、快速傅里叶变换FFT法、中国剩余定理、简单方法(模拟乘法的过程)。前面几种看起来就NB,被吓住的赶紧去百度一下,我这里还是简单研究下简单方法……

这里我们从LeetCode的一道题目说起:Multiply Strings
这里写图片描述
这里我直接贴高票答案的代码,因为实在写的太好了,我自己写的不堪入目。

string multiply(string num1, string num2) {
    string sum(num1.size() + num2.size(), '0');

    for (int i = num1.size() - 1; 0 <= i; --i) {
        int carry = 0;
        for (int j = num2.size() - 1; 0 <= j; --j) {
            int tmp = (sum[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
            sum[i + j + 1] = tmp % 10 + '0';
            carry = tmp / 10;
        }
        sum[i] += carry;
    }

    size_t startpos = sum.find_first_not_of("0");
    if (string::npos != startpos) {
        return sum.substr(startpos);
    }
    return "0";
}

GMP

其实关于大数运算,早就有高精度计算库GUN的GMP(Arithmetic without limitations)
GMP,我们只需要调用就行了。

2016-06-18 23:07:24 github_33736971 阅读数 263
    #include<cstdio>  
    #include<iostream>  
    using namespace std;  

    const int maxn = 200;  
    struct bign{  
      int len, s[maxn];  

      bign() {  
        memset(s, 0, sizeof(s));  
        len = 1;  
      }  

      bign(int num) {  
        *this = num;  
      }  

      bign(const char* num) {  
        *this = num;  
      }  

      bign operator = (int num) {  
        char s[maxn];  
        sprintf(s, "%d", num);  
        *this = s;  
        return *this;  
      }  

      bign operator = (const char* num) {  
        len = strlen(num);  
        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';  
        return *this;  
      }  

      string str() const {  
        string res = "";  
        for(int i = 0; i < len; i++) res = (char)(s[i] + '0') + res;  
        if(res == "") res = "0";  
        return res;  
      }  

      bign operator + (const bign& b) const{  
        bign c;  
        c.len = 0;  
        for(int i = 0, g = 0; g || i < max(len, b.len); i++) {  
          int x = g;  
          if(i < len) x += s[i];  
          if(i < b.len) x += b.s[i];  
          c.s[c.len++] = x % 10;  
          g = x / 10;  
        }  
        return c;  
      }  

      void clean() {  
        while(len > 1 && !s[len-1]) len--;  
      }  

      bign operator * (const bign& b) {  
        bign c; c.len = len + b.len;  
        for(int i = 0; i < len; i++)  
          for(int j = 0; j < b.len; j++)  
            c.s[i+j] += s[i] * b.s[j];  
        for(int i = 0; i < c.len-1; i++){  
          c.s[i+1] += c.s[i] / 10;  
          c.s[i] %= 10;  
        }  
        c.clean();  
        return c;  
      }  

      bign operator - (const bign& b) {  
        bign c; c.len = 0;  
        for(int i = 0, g = 0; i < len; i++) {  
          int x = s[i] - g;  
          if(i < b.len) x -= b.s[i];  
          if(x >= 0) g = 0;  
          else {  
            g = 1;  
            x += 10;  
          }  
          c.s[c.len++] = x;  
        }  
        c.clean();  
        return c;  
      }  

      bool operator < (const bign& b) const{  
        if(len != b.len) return len < b.len;  
        for(int i = len-1; i >= 0; i--)  
          if(s[i] != b.s[i]) return s[i] < b.s[i];  
        return false;  
      }  

      bool operator > (const bign& b) const{  
        return b < *this;  
      }  

      bool operator <= (const bign& b) {  
        return !(b > *this);  
      }  

      bool operator == (const bign& b) {  
        return !(b < *this) && !(*this < b);  
      }  

      bign operator += (const bign& b) {  
        *this = *this + b;  
        return *this;  
      }  
    };  

    istream& operator >> (istream &in, bign& x) {  
      string s;  
      in >> s;  
      x = s.c_str();  
      return in;  
    }  

    ostream& operator << (ostream &out, const bign& x) {  
      out << x.str();  
      return out;  
    }  

    int main() {  
      bign a, b;  
      cin >> a >> b;  
      a += b;  
      cout << a << endl;  
      return 0;  
    }  
2013-03-17 16:19:03 lizhi389 阅读数 512
#include <string>  
#include <iostream> 
using namespace std; 
char num[4][100];
char s[100];
int main() 
{ 
	void swi();
	void clear(char *s);
	void add(char *s1, char *s2, char *s);
	while(cin>>num[0]>>num[1]>>num[2]){
		for(int i = 0; i < 97; i++){
			add(num[0], num[1], s);
			add(num[2], s, num[3]);
			strcpy(num[0], num[1]);
			strcpy(num[1], num[2]);
			strcpy(num[2], num[3]); 
		}
			cout << num[3] << endl;
			clear(s);
			clear(num[3]);
	}
	return 0; 
} 
void clear(char *s)
{
	while(*s)
		*s++ = '\0';
}
void add(char *s1, char *s2, char *s)
{
	void swi(char *s);
	int flag = 0;
	int i = 0;
	char *p1 = s1;
	char *p2 = s2;
	while(*p1 != '\0')
		p1++;
	while(*p2 != '\0')
		p2++;
	--p1,--p2;
	while(p1 != s1-1 && p2 != s2-1){
		s[i] = (flag + *p1-'0'+ *p2-'0')%10 +'0';
		i++;
		if(*p1-'0' + *p2-'0' +flag > 9)
			flag = 1;
		else
			flag = 0;
		p1--,p2--;
	}
	if(p1 == s1-1){
		while(p2 != s2-1){
		s[i] = (flag + *p2 -'0')%10 + '0';
		i++;
		if(*p2-- -'0' + flag > 9)
			flag = 1;
		else 
			flag = 0;
		}
	}
	else 
		while(p1 != s1-1){
		s[i] = (flag + *p1 -'0')%10 + '0';
		i++;
		if(flag + *p1-- -'0' > 9)
			flag = 1;
		else
			flag = 0;
		}
	if(flag) 
		s[i] = '1';
	s[++i] = '\0';
	swi(s);
}
void swi(char *s)
{
	int i ;
	int j = strlen(s)-1;
	char c;
	for(i=0; i < strlen(s)/2; i++,j--){
		c    = s[i];
		s[i] = s[j];
		s[j] = c;
	}
}


2013-03-22 12:36:32 xiaofei2010 阅读数 709

1.大数相加

思路:

建立两个长度为N的整型数组分别存放两个大数,和一个长度为N+1的数组存放它们得和。

建立一个字符数组存放每次输入的大数(此时数组中存放的实际为字符,要将它们转化为int型后再传递给整型数组)

//实现两个大数相加
#include <iostream>
using namespace std;

#define N 1000

//将c[n]中字符串转化成数字存入arr[n]
void InitArray(int arr[],char c[],int n)//初始化数组
{
	int k = strlen(c);
	for (int i = 0;i < k;i++)//strlen(c)等于c中字符个数,不包括‘\0’
	{
		arr[n - k + i] = c[i] - '0';
	}
}
void PrintArray(int arr[],int n)//打印数组中的元素
{
	int k = 0;
	for (int i = 0;i < n;i++)
		if(arr[i] != 0)
		{
			k = i;
			break;
		}
	for (int i = k;i < n;i++)
		cout << arr[i];
}
void CulateSum(int arr1[],int arr2[],int sum[],int n)//由低位到高位计算两个大数的和,并把结果存入数组sum
{
	for (int i = n;i >= 1;i--)
	{
		//注意:数组sum比数组arr1和arr2多一位元素,用来存放进位
		sum[i] += arr1[i - 1] + arr2[i - 1];
		if(sum[i] >= 10)
		{
			sum[i] -= 10;//取个位
			sum[i-1] += 1;//进位
		}
	}
}

//在函数体外定义的数组,元素均初始化为零
int a[N];
int b[N];
int sum[N+1];
//字符数组初始化为空,下面strlen(c)的值为0
char c[N];

int main()
{
	cout << "input first number:" << endl;
	cin >> c;
	//对数组a进行初始化
	InitArray(a,c,N);
	//打印数组a中元素
	//PrintArray(a,sizeof(a)/sizeof(int));
	cout << "input second number:" << endl;
	cin.clear();
	cin >> c;
	//对数组b进行初始化
	InitArray(b,c,N);
	//打印数组b中元素
	//PrintArray(b,sizeof(b)/sizeof(int));

	//求sum
	CulateSum(a,b,sum,N);
	cout << "\nthe result is: " << endl;
	PrintArray(sum,sizeof(sum)/sizeof(int));
	cout << endl;

	return 0;
}


运行结果如下:


2.大数相乘

思路:

建立两个字符数组分别存放两个大数,并将字符数组中的char元素转换为int型;

根据等式mResult[i+j] =mResult[i+j] + mult1[i]*mult2[j];求解;

代码如下:

#include <iostream>
using namespace std;

#define M 100

//将c[n]中字符串转化成数字存入arr[n]  
void InitArray(int arr[],char c[],int n)//初始化数组  
{  
	int k = strlen(c);  
	for (int i = 0;i < k;i++)//strlen(c)等于c中字符个数,不包括‘\0’  
	{  
		arr[n - k + i] = c[i] - '0';
	}  
}

void bigDataMultiply(char m1[],char m2[],int mResult[],int m1Length,int m2Length)
{
	int mult1[M];
	int mult2[M];
	//数组初始化
	InitArray(mult1,m1,m1Length);
	InitArray(mult2,m2,m2Length);
	memset(mResult,0,sizeof(int)*2*M);//注意:将指针mResult指向位置开始的前sizeof(int)*2*M个字节值为0
	//carry表示进位
	int carry = 0;
	//remainder表示余数
	int remainder = 0;

	for (int i = 0;i < m1Length;++i)
		for(int j = 0;j < m2Length;++j)
			mResult[i+j] =mResult[i+j] + mult1[i]*mult2[j];
	//处理进位
	for (int i = 0;i < m1Length + m2Length;++i)
	{
		mResult[i] += carry;
		carry = mResult[i]/10;
		//若存在进位,则对mResult[i]求余
		int k = carry;
		while (k)
		{
			mResult[i] = mResult[i]%10;
			k /= 10;
		}
	}
}

//打印数组中的元素
template<class T>
void printArray(T arr[],int n)  
{
	int k = 0;
	for (int i = 0;i < n;i++)
	{
		if(arr[i] != 0)
		{
			k = i;
			break;
		}
	}
	for (int i = k;i < n;i++)
		cout << arr[i];
	cout << endl;
}

int main()
{
	char bigData1[M],bigData2[M];
	int resultData[2*M] = {0};

	cout << "输入两个大数:\n";
	while(cin >> bigData1 >> bigData2)
	{
		
		reverse(bigData1,bigData1+strlen(bigData1));
		reverse(bigData2,bigData2+strlen(bigData2));
		//printArray(bigData1,strlen(bigData1));
		//printArray(bigData2,strlen(bigData2));
		bigDataMultiply(bigData1,bigData2,resultData,strlen(bigData1),strlen(bigData2));
		reverse(resultData,resultData+sizeof(resultData)/sizeof(int));
		cout << "乘积为:\n";
		printArray(resultData,2*M);
		cout << "\n输入两个大数:\n";
	}

	return 0;
}

运行结果如下:


待续。。。

C++实现大数运算

阅读数 3

项目背景:大数运算,顾名思义,就是很大的数值的数进行一系列的运算。我们知道,在数学中,数值的大小是没有上限的,但是在计算机中,由于字长的限制,计算机所能表示的范围是有限的,当我们对比较小的数进行运算时,如:1234+5678,这样的数值并没有超出计算机的表示范围,所以可以运算。但是当我们在实际的应用中进行大量的数据处理时,会发现参与运算的数往往超过计算机的基本...

博文 来自: weixin_34178244

C++大数运算类

阅读数 398

#include#include#include#includeusingnamespacestd;#defineMAXN9999//每一位的数#defineMAXSIZE10//10*9999四位,共40位#defineDLEN4classBigNum{private:inta[500];//可以控制大数的位数

博文 来自: atlasscarlet

大数运算实现(C++)

阅读数 1545

实现带符号的大数运算的+,-,*,/,mod以及最大公约数和模数的乘法逆元,参考了以前(不知道哪搜集到的)大数运算的代码实现并进行封装。本人对C++理解不深,如有错误,欢迎指正!ClassBigInteger.h/**************************************************************************Copyrig

博文 来自: u011216699

c++实现大数运算

阅读数 982

刷上交大的题遇到大数运算的问题(权当记录)题目描述如下:Today,facingtherapiddevelopmentofbusiness,SJTUrecognizesthatmorepowerfulcalculatorshouldbestudied,developedandappearedinfuturemarketshortly.SJTU...

博文 来自: zhaokx3

C++大数运算与运算符重载

阅读数 141

应博问里面一个童鞋的要求,写了下面一个程序,主要是大数运算和运算符的重载,时间限制,只做了加法。大神你可以直接略过,见笑见笑,呵呵(PS:写博客的时候怎么插入表情?)。废话不多说,程序如下。#include&lt;iostream&gt;#include&lt;cstring&gt;usingnamespacestd;classBigNum{...

博文 来自: yanyojun
没有更多推荐了,返回首页