Bubble Sort method in java

this is the program to sort the given numbers in a accenting or decanting order

import java.util.*;

public class sorting
{
    int table[]=new int[5];
    public static void main(String arg[])
    {   
        sorting m=new sorting();
        m.readArray();
        m.bubbleSort();
        m.print();
    }
        void bubbleSort()
        {
            for(int i=1;i<=4;i++)
            {
                for(int j=0;j<=(4-i);j++)
                {   
                    if(table[j]>table[j+1])
                    swap(j,j+1);   
                }
            }
        }
       
        void print()
        {
                System.out.print("sorted list of your numbers:");
            for(int i=0;i<=4;i++)
                {
                System.out.print(" "+table[i]);
                }
        }
       
        void readArray()
        {   
            for(int i=0;i<=4;i++)
            {
                Scanner n=new Scanner(System.in);
                System.out.println("enter your number    "+(i+1));
                table[i]=n.nextInt();
            }
        }
           
        void swap(int x,int y)
        {
            int m=table[x];
            table[x]=table[y];
            table[y]= m;   
        }   
}   

Bubble Sort method in java

this is the program to sort the given numbers in a accenting or decanting order

GCD (Greater common Divider ) in Java

this programe to find the greatest common divider when we enter two integer numbers

import java.util.*;
public class gcd
{
    public static void main(String arg[])
    {
    Scanner input = new Scanner(System.in);
        System.out.println("Enter your number 1");
        int n1 = input.nextInt();
        System.out.println("Enter your number 2");
        int n2 = input.nextInt();
    gcd m=new gcd();
    m.check(n1,n2);
    }
   
    void check(int n1,int n2)
    {
        for(int i=2;i<n1;i++)
        {
            if(n1%i==0&& n2%i==0)
            {
            System.out.println("GCD="+i);break;
            }
        }
    }
}

GCD (Greater common Divider ) in Java

this programe to find the greatest common divider when we enter two integer numbers

Hash table with separate chaining

import java.io.IOException;

class Link {
  private int data;
  public Link next;

  public Link(int d) {
    data = d;
  }

  public int getKey() {
    return data;
  }

  public void displayLink() {
    System.out.print(data + " ");
  }
}

class SortedList {
  private Link first;
  public SortedList() {
    first = null;
  }

  public void insert(Link theLink){
    int key = theLink.getKey();
    Link previous = null; // start at first
    Link current = first;
    // until end of list,
        //or current bigger than key,
    while (current != null && key > current.getKey()) { 
      previous = current;
      current = current.next; // go to next item
    }
    if (previous == null) // if beginning of list,
      first = theLink; 
    else
      // not at beginning,
      previous.next = theLink; 
    theLink.next = current; 
  }

  public void delete(int key){ 
    Link previous = null; 
    Link current = first;

    while (current != null && key != current.getKey()) { 
      previous = current;
      current = current.next; 
    }
    // disconnect link
    if (previous == null) //   if beginning of list delete first link
      first = first.next;       
    else
      //   not at beginning
      previous.next = current.next; //delete current link
  }

  public Link find(int key) {
    Link current = first; 
    while (current != null && current.getKey() <= key) { // or key too small,
      if (current.getKey() == key) // found, return link
        return current;  
      current = current.next; // go to next item
    }
    return null; // cannot find it
  }

  public void displayList() {
    System.out.print("List: ");
    Link current = first;
    while (current != null){
      current.displayLink(); 
      current = current.next;
    }
    System.out.println("");
  }
}

public class HashChain {
  private SortedList[] hashArray; 

  private int arraySize;

  public HashChain(int size) {
    arraySize = size;
    hashArray = new SortedList[arraySize];
    for (int i = 0; i < arraySize; i++)
      hashArray[i] = new SortedList(); 
  }

  public void displayTable() {
    for (int j = 0; j < arraySize; j++) {
      System.out.print(j + ". "); 
      hashArray[j].displayList(); 
    }
  }

  public int hashFunc(int key) {
    return key % arraySize;
  }

