Tower of Hanoi implementation in java

The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower  and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a canonical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2ⁿ − 1, where n is the number of disks.

Recursive Algorithm

The recursive solution to move n discs from the start pole to the end pole using an auxiliary pole is given below.

Base Case – When n = 1
Move the disc from start pole to end pole
Recursive Case – When n > 1
Step 1: Move (n-1) discs from start pole to auxiliary pole.
Step 2: Move the last disc from start pole to end pole.
Step 3: Move the (n-1) discs from auxiliary pole to end pole.
Steps 1 and 3 are recursive invocations of the same procedure.

Java Program

The recursive program for the puzzle in Java is given below:

<pre>import java.util.Scanner;

/**
 * java program to implement tower of hanoi
 * Created by sani kamal on 07-May-17.
 */
public class TowerOfHanoi {
    //main function
    public static void main(String[] args) {
        System.out.println("Enter number of disc:");
        Scanner sc = new Scanner(System.in);
        int numberOfDiscs = sc.nextInt();
        moveDiscs(numberOfDiscs, "A", "B", "C");


    }

    public static void moveDiscs(int n, String start, String middle, String end) {
        //Moved n-th disc to the end pole
        if (n == 1) {
            System.out.println("Move " + n + " disc from " + start + " to " + end);
        } else {
            //Move n-1 discs from start pole to the midle
            moveDiscs(n - 1, start, end, middle);
            System.out.println("Move " + n + " disc from " + start + " to " + end);
            //Move n-1 discs from middle pole to the end
            moveDiscs(n - 1, middle, start, end);

        }

    }
}</pre>

Java Program to Implement Euclid GCD Algorithm using Recursion

The Euclidean algorithm calculates the greatest common divisor (GCD) of two number a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. Synonyms for the GCD include the greatest common factor (GCF), the highest common factor (HCF), the highest common divisor (HCD), and the greatest common measure (GCM).

The Algorithm

The Euclidean Algorithm for finding GCD(A,B) is as follows:

• If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.
• If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.
• Write A in quotient remainder form (A = B⋅Q + R)
• Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)

           // Function to return gcd of a and b

        int gcd(int a, int b)

          {

             if (a == 0)

                 return b;

             return gcd(b%a, a);

           }

This is a program to find GCD (Greatest Common Divisor) of two numbers using Euclid’s Algorithm.

<pre>import java.util.Scanner;

/**
 * Java Program to Implement Euclid GCD Algorithm using Recursion
 * Created by sani kamal on 07-May-17.
 */
public class GCDEuclid {
    //main function
    public static void main(String[] args) {
        GCDEuclid gcdeu = new GCDEuclid();
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number1:");
        int num1 = sc.nextInt();
        System.out.println("Enter number2:");
        int num2 = sc.nextInt();
        System.out.println("GCD of " + num1 + " and " + num2 + " is:" + gcdeu.gcd(num1, num2));


    }

    // This function calculate GCD
    private int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);

    }
}</pre>

The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

"C:\Program Files\Java\jdk1.8.0_65\bin\java" -Didea.launcher.port=7536 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.1.3\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_65\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\rt.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\out\production\JavaByExample;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\laf-plugin-7.2.1.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\laf-widget-6.3.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\substance-7.2.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\trident.jar.zip;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\xmlbeans-2.6.0.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\poi-ooxml-schemas-3.14-20160307.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\poi-ooxml-3.14-20160307.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\poi-3.14-20160307.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\mail.jar;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.1.3\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain com.muktangon.net.recursion.GCDEuclid
Enter number1:
5
Enter number2:
25
GCD of 5 and 25 is:5

Process finished with exit code 0

java program to find n-th fibonacci number using recursion

The Fibonacci numbers are the numbers in the following integer sequence called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:

The fibonacci series is defined as follows:

0,1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , …

Recursive Algorithm for Fibonacci Numbers

