高精度模板

<<高精度模板>>

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstring>
using namespace std;
#define maxsize 1005
//建立一个结构体
struct hp
{
    int len;//用来存储转化为整型后的长度
    int s[maxsize+1];//用来存储每一位
};
//copy  函数把b  copy给a
void copy(hp &a,hp &b)
{
    a.len=b.len;
    for(int i=1;i<=b.len;i++)
        a.s[i]=b.s[i];
}
//输入函数
void input(hp &a,string str)
{
    int i;
    while(str[0]=='0' && str.size()!=1)
        str.erase(0,1);//删除第一个元素
    a.len=(int)str.size();//把str的长度复制给a的len
    for(i=1;i<=a.len;++i)
        a.s[i]=str[a.len-i]-48;//a数组存储每一位，并且字符要逆向存入数组
    for (i=a.len+1;i<=maxsize;++i)
        a.s[i]=0;//剩下的为0
}
//输出函数
void print(const hp &y)
{
    int i;
    for(i=y.len;i>=1;i--)//注意输出是要后面向前输出i=y.len
        printf("%d",y.s[i]);
    cout<<endl;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1 高精度加法
void plusk(const hp &a,const hp &b,hp &c)
{
    int i,len;
    for(i=1;i<=maxsize;i++)
            c.s[i]=0;//初始化数组可以用memset
    //len为两者中的最大值
    if(a.len>b.len)
           len=a.len;
    else
          len=b.len;
    //计算
    for(i=1;i<=len;i++)
    {
        c.s[i]+=a.s[i]+b.s[i];//注意这里是c.s[i]+=a.s[i]+b.s[i]
        if(c.s[i]>=10)//考虑进位思想
        {
            c.s[i]-=10;
            c.s[i+1]++;
        }
    }
    if(c.s[len+1]>0) //最后一位有进位情况
         len++;
    c.len=len;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2 高精度减法
void subtract(const hp &a,const hp &b,hp &c)
{
    int i,len;
    for(i=1;i<=maxsize;i++)
          c.s[i]=0;//初始化为0
    //求最大的长度
    if(a.len>b.len)
          len=a.len;
    else
         len=b.len;
    //减法计算
    for(i=1;i<=len;i++)
    {
        c.s[i]+=a.s[i]-b.s[i];//这个地方注意c.s[i]+=a.s[i]-b.s[i]
        if(c.s[i]<0)//如果小于0则要向前借位
        {
            c.s[i]+=10;//这里对应加10
            c.s[i+1]--;//前一位减1
        }
    }
    while(len>1&&c.s[len]==0)
           len--;//舍去前面的0
    c.len=len;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
3 高精度比较
int compare(const hp &a,const hp &b)
{
    int len;
    //求最大的长度
    if(a.len>b.len)
        len=a.len;
    else
        len=b.len;
    while(len>0 && a.s[len]==b.s[len])
        len--;
    if(len==0) //如果两个相等
        return 0;
    else
        return a.s[len]-b.s[len];//a.s[len]-b.s[len]如果是负数则说明a小于b，反之
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
4高精度*单精度
void multiply(const hp &a,int b,hp &c)
{
    int i,len;
    for(i=1;i<=maxsize;i++)
         c.s[i]=0;//初始化为0
    len=a.len;
    //计算乘法
    for(i=1;i<=len;i++)
    {
        c.s[i]+=a.s[i]*b;//把每一位乘上b存到结构体C里，这里是 c.s[i]+=a.s[i]*b
        //进位思想
        c.s[i+1]+=c.s[i]/10;
        c.s[i]%=10;
    }
    //处理进位
    len++;
    while(c.s[len]>=10)
    {
        //进位运算
        c.s[len+1]+=c.s[len]/10;
        c.s[len]%=10;
        len++;
    }
    while(len>1&&c.s[len]==0)
          len--;//舍去前面没用的0
    c.len=len;
}


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
5高精度*高精度
void multiplyh(const hp &a,const hp &b,hp &c)
{
    int i,j,len;
    for(i=1;i<=maxsize;i++)
         c.s[i]=0;//初始化为0
    //计算
    for(i=1;i<=a.len;i++)
        for(j=1;j<=b.len;j++)
        {
            c.s[i+j-1]+=a.s[i]*b.s[j];//注意这里的计算
            c.s[i+j]+=c.s[i+j-1]/10;
            c.s[i+j-1]%=10;
        }
    ////////////////////////////
    len=a.len+b.len+1;
    while(len>1&&c.s[len]==0)
           len--;//舍去前面没用的0
    c.len=len;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
6高精度/单精度  {d为余数}
void divide(const hp &a,int b,hp &c,int &d)  　
{
    int i,len;
    for(i=1;i<=maxsize;i++)
         c.s[i]=0;//初始化为0
    len=a.len;
    d=0;
    //注意除法的计算要从高位向下除
    for(i=len;i>=1;i--)
    {
        d=d*10+a.s[i];//计算
        c.s[i]=d/b;//存入c中
        d%=b;//d为于数
    }
    ////////////////////////////////
    while(len>1&&c.s[len]==0)
        len--;//舍去前面没用的0
    c.len=len;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
7 高精度*10
void multiply10(hp &a)    
{
    int i;
    //乘上10就是每一位都向前移动，而s[1]=0；
    for(i=a.len;i>=1;i--)
        a.s[i+1]=a.s[i];
    a.s[1]=0;
    //////////////////////
    a.len++;
    while(a.len>1&&a.s[a.len]==0)
        a.len--;//舍去前面没用的0
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
8   高精度/高精度 　{d为余数}
void divideh(const hp &a,const hp &b,hp &c,hp &d)  
{
    hp e;
    int i,len;
    //初始化
    for(i=1;i<=maxsize;i++)
    {
        c.s[i]=0;
        d.s[i]=0;
    }
    ////////////////////////////
    len=a.len;
    d.len=1;
    for(i=len;i>=1;i--)
    {
        multiply10(d);//高进度乘上10
        d.s[1]=a.s[i];
        while(compare(d,b)>=0)
        {
            subtract(d,b,e);
            d=e;
            c.s[i]++;
        }
    }
    while(len>1&&c.s[len]==0)
          len--;//舍去前面没用的0
    c.len=len;
}
///////////////////////////////////////////////////////////////////
hp sum[1003];//创建一个结构体数组
int main()
{
            int n=1002;
        hp a, b,c,tmp;
        c.len=0;
        a.s[1]=1;
        for(int i=2;i<1002;i++)
        {
                     b.s[i]=0;    
                     a.s[i]=0;
                 }
        for(int i=0;i<1002;i++)
        {
            sum[i].len=1;
            memset(sum[i].s,0,sizeof(sum[i].s));
        }
        a.len=1;
        b.s[1]=2    ;
        sum[1].s[1]=2;
        sum[2].s[1]=1;
        b.len=1;
        int pos=2;
        if(n>2)
        {    
                for(int i=1;i<n;i++)
                {
                      plusk(a,b,c);
                      copy(sum[pos],c);
                      int pos2;
                      pos2=pos+1;
                      copy(a,b);
                      copy(b,c);
                      pos++;
                  }
        }
        while(cin>>n)
        {
           print(sum[n]);
         }
         return 0;
}