高精度 大数加法 乘法 除法 模板

转载请注明出处：http://blog.csdn.net/u012860063?viewmode=contents

一：加法

1、普通两个大数相加

代码如下：

#include <cstdio>
#include <cmath>
#include <cstring>
void fan(char s[])
{
    char t;
    int i,j;
    for(i = 0,j = strlen(s)-1; i <= j; i++,j--)
    {
        t=s[i];
        s[i]=s[j];
        s[j]=t;
    }
}
int main()
{
    int p = 0,g = 0,h = 1;
    int k,l;
    char x[100010],y[100010],z[100010];
    while(scanf("%s%s",x,y)!=EOF)
    {
        p = 0;
        fan(x);
        fan(y);
        k = strlen(x);
        l = strlen(y);
        int i;
        for(i = 0; i < k || i < l; i++)
        {
            if(i < k && i < l )
                z[i] = x[i]+y[i]+ p-'0';
            else if(i < k && i >= l)
                z[i] = x[i]+p;
            else if(i >= k && i < l)
                z[i] = y[i]+p;
            if(z[i] > '9')
            {
                z[i]-=10;
                p = 1;
            }
            else
                p = 0;
        }
        if(p)
            z[i++] = '1';
        z[i] = '';
        fan(x);
        fan(y);
        fan(z);
        printf("%s + %s = %sn",y,z);
    }
    return 0;
}

2、多个大数相加：//poj 1503?

#include <cstdio>
#include <cstring>
const int MAXN = 117;
int main()
{
    char s[MAXN];
    int sum[MAXN] = {0};
    int i,j;
    while(gets(s))
    {
        int len = strlen(s);
        if(s[0] == '0' && len == 1)
            break;
        for(i = 110,j = len-1; j >= 0; i--,j--)
        {
            sum[i] += s[j]-'0';
        }
    }
    for(i = 110; i > 0; i--)
    {
        sum[i-1] += sum[i] / 10;
        sum[i] %= 10;
    }
    for(i = 0; sum[i] == 0 && i < 111; i++)
    {
        if(i == 111)//意味着全为零
        {
            printf("0n");
        }
    }
    for( ; i < 111; i++)
    {
        printf("%d",sum[i]);
    }
    printf("n");
    return 0;
}

二：大数乘法

1、普通模拟乘法(char )

代码如下：//POJ 2389 ??ζёСяêτ - 小優YoU?小優YoU

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

const int size = 1000;  //大数位数

void mult(char* A,char* B,char* ans)
{
    int a[size+1]= {0};
    int b[size+1]= {0};
    int pa=0,pb=0;
    int c[2*size+1]= {0};

    int lena=strlen(A);
    int lenb=strlen(B);

    for(int i=lena-1; i>=0; i--)
        a[pa++]=A[i]-'0';
    for(int j=lenb-1; j>=0; j--)
        b[pb++]=B[j]-'0';

    for(pb=0; pb<lenb; pb++)
    {
        int w=0;  //低位到高位的进位
        for(pa=0; pa<=lena; pa++)
        {
            int temp=a[pa]*b[pb]+w;
            w=temp/10;
            temp=(c[pa+pb]+=temp%10);
            c[pa+pb]=temp%10;
            w+=temp/10;
        }
    }
    bool flag=false;
    bool sign=false;  //标记ans是否为全0
    for(pa=0,pb=lena+lenb-1; pb>=0; pb--)
    {
        if(!flag && c[pb]==0)  //删除ans开头的0
            continue;
        else
            flag=true;

        sign=true;
        ans[pa++]=c[pb]+'0';
    }
    if(sign)
        ans[pa]='';
    else
    {
        ans[0]='0';
        ans[1]='';
    }

    return;
}

int main()
{
    char a[size+1];
    char b[size+1];
    char ans[2*size+1];
    while(cin>>a>>b)
    {
        mult(a,b,ans);
        cout<<ans<<endl;
    }
    return 0;
}

2、(string)

代码如下：http://www.voidcn.com/article/p-mfokjjoi-gg.html

string sum(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]=char(s1[i]+(j>=0?s2[j]-'0':0));   //注意细节
		if(s1[i]-'0'>=10)
		{
			s1[i]=char((s1[i]-'0')%10+'0');
			if(i) s1[i-1]++;
			else s1='1'+s1;
		}
	}
	return s1;
}

