Finding The Fibonacci Number(logn)

#include <stdio.h>

int buf[1000] = {0, 1, 1};

typedef struct
{
    int a;
    int b;
}intPair;

intPair devideIndex(int index)
{
    intPair temp;
    if (index & 1)
    {
        temp.a = index / 2;
        temp.b = index / 2 + 1;
        return temp;
    }
    else
    {
        temp.a = index / 2;
        temp.b = index / 2;
        return temp;
    }
}

int Fibonacci(int n)
{
    intPair p;
    if (buf[n])
        return buf[n];
    p = devideIndex(n);
    return buf[n] = Fibonacci(p.a) * Fibonacci(p.b - 1) + Fibonacci(p.a + 1) * Fibonacci(p.b);
}

int main()
{
    int i;
    for (i = 1; i <= 20; ++i)
        printf("%d\n", Fibonacci(i));
    system("pause");
    return 0;
}

以上

没人理我诶

这个是用斐波纳契数列的另一个公式a[m+n] = a[m] * a[n-1] + a[m+1] * a[n]计算的，每次尽量分出接近的m和n就可以做到近似的二分计算

可惜int能表示的范围太小

帮顶

话说对数学问题感兴趣的人少啊…�

//输出数列
#include <stdio.h>
int main()
{
unsigned int n;
unsigned __int64 a=0, b=1;
for (scanf("%u", &n); n; n--) printf("%I64u ", a+=b^=a^=b^=a);
return 0;
}

只是为了简洁…�

学到公式a[m+n] = a[m] * a[n-1] + a[m+1] * a[n]了，也算有了收获

如果只需要第n个的话，你这个是O(n)，我这个是O(nlogn)，还是有差别的

如果需要简洁的交换的话我宁愿写一个swap函数…�

//这个公式不错，这下可以改进速度了

#include <stdio.h>

unsigned __int64 fibonacci(unsigned short n)
{
unsigned short a, b;
if (n<3) return 1;
a=n>>1;
b=(n>>1)+(n&1);
return fibonacci(a)*fibonacci(b-1) + fibonacci(a+1)*fibonacci(b);
}

int main(void)
{
unsigned short n;
while (scanf("%hu", &n))
printf("%I64u\n", fibonacci(n));
return 0;
}

你试一下速度吧，笑

那个数组可不是多余的

//我知道，让递归的另一分支能享用到第一支计算的结果，虽然为你的“笑”愤怒，但不可否认确实是个好方法

#include <stdio.h>

unsigned __int64 fib[200]={0, 1, 1};

unsigned __int64 fibonacci(unsigned short n)
{
unsigned short a, b;
if (fib[n]) return fib[n];
b = (a=n>>1) + (n&1);
return fibonacci(a)*fibonacci(b-1) + fibonacci(a+1)*fibonacci(b);
}

int main(void)
{
unsigned short n;
while (scanf("%hu", &n))
printf("%I64u\n", fibonacci(n));
return 0;
}

//我知道，让递归的另一分支能享用到第一支计算的结果，虽然为你的“笑”愤怒，但不可否认确实是个好方法

#include <stdio.h>

unsigned __int64 fib[200]={0, 1, 1};

unsigned __int64 fibonacci(unsigned short n)
{
unsigned short a, b;
if (fib[n]) return fib[n];
b = (a=n>>1) + (n&1);
return fib[n]=fibonacci(a)*fibonacci(b-1) + fibonacci(a+1)*fibonacci(b);
}

int main(void)
{
unsigned short n;
while (scanf("%hu", &n))
printf("%I64u\n", fibonacci(n));
return 0;
}

的确不错，又发现了更好的计算方法

路过...

一起研究研�

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

1 2 下一页尾页
28回复贴，共2页
，跳到页

<<返回c语言吧

分享到:

日	一	二	三	四	五	六