GCD of two numbers and its application...

The greatest common divisor (gcd) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The gcd can be found using the Euclidean algorithm

GCD is useful in cases when you want different amounts of things to be arranged in the same number of order. 

For example there are 32 soldiers and 48 bandsman and during the parade you want them to march in the same number of rows. 

So , you calculate the HCF which is 8 and thus you can make 8 rows each for each group.

Write C++ program to find GCD two numbers a and b using  user defined function. i.e. GCD(a,b) using Euclids algorithm.

 #include <iostream>

using namespace std;

int gcd(int a, int b) {

   if (b == 0)

   return a;

   return gcd(b, a % b);

}

int main() {

   int a , b;

   cout<<"Enter the values of a and b: "<<endl;

   cin>>a>>b;

   cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);

   return 0;

}

Output:

Enter the values of a and b: 

10

20

GCD of 10 and 20 is 10

C program to count number of words from a sentence.

4) Java program to find largest of two integers using "if" statement.

Java program to read two integers from keyboard and find addition.

Java program to perform Arithmetic Calculations for given two integers.

TOP 10 MOTIVATIONAL STORIES - By Sandeep Maheshwari | Compilation of Bes...

Centering equations with a right-justified number in Microsoft Word

6.3 Graph Coloring Problem - Backtracking (Reference/Curtesy: Prof. Abdul Bari)

Module 5: L2: Design and implement the presence of Hamiltonian Cycle in an undirected Graph G of n vertices.

 

Design and implement the presence of Hamiltonian Cycle in an undirected Graph G of n vertices.

 

importjava.util.*;

 

 

classHamiltoniancycle

 

{

privateintadj[][],x[],n;

publicHamiltoniancycle()

{

Scanner src = newScanner(System.in);

System.out.println("Enter the number of nodes");

n=src.nextInt();

x=new int[n];

x[0]=0;

for(inti=1;i<n; i++)

x[i]=-1;

adj=new int[n][n];

System.out.println("Enter the adjacency matrix"); for (inti=0;i<n; i++)

for(intj=0; j<n; j++)

adj[i][j]=src.nextInt();

}

 

public void nextValue (intk)

 

{

inti=0;

while(true)

{

x[k]=x[k]+1;

if(x[k]==n)

x[k]=-1;

if(x[k]==-1)

return;

if(adj[x[k-1]][x[k]]==1)

for(i=0; i<k; i++)

if(x[i]==x[k])

break;

if(i==k)

if(k<n-1 || k==n-1 &&adj[x[n-1]][0]==1)

return;

}

}

public void getHCycle(intk)

{

while(true)

{

nextValue(k);

if(x[k]==-1)

return;

if(k==n-1)

{

System.out.println("\nSolution : ");

for(inti=0; i<n; i++)

System.out.print((x[i]+1)+" ");

System.out.println(1);

}

else

getHCycle(k+1);

}

 

}

}

 

 

classHamiltoniancycleExp

{

public static void main(String args[])

{

Hamiltoniancycleobj=newHamiltoniancycle(); obj.getHCycle(1);

}

}

 

 

Output:

 

Enter the number of nodes

 

6

Enter the adjacency matrix

0 1 1 1 0 0

1 0 1 0 0 1

1 1 0 1 1 0

1 0 1 0 1 0

0 0 1 1 0 1

0 1 0 0 1 0

 

Solution :					4	1
1	2	6	5	3
Solution :					3	1
1	2	6	5	4
Solution :					4	1
1	3	2	6	5
Solution :					2	1
1	3	4	5	6
Solution :					2	1
1	4	3	5	6
Solution :					3	1
1	4	5	6	2

Module-5: L1 Subset Problem :Java Program to find a subset of a given set S = {Sl, S2,…, Sn} of n positive integers whose SUM is equal to a given positive integer d

 Design and implement in Java to find a subset of a given set S = {Sl, S2,.....,Sn} of n

 

positive integers whose SUM is equal to a given positive integer d. For example, if S ={1, 2, 5,6, 8} and d= 9, there are two solutions {1,2,6}and {1,8}. Display a suitable message, if the given problem instance doesn't have a solution.

 

import java.util.Scanner;

 

import static java.lang.Math.pow;

 

 

public class subSet {

 

 

void subset(intnum,int n, int x[])

{

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

x[i]=0;

for(i=n;num!=0;i--)

{

x[i]=num%2;

num=num/2;

}

}

 

public static void main(String[] args) {

 

//                    TODO Auto-generated method stub int a[]=new int[10];

 

int x[]=new int[10]; intn,d,sum,present=0; int j;

 

System.out.println("enter the number of elements of set"); Scanner sc=new Scanner(System.in);

 

n=sc.nextInt();

System.out.println("enter the elements of set"); for(int i=1;i<=n;i++)

 

a[i]=sc.nextInt();

System.out.println("enter the positive integer sum"); d=sc.nextInt();

 

if(d>0)

{

for(int i=1;i<=Math.pow(2,n)-1;i++)

{

subSet s=new subSet(); s.subset(i,n,x); sum=0; for(j=1;j<=n;j++) if(x[j]==1)

sum=sum+a[j];

 

if(d==sum)

{

System.out.print("Subset={");

present=1;

for(j=1;j<=n;j++)

if(x[j]==1)

System.out.print(a[j]+",");

 

System.out.print("}="+d);

 

System.out.println();

}

 

}

 

}

 

if(present==0)

System.out.println("Solution does not exists");

 

}

 

}

 

