高精度相关运算

た入场券 2021-06-24 15:56 411阅读 0赞

部分内容参考自：[http://blueve.me/archives/category/lrn/cpts][http_blueve.me_archives_category_lrn_cpts]

//高精度模板，注意本模板并没有考虑中间会出现负数的情况  
    #include "stdafx.h" 
    #include <cstdio>  
    #include <cstdlib>   
    #include <cctype>  
    #include <string>   
    using  namespace  std;   
    const  int MAXL = 500;   
    struct  BigNum   
    {   
    	int  num[MAXL];   
    	int  len;   
    };   
    //高精度比较 a > b return 1, a == b return 0; a < b return -1;   
    int  Comp(BigNum &a, BigNum &b)   
    {   
    	int  i;   
    	if(a.len != b.len) return (a.len > b.len) ? 1 : -1;   
    	for(i = a.len-1; i >= 0; i--)   
    		if(a.num[i] != b.num[i]) return  (a.num[i] > b.num[i]) ? 1 : -1;   
    	return  0;   
    }   
    //高精度加法   
    BigNum  Add(BigNum &a, BigNum &b)   
    {   
    	BigNum c;   
    	int  i, len;   
    	len = (a.len > b.len) ? a.len : b.len;   
    	memset(c.num, 0, sizeof(c.num));   
    	for(i = 0; i < len; i++)   
    	{   
    		c.num[i] += (a.num[i]+b.num[i]);   
    		if(c.num[i] >= 10)   
    		{   
    			c.num[i+1]++;   
    			c.num[i] -= 10;   
    		}   
    	}   
    	if(c.num[len]) len++;   
    	c.len = len;   
    	return  c;   
    }   
    //高精度减法,保证a >= b   
    BigNum Sub(BigNum &a, BigNum &b)   
    {   
    	BigNum  c;   
    	int  i, len;   
    	len = (a.len > b.len) ? a.len : b.len;   
    	memset(c.num, 0, sizeof(c.num));   
    	for(i = 0; i < len; i++)   
    	{   
    		c.num[i] += (a.num[i]-b.num[i]);   
    		if(c.num[i] < 0)   
    		{   
    			c.num[i] += 10;   
    			c.num[i+1]--;   
    		}   
    	}   
    	while(c.num[len] == 0 && len > 1) len--;   
    	c.len = len;   
    	return  c;   
    }   
    //高精度乘以低精度，当b很大时可能会发生溢出int范围,具体情况具体分析   
    //如果b很大可以考虑把b看成高精度   
    BigNum Mul1(BigNum &a, int  &b)   
    {   
    	BigNum c;   
    	int  i, len;   
    	len = a.len;   
    	memset(c.num, 0, sizeof(c.num));   
    	//乘以0，直接返回0   
    	if(b == 0)    
    	{   
    		c.len = 1;   
    		return  c;   
    	}   
    	for(i = 0; i < len; i++)   
    	{   
    		c.num[i] += (a.num[i]*b);   
    		if(c.num[i] >= 10)   
    		{   
    			c.num[i+1] = c.num[i]/10;   
    			c.num[i] %= 10;   
    		}   
    	}   
    	if(c.num[len] > 0)   
    	{   
    		c.num[len+1] = c.num[len]/10;   
    		c.num[len++] %= 10;   
    	}   
    	c.len = len;    
    	return  c;   
    }   
    
    //高精度乘以高精度,注意要及时进位，否则肯能会引起溢出,但这样会增加算法的复杂度，   
    //如果确定不会发生溢出, 可以将里面的while改成if   
    BigNum  Mul2(BigNum &a, BigNum &b)   
    {   
    	int     i, j, len = 0;   
    	BigNum  c;   
    	memset(c.num, 0, sizeof(c.num));   
    	for(i = 0; i < a.len; i++)   
    		for(j = 0; j < b.len; j++)   
    		{   
    			c.num[i+j] += (a.num[i]*b.num[j]);   
    			if(c.num[i+j] >= 10)   
    			{   
    				c.num[i+j+1] += c.num[i+j]/10;   
    				c.num[i+j] %= 10;   
    			}   
    		}   
    		len = a.len+b.len-1;   
    		while(c.num[len-1] == 0 && len > 1) len--;   
    		if(c.num[len]) len++;   
    		c.len = len;   
    		return  c;   
    }   
    
    //高精度除以低精度,除的结果为c, 余数为f   
    void Div1(BigNum &a, int &b, BigNum &c, int &f)   
    {   
    	int  i, len = a.len;   
    	memset(c.num, 0, sizeof(c.num));   
    	f = 0;   
    	for(i = a.len-1; i >= 0; i--)   
    	{   
    		f = f*10+a.num[i];   
    		c.num[i] = f/b;   
    		f %= b;   
    	}   
    	while(len > 1 && c.num[len-1] == 0) len--;   
    	c.len = len;   
    }   
    //高精度*10   
    void  Mul10(BigNum &a)   
    {   
    	int  i, len = a.len;   
    	for(i = len; i >= 1; i--)   
    		a.num[i] = a.num[i-1];   
    	a.num[i] = 0;   
    	len++;   
    	//if a == 0   
    	while(len > 1 && a.num[len-1] == 0)  len--;   
    }   
    
    //高精度除以高精度，除的结果为c，余数为f   
    void Div2(BigNum &a, BigNum &b, BigNum &c, BigNum &f)   
    {   
    	int  i, len = a.len;   
    	memset(c.num, 0, sizeof(c.num));   
    	memset(f.num, 0, sizeof(f.num));   
    	f.len = 1;   
    	for(i = len-1;i >= 0;i--)   
    	{   
    		Mul10(f);   
    		//余数每次乘10   
    		f.num[0] += a.num[i];   
    		//然后余数加上下一位   
    		//利用减法替换除法, 减的次数就是商，剩下的就是余数   
    		while(Comp(f, b) >= 0)   
    		{   
    			f = Sub(f, b);   
    			c.num[i]++;   
    		}   
    	}   
    	while(len > 1 && c.num[len-1] == 0)len--;   
    	c.len = len;   
    }
    void  print(BigNum &a)   
    {   
    	int  i;   
    	for(i = a.len-1; i >= 0; i--)   
    		printf("%d", a.num[i]);   
    	puts("");   
    }   
    //将字符串转为大数存在BigNum结构体里面   
    BigNum ToNum(char *s)   
    {   
    	int i, j;   
    	BigNum  a;   
    	a.len = strlen(s);   
    	for(i = 0, j = a.len-1; s[i] != '\0'; i++, j--)   
    		a.num[i] = s[j]-'0';   
    	return  a;   
    }   
    
    void  Init(BigNum &a, char *s, int &tag)
    {
    	int  i = 0, j = strlen(s);
    	if(s[0] == '-') {j--; i++; tag *= -1;}
    	a.len = j;
    	for(; s[i] != '\0'; i++, j--)
    		a.num[j-1] = s[i]-'0';
    	//print(a);
    }
    
    int  main()   
    {   
    	int ival=5;
    	BigNum a, b;
    	BigNum c,f;
    	char  s1[100], s2[100];
    	while(scanf("%s %s", s1, s2) != EOF)
    	{
    		int tag = 1;
    		Init(a, s1, tag);
    		Init(b, s2, tag);
    		//a=Mul1(a,ival);
    		//a = Mul2(a, b);
    		/*Div2(a,b,c,f);
    		print(c);
    		print(f);*/
    		if(a.len == 1 && a.num[0] == 0)
    		{
    			puts("0");
    		}
    		else 
    		{
    			if(tag < 0) putchar('-');
    			print(a);
    		}
    	}
    	system("pause");
    	return 0;
    }

高精度n阶乘N!

首先，定义两个整型的数组：   
int fac\[1000\];暂且先设定是1000位，我称之为“结果数组”   
int add\[1000\];我称之为“进位数组”   
现在具体说明两个数组的作用：   
1.fac\[1000\]   
比如说，一个数5的阶乘是120，那么我就用这个数组存储它：   
fac\[0\]=0   
fac\[1\]=2   
fac\[2\]=1   
现在明白了数组fac的作用了吧。用这样的数组我们可以放阶乘后结果是1000位的数。   
  
2.在介绍add\[1000\]之前，我介绍一下算法的思想，就以6！为例：   
从上面我们知道了5！是怎样存储的。   
就在5！的基础上来计算6！，演示如下：   
  
fac\[0\]=fac\[0\]\*6=0   
fac\[1\]=fac\[1\]\*6=12   
fac\[2\]=fac\[2\]\*6=6   
  
3.现在就用到了我们的：“进位数组”add\[1000\].   
先得说明一下：add就是在第2步中用算出的结果中，第i位向第i+1位的进位数值。还是接上例：   
add\[0\]=0;   
add\[1\]=1;  // 计算过程：就是 (fac\[1\]+add\[0\])  %  10＝1   
add\[2\]=0;  /\*计算过程：就是 (fac\[2\]+add\[1\]) % 10=0   
add\[i+1\] =( fac\[i+1\] + add\[i\] ) % 10    这个  
现在就知道了我们的数组add\[\]是干什么的了吧，并且明白了add是如何求得的了吧。   
4.知道了add\[1000\]的值，现在就在 1. 和 3 . 两步的基础上来计算最终的结果。（第2步仅作为我们理解的步骤，我们下面的计算已经包含了它）   
fac\[0\] = ( fac\[0\]\*6 )  mod 10 =0    
fac\[1\] = ( fac\[1\]\*6 + add\[0\] ) mod 10 ＝2   
fac\[2\] = ( fac\[2\]\*6 + add\[1\] ) mod 10=7    //data\[j+1\]=(data\[j+1\]\*i+add\[j\])%10  
到这里我们已经计算完了6！。然后就可以将数组fac\[1000\]中的数，以字符的形式按位输出到屏幕上了。   
5.还有一点需要说明，就是我们需要一个变量来记录fac\[1000\]中实际用到了几位，比如5！用了前3位；   
我们在这里定义为 top    
      为了计算top，我们有用到了add\[1000\],还是以上面的为例：   
    5！时，top=3,在此基础上我们来看6！时top=?   
      由于  add\[2\]=0   
      所以  top=3（没有变）   
也就是说，如果最高位有进位时，我们的top=top+1,否则，top值不变。   
6.总结一下，可以发现，我们把阶乘转化为 两个10以内的数的乘法，还有两个10以内的数的家法了。   
  因此，不管再大的数，基本上都能算出了，只要你的数组够大就行了。

// 1042 N!.cpp : 定义控制台应用程序的入口点。
    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    #define  MAX 1000
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int flag=0;//进位标记
    	int val,index,length;
    	while(cin>>index)
    	{
    		int result[MAX]={0};//存放运算结果的数组
    		result[0]=1;
    		for(int i=2;i<=index;++i)
    			{
    				flag=0;
    				for (int j=1;j<MAX;++j)
    				{
    					val=result[j-1]*i+flag;
    					result[j-1]=val%10;
    					flag=val/10;
    				}
    			}
    		for(int j=MAX-1;j>=0;j--)
    			if (result[j])//忽略前导0
    			{
    				length=j;
    				break;
    			}
    
    		for(int i=length;i>=0;i--)
    			cout<<result[i];
    		cout<<endl;
    	}
    	
    	system("pause");
    	return 0;
    }

[http_blueve.me_archives_category_lrn_cpts]: http://blueve.me/archives/category/lrn/cpts