hanoi.cpp

奇妙的汉诺塔

// hanoi.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "conio.h"
#include "stdlib.h"

#define DISH_MAXN 64

int stack[3][DISH_MAXN];
static int COVER=1<<(sizeof(int)*8-1);

int pow2(int n)
{
	return 1<<n;
}

void stack_init(int n)
{
	int i,j;
	
	for(i=0;i<3;i++)
		for(j=0;j<DISH_MAXN;j++)
			stack[i][j]=65;

	for(i=n;i>=1;i--)
		stack[0][n-i+1]=i;

	stack[0][0]=n-1;
	stack[1][0]=0;
	stack[2][0]=0;
	stack[0][n]=65;

	if(n%2==0)
	{
		stack[1][0]=1;
		stack[1][1]=1;
		printf("\nA->B");
	}
	else
	{
		stack[2][0]=1;
		stack[2][1]=1;
		printf("\nA->C");
	}
}

 
int dish_no(int n)
{ 
	int i,p;
	p=n^(n-1);

	for(i=1;i<=sizeof(int)*8;i++)
		if(((p<<i) & COVER)!=0)
			break;

	return sizeof(int)*8-i;
}
 
int pin_source(int b_s)
{
	int i;
	
	for(i=0;i<3;i++)
		if(stack[i][stack[i][0]]==b_s) 
			return i;

	return -1;
}

int pin_target(int b_s,int p_s)
{
	int i,temp1,temp2;
	
	if(b_s>1)
		for(i=0;i<3;i++)
		{
			if((p_s!=i)&&( stack[p_s][stack[p_s][0]]<stack[i][stack[i][0]])||stack[i][0]==0)
				return i;
			else if(p_s!=i)
				return 3-i-p_s;
		}
	else if(b_s==1)
	{
		temp1=-1;
		temp2=-1;

		for(i=0;i<3;i++)
		{
			if(stack[i][0]!=0&&stack[i][stack[i][0]]%2==0) 
				temp1=i;
			if(stack[i][0]==0) 
				temp2=i;
		}

		if(temp1!=-1)
			return temp1;
		else if(temp2!=-1)
			return temp2;
		else
			exit(0);
	}
}

void move(int p_s,int p_t)
{
	int n;
	
	++stack[p_t][0];
	n=stack[p_s][0];
	--stack[p_s][0];
	stack[p_t][stack[p_t][0]]=stack[p_s][n];
	stack[p_s][n]=65;
}

int main()
{ 
	int i,b_s,p_s,p_t,n;
	
	printf("\nEnter number of disks:");
	scanf("%d",&n);
	stack_init(n);
	
	for(i=2;i<pow2(n);i++)
	{
		b_s=dish_no(i);
		p_s=pin_source(b_s);
		p_t=pin_target(b_s,p_s);
		move(p_s,p_t);
		printf("\n%c->%c",p_s+'A',p_t+'A');
	}
	getch();
}