Fibonacci 数列有如下特点：其第 1 ， 2 项均为 1 ， 1 。从第 3 个数开始，该数是其前两个数之和 . 即 :


F1=1 (n=1)
F2=1 (n=2)
Fn=Fn-1+Fn-2 (n>=3)
请你编写一个函数 fun ，它的功能是：对于一个给定的 数（ N ）， 求不大于 N 的最大 Fibonacci 数。

输入

输入的第一行是一个正整数，表示下面有几组数据需要计算。之后的每一行是一个数据 N ，其中 1 < N <= 10的1000次方。

输出

对应输入的每一行，输出一个 不大于 N 的最大 Fibonacci 数。

简单的问题，复杂的算法，好像要字符串，可又不会用字符进行加减运算，望进来的高手指点一下算法，只要算法不要程序。

这种题有难度..我写的方法只是能算出结果..还没考虑效率..昨天就有这样的题目已经发了程序了..就在c的论坛里面

#include "stdio.h"
int main(void)
{
   int temp[1000];
   int i;
   temp[0]=1;
   for(i=1;i<1000;i++)
      temp[i]=0;
   for(i=0;i<1000;i++)
      printf("%d",temp[i]);      
   return 0;      
}

要是5的1000次方怎么办啊？（投机）

先答完 10

有快速算fib的算法
fib(n)=fx-1*fy+fx*fy+1
x+y=n
同时用二分可以增加速度

高精度乘法直接用数组模拟

复杂度是(logN)^4吧
先简单估个上下界就快了

只有有难度的问题``才能勾出高手们啊``

是啊..大家都隐藏起来了...