计算斐波那契函数前200项的平均值问题 - C语言论坛

楼主

已结贴√ 问题点数：20 回复次数：7

计算斐波那契函数前200项的平均值问题

做一个纯纯的文科生，竟然报了程序设计这门课，更坑爹的是总共才上了三节课，就出了这么一道题“计算斐波那契数列前200项的平均值。”
好晕啊，根本不知道从何处下手，求大神帮助啊

搜索更多相关主题的帖子: 文科生　平均值　程序设计　

第 2 楼

得分:0

目前只有这个#include <stdio.h>

void main()
{
int i,array[20]={1,1};

for (i=2; i<20; i++)
{
array[i]=array[i-2]+array[i-1];
}
for (i = 0; i<20; i++)
{
printf("%d ",array[i]);
}
printf("\n");
}

然后就不知道该怎么办了

第 3 楼

得分:10

程序代码：

//这个是基本的思想，但是数字太大了计算机都表示不了，看看别人有什么办法。
#include <stdio.h>

int main()
{
    int i=0,n[200]={0};
    float sum=0;
    
    for(;i<200;i++)
    {
        if(i<2) n[i]=i;
        else  n[i]=n[i-1]+n[i-2];
        sum+=n[i];
    }

    printf("average=%.3f\n",sum/200);

    return 0;    
}

[此贴子已经被作者于2016-3-20 15:51编辑过]

唯实惟新至诚致志

第 4 楼

得分:10

先给出结果吧 3672724335789090466174544510552246482116.75，免得不想看我的罗嗦话

----------------------------------------------------------------------------------

公式 s(n) = f(n+2) - 1 （只需将数列列出前几项，就可以看出这个规律）
也就是斐波那契数列前n项的和 = 斐波那契数列第n+2项 - 1

但f(202)是很大的，直接用通项公式算一算
double n = 202;
double s5 = sqrt(5.0);
y = ( pow((1+s5)/2,n)-pow((1-s5)/2,n) )/s5;
算出 y = 7.3454486715782300e+041
再减一除以200，最终结果应当是 3.67e+039 （我们可以用这个数来验证结果对不对）

代码很简单，不贴了，还是贴一下吧

程序代码：

#include <stdio.h>
#include <math.h>

double fibonacci_approximately( unsigned n )
{
    double s5 = sqrt(5.0);
    return ( pow((1+s5)/2,n+0.0)-pow((1-s5)/2,n+0.0) )/s5;
}

void fibonacci( unsigned n, unsigned a[5] )
{
    unsigned b[5]={1};
    a[0]=0,a[1]=0,a[2]=0,a[3]=0,a[4]=0;
    while( n-- )
    {
        unsigned carry = 0;
        for( size_t i=0; i!=5; ++i )
        {
            carry += a[i] + b[i];
            a[i] = b[i];
            b[i] = carry%1000000000;
            carry /= 1000000000;
        }
    }
}

int main( void )
{
    const unsigned n = 200;
    printf( "斐波那契数列第%u项 约为 %lg\n", n+2, fibonacci_approximately(n+2) );

    unsigned r[5];
    fibonacci( n+2, r );
    printf( "斐波那契数列第%u项 等于 %u%09u%09u%09u%09u\n", n+2, r[4],r[3],r[2],r[1],r[0] );

这样就算出斐波那契数列第202项

斐波那契数列第202项约为 7.34545e+041
斐波那契数列第202项等于 734544867157818093234908902110449296423351

最终结果就是再减一除以200，得 3672724335789090466174544510552246482116.75

第 5 楼

得分:0

换个公式，s(n) = s(n-2) + s(n-1) + 1; s(-1)=0, s(0)=0

程序代码：

#include <stdio.h>

// s(n) = s(n-2) + s(n-1) + 1; s(-1)=0, s(0)=0
void fibonacci_avg( unsigned n )
{
    // 斐波那契数列前n项之和
    unsigned a[6]={0}, b[6]={0};
    for( unsigned m=0; m!=n; ++m )
    {
        unsigned carry = 1;
        for( size_t i=0; i!=6; ++i )
        {
            carry += a[i] + b[i];
            a[i] = b[i];
            b[i] = carry%10000000;
            carry /= 10000000;
        }
    }

    // 平均值
    unsigned carry = 0;
    for( size_t i=0; i!=6; ++i )
    {
        carry = carry*10000000 + b[5-i];
        a[i] = carry/n;
        carry %= n;
    }

    // 十进制输出
    printf( "%u%07u%07u%07u%07u%06u%g\n", a[0],a[1],a[2],a[3],a[4],a[5]/10,a[5]%10+carry*1.0/n );

    return;
}

int main( void )
{
    fibonacci_avg( 200 );
    return 0;
}

输出

3672724335789090466174544510552246482116.75

第 6 楼

得分:0

rjsp大神换那么萌的头像，是有喜事了吗？

唯实惟新至诚致志

第 7 楼

得分:0

谢谢，弄出来，么么哒

以下是引用rjsp在2016-3-21 11:22:19的发言：

换个公式，s(n) = s(n-2) + s(n-1) + 1; s(-1)=0, s(0)=0
#include <stdio.h>

// s(n) = s(n-2) + s(n-1) + 1; s(-1)=0, s(0)=0
void fibonacci_avg( unsigned n )
{
    // 斐波那契数列前n项之和
    unsigned a[6]={0}, b[6]={0};
    for( unsigned m=0; m!=n; ++m )
    {
        unsigned carry = 1;
        for( size_t i=0; i!=6; ++i )
        {
            carry += a + b;
            a = b;
            b = carry%10000000;
            carry /= 10000000;
        }
    }

    // 平均值
    unsigned carry = 0;
    for( size_t i=0; i!=6; ++i )
    {
        carry = carry*10000000 + b[5-i];
        a = carry/n;
        carry %= n;
    }

    // 十进制输出
    printf( "%u%07u%07u%07u%07u%06u%g\n", a[0],a[1],a[2],a[3],a[4],a[5]/10,a[5]%10+carry*1.0/n );

    return;
}

int main( void )
{
    fibonacci_avg( 200 );
    return 0;
}输出

第 8 楼

得分:0

用递归实现过，但是200数字太大了，计算机记不过来，递归也太深了。