Tower of Hanoi using c++

Tower of Hanoi Using c ++

#include<iostream.h>

#include<conio.h> 

void towers(int,char,char,char); 

void main()

{

int n; //Declare the variables to be used

clrscr();//Get the input for number of disks

cout<<"enter the no of disks : ";

cin>>n;towers(n,'A','C','B'); //Call the function

getch();

} 

void towers(int n,char from,char to,char aux)

{

if(n==1) // If there is only one disk
    {

cout<<endl<<"move 1 from peg "<<from<<" to "<<to;return;

   }

towers(n-1,from,aux,to); //Recursive Call

cout<<endl<<"move "<<n<<" from peg "<<from<<" to "<<to;

towers(n-1,aux,to,from);

}

Information 

->Tower of Hanoi is a mathematical puzzle invented by a French Mathematician Edouard Lucas in 1883.

->The game starts by having few discs stacked in increasing order of size. The number of discs can vary, but there are only three pegs.

->The Objective is to transfer the entire tower to one of the other pegs. However you can only move one disk at a time and you can never stack a larger disk onto a smaller disk. Try to solve it in fewest possible moves.

Solution of tower of Hanoi :-

-To get a better understanding for the general algorithm used to solve the Tower of Hanoi, try to solve the puzzle with a small amount of disks, 3 or 4, and once you master that , you can solve The same puzzle with more discs with the following algorithm.Recursive Solution for the Tower of Hanoi with algorithm Let’s call the three peg Src(Source), Aux(Auxiliary) and  st(Destination). 

Move the top N – 1 disks from the Source to Auxiliary tower

Move the Nth disk from Source to Destination tower

Move the N – 1 disks from Auxiliary tower to Destination tower. 

Transferring the top N – 1 disks from Source to Auxiliary tower can again be thought of as a fresh problem and can be solved in the same manner.

So once you master solving Tower of Hanoi with three disks, you can solve it with any number of disks with the above algorithm.

The puzzle is well known to students of Computer Science since it appears in virtually any introductory text on data structures or algorithms.         

A function solve with four arguments (number of disks) and three pegs (source, intermediary and destination) could look like this.

Algorithms

Solve (N, Src, Aux, Dst)
 If N is 0

Exit

Else solve (N-1, Src, Dst, Aux)

Move from Src to Dst

Solve(N -1 , Aux, Src, Dst)

Finite Automata String Matching Algorithm using c

Finite Automata String Matching Algorithm

# include <iostream.h>

# include <conio.h>

# include <string.h>

class FiniteAutomaton

{

       private:

                       char *T,*P,*sig;

                       int n,m,l,q,trans[15][15];

       public :

                       void begin(void);

                       void set_trans(void);

                       int tfunc(char);

                       void matcher(void);

                       int check(int,int);

};

void FiniteAutomaton :: begin()

{

       int i=0,j=0;

       l=0; m=0; n=0; q=0;

       cout<<"\n\n Enter the input text :";

       cin>>T;

       cout<<"\n\n Enter the pattern :";

       cin>>P;

       n=strlen(T);

       m=strlen(P);

       while (T[i]!='\0') {

                       for (j=0;j<l;j++)  
                      {

                                       if (T[i]==sig[j])

                                                       break;

                       }

                       if (j==l)                 
                      {

                                       sig[l]=T[i];

                                       l++;

                       }

                       i++;

       }

       sig[l]='\0';

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

       {

                       for (j=0;j<15;j++)

                       {

                                       trans[i][j]=0;

                       }

       }

       cout<<sig;

}

void FiniteAutomaton :: set_trans()

{

       int i,j=0,k=0;

       for (i=0;i<=m;i++)
                       {

                        while (sig[j]!='\0') {

                                       (q+2)>(m+1)?k=m+1:k=q+2;

                                       do 
                                       {

                                                       k--;

                                       }
                                       while (check(k,j));

                                       j++;

                        }

       }

}

int FiniteAutomaton:: check(int k,int u)

{

       int i;

       for (i=k;i>=0;i--) 
       {

       }

}

int FiniteAutomaton :: tfunc(char a)

{

       int i;

       for (i=0;i<l;i++) 
       {

                       if (sig[i]==a)

                       break;

       }

       return(trans[q][i]);

}

