关于fibonacci数列的一道题

kakawei 发布于 2007-11-11 17:37， 946 次点击

各位帮忙看一下，下面这个程序有逻辑错误吗？
f（n）是fibonacci数列，当输入一个数x，且f（n）〈x〈f（n+1）时，输出n
否则输出-1。
但是当我输入3，5，7。。。这些属于该数列的数时，本应该输出-1，但是结果并不是
#include<iostream>
#include<cmath>
using namespace std;
double fib(unsigned long);
int main()
{
for(int i=1;;i++)
{
unsigned long num;
cin>>num;
if(num>=1&&num<=pow(2.,31))
{
for(unsigned long j=0;;j++)
{
if(fib(j+1)<=num)
continue;
else if(fib(j+1)>num&&fib(j)<num)
{cout<<j<<endl;break;}
else if(fib(j)>=num)
{cout<<-1<<endl;break;}
}
}
}
system("pause");
}
double fib(unsigned long number)
{
return (pow((1+sqrt(5.))/2.,static_cast<double>(number+1))-pow((1-sqrt(5.))/2.,static_cast<double>(number+1)))/sqrt(5.);
}

10 回复

jonc2007-11-12 14:54

#include<iostream>
#include<cmath>
using namespace std;
int fib(int);
int main()
{
for(int i=1;;i++)
{

int num;
cin>>num;
// cout<<fib(num);
if(num>=1&&num<=pow(2,31))
{
for(int j=0;;j++)
{
if(fib(j+1)<=num)
continue;
else if(fib(j)<num)
{
cout<<j+1<<endl;
break;
}
else if(fib(j)>=num)
{
cout<<-1<<endl;
break;
}
}
}
return 0;
}
system("pause");
}
int fib(int number)
{
if((number==0)||(number==1))
return 1;
else
return fib(number-1)+fib(number-2);
}

kakawei2007-11-12 15:59

递归我会啊，但我想用迭代，帮忙再看看吧

nuciewth2007-11-12 16:10

t=a;
a=b
b=t+b;

kakawei2007-11-12 23:31

看不明白能不能说详细一点，我想要迭代，而且通项我已经写出来了，就是程序有点问题。

nuciewth2007-11-12 23:47

我写的就是迭代啊.

while(num>t)
{
t=a;
a=b
b=t+b;
n++;
}

HJin2007-11-13 09:56

you can use binary search --- f_n is increasing (and thus ordered).

Using the matrix multiplication technique to calculate f_n in O(lgn) time and then use binary search to search for x

Total time should be O(lgn).

kakawei2007-11-14 10:30

6楼的强人：
while(num>t)
{
t=a;
a=b
b=t+b;
n++;
}
t,a,b,n都代表什么啊？说清楚点啊！

nuciewth2007-11-14 11:32

f（n）是fibonacci数列，当输入一个数x，且f（n）〈x〈f（n+1）时，输出n

while(num>t)//t=f(n),num=x,b=f(n)
{
t=a;
a=b
b=t+b;
n++;
}//循环结束时n就是你要的结果

这就是迭代.

#10

kakawei2007-11-14 21:01

如果输入一个num=f（n）的，你的迭代得出的n就不满足f（n）〈x〈f（n+1），
而且b放在这里有什么用啊？

#11

nuciewth2007-11-14 21:03

以下是引用kakawei在2007-11-14 21:01:19的发言：
如果输入一个num=f（n）的，你的迭代得出的n就不满足f（n）〈x〈f（n+1），

如果是这种情况,你说该输出什么?

而且b放在这里有什么用啊？

f(n)=f(n-1)+f(n-2)
b + a