CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks
#include <iostream>
#include 
<stdio.h>
#include 
<string>
#include 
<string.h>
#include 
<math.h>
#include 
<queue>
#include 
<memory.h>
using namespace std;

#define bigNum_size 220  //大数的段数,bigNum能表示的最大长度 = bigNum_size*log(mod) 
#define mod 100000   //每段存储数字的长度为0的个数 

char A[1010], B[1010];

struct bigNum
{
    
int a[bigNum_size];
    
int len;//存储大数的段数,初始化时长度都为1,表示的值默认为0 
    bigNum()
    {
        len 
= 1;
        memset(a, 
0sizeof(a));
    }
    bigNum(
char *str)
    {
        
int n = strlen(str);
        
int t = 0;
        
int m, i, k = 0, inf = 1;
        memset(a, 
0sizeof(a));
        
for (i = n - 1; i >= 0; i--)
        {
            m 
= str[i] - '0';
            k 
+= inf*m;
            inf 
*= 10;
            
if (inf == mod)
            {
                inf 
= 1;
                a[t
++= k;
                k 
= 0;
            }
        }
        a[t
++= k;
        
while (t > 1 && a[t-1== 0) t--;
        len 
= t;
    }
    bigNum(
int x)
    {
        memset(a, 
0sizeof(a));
        a[
0= x;
        
int i = 1;
        
while (a[i-1>= mod)
        {
            a[i] 
= a[i-1]/mod;
            a[i
-1%= mod;
            i
++;
        }
        len 
= i;
    }
};



bigNum 
operator +(bigNum x, bigNum y)
//重载运算符"+",执行两个大数的加法并返回结果 
{
    
int i, n;
    bigNum s;
    
if (x.len < y.len)
    {
        bigNum temp 
= x;
        x 
= y;
        y 
= temp;
    }
    n 
= y.len;
    
for (i = 0; i < n; i++)
    {
        x.a[i] 
+= y.a[i];
        x.a[i
+1+= x.a[i]/mod;
        x.a[i] 
%= mod;
    }
    
while (x.a[n] > mod)
    {
        x.a[n
+1+= x.a[n]/mod;
        n
++;
    }
    
if (x.a[x.len])x.len++;
    
return x;
}



bigNum 
operator *(int m, bigNum x)
//重载运算符"*",执行一个大数乘以一个int内的数字,并返回结果 
{
    
int i,  k = 0;
    
for (i = 0; i < x.len; i++)
    {
        x.a[i] 
= x.a[i] * m + k;
        k 
= x.a[i] / mod;
        x.a[i] 
%= mod;
    }
    
while (k)
    {
        x.a[i] 
= k%mod;
        k 
/= mod;
        i
++;
    }
    x.len 
= i;
    
return x;
}

bool operator < (bigNum x, bigNum y)
//比较两个大数的大小,如果x<y返回true,否则返回false 
{
    
if (x.len < y.len)
        
return true;
    
if (x.len > y.len)
        
return false;
    
int i;
    
for (i = x.len - 1; i >= 0; i--)
        
if (x.a[i] < y.a[i])
            
return true;
        
else if (x.a[i] > y.a[i])
            
return false;
        
return false;
}


bigNum 
operator - (bigNum x, bigNum y)
//计算两个大数的减法,其中保证x>y。 
{
    bigNum s;
    
int i;
    
int k = 0;
    
for (i = 0; i < y.len; i++)
    {
        
if (x.a[i] == -1)
        {
            x.a[i] 
= mod - 1;
            x.a[i
+1]--;
        }
        
if (x.a[i] >= y.a[i])
            s.a[i] 
= x.a[i] - y.a[i];
        
else
        {
            s.a[i] 
= mod + x.a[i] - y.a[i];
            x.a[i
+1]--;
        }
    }
    
while (i < x.len)
    {
        
if (x.a[i] == -1)
        {
            x.a[i] 
= mod - 1;
            x.a[i
+1]--;
        }
        s.a[i] 
= x.a[i];
        i
++;
    }
    s.len 
= i;
    
while (s.a[s.len - 1== 0)
    {
        s.len
--;
    }
    
if (s.len == 0)
        s.len 
= 1;
    
return s;
}


bigNum sqrt_bignum(bigNum x)
//开根号,只能对大的正整数开方求得整数不分,
//如果要对小数开方或对正整数开方求小数点后面的数字,
//可以将这个数扩大10^(2*k)倍在进行开方。
// 在调用开发函数时, mod = 10 才能完成。所以效率不是很高。 
{
    bigNum s, md;
    bigNum p;
    bigNum temp;
    
int n = x.len;
    
int k;
    
int i;
    
if (n%2)
    {
        
if (x.a[n-1> 8)
        {
            s.a[
0= 3;
            md.a[
0= x.a[n-1- 9;
        }
        
else if (x.a[n-1> 3)
        {
            s.a[
0= 2;
            md.a[
0= x.a[n-1- 4;
        }
        
else
        {
            s.a[
0= 1;
            md.a[
0= x.a[n-1- 1;
        }
        n
--;
    }
    
    
for (i = n - 1; i > 0; i = i - 2)
    {
        p.a[
1= x.a[i];
        p.a[
0= x.a[i-1];
        p.len 
= 2;
        md 
= (100 * md + p);    
        
for (k = 1; k < 10; k++)
        {
            p.a[
0= k;
            p.len 
= 1;
            temp 
= 20*+ p;
            temp 
= k*temp;
            
if (md < temp)
                
break;
        }
        k
--;
        p.a[
0= k;
        p.len 
= 1;
        temp 
= 20*+ p;
        temp 
= k*temp;
        md 
= md - temp;
        s 
= 10*+ p;    
    }
    
return s;
}


void output(bigNum x)
//输出大数的函数 
{
    
int i;
    
int n = x.len;
    printf(
"%d", x.a[n-1]);
    
for (i = n - 2; i >= 0; i--)
        printf(
"%05d", x.a[i]);// %d05d与mod大小有关,即每段的数字个数。 
    printf("\n");
}

int main()
{
    
return 0;
}
posted on 2011-04-13 18:49 CodeStream 阅读(382) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理