void FiniteAutomaton :: matcher()

{

       int i;

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

                       if (tfunc(T[i])==m)

                       cout<<"\n\n The string is found at shift s = "<<i;

       }

}

void main()

{

       FiniteAutomaton fa;

       clrscr();

       fa.begin();

       getch();

}

Rabin-karp String Matching Algorithm using c

//Rabin karp String Matching Algorithm using c language 

#include<stdio.h>

#include<conio.h>

#include<string.h>

#include<math.h>

#define d 10

void RabinKarpStringMatch(char *, char *, int);

void main()

{

       char *Text, *Pattern;

       int Number = 11; //Prime Number

       clrscr();

       printf("\nEnter Text String : ");

       gets(Text);

       printf("\nEnter Pattern String : ");

       gets(Pattern);

       RabinKarpStringMatch(Text,Pattern,Number);

       getch();

}

void RabinKarpStringMatch(char *Text, char *Pattern, int Number)

{

       int M,N,h,P=0,T=0, TempT, TempP;

       int i,j;

       M = strlen(Pattern);

       N = strlen(Text);

       h = (int)pow(d,M-1) % Number;

       for(i=0;i<M;i++)  {

                       P = ((d*P) + ((int)Pattern[i])) % Number;

                       TempT = ((d*T) + ((int)Text[i]));

                       T =  TempT % Number;

       }

       for(i=0;i<=N-M;i++)  {

                       if(P==T)  {

                                       for(j=0;j<M;j++)

                                                       if(Text[i+j] != Pattern[j])

                                                                       break;

                                       if(j == M)

                                                       printf("\nPattern Found at Position :  %d",i+1);

                       }

                       TempT =((d*(T - Text[i]*h)) + ((int)Text[i+M]));

                       T = TempT % Number;

                       if(T<0)

                                       T=T+Number;

       }

}

knapsack algorithm using c++

#include<iostream.h>

struct kru

{

  int i,p,w;

  float pr;

}g[10];

void main()

{

int n,j,k,wa;

float total=0;

struct kru temp;

cout<<"enter data ow W";

cin>>wa;

cout<<"Enter no.of nodes";

cin>>n;

cout<<"Enter for sum of calculation:";

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

{

g[j].i=j+1;

cout<<"i th profit =";

cin>>g[j].p;

cout<<"i th weight =";

cin>>g[j].w;

}

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

{

g[j].pr=g[j].p/float(g[j].w);

}

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

{

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

{

 if(g[j].pr<=g[k].pr)

 {

  temp=g[j];

  g[j]=g[k];

  g[k]=temp;

 }

}

}

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

{

  if(wa>=g[j].w)

  {

  total=total+g[j].p;

  wa=wa-g[j].w;

  }

  total=total+(g[j].pr*wa);

}

cout<<"total is "<<total;

}

merge short

#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){

    int merge[MAX],i,n;

    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }

   return 0;
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}


Sample output:

Enter the total number of elements: 5
Enter the elements which to be sort: 2 5 0 9 1
After merge sorting elements are: 0 1 2 5 9

quick sort using c

#include<stdio.h>

void quicksort(int [10],int,int);

int main(){
  int x[20],size,i;

  printf("Enter size of the array: ");
  scanf("%d",&size);

  printf("Enter %d elements: ",size);
  for(i=0;i<size;i++)
    scanf("%d",&x[i]);

  quicksort(x,0,size-1);

  printf("Sorted elements: ");
  for(i=0;i<size;i++)
    printf(" %d",x[i]);

  return 0;
}

void quicksort(int x[10],int first,int last){
    int pivot,j,temp,i;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);

    }
}

Output:
Enter size of the array: 5
Enter 5 elements: 3 8 0 1 2
Sorted elements: 0 1 2 3 8

gcd using c++

#include<iostream.h>
int gcd(int x,int y)
{
if(x==y)
return (x);
else
{
if(x>y)
gcd(x-y,y);
else
gcd(x,y-x);
}
}
void main()
{
int n1,n2,g;
cin>>n1>>n2;
g=gcd(n1,n2);
cout<<"gcd of "<<n1<<" & "<<n2<<" is :"<<g;
}