CareerCup-3.4

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower The puzzle starts with disks sorted in ascending order of size from top to bottom (e g , each disk sits on top of an even larger one) You have the following constraints:

Only one disk can be moved at a time
A disk is slid off the top of one rod onto the next rod
A disk can only be placed on top of a larger disk

Write a program to move the disks from the first rod to the last using Stacks

经典的汉诺塔问题，采用递归的思想来完成

#include <iostream>
using namespace std;
typedef int Data;

struct Node
{
    Node(Data d):data(d){next = NULL;};
    Data data;
    Node* next;
};

class Stack
{
public:
    Stack():topNode(NULL){};
    void pop()
    {
        if(topNode != NULL)
        {
            Node* p = topNode;
            topNode = topNode->next;
            delete p;
        } else {
            throw "Empty Stack";
        }
    };
    Data top()
    {
        if(topNode != NULL)
        {
            return topNode->data;
        } else {
            throw "Empty Stack";
        }
    };
    void push(Data data)
    {
        Node* d = new Node(data);
        d->next = topNode;
        topNode = d;
    };
    void print()
    {
        cout<<"Stack:"<<endl;
        Node* p = topNode;
        while(p != NULL)
        {
            cout<<p->data<<" ";
            p = p->next;
        }
        cout<<endl<<"End"<<endl;
    };
    bool isEmpty(){return topNode == NULL;};
private:
    Node* topNode;
};

class Hanoi
{
public:
    Hanoi(int size):mSize(size)
    {
        while(size--)
        {
            stack[0].push(size);
        }
    };
    void move(int src, int dst)
    {
        if(src < 0 || src > 2 || dst < 0 || dst > 2 || src == dst)
        {
            throw "Error Stack Index";
        }
        Data data = stack[src].top();
        stack[src].pop();
        stack[dst].push(data);
        cout<<"Move: "<<data<<" "<<src<<"->"<<dst<<endl;       
    };
    void move(int src, int dst, int size)
    {
        if(src < 0 || src > 2 || dst < 0 || dst > 2 || src == dst || size <= 0)
        {
            throw "Error Stack Index";
        }
        if(size == 1)
        {
            move(src, dst);
            return;
        }
        int tmp = 3 - src - dst;
        move(src, tmp, size-1);
        move(src, dst);
        move(tmp, dst, size-1);
    };
    void print(int index)
    {
        if(index < 0 || index > 2) return;
        stack[index].print();
    };
private:
    int mSize;
    Stack stack[3];
};

int main()
{
    int size = 8;
    Hanoi hanoi(size);
    hanoi.move(0, 2, size);
    system("pause");
};

CareerCup-3.4

Comments

John Wong @GitHub