Hanoi Tower 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 <iostream>
#include <deque>
#include <stdio.h>
#include <assert.h>

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