  public void insert(Link theLink) {
    int key = theLink.getKey();
    int hashVal = hashFunc(key); 
    hashArray[hashVal].insert(theLink); 
  }

  public void delete(int key) {
    int hashVal = hashFunc(key); // hash the key
    hashArray[hashVal].delete(key); 
  }

  public Link find(int key) {
    int hashVal = hashFunc(key); // hash the key
    Link theLink = hashArray[hashVal].find(key); // get link
    return theLink;
  }

  public static void main(String[] args) throws IOException {
    int aKey;
    Link dataItem;
    int size, initSize, keysPerCell = 100;
    size = 20;
    initSize = 10;
    HashChain hashTable = new HashChain(size);

    for (int i = 0; i < initSize; i++){
      aKey = (int) (java.lang.Math.random() * keysPerCell * size);
      dataItem = new Link(aKey);
      hashTable.insert(dataItem);
    }
    hashTable.displayTable();
    aKey = 100;
    dataItem = new Link(aKey);
    hashTable.insert(dataItem);
    aKey = 100;
    hashTable.delete(aKey);

    aKey = 50;
    dataItem = hashTable.find(aKey);
    if (dataItem != null)
      System.out.println("Found " + aKey);
    else
      System.out.println("Could not find " + aKey);
  }

}

OUTPUT

0. List:
1. List:
2. List:
3. List: 1483
4. List: 204
5. List: 445 605
6. List: 1686
7. List:
8. List: 1748
9. List: 229
10. List:
11. List:
12. List:
13. List:
14. List:
15. List: 635
16. List:
17. List:
18. List: 1218
19. List: 379

Hash table with separate chaining

import java.io.IOException;

class Link {
  private int data;
  public Link next;

  public Link(int d) {
    data = d;
  }

  public int getKey() {
    return data;
  }

  public void displayLink() {
    System.out.print(data + " ");
  }
}

class SortedList {
  private Link first;
  public SortedList() {
    first = null;
  }

  public void insert(Link theLink){
    int key = theLink.getKey();
    Link previous = null; // start at first
    Link current = first;
    // until end of list,
        //or current bigger than key,
    while (current != null && key > current.getKey()) { 
      previous = current;
      current = current.next; // go to next item
    }
    if (previous == null) // if beginning of list,
      first = theLink; 
    else
      // not at beginning,
      previous.next = theLink; 
    theLink.next = current; 
  }

  public void delete(int key){ 
    Link previous = null; 
    Link current = first;

    while (current != null && key != current.getKey()) { 
      previous = current;
      current = current.next; 
    }
    // disconnect link
    if (previous == null) //   if beginning of list delete first link
      first = first.next;       
    else
      //   not at beginning
      previous.next = current.next; //delete current link
  }

  public Link find(int key) {
    Link current = first; 
    while (current != null && current.getKey() <= key) { // or key too small,
      if (current.getKey() == key) // found, return link
        return current;  
      current = current.next; // go to next item
    }
    return null; // cannot find it
  }

  public void displayList() {
    System.out.print("List: ");
    Link current = first;
    while (current != null){
      current.displayLink(); 
      current = current.next;
    }
    System.out.println("");
  }
}

public class HashChain {
  private SortedList[] hashArray; 

  private int arraySize;

  public HashChain(int size) {
    arraySize = size;
    hashArray = new SortedList[arraySize];
    for (int i = 0; i < arraySize; i++)
      hashArray[i] = new SortedList(); 
  }

  public void displayTable() {
    for (int j = 0; j < arraySize; j++) {
      System.out.print(j + ". "); 
      hashArray[j].displayList(); 
    }
  }

  public int hashFunc(int key) {
    return key % arraySize;
  }

  public void insert(Link theLink) {
    int key = theLink.getKey();
    int hashVal = hashFunc(key); 
    hashArray[hashVal].insert(theLink); 
  }

  public void delete(int key) {
    int hashVal = hashFunc(key); // hash the key
    hashArray[hashVal].delete(key); 
  }

  public Link find(int key) {
    int hashVal = hashFunc(key); // hash the key
    Link theLink = hashArray[hashVal].find(key); // get link
    return theLink;
  }