string Mult(string s,int x)  //大数乘以整形数
{
    reverse(s.begin(),s.end());
    int cmp=0;
    for(int i=0;i<s.size();i++)
    {
        cmp=(s[i]-'0')*x+cmp;
        s[i]=(cmp%10+'0');
        cmp/=10;
    }
    while(cmp)
    {
        s+=(cmp%10+'0');
        cmp/=10;
    }
    reverse(s.begin(),s.end());
    return s;
}
string Multfa(string x,string y)  //大数乘法
{
    string ans;
    for(int i=y.size()-1,j=0;i>=0;i--,j++)
    {
        string tmp=Mult(x,y[i]-'0');
        for(int k=0;k<j;k++)
            tmp+='0';
        ans=sum(ans,tmp);
    }
    return ans;
}

3、(FFT 傅里叶高效算法)

代码如下：//HDU1402 ??kuangbin

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

const double PI = acos(-1.0);
//复数结构体
struct complex
{
    double r,i;
    complex(double _r = 0.0,double _i = 0.0)
    {
        r = _r;
        i = _i;
    }
    complex operator +(const complex &b)
    {
        return complex(r+b.r,i+b.i);
    }
    complex operator -(const complex &b)
    {
        return complex(r-b.r,i-b.i);
    }
    complex operator *(const complex &b)
    {
        return complex(r*b.r-i*b.i,r*b.i+i*b.r);
    }
};
/*
 * 进行FFT和IFFT前的反转变换。
 * 位置i和 （i二进制反转后位置）互换
 * len必须去2的幂
 */
void change(complex y[],int len)
{
    int i,j,k;
    for(i = 1,j = len/2; i < len-1; i++)
    {
        if(i < j)swap(y[i],y[j]);
        //交换互为小标反转的元素，i<j保证交换一次
        //i做正常的+1，j左反转类型的+1,始终保持i和j是反转的
        k = len/2;
        while( j >= k)
        {
            j -= k;
            k /= 2;
        }
        if(j < k) j += k;
    }
}
/*
 * 做FFT
 * len必须为2^k形式，
 * on==1时是DFT，on==-1时是IDFT
 */
void fft(complex y[],int len,int on)
{
    change(y,len);
    for(int h = 2; h <= len; h <<= 1)
    {
        complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
        for(int j = 0; j < len; j+=h)
        {
            complex w(1,0);
            for(int k = j; k < j+h/2; k++)
            {
                complex u = y[k];
                complex t = w*y[k+h/2];
                y[k] = u+t;
                y[k+h/2] = u-t;
                w = w*wn;
            }
        }
    }
    if(on == -1)
        for(int i = 0; i < len; i++)
            y[i].r /= len;
}
const int MAXN = 200010;
complex x1[MAXN],x2[MAXN];
char str1[MAXN/2],str2[MAXN/2];
int sum[MAXN];
int main()
{
    while(scanf("%s%s",str1,str2)==2)
    {
        int len1 = strlen(str1);
        int len2 = strlen(str2);
        int len = 1;
        while(len < len1*2 || len < len2*2)len<<=1;
        for(int i = 0; i < len1; i++)
            x1[i] = complex(str1[len1-1-i]-'0',0);
        for(int i = len1; i < len; i++)
            x1[i] = complex(0,0);
        for(int i = 0; i < len2; i++)
            x2[i] = complex(str2[len2-1-i]-'0',0);
        for(int i = len2; i < len; i++)
            x2[i] = complex(0,0);
        //求DFT
        fft(x1,len,1);
        fft(x2,1);
        for(int i = 0; i < len; i++)
            x1[i] = x1[i]*x2[i];
        fft(x1,-1);
        for(int i = 0; i < len; i++)
            sum[i] = (int)(x1[i].r+0.5);
        for(int i = 0; i < len; i++)
        {
            sum[i+1]+=sum[i]/10;
            sum[i]%=10;
        }
        len = len1+len2-1;
        while(sum[len] <= 0 && len > 0)len--;
        for(int i = len; i >= 0; i--)
            printf("%c",sum[i]+'0');
        printf("n");
    }
    return 0;
}

三：大数除法

1(string)大数除以整形数

代码如下：