Algorithm F(n)

if n ≤ 1 then return n

else return F(n-1) + F(n-2)

 

Full java program is given below:

<pre>import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * java program to find n-th fibonacci number using recursion
 * Created by sani kamal on 07-May-17.
 */
public class Fibonacci {
    public static void main(String[] args) {
        Fibonacci fib = new Fibonacci();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            System.out.println("Enter a number:");
            int num = Integer.parseInt(br.readLine());
            System.out.print(num+"th Fibonacci number is:" + fib.fibonacci(num));

        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }

    }

    private int fibonacci(int n) {
        if (n < 1)
            return 0;
        else if (n == 1)
            return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}</pre>

Java program to find factorial of given number using recursion

Recursion  is a method where the solution to a problem depends on solutions to smaller instances of the same problem.One of the classic problems for introducing recursion is calculating the factorial of an integer. The factorial of any given integer — call it n  — is the product of all the integers from 1 to n. Thus, the factorial of 7 is 5040:7x6x 5 x 4 x 3 x 2 x 1.

Here’s the recursive version of the factorial method:

public static int factorial(int n)
{
    if (n <= 1)
        return 1;
    else
        return n * factorial(n-1);
}

<pre>import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * java program to find factorial using recursion
 * Created by sani kamal on 07-May-17.
 */

public class Factorial {
    public static void main(String[] args) {
        Factorial fl = new Factorial();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            System.out.println("Enter number to find factorial(less than 20):");
            int n=Integer.parseInt(br.readLine());
            System.out.println("Factorial of "+n+" is:" + fl.factorial(n));
        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }
    }

    public int factorial(int num) {
        if (num <= 1) {
            return 1;
        }
        return num * factorial(num - 1);
    }
}</pre>

Java program to print Fibonacci sequence using array

This java program will print fibonacci sequence up to given number.

if input is 5 then the program print 0 1 1 2 3

<pre>import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * java program to print fibonacci sequence
 * Created by Sani Kamal on 05-May-17.
 */
public class FibonacciSequence {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            System.out.println("Enter the number of item to be printed: :");
            int num = Integer.parseInt(br.readLine());
            num = num > 2 ? num : 2;
            int[] fibArray = new int[num];
            fibArray[0] = 0;
            fibArray[1] = 1;
            for (int i = 2; i < num; i++) {
                fibArray[i] = fibArray[i - 1] + fibArray[i - 2];

            }
            System.out.println("Fibonacci Sequence..");
            for (int i = 0; i < num; i++) {
                System.out.print(fibArray[i]+" ");

            }


        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }
    }
}</pre>

Java program to find 2nd largest and 2nd smallest number in a given array

<pre>import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * java program to find the largest,2nd largest,smallest and
 * 2nd smallest numbers in a given array
 * Created by Sani Kamal on 05-May-17.
 */
public class FindLargest {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            System.out.println("Enter size of array:");
            int num = Integer.parseInt(br.readLine());
            int[] numbers = new int[num];
            for (int i = 0; i < num; i++) {
                numbers[i] = (int) (Math.random() * 125);

            }
            //print all the numbers in  array
            System.out.println("Array Elements:");
            for (int i = 0; i < num; i++) {
                System.out.print(numbers[i] + " ");
            }
            System.out.println();
            //sort array
            Arrays.sort(numbers);
            System.out.println("Sorted array:");
            for (int number : numbers) {
                System.out.print(number + " ");
            }
            System.out.println();
            System.out.println("Largest element in array:" + numbers[num- 1]);
            System.out.println("2nd largest element in array:" + numbers[num - 2]);
            System.out.println("smallest element in array:" + numbers[0]);
            System.out.println("2nd smallest element in array:" + numbers[1]);

        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }
    }
}</pre>

Print Floyd’s Triangle in java

