高精度算法

高精度

1.高精度加法
  问题描述
　　输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。
算法描述
　　由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。
　　定义一个数组A，A[0]用于存储a的个位，A[1]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。
　　计算c = a + b的时候，首先将A[0]与B[0]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C[0]，即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加，这时还应将低位进上来的值r也加起来，即C[1]应该是A[1]、B[1]和r三个数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C[1]中。依此类推，即可求出C的所有位。
　　最后将C输出即可。
输入格式
　　输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。
输出格式
　　输出一行，表示a + b的值。
样例输入
20100122201001221234567890
2010012220100122
样例输出
20100122203011233454668012

/*
分析：

1.可能两个数的长度不同，那么就需要在一个数加完之后把另一个数的剩下的数全加上。

2.判断最高位，如果最高位有进位，那么还需要把进位位加上。
*/
#include<stdio.h>
#include<string.h>
int main()
{
    char a[200],b[200];//定义字符串数组
    int c[500]; 
    scanf("%s%s",a,b);//输入字符串数组
    int i,j,k=0,r=0;
    int lena,lenb;
    lena = strlen(a);
    lenb = strlen(b);
    for(i=lena-1,j=lenb-1;i>=0&&j>=0;i--,j--){  
        int p=(a[i]-'0')+(b[j]-'0')+r;    
        r=p/10;//进位  
        c[k++]=p%10;//余数加到数组中  
    }
    while(i>=0){   //如果b中的数加完了  
        int p=(a[i]-'0')+r;  
        r=p/10;  
        c[k++]=p%10;  
        i--;  
    }  
    while(j>=0){    //如果a中的数加完了  
        int p=(b[j]-'0')+r;  
        r=p/10;  
        c[k++]=p%10;  
        j--;  
    }  
    if(r){//判断最高位有没有进位
        c[k++]=r;  
    }  
    for(int i=k-1;i>=0;i--){//输出结果 
        printf("%d",c[i]);
    }
    return 0;
}

2.高精度减法
输入被减数和减数,两个数为不超过200位的整数.,每行1个,输出差.
输入:
5324345634734328432
632345667456834
输出:
5323713289066871598

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 1001
using namespace std ;
int main ( )
{
    int a [ N ] , b [ N ] , c [ N ] , i ;
    char n [ N ] , n1 [ N ] , n2 [ N ] ;
    memset ( a , 0 , sizeof ( a ) ) ;
    memset ( b , 0 , sizeof ( b ) ) ;
    memset ( c , 0 , sizeof ( c ) ) ;
    gets ( n1 ) ;
    gets ( n2 ) ;
    int lena = strlen ( n1 ) , lenb = strlen ( n2 ) ;
    if ( lena < lenb || ( lena == lenb && strcmp ( n1 , n2 ) < 0 ) ) 
    //strcmp()为字符串比较函数，当n1=n2时，返回0，
    //n1>n2时，返回正整数；n1<n2时返回负整数
    //比完大小后，发现被减数小于减数，就交换。
    {
        strcpy ( n , n1 ) ;  //将n1数组的值完全赋值给n数组
        strcpy ( n1 , n2 ) ;
        strcpy ( n2 , n ) ;
        swap ( lena , lenb ) ;  //这步不能忘
        printf ( "-" ) ;  //别忘了输出负号
    }
    for ( i = 0 ; i < lena ; i ++ ) a [ lena - i ] = int ( n1 [ i ] - '0' ) ;
    for ( i = 0 ; i < lenb ; i ++ ) b [ lenb - i ] = int ( n2 [ i ] - '0' ) ;
    i = 1 ;
    while ( i <= lena || i<= lenb ) 
    {
        if ( a [ i ] < b [ i ] )   //借位
        {
            a [ i ] += 10 ;
            a [ i + 1 ] -- ;
        }
        c [ i ] = a [ i ] - b [ i ] ;
        i ++ ;
    }       
    int lenc = i ;
    while ( c [ lenc ] == 0 && lenc > 1 ) lenc -- ;    //最高位为0，则不输出
    for ( i = lenc ; i >= 1 ; i -- ) printf ( "%d" , c [ i ] ) ;     
    return 0 ;
}
3.高精度乘法
输入被乘数和乘数,两个数为不超过100位的整数.,每行1个,输出它们的乘积.
输入:
54656546574864562
9525485585514
输出: 
520630146552846973597819154868

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

#define Length 202

int *Multi(int *a, int *b ,int la, int lb)
{
	int i, j,*c;
	int len;
	len = la + lb;
	c = (int *)malloc((len) * sizeof(int));
	memset(c, 0, sizeof(int)*len);
	/*高精度乘法的重点，按照人手工进行乘法运算的方式，通过进位的方法计算结果的每一位的值*/
	for (i = 0; i<la; i++)//整数a的每一位与b的所有位分别相乘
		for (j = 0; j < lb; j++)
		{
			c[i + j] += a[i] * b[j];//在c[i+j]的位置加上a的第i位与b的第j位的积
			c[i + j + 1] += c[i + j] / 10;//在下一位的位置进位
			c[i + j] = c[i + j] % 10;//在当前位置保留除以10后余数
		}
	return c;
}
int *Str2int(char *str)
{
	int len,i;
	int *num;
	len = strlen(str);
	num = (int *)malloc(len * sizeof(int));
	memset(num, 0, len * sizeof(int));
	for (i = 0; i < len; i++)//对每一位字符进行倒序存放
		num[i] = str[len - i - 1] - '0';//以ASCII码值进行相减，再转换成整型
	return num;
}
char *Int2str(int *num,int len)
{
	int i, j;
	char *res;
	res = (char *)malloc(len * sizeof(char));
	memset(res, 0, len * sizeof(char));
	while (num[len-1] == 0 && len>1)//2个数想乘，结果位数必定小于等于2者位数之和
	{                               //大于等于2者位数之和-1
		len--;
	}
	for (i = 0; i < len; i++)//以ASCII码值进行相加，再转换乘字符串形式
	{
		res[i] = num[len - 1 - i] + '0';
	}
	res[len] = '\0';//添加结束符
	return res;
}
int main()
{
	char *s1, *s2,*s;
	int *a, *b, *c;
	int i,la, lb,len;
	s1 = (char *)malloc(Length * sizeof(char));//使用指针进行操作时，需要先分配内存
	s2 = (char *)malloc(Length * sizeof(char));
	memset(s1, 0, sizeof(char)*(Length));//初始化分配的内存，置0
	memset(s2, 0, sizeof(char)*(Length));
	cin >> s1 >> s2;
	la = strlen(s1);//统计字符串长度，不包括结束符'\0'
	lb = strlen(s2);
	len = la + lb;
	a = Str2int(s1);//字符转整型
	b = Str2int(s2);
	c=Multi(a, b, la, lb);//重点：高精度乘法
	s = Int2str(c,len);//整型转字符
	cout << s << endl;
	return 0;
}