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
#include <iostream>
#include <deque>
#include <stdio.h>
#include <assert.h>
using namespace std;
template<class T>
class Tower {
public:
std::deque<T> pillar;
public:
T top() {
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;
}
void Entry(int iBlocks,bool isRec) {
assert(iBlock>0);
const int TOWER_COUNT = 3;
typedef int Process_type;
Tower<Process_type> towers[TOWER_COUNT];
for(int i=iBlocks; i>0; --i) {
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'};
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 != T(0) && (curBlock < targetMinBlock || T(0) == targetMinBlock ) ) {
std::cout << towerName[sourceTowerIndex] << "-->" << towerName[targetTowerIndex] << " block=" << curBlock << std::endl;
towers[targetTowerIndex]->push(curBlock);
towers[sourceTowerIndex]->pop();
towerDirect_shun = !towerDirect_shun;
count++;
} else {
sourceTowerIndex = targetTowerIndex;
towerDirect_shun = adjustDirect;
continue;
}
if ( towers[2]->size() == iBlocks ) {
break;
}
};
}
Points of Interest
History
2008.04.01