What I am not understanding: How the code is able to generate all the Fibonacci series using just one variable?
#include <stdio.h>
#include <stdlib.h>
int main (void) {
unsigned long i = 1;
printf ("0\n");
while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) {
printf ("%d\n", i & 0xffff);
i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff));
}
return 0;
}
I don't see why this is hard?
Written in C, demonstrated on IDEOne:
#include <stdio.h>
int fib(int n)
{
return (n == 0 || n == 1) ? n : fib(n-1) + fib(n-2);
}
int main(void) {
int n;
for(n=0; n<10; ++n)
printf("[%d] : %d\n", n, fib(n));
return 0;
}
I only see 1 variable.
Does that not meet your requirement?
Output
[0] : 0
[1] : 1
[2] : 1
[3] : 2
[4] : 3
[5] : 5
[6] : 8
[7] : 13
[8] : 21
[9] : 34
If you want to be tricky, use the wonderful expression n==!!n?n:
int fib(int n)
{
return n==!!n?n: fib(n-1) + fib(n-2);
}
I saw the answer here: Fibonacci using 1 variable
as suggested by one of the answers. Although the closed form solution is generally hard to come by unless you know how to solve Difference equations and solve the fibonacci recurrance
Fn = Fn-1 + Fn-2
I think the better way is the linear algebra.
The proof can be done easily by induction. Also the matrix multiplication will take O(lgn).
User contributions licensed under CC BY-SA 3.0