In this tutorial we will take a quick look at the Floyd’s triangle using the java language. The Floyd’s triangle (named after Robert Floyd) algorithm is a right-angled triangular array of natural numbers. It is defined by filling the rows of the triangle with consecutive numbers, starting with the number one in the top left corner.

e.g: print floyds triangle for input 4

1

2        3

4          5          6

7           8          9      10

 

</pre>
<pre>
import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
* Java program to print floyd's triangle
* Created by SANI KAMAL on 05-May-17.
*/
public class FloydsTriangle {
public static void main(String[] args) {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
try {
System.out.println("Enter of rows of Floyd's Triangle:");
int num=Integer.parseInt(br.readLine());
int number=1;
for (int i = 0; i <num ; i++) {
for (int j = 0; j <=i ; j++) {
System.out.print(number+" ");
number++;

}
System.out.println();

}

}catch (Exception e){
System.out.println(e.getMessage());
e.printStackTrace();
}

}
}

Java program to print prime number

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * java program to print prime number
 * Created by SANIKAMAL on 04-May-17.
 */
//java program to print prime number
public class PrimeNumberPrinter {
    public static void main(String[] args) {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        try {
            System.out.println("Enter a number:");
            int num = Integer.parseInt(br.readLine());
            System.out.println("Primes Numbers..");
            for (int count = 2, primeCount = 0; primeCount < num; count++) {
                if (checkPrime(count)) {
                    System.out.println(count);
                    primeCount++;
                }
            }


        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }
    }

    private static boolean checkPrime(int number) {
        boolean isPrime = true;
        if (number == 2) {
            isPrime = true;
        } else if (number % 2 == 0) {
            isPrime = false;
        } else {
            int maxCount = (int) Math.ceil(Math.sqrt(number));
            for (int count = 3; count <= maxCount; count = count + 2) {
                if (number % count == 0) {
                    isPrime = false;
                    break;
                }
            }

        }

        return isPrime;
    }
}

Java program to calculate sum of digits of a number

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * java program to calculate sum of digits of a number
 * Created by SANI KAMAL on 05-May-17.
 */
// eg: 136 sum of digits is 1+3+6=10
public class DigitsSummation {
    public static void main(String[] args) {
        System.out.println("Enter a number:");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int num = Integer.parseInt(br.readLine());
            // Remember num/10 reduces one digit from number
            // and num%10 gives you last digit
            int tempNum = num, sum = 0;
            while (tempNum >= 1) {
                sum = sum + tempNum % 10;
                tempNum = tempNum / 10;
            }
            System.out.println("Number:" + num + " Sum of digits:" + sum);
        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }

    }
}

Java program to find number of days in a month

import java.io.BufferedReader;
import java.io.InputStreamReader;


public class daysFinder {
    public static void main(String[] args) {

        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String input;
        try {
            System.out.println("Enter Year: ");
            input = br.readLine();
            int year = Integer.parseInt(input);
            System.out.println("Enter numeric month: ");
            input = br.readLine();
            int month = Integer.parseInt(input);
            int numberOfDays;
            switch (month) {
                case 1:
                case 3:
                case 5:
                case 7:
                case 8:
                case 10:
                case 12:
                    numberOfDays = 31;
                    System.out.println("Month " + month + "  Number of Days: " + numberOfDays);
                    break;
                case 4:
                case 6:
                case 9:
                case 11:
                    numberOfDays = 30;
                    System.out.println("Month " + month + "  Number of Days: " + numberOfDays);
                    break;
                case 2:
                    if ((year % 400 == 0)
                            || (year % 4 == 0 && year % 100 != 0)) {
                        numberOfDays = 29;
                    } else {
                        numberOfDays = 28;
                    }
                    System.out.println("Month " + month + "  Number of Days: " + numberOfDays);
                    break;
                default:
                    System.out.println("Invalid Month ");
            }

        } catch (Exception ex) {
            System.out.println(ex.getMessage());
            ex.printStackTrace();
        }
    }
}