是否有可能在恒定时间内计算isFibonacci（）？

Question

如here所述，可以创建快速的“给出第n个斐波纳契数”函数。有没有办法写一个在O（1）中执行的isFibonacci(int i)函数？

我可以预先估算价值观。但计算最后O（n），我不能为大数字做。

Answer 1

当且仅当（5 * n2 + 4）或（5 * n2 - 4）中的一个或两个是完美正方形时，数字是斐波那契。

bool isFibonacci(int n) 
{ 
    // n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both 
    // is a perferct square 
    return isPerfectSquare(5*n*n + 4) || 
           isPerfectSquare(5*n*n - 4); 
}