Output:

 

enter the number of elements of set

 

5

enter the elements of set

1 2 5 6 8

enter the positive integer sum

9

Subset={1,8,}=9

Subset={1,2,6,}=9

Module 4: Laboratory Component 2: Solve Travelling Sales Person problem using Dynamic programming.

Module 4:

Laboratory Component: M4/L2

Java code to solve Travelling Sales Person problem using Dynamic programming.

 import java.util.Scanner;

 class TSPExp {

 int weight[][],n,tour[],finalCost;

 final int INF=1000;

 TSPExp()

 {

Scanner s=newScanner(System.in);

System.out.println("Enter no. of nodes:=>"); n=s.nextInt();

weight=new int[n][n];

tour=new int[n-1];

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

{

            for(intj=0;j<n;j++)

{

if(i!=j)

{

System.out.print("Enter weight of "+(i+1)+" to "+(j+1)+":=>");

weight[i][j]=s.nextInt();

}

}

}

System.out.println();

System.out.println("Starting node assumed to be node 1.");

eval();

}

 public int COST(intcurrentNode,intinputSet[],intsetSize)

{

if(setSize==0)

returnweight[currentNode][0];

int min=INF;

int setToBePassedOnToNextCallOfCOST[]=new int[n-1]; for(inti=0;i<setSize;i++)

{

int k=0;//initialisenew set

for(int j=0;j<setSize;j++)

{

if(inputSet[i]!=inputSet[j])

setToBePassedOnToNextCallOfCOST[k++]=inputSet[j];

}

int temp=COST(inputSet[i],setToBePassedOnToNextCallOfCOST,setSize-1);

if((weight[currentNode][inputSet[i]]+temp) < min)

{

min=weight[currentNode][inputSet[i]]+temp;

}

}

return min;

}

 

public int MIN(int currentNode,int inputSet[],int setSize)

{

if(setSize==0)

return weight[currentNode][0];

int min=INF,minindex=0;

int setToBePassedOnToNextCallOfCOST[]=new int[n-1];

for(int i=0;i<setSize;i++)//considers each node of inputSet

{

int k=0;

for(int j=0;j<setSize;j++)

{

if(input Set[i]!=inputSet[j])

setToBePassedOnToNextCallOfCOST[k++]=inputSet[j];

 

}

int temp=COST(inputSet[i],setToBePassedOnToNextCallOfCOST,setSize-1);

if((weight[currentNode][inputSet[i]]+temp) < min)

{

min=weight[currentNode][inputSet[i]]+temp; minindex=inputSet[i];

}

}

return minindex;

}

 

public void eval()

{

intdummySet[]=new int[n-1];

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

dummySet[i-1]=i;

finalCost=COST(0,dummySet,n-1);

constructTour();

}

 

public void constructTour()

{

int previousSet[]=new int[n-1];

int nextSet[]=new int[n-2];

for(inti=1;i<n;i++)

previousSet[i-1]=i;

int setSize=n-1;

tour[0]=MIN(0,previousSet,setSize);

for(inti=1;i<n-1;i++)

{

int k=0;

for(intj=0;j<setSize;j++)

{

if(tour[i-1]!=previousSet[j])

nextSet[k++]=previousSet[j];

}

--setSize;

tour[i]=MIN(tour[i-1],nextSet,setSize);

for(intj=0;j<setSize;j++)

previousSet[j]=nextSet[j];

}

display();

}

 public void display()

{

System.out.println();

System.out.print("The tour is 1-");

for(inti=0;i<n-1;i++)

System.out.print((tour[i]+1)+"-");

System.out.print("1");

System.out.println();

System.out.println("The final cost is "+finalCost); }

}

 class TSP

{

public static void main(String args[])

{

TSPExpobj=newTSPExp();

}

}

  

Output:

 

Enter no. of nodes:=>

4

Enter weight of 1 to 2:=>2

Enter weight of 1 to 3:=>5

Enter weight of 1 to 4:=>7

Enter weight of 2 to 1:=>2

Enter weight of 2 to 3:=>8

Enter weight of 2 to 4:=>3

Enter weight of 3 to 1:=>5

Enter weight of 3 to 2:=>8

Enter weight of 3 to 4:=>1

Enter weight of 4 to 1:=>7

Enter weight of 4 to 2:=>3

Enter weight of 4 to 3:=>1

 

Starting node assumed to be node 1.

 

The tour is 1-2-4-3-1

 

The final cost is 11