  public static void main(String[] args) throws IOException {
    int aKey;
    Link dataItem;
    int size, initSize, keysPerCell = 100;
    size = 20;
    initSize = 10;
    HashChain hashTable = new HashChain(size);

    for (int i = 0; i < initSize; i++){
      aKey = (int) (java.lang.Math.random() * keysPerCell * size);
      dataItem = new Link(aKey);
      hashTable.insert(dataItem);
    }
    hashTable.displayTable();
    aKey = 100;
    dataItem = new Link(aKey);
    hashTable.insert(dataItem);
    aKey = 100;
    hashTable.delete(aKey);

    aKey = 50;
    dataItem = hashTable.find(aKey);
    if (dataItem != null)
      System.out.println("Found " + aKey);
    else
      System.out.println("Could not find " + aKey);
  }

}

OUTPUT

0. List:
1. List:
2. List:
3. List: 1483
4. List: 204
5. List: 445 605
6. List: 1686
7. List:
8. List: 1748
9. List: 229
10. List:
11. List:
12. List:
13. List:
14. List:
15. List: 635
16. List:
17. List:
18. List: 1218
19. List: 379

Hash table drill program

import java.util.Random;
import java.io.*;
import java.util.Scanner;

public class HashDrill
{  // Selection the hash function for int hash()
   static private int   option = 0;

   static private boolean[] displaced;

   // Seeded in main, used in fillTable
   static Random generator = new Random();

   static Scanner console = new Scanner(System.in);

// Hash function, based on the selection option
   private static int hash ( int value, int size )
   {  int d1 = Math.abs(value),
          d0 = d1 % 10;
      int key = d1 % size;   // Used for single-digit value

      // More than one digit; isolate d1 and compute.
      if ( d1 != d0 )
      {  while ( d1 > 9 )
            d1 /= 10;
         if ( option == 0 )
            key = (d1*10 + d0) % size;
         else
            key = (d1 * d0) % size;
      }
      return key;
   }

   // Fill table[], val[] and key[]
   private static void fillTable ( int[] table, int[] val, int[] key )
   {  int j, k,
          size = table.length;

      // Initialize the table to empty (-1 throughout)
      for ( j = 0; j < size; j++ )
         table[j] = -1;

      // Generate the values, then place them into the table
      for ( j = 0; j < val.length; j++ )
      {  k = generator.nextInt(4) + 1;
         val[j] = generator.nextInt((int)Math.pow(10,k));
         k = hash(val[j], size);
         key[j] = k;

         // Linear probe for an available cell
         while ( table[k] != -1 )
            k = (k+1) % size;
         // Position the value into the table
         table[k] = val[j];
         displaced[k] = k != hash(val[j], size);
      }
   }

   // Display table[], val[] and key[]
   private static void showTable ( int[] table, int[] val, int[] key )
   {  int j;

      System.out.println ("\nd1 is the leading digit, d0 the trailing." +
         "\nHash function:  " +
         ( option == 0 ? "(d1*10 + d0) % " : "(d1 * d0) % " ) +
         table.length );

      System.out.println ("\nindex    value  key");
      for ( j = 0; j < val.length; j++ )
         System.out.printf ("%5d %8d %4d\n", j, val[j], key[j]);

      System.out.print ("\nPress enter to see the hash table.");
      console.nextLine();

      System.out.println ("\nindex    table");
      for ( j = 0; j < table.length; j++ )
      {  System.out.printf ("%5d %8d", j, table[j]);
         if (displaced[j]) System.out.print("  *");
         System.out.println();
      }
   }

