hanoitower1.cpp

上海交通大学研究生算法分析课的作业.实现了<<算法引论-一种创造性方法>>(Udi Manber 黄林鹏 电子工业出版社)第五章中的大部分算法

#include <iostream> 
#include <stdlib.h> 

#ifdef _WIN32 
using namespace std; 
#endif 

void hanoi(int height) 
{ 
    int fromPole, toPole, Disk;          //fromPole移动原柱子, toPole移动目标柱子, Disk盘号
    int *BitStr = new int[height],       
        *Hold   = new int[height];       
    char Place[]  = {'A', 'B', 'C'};     //标示柱子
    int i, j, temp; 
  
    for (i=0; i < height; i++)           //初始化状态
    { 
        BitStr[i] = 0; 
        Hold[i] = 1; 
    } 
    temp = 3 - (height % 2);             
    int TotalMoves = (1 << height) - 1;  //计算总移动次数，2^n-1
    for (i=1; i <= TotalMoves; i++) 
    { 
        for (j=0 ; BitStr[j] != 0; j++)  //找到 
        { 
            BitStr[j] = 0;               
        } 
        BitStr[j] = 1; 
        Disk = j+1; 
        if (Disk == 1) 
        { 
            fromPole = Hold[0]; 
            toPole = 6 - fromPole - temp; 
            temp = fromPole; 
        } 
        else 
        { 
            fromPole = Hold[Disk-1]; 
            toPole = 6 - Hold[0] - Hold[Disk-1]; 
        }        
		printf("将第 %i 盘子 从柱子%c 移动到 柱子%c\n",Disk,Place[fromPole-1],Place[toPole-1]);
        Hold[Disk-1] = toPole; 
    } 
} 

void main(int argc, char *argv[]) 
{ 
    printf("汉诺塔问题的非递归非栈算法(第一种实现方法)\n");
	printf("\n作者:茹炳晟(学号:1060379162)\n");
        
    printf("\n请输入汉诺塔的高度: ");
    int height; 
    scanf("%i",&height); 
    hanoi(height); 

    system("PAUSE"); 
}