string Except(string s,int x)  //大数除以整形数
{
    int cmp=0,ok=0;
    string ans="";
    for(int i=0;i<s.size();i++)
    {
        cmp=(cmp*10+s[i]-'0');
        if(cmp>=x)
        {
            ok=1;
            ans+=(cmp/x+'0');
            cmp%=x;
        }
        else{
            if(ok==1)
                ans+='0';  //注意这里
        }
    }
    return ans;
}

四、浮点大数求幂

代码如下：ζёСяêτ - 小優YoU?

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;

const int size=1000;  //大数位数

void mult(char* A,char* ans)
{
    int i,k;

    int fract;   //总小数个数
    int dot=-1;  //小数点位置
    for(k=0; A[k]!=''; k++)
        if(A[k]=='.')
            dot=k;
    int lena=k;
    if(dot==-1)
        fract=0;
    else
        fract=lena-dot-1;

    dot=-1;
    for(k=0; B[k]!=''; k++)
        if(B[k]=='.')
            dot=k;
    int lenb=k;
    if(dot==-1)
        fract+=0;
    else
        fract+=(lenb-dot-1);  //总小数个数

    int a[size+1]= {0};
    int b[size+1]= {0};
    int pa=0,pb=0;

    /*倒序*/

    for(i=lena-1; i>=0; i--)
    {
        if(A[i]=='.')
            continue;
        a[pa++]=A[i]-'0';
    }
    for(j=lenb-1; j>=0; j--)
    {
        if(B[j]=='.')     //暂时删除小数点
            continue;
        b[pb++]=B[j]-'0';
    }

    int c[2*size+1]= {0};
    int lenc;
    for(pb=0; pb<lenb; pb++)
    {
        int w=0;  //低位到高位的进位
        for(pa=0; pa<=lena; pa++) // = 为了处理最后的进位
        {
            int temp=a[pa]*b[pb]+w;
            w=temp/10;
            temp=(c[pa+pb]+=temp%10);
            c[lenc=pa+pb]=temp%10;
            w+=temp/10;
        }
    }

    /*倒序，得到没有小数点的ans*/

    for(pa=0,pb=lenc; pb>=0; pb--)
        ans[pa++]=c[pb]+'0';
    ans[pa]='';
    lena=pa;

    /*插入小数点*/

    bool flag=true; //标记是否需要删除小数末尾的0
    if(fract==0)   //小数位数为0，无需插入小数点
        flag=false;
    else if(fract<lena) //小数位数小于ans长度，在ans内部插入小数点
    {
        ans[lena+1]='';
        for(i=0,pa=lena; pa>0; pa--,i++)
        {
            if(i==fract)
            {
                ans[pa]='.';
                break;
            }
            else
                ans[pa]=ans[pa-1];
        }

    }
    else //小数位数大于等于ans长度，在ans前面恰当位置插入小数点
    {
        char temp[size+1];
        strcpy(temp,ans);
        ans[0]='0';
        ans[1]='.';
        for(int i=0; i<fract-lena; i++) //补充0
            ans[i+2]='0';
        for(j=i,pa=0; pa<lena; pa++)
            ans[j++]=temp[pa];
        ans[j]='';
    }

    /*删除ans小数末尾的0*/

    if(flag)
    {
        lena=strlen(ans);
        pa=lena-1;
        while(ans[pa]=='0')
            ans[pa--]='';
        if(ans[pa]=='.')   //小数全为0
            ans[pa--]='';
    }

    /*删除ans整数开头的0，但至少保留1个0*/

    pa=0;
    while(ans[pa]=='0')  //寻找ans开头第一个不为0的位置
        pa++;

    if(ans[pa]=='')  //没有小数
    {
        ans[0]='0';
        ans[1]='';
    }
    else  //有小数
    {
        for(i=0; ans[pa]!=''; i++,pa++)
            ans[i]=ans[pa];
        ans[i]='';
    }
    return;
}

char a[size+1];
char ans[size*size+1];

int main(void)
{
    int b;
    while(cin>>a>>b)
    {
        memset(ans,'',sizeof(ans));
        ans[0]='1';
        ans[3]='';

        for(int i=1; i<=b; i++)
            mult(a,ans,ans);

        cout<<ans<<endl;
    }
    return 0;
}