   public static void main ( String[] args )
   {  long   seed = generator.nextLong();
      int    size = -1;
      int[]  table;
      int[]  val = new int[10];
      int[]  key = new int[10];
      int    j, k;

      System.out.print ("Size:  ");
      if ( args.length > 0 )
      {  try
         {  size = Integer.parseInt(args[0].trim());  }
         catch (Exception e)
         {  System.out.println(e);  System.exit(-1);  }
         System.out.println(size);
      }
      else
      {  size = console.nextInt();  console.nextLine();  }
      table = new int[size];
      displaced = new boolean[size];

      if ( args.length > 1 )
      {  try
         {  option = Integer.parseInt(args[1].trim());  }
         catch (Exception e)
         {  System.out.println(e);  System.exit(-1);  }
      }

      if ( args.length > 2 )
      {  try
         {  seed = Long.parseLong(args[2].trim());  }
         catch (Exception e)
         {  System.out.println(e);  System.exit(-1);  }
         System.out.println("Setting seed to " + seed);
      }
      generator.setSeed(seed);

      fillTable(table, val, key);

      showTable(table, val, key);
      System.out.print ("\nPress enter to exit.");
      console.nextLine();
   }
}


OUTPUT

Size:  10

d1 is the leading digit, d0 the trailing.
Hash function:  (d1*10 + d0) % 10

index    value  key
    0      501    1
    1      997    7
    2     3252    2
    3      624    4
    4      939    9
    5       46    6
    6      923    3
    7        8    8
    8       99    9
    9        8    8

Press enter to see the hash table.

index    table
    0       99  *
    1      501
    2     3252
    3      923
    4      624
    5        8  *
    6       46
    7      997
    8        8
    9      939

Hash table drill program

import java.util.Random;
import java.io.*;
import java.util.Scanner;

public class HashDrill
{  // Selection the hash function for int hash()
   static private int   option = 0;

   static private boolean[] displaced;

   // Seeded in main, used in fillTable
   static Random generator = new Random();

   static Scanner console = new Scanner(System.in);

// Hash function, based on the selection option
   private static int hash ( int value, int size )
   {  int d1 = Math.abs(value),
          d0 = d1 % 10;
      int key = d1 % size;   // Used for single-digit value

      // More than one digit; isolate d1 and compute.
      if ( d1 != d0 )
      {  while ( d1 > 9 )
            d1 /= 10;
         if ( option == 0 )
            key = (d1*10 + d0) % size;
         else
            key = (d1 * d0) % size;
      }
      return key;
   }

   // Fill table[], val[] and key[]
   private static void fillTable ( int[] table, int[] val, int[] key )
   {  int j, k,
          size = table.length;

      // Initialize the table to empty (-1 throughout)
      for ( j = 0; j < size; j++ )
         table[j] = -1;

      // Generate the values, then place them into the table
      for ( j = 0; j < val.length; j++ )
      {  k = generator.nextInt(4) + 1;
         val[j] = generator.nextInt((int)Math.pow(10,k));
         k = hash(val[j], size);
         key[j] = k;

         // Linear probe for an available cell
         while ( table[k] != -1 )
            k = (k+1) % size;
         // Position the value into the table
         table[k] = val[j];
         displaced[k] = k != hash(val[j], size);
      }
   }

   // Display table[], val[] and key[]
   private static void showTable ( int[] table, int[] val, int[] key )
   {  int j;

      System.out.println ("\nd1 is the leading digit, d0 the trailing." +
         "\nHash function:  " +
         ( option == 0 ? "(d1*10 + d0) % " : "(d1 * d0) % " ) +
         table.length );

      System.out.println ("\nindex    value  key");
      for ( j = 0; j < val.length; j++ )
         System.out.printf ("%5d %8d %4d\n", j, val[j], key[j]);

      System.out.print ("\nPress enter to see the hash table.");
      console.nextLine();

      System.out.println ("\nindex    table");
      for ( j = 0; j < table.length; j++ )
      {  System.out.printf ("%5d %8d", j, table[j]);
         if (displaced[j]) System.out.print("  *");
         System.out.println();
      }
   }

