1828--高精度

小康

这道题，答案明显会是1000位，用什么数据类型都不行。所以要用高精度。
先看看以下程序。
int i,j,k;
i=100;
j=200;
k=i+j;

int i[3],j[3],k[3];

i[0]=1; i[1]=0; i[2]=0;

j[0]=1; j[1]=0; j[2]=0;

k[0]=i[0]+j[0]; k[1]=i[1]+j[1]; k[2]+j[2];

两个的答案分别是 k=200 ;  k[]={2,0,0}

可见，用数组保存一位位的数字，然后我们可以模拟加法运算。
用数组模拟运算，可以达到很高的位数，精度，这就是高精度。
我们定义一个int i[1000]，就可以实现100位的加法运算了。。

[ Last edited by 小康 on 2005-8-1 at 21:54 ]

晓东

#include<stdio.h>
#include<string.h>}
main()
{
        char s1[1000];
        char s2[1000];
        char s[1000];
        int n,i,m,flag,t;
        while(scanf("%d",&n)!=EOF)
        {
                m=1;
        for(i=0;i<1000;i++)
                        s1='0';
                s1[999]='1';
                for(i=0;i<1000;i++)
                        s2='\0';
                s2[999]='1';
                for(i=0;i<1000;i++)
                        s='0';
                while(m<=n)
                {
           if(m==1)
                   {
                           for(i=0;i<1000;i++)
                                   s='0';
                           s[999]='1';
                   }
                   if(m==2)
                   {
                          for(i=0;i<1000;i++)
                                   s2='0';
                           s2[999]='1';
                   }
                   if(m>2)
                   {
                           t=0;
                           for(i=999;i>=0;i--)
                           {
                                       s=(s1-48+s2-48+t)%10+48;
                               t=(s1-48+s2-48+t)/10;
                                       
                           }
                           for(i=0;i<1000;i++)
                                   s1=s2;
                           for(i=0;i<1000;i++)
                                   s2=s;
                   }
                   m++;
                }
                flag=0;
            for(i=0;i<1000;i++)
                    if(flag==0&&s=='0')continue;
                        else
                        {
                           printf("%c",s);
                           flag=1;
                        }
                printf("\n");
        }
}

小康

#include<stdio.h>
#include<string.h>
const int bitlong=1100;
struct Bigint{
        int len;
        char bit[bitlong];
};
Bigint add(Bigint a,Bigint b)
{
        Bigint c;
        int i;
        if(a.len<b.len)
        {
                for (i=a.len;i<b.len;i++) a.bit=0;
                c.len=b.len;
        }else
        {
                        for (i=b.len;i<a.len;i++) b.bit=0;
                        c.len=a.len;
        }
        int k=0;
        for (i=0;i<c.len ;i++)
        {
        c.bit=a.bit+b.bit+k;
                if(c.bit>9)
                {
                        k=1;
                        c.bit-=10;
                }else k=0;
        }
        if(k==1)
        {
                c.bit[c.len]=k;
                c.len++;               
        }
        return c;
}
void print(Bigint a)
{
        int i;
        i=a.len-1;
        while(i>-1)
                printf("%d",a.bit[i--]);       
        printf("\n");
}
Bigint s[5000];
int main()
{
       
        int i,j,k,n;       
        s[1].bit[0]=1;
        s[2].bit[0]=1;
        s[1].len=1;
        s[2].len=1;
        for (i=3;i<5000;i++)
        {
                s=add(s[i-1],s[i-2]);
        }
        while(scanf("%d",&n)!=EOF)
        {
                print(s[n]);               
        }       
        return 0;
}

迷你大象

#include "stdafx.h"
#define N 1000

class Number{
public :       
        char digit[N];
        int i;
        Number(){
                digit[0]='1';
                digit[1]=0;
                i=1;
        }
};

void converse(char array[],int n){
        int temp;
        for(int i=n-1;i>=n/2;i--){
                temp=array;
                array=array[n-1-i];
                array[n-1-i]=temp;
        }
}

inline Number  add(Number first,Number second){
        Number c;
        c.i=0;
        int sum;
        bool up;
        char *p;                //指向较短的数组
        int max,min;        //通过max和min来把短的数组后填'0'

                up=0;

                min=first.i>second.i?second.i:first.i;
                max=first.i>second.i?first.i:second.i;
                p=first.i>second.i?second.digit:first.digit;

                for(int addzero=min;addzero<max;addzero++){
                        p[addzero]='0';
                }

                first.digit[max]=0;
                second.digit[max]=0;

                converse(first.digit,first.i);
                converse(second.digit,second.i);

                first.i=0;
                second.i=0;

                while(first.digit[first.i]!=0 && second.digit[second.i]!=0){
                        sum=first.digit[first.i]+second.digit[second.i]+up-'0'-'0';
                        c.digit[c.i]=sum%10+'0';
                        if(sum>9)up=1;
                        else up=0;
                        first.i++;
                        second.i++;
                        c.i++;
                }

                if(up)c.digit[c.i++]='1';
                c.digit[c.i]=0;

                //把多余的'0'去掉
                while(c.digit[c.i-1]=='0' && c.i>=0)first.digit[--c.i]=0;

                converse(c.digit,c.i);


                //如果答案为0,上代码计算结果为空,将其变为 "0\0"
        /*        if(first.digit[0]==0){
                        first.digit[0]='0';
                        first.digit[first.i=1]=0;
                }*/


        return c;
}

int _tmain(int argc, _TCHAR* argv[])
{
        int in;
        while(scanf("%d",&in)!=EOF){
                if(in==1 || in==2){
                        printf("1\n");
                        continue;
                }
                Number array[3];
                int now=2,pre1,pre2;
                for(int i=2;i<in;i++){
                        now=i%3;
                        pre1=now-1;
                        pre2=now-2;
                        if(pre1<0)pre1+=3;
                        if(pre2<0)pre2+=3;

                        array[now]=add(array[pre1],array[pre2]);
                }

                printf("%s\n",array[now].digit);
        }


}