PersonalCorpus 版 (精华区)

寄信人: sino (茶水)
标  题: 495
发信站: 哈工大紫丁香 (2002年06月16日18:19:15 星期天)
来  源: 202.118.239.224 

Your C++ program has solved Ok the problem 495 (Fibonacci Freeze)
in 0.730 seconds using as much as 6288 kbytes of virtual memory.

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <ctype.h>


struct longinteger{
    int a[300];
    int len;
};

void copyLI(struct longinteger *des,struct longinteger *src)
{

    for ( int i=0; i<src->len;i++) des->a[i]=src->a[i];
    des->len=src->len;
}

void addLI2(struct longinteger *des, struct longinteger *src)
{
    int i,j,k;

    k=0; i=0;
    while ((i<des->len)&&((i<src->len))) {
        des->a[i]+=src->a[i];
        des->a[i]+=k;
        k=des->a[i]/10000;
        des->a[i]%=10000;
        i++;
    }
    while (i<des->len) {
        des->a[i]+=src->a[i];
        des->a[i]+=k;
        k=des->a[i]/10000;
        des->a[i]%=10000;
        i++;
    }
    while (i<src->len) {
        des->a[i]+=src->a[i];
        des->a[i]+=k;
        k=des->a[i]/10000;
        des->a[i]%=10000;
        i++;
    }
    if (k!=0) { des->a[i]=k; i++; }
    des->len=i;
}




void addLI3(struct longinteger *des, struct longinteger *src1, struct 
longinteger *src2)
{
    copyLI(des,src1);
    addLI2(des,src2);
}

void setzeroLI(struct longinteger *des)
{
    memset(des,0,sizeof(struct longinteger));
    des->len=1;
}

void setoneLI(struct longinteger *des)
{
    setzeroLI(des);
    des->len=1;
    des->a[0]=1;
}

void mulLI2(struct longinteger *des, int src)
{
    int i,j,k;

    k=0; i=0;
    while (i<des->len) {
        des->a[i]*=src;
        des->a[i]+=k;
        k=des->a[i]/10000;
        des->a[i]%=10000;
        i++;
    }
    des->a[i]=k; i++;
    while (des->a[i-1]>10000) {
        des->a[i]=des->a[i-1]/10000;
        des->a[i-1]%=10000;
        i++;
    }
    des->len=i;
}

void mulLI3(struct longinteger *des, struct longinteger *src1,int 
src2)
{
    copyLI(des,src1);
    mulLI2(des,src2);
}



void mulLL2(struct longinteger *des, struct longinteger *src)
{
    int i,j,k;
    struct longinteger temp1,temp2;

    setzeroLI(&temp2);
    for (i=0;i<src->len;i++) {
        setzeroLI(&temp1);
        mulLI3(&temp1,des,src->a[i]);
        addLI2(&temp2,&temp1);
    }
    copyLI(des,&temp2);
}


void mulLL3(struct longinteger *des, struct longinteger *src1, struct 
longinteger *src2)
{
    copyLI(des,src1);
    mulLL2(des,src2);
}

void printLI(struct longinteger *des)
{
    int i,j,k;
    if (des->len<=0) return;

    for (i=des->len-1;i>=0;i--)  if (des->a[i]>0) {
        printf("%d",des->a[i]);
        break;
    }
    if (i<0) {
        printf("0");
        return;
    }
    for (j=i-1;j>=0;j--) {
        if (des->a[j]<1000) printf("0");
        if (des->a[j]<100) printf("0");
        if (des->a[j]<10) printf("0");
        printf("%d",des->a[j]);
    }
}




void main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\uva\\input495.txt","r",stdin);
    freopen("c:\\uva\\output495.txt","w",stdout);
#endif

    struct longinteger *f;
    int i;
    f=(struct longinteger *) malloc(sizeof(struct longinteger)*5001);
    setzeroLI(&f[0]); setoneLI(&f[1]);
    for (i=2;i<5001;i++) addLI3(&f[i],&f[i-1],&f[i-2]);
    while (scanf("%d\n",&i)==1) {
        printf("The Fibonacci number for %d is ",i);
        printLI(&f[i]);printf("\n");
    }
}

--
SecureNetTerm can be dowloaded to all countries except
Cuba, Iran, Iraq, Libya, North Korea, Sudan and Syria.

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.224]