15,962,891 members
Articles / Programming Languages / C++
Article

Hanoi Tower Non-Recursive computing

Rate me:
2 Apr 2008CPOL1 min read 151.3K   10   2
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

C++
``` // 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 towerDirect_shun;

if ( iBlocks % 2 ) { // 奇数块，使用逆时针->顺时针的 策略
towerDirect_shun = false;
} else {            // // 偶数块，使用顺时针->逆时针的 策略
towerDirect_shun = 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;
// 恢复顺时针->逆时针的 顺序
continue;
}
// 如果不对奇数 偶数进行调整处理，就使用下面的判断方式
//if ( towers[1].size() == iBlocks ||　towers[2].size() == iBlocks ) {

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

History

2008.04.01

Written By
Software Developer (Senior)
China
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.