   public static void main ( String[] args )
   {  long   seed = generator.nextLong();
      int    size = -1;
      int[]  table;
      int[]  val = new int[10];
      int[]  key = new int[10];
      int    j, k;

      System.out.print ("Size:  ");
      if ( args.length > 0 )
      {  try
         {  size = Integer.parseInt(args[0].trim());  }
         catch (Exception e)
         {  System.out.println(e);  System.exit(-1);  }
         System.out.println(size);
      }
      else
      {  size = console.nextInt();  console.nextLine();  }
      table = new int[size];
      displaced = new boolean[size];

      if ( args.length > 1 )
      {  try
         {  option = Integer.parseInt(args[1].trim());  }
         catch (Exception e)
         {  System.out.println(e);  System.exit(-1);  }
      }

      if ( args.length > 2 )
      {  try
         {  seed = Long.parseLong(args[2].trim());  }
         catch (Exception e)
         {  System.out.println(e);  System.exit(-1);  }
         System.out.println("Setting seed to " + seed);
      }
      generator.setSeed(seed);

      fillTable(table, val, key);

      showTable(table, val, key);
      System.out.print ("\nPress enter to exit.");
      console.nextLine();
   }
}


OUTPUT

Size:  10

d1 is the leading digit, d0 the trailing.
Hash function:  (d1*10 + d0) % 10

index    value  key
    0      501    1
    1      997    7
    2     3252    2
    3      624    4
    4      939    9
    5       46    6
    6      923    3
    7        8    8
    8       99    9
    9        8    8

Press enter to see the hash table.

index    table
    0       99  *
    1      501
    2     3252
    3      923
    4      624
    5        8  *
    6       46
    7      997
    8        8
    9      939

The n-Queens Problem

import java.util.*;       //to import Scanner class for take the value from user of the chess board

public class quen{

int[] x=new int[16];      //allocate a location for array storage

    public void Nquens(int r, int n){

        for(int c=0;c<n;c++){

            if (canPlace(r,c)){

                x[r] =c;

                if(r==n-1){  //it's say successfully filled

                    print(x,n);

                    board(x,n);

                    break;

                }

            else Nquens(r+1,n); //call or move 1st one queen to up box

             }

        }

    }

    boolean canPlace(int r,int t){   // to check can place or not

        for(int i=0;i<r;i++){

        if (x[i]==t||Math.abs(i-r)==Math.abs(x[i]-t)) //to check if any queen take place in vertical or horizontal line

        return false;

        }

        return true;

    }

       

       

       

    public void print(int[] y,int n){     //print the possible way

    System.out.println();

    System.out.println("another posible way");

    System.out.println();

   

        for (int i=0;i<n;i++){//n or y.length

            System.out.print(y[i]+"|");

            }

            System.out.println();

            System.out.println("board");

        }

       

       

       

    public void board(int[] y,int n){  //command for print chess board

        for(int i=0;i<n;i++){

        System.out.println();

            for(int j=0;j<n;j++){

                if(j==y[i]){

                System.out.print("Q"+"|");}

                else{

            System.out.print("*"+"|");}

            }

            System.out.println();

            for(int k=0;k<2*n;k++){

            System.out.print("-");}

            }

        }

       

       

       

    public static void main(String arg[]){   //main method head of the program 

    Scanner p=new Scanner(System.in);   // to take the input from outside

    System.out.println("enter your board length");

    System.out.println();

    int r=p.nextInt();    //to assign the value to r that take from outside

    System.out.println("your possible ways are");

        quen x=new quen(); //to create a new instance

        x.Nquens(0,r); //call the method  

    }

}

 Result for above coding

enter your board length
4

your possible ways are
Nquens          (0,4)
canplace        (0,0)
        yes     x[0]=0

Nquens          (1,4)
canplace        (1,0)
0==0    1==0
              no
canplace        (1,1)
0==1    1==1
                no
canplace        (1,2)
0==2    1==2
        yes     x[1]=2

Nquens          (2,4)
canplace        (2,0)
0==0    2==0
                no
canplace        (2,1)
0==1    2==1
2==1    1==1
                no
canplace        (2,2)
0==2    2==2
                no
canplace        (2,3)
0==3    2==3
2==3    1==1
                no
                no
canplace        (1,3)
0==3    1==3
        yes     x[1]=3

Nquens          (2,4)
canplace        (2,0)
0==0    2==0
                no
canplace        (2,1)
0==1    2==1
3==1    1==2
        yes     x[2]=1

Nquens          (3,4)
canplace        (3,0)
0==0    3==0
                no
