true

Learn Advanced Java coaching from the Best Tutors

• Affordable fees
• 1-1 or Group class
• Flexible Timings
• Verified Tutors

Search in

# Simple Algorithms - Fibonacci, Finding GCD & Finding LCM.

Paras Chawla
29/05/2017 0 0

import java.util.Scanner;

//0,1,1,2,3,5,8,13,21,34...

//fun(n)=fun(n-1)+fun(n-2) where n>=2

/*fib(9)=fib(8)+fib(7)

=fib(7)+fib(6)+fib(6)+fib(5)

=fib(6)+fib(5)+fib(5)+fib(4)+fib(5)+fib(4)+fib(4)+fib(3)

*/

public class FibonacciNumberFast {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

long fno=fibonacciNumber(n);

System.out.println(fno);

}

public  static long fibonacciNumber(int n){

int array[]= new int[n+1];

array[0]=0;

if(n==0)

return array[0];

array[1]=1;

for(int i=2;i<=n;i++)

array[i]=array[i-1]+array[i-2];

return array[n];

}

}

Algorithm 2– Finding GCD of a number

1) GCD using Recursion

2) GCD using naïve approach

import java.util.Scanner;

// Largest number which divides both a and b

public class GCDNaive {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

long a = scanner.nextLong();

long b = scanner.nextLong();

//long gcd = gcd(a, b);

//System.out.println("Result from GCD Naive "+gcd);

gcdFast(a, b);

}

static void gcdFast(long a, long b) {

if (b == 0) {

System.out.println(a);

System.exit(0);

}

long rem=a%b;

gcdFast(b, rem);

}

/*   static long gcd(long a, long b) {

long best = 0;

for (long i = 1; i <= a + b; i++) {

if ((a%i ==0) && (b%i== 0))

best = i;

}

return best;

}

*/}

Algorithm 3 – Finding LCM of a number

import java.util.Scanner;

// GCD(a,b)*LCM(a,b)=a*b

public class LCM {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

long a = scanner.nextLong(); // 8

long b = scanner.nextLong(); // 6

// long c = gcd(a, b);

// System.out.println("GCD is" + c);

long c = gcdFast(a, b);

long d = (a * b) / c;

System.out.println(d);

}

static long gcdFast(long a, long b) {

if (b == 0) {

return a;

}

long rem = a % b;

long c=gcdFast(b, rem);

return c;

}

/*   static long gcd(long a, long b) {

long best = 0;

for (long i = 1; i <= a + b; i++) {

if ((a % i == 0) && (b % i == 0))

best = i;

}

return best;

}*/

}

0 Dislike

## Other Lessons for You

Volume and Surface Forces
Generally speaking, fluids are acted upon by two distinct types of force. The first type is long range in nature—that is, such that it decreases relatively slowly with increasing Mathematical Models...

OOPS: Polymorphism
Polymorphism:Polymorphism (from the Greek meaning "having multiple forms") is the characteristic of being able to assign a different meaning or usage to something in different contexts - specifically,...

Resistor Labels
• Wire-wound resistors have a label indicating resistance and power ratings. • A majority of resistors have color bars to indicate their resistance magnitude. • There are usually 4 to...

Language of mathematics (IMP Tip for Engineering Students)
From childhood we are often asked which is our favourite subject. We, without batting an eyelid would say the subject which we aced which most likely is MATHS. Because the examiner has least bit of chance...

Venu Gopal

To solve any mathematical problem follow the steps as stated below. Read the problem clearly to identify the information provided and the part to be solved. Represent the data or information you read...

### Looking for Advanced Java coaching ?

Learn from Best Tutors on UrbanPro.

Are you a Tutor or Training Institute?

Join UrbanPro Today to find students near you
X

### Looking for Advanced Java coaching Classes?

The best tutors for Advanced Java coaching Classes are on UrbanPro

• Select the best Tutor
• Book & Attend a Free Demo
• Pay and start Learning

### Learn Advanced Java coaching with the Best Tutors

The best Tutors for Advanced Java coaching Classes are on UrbanPro