Scribd Logo
Upload

Welcome to Scribd!

  • 14 views

    MID DSA COURSE - 020 - ZRB

    Uploaded by

    Psyco Path
    The document contains the name and details of a student and the question they are answering regarding the Tower of Hanoi problem. They provide a table demonstrating the steps to solve the problem by moving 5 disks from peg A to peg C. They also provide the C++ code implementation of the Tower of Hanoi problem solving algorithm.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    MID DSA COURSE - 020 - ZRB

    Uploaded by

    Psyco Path
    14 views6 pages
    The document contains the name and details of a student and the question they are answering regarding the Tower of Hanoi problem. They provide a table demonstrating the steps to solve the problem by moving 5 disks from peg A to peg C. They also provide the C++ code implementation of the Tower of Hanoi problem solving algorithm.

    Original Title

    MID DSA COURSE _020_zrb (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains the name and details of a student and the question they are answering regarding the Tower of Hanoi problem. They provide a table demonstrating the steps to solve the problem by moving 5 disks from peg A to peg C. They also provide the C++ code implementation of the Tower of Hanoi problem solving algorithm.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    14 views6 pages

    MID DSA COURSE - 020 - ZRB

    Uploaded by

    Psyco Path
    The document contains the name and details of a student and the question they are answering regarding the Tower of Hanoi problem. They provide a table demonstrating the steps to solve the problem by moving 5 disks from peg A to peg C. They also provide the C++ code implementation of the Tower of Hanoi problem solving algorithm.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 6

    Name: Zunaira Rashid

    Roll #: 19014020-020

    B S C S

    3 rd S E M E S T E R

    Data Structures & Algorithm

    SUBMITTED TO Sehrish Munawar

    MID TERM

    S E SS I O N 8
    a) Now, consider you have 5 disks, labeled 1,2,3,4,5 where 1 is the smallest disk and 5 is
    the largest disk. You need to demonstrate the process of moving disks from peg A to peg C.
    To demonstrate the process, you are required to construct a table like Table 1., and
    draw/write the stack at each step.
    Answer:

    According to statement I have 5 disks to demonstrate and construct table that is:

    Move Disk From Peg To Peg n


    1 A B 0
    2 A C 1
    1 B C 2
    3 A B 3
    1 C A 4
    2 C B 5
    1 A B 6
    4 A C 7
    1 B C 8
    2 B A 9
    1 C A 10
    3 B C 11
    1 A B 12
    2 A C 13
    1 B C 14
    5 A B 15
    1 C A 16
    2 C B 17
    1 A B 18
    3 C A 19
    1 B C 20
    2 B A 21
    1 C A 22
    4 C B 23
    1 A B 24
    2 A C 25
    1 B C 26
    3 A B 27
    1 C A 28
    2 C B 29
    1 A B 30
    b) Also write code implementation in c++ for above problem.
    #include <iostream>
    using namespace std;
    typedef struct Stack
    {
    int s;
    int top;
    int *arr;
    }StackNode;

    StackNode* Create_stack(int s)
    {
    StackNode* stack= new Stack;
    stack->s =s;
    stack->top =-1;
    stack->arr = new int[s];
    return stack;
    }
    bool CheckFull(StackNode* stack);
    bool CheckEmpty(StackNode* stack);
    void push(StackNode* stack, int element);
    int pop(StackNode* stack);
    void MoveDisc(int disc, char from_Rod, char to_Rod) ;
    void MoveDisc_Helper(struct Stack *source, struct Stack*dest, char s, char d);
    double pow (double A, double B);
    void TowerOfHanoi(int nod, struct Stack*source, struct Stack *aux, struct Stack *dest) ;

    bool CheckFull(StackNode* stack){


    if(stack->top == stack->s - 1)
    return true;
    else
    return false;
    }

    bool CheckEmpty(StackNode* stack){


    if(stack->top == -1)
    return true;
    else
    return false;
    }
    void push(StackNode* stack, int element)

    {
    if(CheckFull(stack))
    return;
    stack->arr[++stack->top]= element;
    }
    int pop(StackNode* stack){
    if(CheckEmpty(stack))
    return -1;
    return(stack->arr[stack->top--]);
    }
    void MoveDisc(int disc, char from_Rod, char to_Rod)

    {
    int NoOfPass;
    cout<<NoOfPass++<<" "<<"\nMove the disc "<<disc<<" "<<"from Peg '"<<from_Rod<<"' to Peg
    '"<<to_Rod<<"'"<<endl;
    }
    void MoveDisc_Helper(struct Stack *source, struct Stack*dest, char s, char d)
    {
    int top1=pop(source);
    int top2 =pop(dest);
    if (top1 == -1)
    {
    push (source, top2);
    MoveDisc(top2, d, s);
    }
    else if (top2 ==-1)

    {
    push(dest, top1);
    MoveDisc(top1, s, d);
    }
    else if (top1 >top2)
    {
    push (source, top1);
    push (source, top2);
    MoveDisc(top2, d, s);
    }
    else
    {
    push(dest, top2);
    push(dest, top1);
    MoveDisc(top1, s, d);

    }
    }
    double pow(double A , double B);

    double ans=A;
    int i=1;
    while(i<B) {
    ans = ans * A;
    i++;
    }
    return ans;
    }
    void TowerOfHanoi(int nod, struct Stack*source, struct Stack *aux, struct Stack *dest)
    {
    char s = 'A', d = 'B',a = 'C';

    if (nod % 2== 0)
    {
    char var =d;
    d =a;
    a =var;
    }

    int nom =pow (2, nod) - 1;

    for (int i =nod; i >= 1; i--)


    {
    push(source,i);
    }

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


    {
    if (i % 3== 0)
    MoveDisc_Helper(aux, dest, a, d);
    else if (i% 3 == 2)
    MoveDisc_Helper(source,aux, s, a);
    else if (i% 3 == 1)
    MoveDisc_Helper(source,dest, s, d);
    }
    }

    int main () {
    cout<<"\n************************* "<<endl;
    cout<<"***** S T A R T ***** "<<endl;
    cout<<"************************* "<<endl;
    int n;
    cout<<" NUMBER OF DISK = ";
    cin>>n;
    StackNode* source;
    StackNode* dest;
    StackNode* aux;
    source =Create_stack(n);
    aux =Create_stack(n);
    dest =Create_stack(n);

    TowerOfHanoi(n,source, aux, dest);


    delete source;
    delete aux;
    delete dest;
    cout<<"\n************************* " <<endl;
    cout<<"*****END OF PROGRAM***** " <<endl;
    cout<<"************************* " <<endl;
    cout<<"____Zunaira__BSCS__020____" <<endl;
    cout<<"__More Information on Word file__";

    return 0;
    }

    ****THE END*****

    You might also like