canplace        (3,1)
0==1    3==1
3==1    2==2
                no
canplace        (3,2)
0==2    3==2
3==2    2==1
1==2    1==1
                no
canplace        (3,3)
0==3    3==3
                no
                no
canplace        (2,2)
0==2    2==2
                no
canplace        (2,3)
0==3    2==3
3==3    1==0
                no
                no
                no
canplace        (0,1)
        yes     x[0]=1

Nquens          (1,4)
canplace        (1,0)
1==0    1==1
                no
canplace        (1,1)
1==1    1==0
                no
canplace        (1,2)
1==2    1==1
                no
canplace        (1,3)
1==3    1==2
        yes     x[1]=3

Nquens          (2,4)
canplace        (2,0)
1==0    2==1
3==0    1==3
        yes     x[2]=0

Nquens          (3,4)
canplace        (3,0)
1==0    3==1
3==0    2==3
0==0    1==0
                no
canplace        (3,1)
1==1    3==0
                no
canplace        (3,2)
1==2    3==1
3==2    2==1
0==2    1==2
        yes     x[3]=2


 posible way
1|3|0|2|
board

*|Q|*|*|
--------
*|*|*|Q|
--------
Q|*|*|*|
--------
*|*|Q|*|
--------                no
canplace        (3,3)
1==3    3==2
3==3    2==0
                no
                no
canplace        (2,1)
1==1    2==0
                no
canplace        (2,2)
1==2    2==1
3==2    1==1
                no
canplace        (2,3)
1==3    2==2
                no
                no
                no
canplace        (0,2)
        yes     x[0]=2

Nquens          (1,4)
canplace        (1,0)
2==0    1==2
        yes     x[1]=0

Nquens          (2,4)
canplace        (2,0)
2==0    2==2
                no
canplace        (2,1)
2==1    2==1
0==1    1==1
                no
canplace        (2,2)
2==2    2==0
                no
canplace        (2,3)
2==3    2==1
0==3    1==3
        yes     x[2]=3

Nquens          (3,4)
canplace        (3,0)
2==0    3==2
0==0    2==0
                no
canplace        (3,1)
2==1    3==1
0==1    2==1
3==1    1==2
        yes     x[3]=1


 posible way
2|0|3|1|
board

*|*|Q|*|
--------
Q|*|*|*|
--------
*|*|*|Q|
--------
*|Q|*|*|
--------                no
canplace        (3,2)
2==2    3==0
                no
canplace        (3,3)
2==3    3==1
0==3    2==3
3==3    1==0
                no
                no
                no
canplace        (1,1)
2==1    1==1
                no
canplace        (1,2)
2==2    1==0
                no
canplace        (1,3)
2==3    1==1
                no
                no
canplace        (0,3)
        yes     x[0]=3

Nquens          (1,4)
canplace        (1,0)
3==0    1==3
        yes     x[1]=0

Nquens          (2,4)
canplace        (2,0)
3==0    2==3
0==0    1==0
                no
canplace        (2,1)
3==1    2==2
                no
canplace        (2,2)
3==2    2==1
0==2    1==2
        yes     x[2]=2

Nquens          (3,4)
canplace        (3,0)
3==0    3==3
                no
canplace        (3,1)
3==1    3==2
0==1    2==1
2==1    1==1
                no
canplace        (3,2)
3==2    3==1
0==2    2==2
                no
canplace        (3,3)
3==3    3==0
                no
                no
canplace        (2,3)
3==3    2==0
                no
                no
canplace        (1,1)
3==1    1==2
        yes     x[1]=1

Nquens          (2,4)
canplace        (2,0)
3==0    2==3
1==0    1==1
                no
canplace        (2,1)
3==1    2==2
                no
canplace        (2,2)
3==2    2==1
1==2    1==1
                no
canplace        (2,3)
3==3    2==0
                no
                no
canplace        (1,2)
3==2    1==1
                no
canplace        (1,3)
3==3    1==0
                no
                no

The n-Queens Problem

import java.util.*;       //to import Scanner class for take the value from user of the chess board

public class quen{

int[] x=new int[16];      //allocate a location for array storage