Overview
This problem is very similar to the original Fibonacci problem. The only difference is the definition.
The original definition of fibonacci sequence is as follows:
f(n) = f(n-1) + f(n-2)
We can easily reverse the above equation to instead of calculating next number if the sequence, calculate the previous number:
f(n-2) = f(n) - f(n-1)
Using this modified approach we can easily calculate negative Fibonacci numbers.
Example sequence of negafibonacci numbers:
−21 13 −8 5 −3 2 −1 1 0 1
Please note that because f(1) = 1, f(0) = 0, the f(-1) = 1 (positive number!) - this is in accordance with the above equation.
Knowing this, we can implement the negafibonacci sequence.
Complexity
Computational complexity of this algorithm differs between recursive and iterative solution. In case of recursive solution, because there is lots of repetition for calculating the same value, the complexity is exponential. In case of iterative approach the complexity is O(n).
Solution - iterative
//
// f(n-2) = f(n) - f(n-1)
// or in different way:
// f(n) = f(n+2) - f(n+1)
// or in different way:
// f(-n) = (-1)^(n+1) * f(n)
//
long negafib(int n)
{
long nPlus2 = 1; // f(0)
long nPlus1 = 0; // f(1)
long result = 1;
// error condition
if (n > 0) return -1;
// base values
if (n == 0) return 0;
// this starts usually from 2
for (int i = -1; i >= n; i--)
{
result = nPlus2 - nPlus1;
nPlus2 = nPlus1;
nPlus1 = result;
}
return result;
}
External Resources