CareerCup

Matrix m = new Matrix(new row(1,1), new row(1,0));

Matrix FibN = m.power(n);

return FibN.Row(1).Column(1)


// Assume some implementation of Matrix...
// m = [1 1]
// [1 0]
//

package com.badal.careercup;

import java.util.ArrayList;

public class Fibonacci {

private ArrayList<Integer> generateFibonacci (int n){
ArrayList<Integer> fib=new ArrayList<Integer>();
fib.add(0);
fib.add(1);
for(int i=2;i<n;i++){

fib.add(fib.get(i-1)+fib.get(i-2));

}
return fib;
}

public static void main(String[] args){
Fibonacci f=new Fibonacci();
System.out.println(f.generateFibonacci(13));

}

}

int fib(int f) {
if ( f = 1 || f == 2 ) return 1;
else return (fib(f-2)+(f-1));
}

int fib(int f) {
if ( f == 1 || f == 2 ) return 1;
else return ( fib(f-2)+fib(f-1) );
}

This is O(log n) time algorithm.

int Fibonacci(int f)
{
int n = 1;
int nminus = 0;
for (int i = 0; i <= f - 2; i++)
{
int nhold = nminus;
nminus = n;
n = n + nhold;
}
return n;
}

Recursion is nice and all but will quickly bog down with large f numbers...

for the sequence simply change the return type and do a list...

IEnumerable<int> Fib(int f)
{
int n = 1;
int nminus = 0;
for (int i = 0; i <= f - 2; i++)
{
int nhold = nminus;
nminus = n;
n = n + nhold;
yield return n;
}
}

Here's Python:

def fib():
    a0,a1 = 0,1
    while 1:
        yield a0
        a0,a1 = a1,a0+a1

fibber = fib()
print(next(fibber)) # 0
print(next(fibber)) # 1
print(next(fibber)) # 1
print(next(fibber)) # 2
# and so on as many times as you like

class Fabonacci
{
public static void main( String [] args)
{
int a = 0;
int b = 1;
System.out.print(" " + a +" ");
System.out.print(" " + b +" ");
for (int i=0;i <=10; i++)
{
int c = a+b;
System.out.print(" " + c +" ");
b=c;
a=b-a;
}
}
}

Fibonacci series is based on the distribution of chloroplasts. When they divide, they are of opposite charge. The same in java can be done as below. The benefit of the following code is that it doesnt require additional sysouts.

class Fibo {
	public static void main(String[] args) {
		int a = -1, b = 1, c = 0;
		for(int count=0; count < 10; count++) {
			c = a + b;
			System.out.println(c);
			a = b;
			b = c;
		}
	}
}