import java.util.Scanner;
//=============================================================================
public class Fibonacci {
//-----------------------------------------------------------------------------
    private static Scanner keyboard = new Scanner(System.in);
//-----------------------------------------------------------------------------
    public static void main(String[] args) {

        int number;
        long fibonacci;

        System.out.print("What is the number : ");
        number = keyboard.nextInt();

        fibonacci = computeFibonacci1(number);
        System.out.println("1 Fibonacci(" + number + ") = " + fibonacci);

        fibonacci = computeFibonacci2(number);
        System.out.println("2 Fibonacci(" + number + ") = " + fibonacci);

        fibonacci = computeFibonacci3(number);
        System.out.println("3 Fibonacci(" + number + ") = " + fibonacci);
    }
//-----------------------------------------------------------------------------
    private static long computeFibonacci1(int number) {

        long previous,current,next;
        int index;

        previous = 0;
        current = 1;

        for (index = 1; index < number; index++) {
            next = current + previous;
            previous = current;
            current = next;
        }

        return(current);
    }
//-----------------------------------------------------------------------------
    private static long computeFibonacci2(int number) {

        FibonacciNode head;
        FibonacciNode tail;
        FibonacciNode searcher;
        int nodes;

        head = new FibonacciNode(2,1,null);
        tail = new FibonacciNode(1,1,head);
        nodes = 2;

        while (number > nodes) {
            nodes++;
            searcher = tail;
            while (searcher.getNext().getNext() != null) {
                searcher = searcher.getNext();
            }
            head = new FibonacciNode(nodes,searcher.getNumber() + 
searcher.getNext().getNumber(),null);
            searcher.getNext().setNext(head);
        }

        return(head.getNumber());
    }
//-----------------------------------------------------------------------------
    private static long computeFibonacci3(int number) {

        if (number <= 2) {
            return(1);
        } else {
            return(computeFibonacci3(number-1) +
computeFibonacci3(number - 2));
        }
    }
//-----------------------------------------------------------------------------
}
//=============================================================================
//=============================================================================
class FibonacciNode {
//-----------------------------------------------------------------------------
    private int index;
    private long number;
    private FibonacciNode next;
//-----------------------------------------------------------------------------
    public FibonacciNode(int index,long number,FibonacciNode next) {

        this.index = index;
        this.number = number;
        this.next = next;
    }
//-----------------------------------------------------------------------------
    public String toString() {

        return(Long.toString(number));
    }
//-----------------------------------------------------------------------------
    public long getNumber() {

        return(number);
    }
//-----------------------------------------------------------------------------
    public FibonacciNode getNext() {

        return(next);
    }
//-----------------------------------------------------------------------------
    public void setNext(FibonacciNode next) {

        this.next = next;
    }
//-----------------------------------------------------------------------------
}
//=============================================================================