Click here to Skip to main content
Click here to Skip to main content

Tagged as

Go to top

Hanoi Tower Non-Recursive computing

, 2 Apr 2008
Rate this:
Please Sign up or sign in to vote.
Hanoi Tower Recursive & Non-Recursive computing

Introduction

Hanoi Tower is a older question;

The Question descrition:

Have 3 Tower A B C; First A have 64 Blocks, these blocks have difference size; Top->Down is small -> Large; We must move these blocks from A to C, and when Moving we can use B;

Moving Limit:

1 Large Blocks can't place on small block

2 Once move a Block

Background

General we using Recurse Method process the Question;

Recurse Method can be Descrited:

Tranlate N blocks from A to C, Using B {

Tranlate N-1 Blocks from A to B, Using C;

Move N'th Block from A to C;

Tranlate N-1 Blocks from B to C, Using A;

}

Today, provide a method Iteration compute Hanoi Question;

Using little Rule:

1 Move a Block to other Tower, Order->Retrorse ->Order ->Retrorse ....

2 if can't Move N'th Block, must change Tower; if current need move Block is order, we change Tower is Order; else we change Tower is Retrorse;

3 When changed Tower, must be restore Move Block rule;

4 Adjust Rule 1: if Max Blocks Number is odd number, using Order->Retrorse

else Retrorse->Order

// 汉诺塔(hanoi tower)的非递归计算
// 计算策略:
// 1 如果有块可以移动,基本上遵从 先顺时针移动,然后逆时针移动的策略
// 2 如果无快可以移动,变换柱子,如果当前是要顺时针,就顺时针变换柱子,否则就反时针变化
// 3 如果柱子变换了,就恢复块的移动次序,为 起始的方式
// 4 对块的奇 偶性进行检查
// 奇数块,使用逆时针->顺时针的 策略
// 偶数块,使用顺时针->逆时针的 策略


Using the code

 // hanoi.cpp : Defines the entry point for the console application.
//



#include <span class="code-keyword"><iostream></span>
#include <span class="code-keyword"><deque></span>
#include <span class="code-keyword"><stdio.h></span>
#include <span class="code-keyword"><assert.h></span>

using namespace std;

// Helper Class, equals a Stack
template<class T>
class Tower {
public:
    std::deque<T> pillar;

public:
    T top() { 
        // Only for this question, general we can using thow exception instead
        if ( 0 == pillar.size() ) return T(0);
        return pillar.front();
    }
    void pop() {
        pillar.pop_front();
    }
    void push(const T &t) {
        return pillar.push_front(t);
    }
    size_t size() const  {
        return pillar.size();
    }
    template<class T>
    friend ostream & operator << (ostream &os , const Tower<T> &tower);
};

template<class T>
ostream & operator << (ostream &os , Tower<T> &tower) {
    for(size_t i=0; i<tower.pillar.size();++i) {
        os << tower.pillar[i] << " ";
    }
    return os;
}

template<class T>
void Iteration(int iBlocks,Tower<T>&tower1,Tower<T> &tower2,Tower<T> &tower3);

template<class T>
void move(Tower<T> &source,Tower<T> &target);

template<class T>
void Recursion(int iBlocks, Tower<T> &tower1,Tower<T> &tower2,Tower<T> &tower3);

void Entry(int iBlocks,bool isRec=false);

int main(int argc, char* argv[])
{
    int iBlocks=5;
    if ( argc == 2 ) {
        iBlocks = atoi(argv[1]);
    }
    if ( iBlocks <= 0 ) iBlocks=3;

    Entry(iBlocks,true);

    return 0;
}
/*
// 汉诺塔(hanoi tower)的非递归计算
// 计算策略:
//        1 如果有块可以移动,基本上遵从 先顺时针移动,然后逆时针移动的策略
//        2 如果无快可以移动,变换柱子,如果当前是要顺时针,就顺时针变换柱子,否则就反时针变化
//        3 如果柱子变换了,就恢复块的移动次序,为 起始的方式
//        4 对块的奇 偶性进行检查
//            奇数块,使用逆时针->顺时针的 策略
//            偶数块,使用顺时针->逆时针的 策略
*/

