#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
#include <Windows.h>

/*柔性数组*/
typedef struct _soft_array{
	int len;
	int array[];
}soft_array;

/*汉诺塔结构体*/
typedef struct _hannuo{
	soft_array *p_data;
	char name;
}hannuo;

hannuo * han_a = NULL;
hannuo * han_b = NULL;
hannuo * han_c = NULL;

void hannoiii(int n,hannuo * a,hannuo * b,hannuo * c);
void moveiii (int n,hannuo * a,hannuo * c);

int count = 0;
int total;

void printf_han_data(hannuo * han)
{
	int i = 0;
	int j = 0;
	int tmp = 0;
	
	/*获取长度*/
	int n = han->p_data->len;
	soft_array *p_array = NULL;
	
	/*申请内存，赋值数据*/ 
	p_array = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
	memcpy(p_array,han->p_data,sizeof(soft_array)+sizeof(int)*n); 
	printf("%c: ",han->name);

	/*排序*/
	for(i = 0;i<n;i++)
	{
		for(j=0;j<n-1;j++)
		{
			if(p_array->array[j] > p_array->array[j+1])
			{
				tmp = p_array->array[j];
				p_array->array[j] = p_array->array[j+1];
				p_array->array[j+1] = tmp;
			}
		}
	}

	/*输出汉诺塔的数据*/
	for(i = 0;i<n;i++)
	{
		if(i != n-1)
			printf("%d-",p_array->array[i]);
		else
			printf("%d",p_array->array[i]);
	}
	
	/*释放内存*/
	if(p_array != NULL)
		free(p_array);
	printf("\n");
}


int main()
{
	int i = 0;
	int n = 0;

	scanf(" %d",&n);
	total = n;
	/*定义三个汉诺塔节点*/
	han_a = (hannuo *)malloc(sizeof(hannuo));
	han_a->name = 'A';
	han_a->p_data = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
	han_a->p_data->len = n;
	
	/*数据原来在第一根柱子上*/
	for(i = 0;i<n;i++)
	{
		han_a->p_data->array[i] = i+1;
	}
	printf_han_data(han_a);
	
	/*初始化第二根柱子*/
	han_b = (hannuo *)malloc(sizeof(hannuo));
	han_b->name = 'B';
	han_b->p_data = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
	memset(han_b->p_data,0,sizeof(soft_array)+sizeof(int)*n);
	han_b->p_data->len = n;
	printf_han_data(han_b);
	/*初始化第三根柱子*/
	han_c = (hannuo *)malloc(sizeof(hannuo));
	han_c->name = 'C';
	han_c->p_data = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
	memset(han_c->p_data,0,sizeof(soft_array)+sizeof(int)*n);
	han_c->p_data->len = n;
	printf_han_data(han_c);
	printf("初始化结束------------------------\n");
	
	hannoiii(n,han_a,han_b,han_c);
	
	/*清内存*/
	if(han_a != NULL)
		free(han_a);
	if(han_b != NULL)
		free(han_b);
	if(han_c != NULL)
		free(han_c);
	if(han_a->p_data != NULL)
		free(han_a->p_data);
	if(han_b->p_data != NULL)
		free(han_b->p_data);		
	if(han_c->p_data != NULL)
		free(han_c->p_data);
		
	scanf(" %d",&n);
	printf("Exiting main ....\n");
    return 0;
}

void hannoiii(int n,hannuo * a,hannuo * b,hannuo * c)
{
	if(n == 1)
	{
		moveiii(n, a, c);        /*把 n 从 a 移动到 c 上*/
		printf_han_data(han_a);
		printf_han_data(han_b);
		printf_han_data(han_c);
		printf("------------------------\n");
	}
	else
	{
		hannoiii(n - 1, a, c, b);/*把 n-1 从 a 柱子放到 b 柱子上面*/
        moveiii(n, a, c);        /*把 n 从 a 移动到 c 上*/
		printf_han_data(han_a);
		printf_han_data(han_b);
		printf_han_data(han_c);
		printf("------------------------\n");
        hannoiii(n - 1, b, a, c);/*把n - 1 通过 a 的辅助作用 从 b 移动到 c 上*/
	}
}

void moveiii (int n,hannuo * a,hannuo * c)
{
    int tmp = a->p_data->array[n-1];
	a->p_data->array[n-1] = 0;
	c->p_data->array[n-1] = tmp;
	count++;
	printf("第%d次移动 Move %d: 从 %c 位置 移动到 %c !\n",count,tmp,a->name,c->name);
}