斐波那契第2009项目

Nisy

// MyFei.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <string.h>
#define MAX 1000000000
#define LEN 1004

void BigNumAdd(int * num1,int * num2,int * len1,int * len2)
{
    int temp = 0;
    for(int i=0;i<*len2;i++)
    {
        num1[i] += num2[i] + temp;  // += <==> +()
        temp = num1[i]/MAX;
        num1[i]%=MAX;
    }
    num1[i]+=temp;
    if(*len1 < *len2)
    {
        *len1 = *len2;         
    }  
    if(num1[i])
        (*len1)++;  // 再次犯下同样的错误
}

void ShowBigNum(int * num1,int len1)
{
    if(!num1[len1])len1--;
    printf("%d",num1[len1--]);
    for(int k=len1;k>=0;k--)
        printf("%09d",num1[k]);
    printf("\r\n");
}

int main(int argc, char* argv[])
{
    int * num1 = new int[100];
    int * num2 = new int[100];
    memset(num1,0,sizeof(int)*100);
    memset(num2,0,sizeof(int)*100);
    int len1,len2;
    len1 = len2 = num1[0] = num2[0] = 1;
    for(int i=0;i<LEN;i++)
    {
        BigNumAdd(num1,num2,&len1,&len2);
        BigNumAdd(num2,num1,&len2,&len1);
    }
    printf("斐波那契数列第%d项为：\r\n",LEN*2+1); // 单项+1 双项+2
    ShowBigNum(num1,len1);
    return 0;
}

斐波那契数列第2009项为：
32113249982681582845238472032097086207406078264369213828207269738873528372164658
13601607624368278410255618945484808988900205426234968094236646697230669809316249
08775724739402394881483009611433054415348267177640331222672835631629564907858584
30785050847615157489167011704773920617812432061755619769908742336741418110524930
07153851287942959207659531735086437334610990020876787656487609216126565715584580
25510084617009128909
请按任意键继续. . .

超然

很好，很强大

学习

wmp1014

就想知道这题。

xusir98

展望明年，就是飞不拉鸡的第2010项了！

Nisy

这个大数加法的精髓在这句话上：

#define MAX 1000000000

搞明白这个 就什么都明白了

evilknight

膜拜一下大牛!

Nisy

原帖由 evilknight 于 2009-9-24 18:42 发表
膜拜一下大牛!

膜拜下小齐 再膜拜一下 ~~

dabing85

#include   <stdio.h>   
#include   <malloc.h>   
#include   <memory.h>   

#define   UNIT_VALUE 1000000000L   
#define   STEP_VALUE 43   
#define   PRINT_SIZE 9   

typedef   int   int32;   

void   main()   
{   
        int32   n,i;   
        int32   size;   
        int32   *p,*q,*r,*s;   
        //
starthere:
       
        printf("Please input a number n to calculate the nth Fibonacci  number:");   
       
        scanf("%d",&n);   
        if(n<=0)   
        {   
                printf("1\n");   
                return;   
        }
       
        size=(n+STEP_VALUE-1)/STEP_VALUE;   
       
        p=(int32   *)malloc(size*sizeof(int32));   
        q=(int32   *)malloc(size*sizeof(int32));   
        r=(int32   *)malloc(size*sizeof(int32));   
        memset(p,0,size*sizeof(int32));   
        memset(q,0,size*sizeof(int32));   
        memset(r,0,size*sizeof(int32));   
       
        q[0]=1;
       
        for(i=1;i<n;i++)   
        {   
                int32   j;   
                int32   limit=(i+STEP_VALUE-1)/STEP_VALUE;   
                int32   carry=0;   
                for(j=0;j<limit;j++)   
                {   
                        int32   result;   
                        result=p[j]+q[j]+carry;   
                        if(result>=UNIT_VALUE)   
                        {   
                                carry=1;   
                                result-=UNIT_VALUE;   
                        }   
                        else   
                        {   
                                carry=0;   
                        }   
                        r[j]=result;   
                }   
               
               
                s=p;   
                p=q;   
                q=r;   
                r=s;   
        }   
        for(i=size-1;i>=0;i--)   
        {   
                if(q[i]!=0)   
                        break;   
        }   
       
        printf("%d",q[i--]);  
       
        for(;i>=0;i--)   
        {   
                printf("%0*d",PRINT_SIZE,q[i]);   
        }   
        printf("\n");  
       
        free(p);   
        free(q);   
        free(r);   
        goto   starthere;   
}   



看到过的一个例子 检验过了 可以用。

backer

节约只有两个字
1111234567890 2345678901 3456789012
+  9876543210 8765432109 7654321098
======================================>

   0000000000 0000000000 3456789012
+  0000000000 0000000000 7654321098
----------------------------------------
   0000000000 000000000? ??????????
+  0000000000 2345678901 0000000000

+  0000000000 8765432109 0000000000
+  1234567890 0000000000 0000000000
+  9876543210 0000000000 0000000000

[ 本帖最后由 backer 于 2009-9-25 00:49 编辑 ]