Fibonacci Number

The Fibonacci numbers are defined as follows:
F0 = 0,F1 = 1, and Fi = Fi-1 + F i-2  for i >= 2.

1) Efficient code for computing Fibonacci Number:
import java.util.Scanner;
public class Fib {
        
        //This will calculate slower
	private static long calc_fib(long n) {
		if (n <= 1)
		return n;
		else
		return calc_fib(n - 1) + calc_fib(n - 2);
	}
	
        //This will calculate faster 
	private static long fast_fib(int n){
		if(n <=1)
			return n;
		else {
			int[] arr = new int[n+1];
			arr[0] = 0;
			arr[1] = 1;
			int i;
			for(i = 2;i<=n;i++){
				arr[i] = arr[i-1] + arr[i-2];
			}
			return arr[n];
		}
	}

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		
		System.out.println(fast_fib(n));
	}
}


2) Show last digit of large Fibonacci Number:
//Last digit of a Fibonacci number is sum of last two Fibonacci numbers last digit!!!! private static int getFibonacciLastDigit(int n) { if(n <= 1) return n; else { int[] arr = new int[n+1]; arr[0] = 0; arr[1] = 1; int i; int sum = 0; for(i = 2;i<=n;i++){ sum = arr[i-1] + arr[i-2]; arr[i] = sum % 10; } return arr[n]; } }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s