Aim: implementation of program for
Towers of Hanoi-A Recursion application.
Requirements: Java (JDK KIT)
Theory
Towers of Hanoi’s best
example of Recursion. A tower of Hanoi is an old puzzle, originated in a
Monastery in Tibet. A tower
of Hanoi
Algorithm:
MoveDisc(whichDisc,
frompeg, topeg)
{
System.out.println("Move
ring"+ whichDisc+"frompeg"+frompeg+"topeg"+topeg);
}
MoveTower( height, frompeg, topeg, usingpeg)
{
MoveTower( height-1,
frompeg,usingpeg, topeg);
MoveDisc( height, frompeg, topeg);
MoveTower( height-1, usingpeg,
topeg,frompeg);
}
Implementation
Coding:
import
java.io.*;
class
TowerOfHanoi
{
public
static void main(String args[])throws IOException
{
int n;
DataInputStream in=new
DataInputStream(System.in);
System.out.println("Enter the no of rings");
n=Integer.parseInt(in.readLine());
Hanoi(n);
}
static void MoveDisc(int
whichDisc,char frompeg,char topeg)
{
System.out.println("Move
ring"+ whichDisc+"frompeg"+frompeg+"topeg"+topeg);
}
static void MoveTower(int height,char frompeg,char topeg,char usingpeg)
{
if(height<=0)
{}
else
{
MoveTower( height-1,
frompeg,usingpeg, topeg);
MoveDisc( height, frompeg,
topeg);
MoveTower( height-1, usingpeg,
topeg,frompeg);
}
}
static void Hanoi(int n)
{
MoveTower(n,'A','B','C');
}
}
/*
OUTPUT:
Enter
the no of rings
3
Move
ring1frompegAtopegB
Move
ring2frompegAtopegC
Move
ring1frompegBtopegC
Move
ring3frompegAtopegB
Move
ring1frompegCtopegA
Move
ring2frompegCtopegB
Move
ring1frompegAtopegB
*/
Aim: implementation of quick sort
algorithm.
Requirements: Java (JDK KIT)
Theory:
Let 'x' be an array & 'n' number
of elements in array to be stored. Then choose element 'a'(pivot element) from
specific position within the array (eg. a can be chosen as first element so
that a=x[0]).suppose that elements of x are partitioned so that a is placed
into position j and following condition hold:
·
Each
of elements in positions 0 through j-1 is than
or equal to a.
·
Each of elements in positions j+1 through n-1 is greater than or
equal to a.
If these two conditions hold for a
particular a and j, a is jth smallest element of x, so that a remains in
position j when array is completely sorted. If this process is repeated with
sub-arrays x[0] through x[j-1] and [j+1] through x[n-1] and sub arrays created
by process in successive iterations, final array is sorted array.
Algorithm
:
// Function for partition function
int
partition(int lb, int ub)
{
int down,up,x,temp;
down=lb;
up=ub;
x=a[lb];
while(down<up)
{
while(a[down]<=x &&
down<=up)
down++;
while(a[up]>x)
up--;
if(down<up)
{
temp=a[down];
a[down]=a[up];
a[up]=temp;
}
}
temp=a[lb];
a[down]=a[up];
a[up]=temp;
return up;
}
//
function for quick for divide and combing.
void
quick(int lb, int ub)
{
int p;
if(lb<ub)
{
p=partition(lb,ub);
quick(lb,p-1);
quick(p+1,ub);
}
}
Implementation
Coding:
import
java.io.*;
class
QuickSort
{
static int a[]=new int[20];
static int n,k=1;
public static void main(String
[]args) throws IOException
{
int
down,up,lb,ub,n;
DataInputStream
in=new DataInputStream(System.in);
System.out.println("Enter
No. Of Elements U Want To Sort:");
n=Integer.parseInt(in.readLine());
System.out.println("Input
Elements:");
for (int
i=0;i<n;i++)
a[i]=Integer.parseInt(in.readLine());
quick(0,n-1);
System.out.println("Elements
In Ascending Order Are:");
for (int
i=0;i<n;i++)
System.out.println(a[i]);
}
static int partition(int lb,int
ub)
{
int
down,up,x,temp;
down=lb;
up=ub;
x=a[lb];
while(down<up)
{
while(a[down]<=x
&& down<=up)
down++;
while(a[up]>x)
up--;
if(down<up)
{
temp=a[down];
a[down]=a[up];
a[up]=temp;
}
}
temp=a[lb];
a[lb]=a[up];
a[up]=temp;
return up;
}
static void quick(int lb,int ub)
{
int p;
if(lb<ub)
{
p=partition(lb,ub);
quick(0,p-1);
quick(p+1,ub);
}
}
}
/*
OUTPUT:
Enter
No. Of Elements U Want To Sort:
5
Input
Elements:
23
56
97
48
12
Elements
In Ascending Order Are:
12
23
48
56
97
*/
Aim: implementation of merge sort
algorithm.
Requirements: Java (JDK KIT)
Theory:
Algorithm:
mergesort(low,
high)
{
int mid;
if(low < high)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
merge(low, mid, high)
{
int h=low,k;
int j=mid+1;
int i=low;
int b[]=new int[50];
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h=h+1;
}
else
{
b[i]=a[j];
j=j+1;
}
i=i+1;
}
if(h >mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i=i+1;
a[k]=b[k];
}}
for(k=low;k<=high;k++)
{
a[k]=b[k];
}
}
Implementation:
Coding:
import
java.io.*;
class
MergeSort
{
static int a[]=new int[50];
public static void main(String
args[])throws IOException
{
int i,n;
DataInputStream
in=new DataInputStream(System.in);
System.out.println("ENTER
NUMBER OF OF ELEMENT WANT TO SORT");
n=Integer.parseInt(in.readLine());
System.out.println("ENTER
ELEMENT");
for(i=0;i<n;i++)
{
a[i]=Integer.parseInt(in.readLine());
}
mergesort(0,n-1);
System.out.println("ARRAY
ELEMENT IN ASCENDING ORDER");
for(i=0;i<n;i++)
{
System.out.println(a[i]);
}
}
static void mergesort(int
low,int high)
{
int
mid;
if(low <
high)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
static void merge(int low,int
mid,int high)
{
int h=low;
int k;
int j=mid+1;
int i=low;
int b[]=new
int[50];
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h=h+1;
}
else
{
b[i]=a[j];
j=j+1;
}
i=i+1;
}
if(h >mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i=i+1;
a[k]=b[k];
}
}
for(k=low;k<=high;k++)
{
a[k]=b[k];
}
}
}
/*
OUTPUT:
ENTER
NUMBER OF OF ELEMENT WANT TO SORT
5
ENTER
ELEMENT
23
56
97
48
12
ARRAY
ELEMENT IN ASCENDING ORDER
12
23
48
56
97
*/
Aim: implementation of Binary search
algorithm.
Theory:
The improvement in
searching method to reduce the amount of work is made is and us known as binary
search. It works by comparing the target (search key) with the middle element
of the array and terminates if it is the same, else it divides the array into
two sub arrays and continues the search in the left (right) sub array if the
target is less (greater) than the middle element of the array. In this way, at
each step we reduce the length of the list to be searched by half, hence the
name binary search.
Algorithm:
Step 1: Read the 'n' elements in an array, say 'K'.
Step 2: Read the element to be searched,
say KEY.
Step 3: low=1, high=n (Initialize the lower
and upper limit of the list, tobe searched)
Step 4: Find the middle element,
mid_position=(low+high)/2
Y=K[mid position]
Step 5: If (KEY=Y) then display
"Element found and its location is value of ‘mid_position’ and goes to
step 9
Step 6: If (KEY<Y) (i.e. element to be
searched is less than the middle element) then search to be
continued
in lower half; high=mid_position-1, and go to step 8.
Step 7: Otherwise, the element is in upper
half, low=mid_position +1,
Step 8: If (high>=low) then go to step 4
else display "Element not in the list".
Step 9: Stop.
Implementation
Coding:
import
java.io.*;
class
BinarySearch
{
public static void main (String
args[]) throws IOException
{
int i,j,n =
0,KEY,temp,flag=0;
String
ans="y";
int x[]=new
int[25];
DataInputStream
in=new DataInputStream (System.in);
try
{
System.out.print("Enter
how many numbers to be stored :");
n=Integer.parseInt(in.readLine());
System.out.println("Enter
"+n+" numbers....");
for
(i=1;i<=n;i++)
{
System.out.print("\t\tElement
["+i+"]=");
x[i]=
Integer.parseInt(in.readLine());
}
for(i=0;i<5;i++)
{
for(j=0;j<=n-i-1;j++)
{
if(x[j]>x[j+1])
{
temp=x[j];
x[j]=x[j+1];
x[j+1]=temp;
}
}
}
do
{
System.out.print("Enter
the number to be searched :");
KEY=Integer.parseInt(in.readLine());
flag=Binary_Search(x,n,KEY);
if(flag==-1)
System.out.println("Number
not present in the given array");
else
System.out.println("Number
"+KEY+" found in the array");
System.out.print("Want
to search another number :");
ans=in.readLine();
}
while((ans.equals("y"))||(ans.equals("Y")));
}
catch (Exception
e)
{
System.out.println("I/O
Error");
}
}
//Binary Search Function
static int Binary_Search(int
k[],int n,int KEY)
{
int low=1;
int high=n;
int mid;
mid=(low+high)/2;
while
(high>=low)
{
if
(k[mid]==KEY)
return
(mid);
else
{
if
(KEY>k[mid])
low=mid+1;
else
high=mid-1;
mid=(low+high)/2;
}
}
return (-1);
}
}
/*
OUTPUT:
Enter
how many numbers to be stored :5
Enter 5
numbers....
Element [1]=23
Element [2]=56
Element [3]=98
Element [4]=48
Element [5]=12
Enter
the number to be searched :12
Number
12 found in the array
Want to
search another number :y
Enter
the number to be searched :29
Number
not present in the given array
Want to
search another number :n
*/
Aim: To find Minimum & Maximum no.
from given elements using ”Divide and Conquer” Method.
Requirements: Java (JDK KIT)
Theory:
The divide and conquer approach for
finding minimum and maximum number,
Let P= (n,
a[i],…..,a[j]) denote an arbitrary instance of the problem. Hence n is the
number of elements in the list a[i],…a[j].
- If n=1 the maximum and minimum are a[1].
- If n=2 the problem can be solved by making
comparison.
- If the list has more than 2 elements, P has to be
divided into smaller instances.
We might
divide P into 2 instances:
- P1= (n/2, a[1],….a[n2]) and
- P2= (n=n/2, a[n/2+1,….a[n])
After
having divided P into two smaller sub problems, we can solve them by
recursively invoking the same divide and conquer algorithm.
If
MAX(P) and MIN(P) are the maximum and minimum elements of P, then MAX(P) is
larger of MAX(P1) and Max(P2). Also MIN(P) is smaller of MIN(P1) and MIN(P2).
Algorithm:
minMax(int x)
{
if(x==-1)
return;
if
(min>a[x])
{
min=a[x];
minMax(x-1);
}
else
minMax(x-1);
if
(max<a[x])
{
max=a[x];
minMax(x-1);
}
else
minMax(x-1);
}
Implementation
Coding:
import
java.io.*;
class
MinMax_demo
{
static int a[]=new int[100];
static int min,max;
public static void main(String
args[]) throws IOException
{
int i,n;
DataInputStream
in=new DataInputStream(System.in);
System.out.println("How
many number ? : ");
n=Integer.parseInt(in.readLine());
System.out.println("Enter
the no:");
for(i=0;i<n;i++)
{
a[i]=Integer.parseInt(in.readLine());
}
min=a[0];
max=a[0];
minMax(n-1);
System.out.println("min
no.: "+min);
System.out.println("max
no.: "+max);
}
static void minMax(int x)
{
if(x==-1)
return;
if(min>a[x])
{
min=a[x];
minMax(x-1);
}
else
minMax(x-1);
if(max<a[x])
{
max=a[x];
minMax(x-1);
}
else
minMax(x-1);
}
}
/*
OUTPUT:
How many
number ? :
4
Enter
the no:
12
13
55
1
min no.:
1
max no.:
55
*/
Aim: To find Mean Retrieval Time for
Tape Drive.
Requirements: Java (JDK KIT)
Theory:
There are n
programs that are to be stored on a computer tape of l. all programs can be stored on the tapes if
and only if the sum of the lengths of the programs is at the most l.
We assume
that whenever a program is to be retrieved from this tape, the tape is
initially positioned at the front. If the programs are stored in the order I=
i1, i2,….in the time tj is required to
retrieve program ij proportional to ∑1≤k≤j lik .
If all
programs retrieved equally often, then the expected or mean retrieval time
(MRT) is (1/n) ∑1≤j≤n tj .
Here we are
required to find a permutation for the n programs so that when they are stored
on the tape in this order the MRT is minimized.
Implementation
Coding:
import
java.io.*;
class
optimal
{
public static void main(String
args[]) throws IOException
{
int
i,j,k,t,min,a=0,p=-1;
int x[]=new
int[10];
int l[]=new
int[10];
int b[]=new
int[10];
int x1[]=new
int[10];
int l1[]=new
int[10];
int c[][]=new
int[10][10];
int c1[][]=new
int[10][10];
int sum=0;
DataInputStream
in= new DataInputStream(System.in);
System.out.println("Input
program & its length");
for(i=0;i<3;i++)
{
x[i]=Integer.parseInt(in.readLine());
l[i]=Integer.parseInt(in.readLine());
}
for(j=0;j<3;j++)
{
for(k=0;k<3;k++)
{
x1[k]=x[k];
l1[k]=l[k];
}
t=x1[0];
x1[0]=x1[j];
x1[j]=t;
t=l1[0];
l1[0]=l1[j];
l1[j]=t;
++p;
for(k=0;k<3;k++)
{
c[p][k]=x1[k];
c1[p][k]=l1[k];
}
t=x1[1];
x1[1]=x1[2];
x1[2]=t;
t=l1[1];
l1[1]=l1[2];
l1[2]=t;
++p;
for(k=0;k<3;k++)
{
c[p][k]=x1[k];
c1[p][k]=l1[k];
}
}
for(i=0;i<=p;i++)
{
sum=0;
for(j=0;j<3;j++)
{
for(k=0;k<=j;k++)
{
sum=sum+c1[i][k];
}
}
b[i]=sum;
}
for(k=0;k<6;k++)
System.out.println(b[k]);
min=b[0];
for(i=0;i<6;i++)
{
if(min>b[i])
{
min=b[i];
a=i;
}
}
System.out.println("Optimal
Solution value is : "+min);
System.out.println("Optimal
Storage tape is :");
for(k=0;k<3;k++)
{
System.out.println("
"+c[a][k]);
}
}
}
/*
OUTPUT:
Input
program & its length
1
5
2
10
3
3
38
31
43
41
34
29
Optimal
Solution value is : 29
Optimal
Storage tape is :
3
1
2
*/
Aim: Implementation of KNAPSACK
Algorithm
Requirements: Java (JDK KIT)
Theory:
We are
given n objects and a knapsack or bag.
Object i
has a weight wi and the knapsack has capacity m. if a fraction xi,
0<= xi<=1, of object I is placed into the knapsack, then a
profit of pixi is earned.
The
objective is to obtain a filling of the knapsack that maximizes the total
profit earned. Since the knapsack capacity is m, we require the total weight of
all chosen objects to be at most m.
The problem
can be stated as:
Maximize ∑1≤i≤n
pixi
Subject to
∑1≤i≤n wixi≤m
and 0≤xi≤1, 1≤i≤ n
A feasible
solution is any set(x1,…,xn) satisfying. The above
equations.
Algorithm:
for(i=0;i<n;i++)
r[i]=pw[i][0]/pw[i][1];
for(i=0;i<n;i++)
{
for(j=i;j<n-i-1;j++)
{
if(r[j]<r[j+1]);
{
t1=pw[j][0];
t2=pw[j][1];
pw[j][0]=pw[j+1][0];
pw[j][1]=pw[j+1][1];
pw[j+1][0]=t1;
pw[j+1][1]=t2;
t1=r[j];
r[j]=r[j+1];
r[j+1]=t1;
}
}
}
float
u=m;
for(i=0;i<n;i++)
{
if(pw[i][1]>u)
break;
x[i]=1;
u=u-pw[i][1];
}
if(i<n)
x[i]=u/pw[i][1];
for(i=0;i<n;i++)
p=p+x[i]*pw[i][0];
Implementation
Coding:
import
java.io.*;
class
knapsack
{
public static void main(String
args[]) throws IOException
{
int i,j,n;
float
m,p=0,t1,t2;
DataInputStream
in=new DataInputStream(System.in);
float pw[][]=new
float[10][2];
float r[]=new
float[10];
float x[]=new
float[10];
System.out.println("Input
no.of objects");
n=Integer.parseInt(in.readLine());
System.out.println("Input
profit and weight of each objrct");
for(i=0;i<n;i++)
{
pw[i][0]=Integer.parseInt(in.readLine());
pw[i][1]=Integer.parseInt(in.readLine());
}
System.out.println("Input
capacity of knapsack");
m=Integer.parseInt(in.readLine());
for(i=0;i<n;i++)
r[i]=pw[i][0]/pw[i][1];
for(i=0;i<n;i++)
{
for(j=i;j<n-i-1;j++)
{
if(r[j]<r[j+1]);
{
t1=pw[j][0];
t2=pw[j][1];
pw[j][0]=pw[j+1][0];
pw[j][1]=pw[j+1][1];
pw[j+1][0]=t1;
pw[j+1][1]=t2;
t1=r[j];
r[j]=r[j+1];
r[j+1]=t1;
}
}
}
float u=m;
for(i=0;i<n;i++)
{
if(pw[i][1]>u)
break;
x[i]=1;
u=u-pw[i][1];
}
if(i<n)
x[i]=u/pw[i][1];
for(i=0;i<n;i++)
p=p+x[i]*pw[i][0];
System.out.println("Optimal
Solution ");
System.out.println("Instances
are");
for(i=0;i<n;i++)
System.out.print(x[i]+" ");
System.out.println("Profit : "+p);
}
}
/*
OUTPUT:
Input
no.of objects
3
Input
profit and weight of each objrct
25
18
24
15
15
10
Input
capacity of knapsack
20
Optimal
Solution
Instances
are
1.0 0.5
0.0 Profit : 31.5
*/
Comments
Post a Comment