void Entry(int iBlocks,bool isRec) {
    assert(iBlock>0);

    const int TOWER_COUNT = 3;

    //typedef char Process_type;
    typedef int Process_type;    
    Tower<Process_type> towers[TOWER_COUNT]; 

    // initialize,must be start from 1 , because 0 is equal Tower Emtpy
    for(int i=iBlocks; i>0; --i) {
        //towers[0].push('A'+i-1);    
    towers[0].push(i);
    }
    
    char towerName[3]={'A','B','C'};
    std::cout << "--------------------------" << std::endl;
    for(int i=0; i<TOWER_COUNT;++i) {
        std::cout <<towerName[i] << ":" <<  towers[i] << std::endl;
    }
    std::cout << "==========================" << std::endl;
    if ( isRec ) 
        Recursion<Process_type>(iBlocks,towers[0],towers[1],towers[2]);
    else 
        Iteration<Process_type>(iBlocks,towers[0],towers[1],towers[2]);

    std::cout << "--------------------------" << std::endl;
    for(int i=0; i<TOWER_COUNT;++i) {
        std::cout <<towerName[i] << ":" <<  towers[i] << std::endl;
    }
    std::cout << "==========================" << std::endl;

}


template<class T>
void move(Tower<T> &source,Tower<T> &target) {
    target.push(source.top());
    source.pop();
}

template<class T>
void Recursion(int iBlocks, Tower<T> &tower1,Tower<T> &tower2,Tower<T> &tower3) {
    if ( 1 == iBlocks ) {
        move(tower1,tower3);
        return;
    } else if ( 2 == iBlocks ) {
        move(tower1,tower2);
        move(tower1,tower3);
        move(tower2,tower3);
        return;
    }
    Recursion(iBlocks-1, tower1,tower3,tower2);
    move(tower1,tower3);
    Recursion(iBlocks-1,tower2,tower1,tower3);
}


template<class T>
void Iteration(int iBlocks,Tower<T>&tower1,Tower<T> &tower2,Tower<T> &tower3) {
    const int TOWER_COUNT = 3;
    Tower<T> *towers[3];

    towers[0]=&tower1;
    towers[1]=&tower2;
    towers[2]=&tower3;

    char towerName[3]={'A','B','C'};

        //用于调整方向,如果一直是遵从顺时针->逆时针 的次序,那么对于iBlocks是奇数和偶数的时候,最后生成的位置是不同的;
    bool adjustDirect;
    bool towerDirect_shun;

    if ( iBlocks % 2 ) { // 奇数块,使用逆时针->顺时针的 策略
        towerDirect_shun = false;
        adjustDirect = false;
    } else {            // // 偶数块,使用顺时针->逆时针的 策略     
        towerDirect_shun = true;
        adjustDirect = true;
    }

    unsigned long long count=0;

    int sourceTowerIndex=0;
    int targetTowerIndex;
    T curBlock,targetMinBlock;

    while(true) {
        if ( towerDirect_shun ) {
            targetTowerIndex = ( sourceTowerIndex + 1 ) % TOWER_COUNT;
        } else { 
            targetTowerIndex = ( sourceTowerIndex + 2 ) % TOWER_COUNT;
        }

        curBlock = towers[sourceTowerIndex]->top();
        targetMinBlock = towers[targetTowerIndex]->top();

        //if ( curBlock!=0 && (curBlock < targetMinBlock || towers[targetTowerIndex].size() ==0) ) { 
        if ( curBlock != T(0) && (curBlock < targetMinBlock || T(0) == targetMinBlock ) ) { 
//#ifdef _DEBUG
            std::cout << towerName[sourceTowerIndex] << "-->" << towerName[targetTowerIndex] << " block=" << curBlock << std::endl;

//#endif
            towers[targetTowerIndex]->push(curBlock);
            towers[sourceTowerIndex]->pop();

            // 每次块移动之后,就改变方向
            towerDirect_shun = !towerDirect_shun;

            count++;
        } else {
            // 如果不能移动,那么在需要顺时针的情况下,顺时针移动到下一个塔
            // 如果不能移动,那么在需要逆时针的情况下,逆时针移动到下一个塔
            sourceTowerIndex = targetTowerIndex;
            // 恢复顺时针->逆时针的 顺序
            towerDirect_shun = adjustDirect;
            continue;
        } 
        // 如果不对奇数 偶数进行调整处理,就使用下面的判断方式
        //if ( towers[1].size() == iBlocks || towers[2].size() == iBlocks ) { 

        if ( towers[2]->size() == iBlocks ) { 
            break; 
        }
    };
}

Points of Interest


History

2008.04.01

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Solomon Wu
Software Developer (Senior)
China China
No Biography provided

Comments and Discussions

 
GeneralMy vote of 2 Pinmembersauravkabra21-Mar-09 23:40 
GeneralYour comments !!! PinmemberRedwan Al-Bougha22-Oct-08 15:03 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140922.1 | Last Updated 2 Apr 2008
Article Copyright 2008 by Solomon Wu
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid