随笔 - 87  文章 - 279  trackbacks - 0
<2006年4月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214754
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

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

typedef  
long   long  _BigInt;
const   int  BITSIZE  =   7000 ;
const   int  EACHBITNUM  =   1000000000 ;
class  BIGINT
{
public :
    _BigInt size;
    _BigInt data[BITSIZE];
    BIGINT();
    BIGINT(
string );
    BIGINT 
operator = ( const  BIGINT & );
    
bool   operator < ( const  BIGINT  & );
    
bool   operator == ( const  BIGINT  & );
    
bool   operator > ( const  BIGINT  & );
    
bool   operator <= ( const  BIGINT  & );
    
bool   operator >= ( const  BIGINT  & );
    
bool   operator != ( const  BIGINT  & );
    friend BIGINT 
operator + ( const  BIGINT & const  BIGINT & );
    friend BIGINT 
operator - (BIGINT, BIGINT);
    friend BIGINT 
operator * ( const  BIGINT  & const  BIGINT  & );
    
// friend BIGINT operator/(const BIGINT &, const BIGINT &);
     void  print();
}
;

BIGINT::BIGINT()
{
    size 
=   0 ;
    memset(data, 
0 sizeof (data));
}

BIGINT::BIGINT(
string  s)
{
    
int  i;
    
int  len  =  s.length();
    
int  exp  =   1 ;
    _BigInt tmp 
=   0 ;
    size 
=   0 ;
    memset(data, 
0 sizeof (data));
    
for  (i = len; i >= 1 ; i -- )
    
{
        tmp 
+=  (s[i - 1 -   ' 0 ' *  exp;
        
if  (exp  ==  EACHBITNUM / 10 )
        
{    
            data[
++ size]  =  tmp;
            tmp 
=   0 ;
            exp 
=   1 ;
        }

        
else
            exp 
*=   10 ;
    }

    
if  (tmp  !=   0 )
        data[
++ size]  =  tmp;
}

BIGINT BIGINT::
operator = ( const  BIGINT  & a)
{
    
int  i;
    memset(data, 
0 sizeof (data));
    size 
=  a.size;
    
for  (i = 1 ; i <= size; i ++ )
        data[i] 
=  a.data[i];
    
return   * this ;
}

void  BIGINT::print()
{
    
int  i;
    
for  (i = size; i >= 1 ; i -- )
        
if  (i  !=  size)
           printf(
" %.9lld " , data[i]);
        
else
           printf(
" %lld " , data[i]);
    printf(
" \n " );
}

bool  BIGINT:: operator < ( const  BIGINT  & a)
{
     
int  i;
     
if  (size  <  a.size)  return   true ;
     
if  (size  >  a.size)  return   false ;
     
for  (i = 1 ; i <= size; i ++ )
         
if  (data[i]  >=  a.data[i])  return   false ;
     
return   true ;     
}

bool  BIGINT:: operator == ( const  BIGINT  & a)
{
     
int  i;
     
if  (size  !=  a.size)  return   false ;
     
for  (i = 1 ; i <= size; i ++ )
         
if  (data[i]  !=  a.data[i])  return   false ;
     
return   true ;
}

bool  BIGINT:: operator > ( const  BIGINT  & a)
{
     
int  i;
     
if  (size  >  a.size)  return   true ;
     
if  (size  <  a.size)  return   false ;
     
for  (i = 1 ; i <= size; i ++ )
         
if  (data[i]  <=  a.data[i])  return   false ;
     
return   true ;  
}

bool  BIGINT:: operator >= ( const  BIGINT  & a)
{
     
return   ! (( * this <  a);
}

bool  BIGINT:: operator <= ( const  BIGINT  & a)
{
     
return   ! (( * this >  a);
}

bool  BIGINT:: operator != ( const  BIGINT  & a)
{
     
return   ! (( * this ==  a);
}

BIGINT 
operator + ( const  BIGINT  & a,  const  BIGINT  & b)
{
    BIGINT rnt;
    
int  i;
    
bool  t  =   false ;
    _BigInt tmp;
    
int  len  =  a.size  >  b.size  ?  a.size : b.size;
    
for  (i = 1 ; i <= len; i ++ )
    
{
        tmp 
=  a.data[i]  +  b.data[i];
        
if  (t) tmp  +=   1 ;
        t 
=   false ;
        
if  (tmp  >=  EACHBITNUM)
        
{
            tmp 
-=  EACHBITNUM;
            t 
=   true ;
        }

        rnt.data[
++ rnt.size]  =  tmp;
    }

    
if  (t) rnt.data[ ++ rnt.size]  +=   1
    
return  rnt;
}

BIGINT 
operator - (BIGINT a, BIGINT b)
{
    BIGINT rnt;
    
int  i;
      
//  if (a < b) return rnt;
     for  (i = 1 ; i <= a.size; i ++ )
    
{
        
if  (a.data[i]  <  b.data[i])
        
{
            a.data[i
+ 1 ] -- ;
            a.data[i] 
+=  EACHBITNUM;
        }

        rnt.data[
++ rnt.size]  =  a.data[i]  -  b.data[i];
    }

    
return  rnt;
}

BIGINT 
operator * ( const  BIGINT  & a,  const  BIGINT  & b)
{
    
int  i, j;
    BIGINT rnt;
    _BigInt tmp;
    
for  (i = 1 ; i <= a.size; i ++ )
        
for  (j = 1 ; j <= b.size; j ++ )
        
{
            tmp 
=  a.data[i]  *  b.data[j];
            rnt.data[i
+ j - 1 +=  tmp;
            rnt.data[i
+ j]  +=   rnt.data[i + j - 1 /  EACHBITNUM;
            rnt.data[i
+ j - 1 %=  EACHBITNUM;
        }

    
for  (i = BITSIZE - 1 ; i >= 1 ; i -- )
        
if  (rnt.data[i]  >   0   ||  i  ==   1 )
        
{
            rnt.size 
=  i;
            
break ;
        }

    
return  rnt;
}


int  main()
{    
    
int  n;
    
int  i;
    BIGINT one(
" 1 " );
    BIGINT y(
" 1 " );
    cin 
>>  n;

    
for  (i = 1 ; i <= n; i ++ )
    
{
        y 
=  y  +  one;
        y.print();
        y 
=  y  *  (y  -  one);
    }

    system(
" pause " );
    
return   0 ;
}

posted on 2006-09-03 04:29 阅读(520) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理