hanoitower2.cpp

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

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

#ifdef _WIN32 
using namespace std; 
#endif 

void DoStep(int vHeight,int vStep)   //根据hanoi的高度vHeight，第几步vStep，算出盘号、源柱号和标柱号
{
	int sDisk;                       //盘号
	for (int i = 1; i <= vHeight ; i++ )	//计算盘号
	{
		if (vStep % (1 << i) == (1 << (i - 1)))
		{
			sDisk = i;
			break;
		}
	}

	int sGroup = vStep % 3;     //分为3组

	bool sReverse;			    //柱号是否反序标志	
	if (sGroup == 2)			//计算反序标志
	{
		sReverse = (sDisk % 2) == 0;
	}
	else
	{
		sReverse = (sDisk % 2) == 1; 
	}

	char sPlace[] = { 'B', 'C','A', 'B', 'A', 'C',		//hanoi的高度分奇偶两组，每组再分3组，的柱号标示
	                  'C', 'B','A', 'C', 'A', 'B'};

	if (sReverse)										//输出
	{
		printf("将第 %i 盘子 从柱子%c 移动到 柱子%c\n",
		sDisk,sPlace[sGroup * 2 + (vHeight % 2) * 6],sPlace[sGroup * 2 + 1 + (vHeight % 2) * 6]);
	}
	else
	{
		printf("将第 %i 盘子 从柱子%c 移动到 柱子%c\n",
	    sDisk,sPlace[sGroup * 2 + 1 + (vHeight % 2) * 6],sPlace[sGroup * 2 + (vHeight % 2) * 6]);
	}
} 

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

	int sTotalMoves = (1 << height) - 1;     //sTotalMoves是总移动次数，等于2^n-1
    for (int i=1; i <= sTotalMoves; i++) 
    { 
		DoStep(height, i); 
	}

    system("PAUSE"); 
}