hanyeah

之前用flash做了汉诺塔自动求解 。

阶数大了，flash计算太慢，所以用c语言写了一份。

代码如下：

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

struct Node;
struct Triangle;
typedef struct Node {
	char value;
	char fullValue[20];
	Triangle* triangle;

	Node* left;
	Node* right;
	Node* parent;
} Node;

typedef struct Triangle {
	Node* head;
	Node* left;
	Node* right;
} Triangle;

void nodeFlip(Node* node);
void nodeTurnLeft(Node* node);
void nodeTurnRight(Node* node);
void triFlip(Triangle* tri);
void triTurnLeft(Triangle* tri);
void triTurnRight(Triangle* tri);
Triangle* triClone(Triangle* source);
void nodeClone(Node* target, Node* source);
void nodePrepare(Node* node, char* pre);
void triPrepare(Triangle* tri, char* pre);
void nodeSetLeft(Node* node, Node* left);
void nodeSetLeft(Node* node, Node* left);
void appendChar(char* s, char c);

Triangle* pTri;

int getNum(int n) {
	if(n == 1){
		return 1;
	}
	return 1 + 3 * (getNum(n - 1));
}


void nodeFlip(Node* node){
	if(node->triangle != NULL){
		triFlip(node->triangle);
	}
}

void nodeTurnLeft(Node* node){
	if(node->triangle != NULL){
		triTurnLeft(node->triangle);
	}
}

void nodeTurnRight(Node* node){
	if(node->triangle != NULL){
		triTurnRight(node->triangle);
	}
}

void triFlip(Triangle* tri) {
	Node* temp = tri->left;
	tri->left = tri->right;
	tri->right = temp;

    nodeFlip(tri->head);
	nodeFlip(tri->left);
	nodeFlip(tri->right);
}

void triTurnLeft(Triangle* tri) {
	Node* temp = tri->head;
	tri->head = tri->right;
	tri->right = tri->left;
	tri->left = temp;

	nodeTurnLeft(tri->head);
	nodeTurnLeft(tri->left);
	nodeTurnLeft(tri->right);
}

void triTurnRight(Triangle* tri) {
	Node* temp = tri->head;
	tri->head = tri->left;
	tri->left = tri->right;
	tri->right = temp;

	nodeTurnRight(tri->head);
	nodeTurnRight(tri->left);
	nodeTurnRight(tri->right);
}

void nodeClone(Node* target, Node* source){
	target->value = source->value;
	if(source->triangle != NULL) {
		target->triangle = triClone(source->triangle);
	}
}

Triangle* triClone(Triangle* source){
	Triangle* tri = pTri++;

	nodeClone(tri->head, source->head);
	nodeClone(tri->left, source->left);
	nodeClone(tri->right, source->right);

	return tri;
}

Node* leafHead(Node* node){
	if(node->triangle == NULL){
		return node;
	}
	return leafHead(node->triangle->head);
}

Node* leafLeft(Node* node){
	if(node->triangle == NULL){
		return node;
	}
	return leafLeft(node->triangle->left);
}

Node* leafRight(Node* node){
	if(node->triangle == NULL){
		return node;
	}
	return leafRight(node->triangle->right);
}

void appendChar(char* s, char c){
	int len = strlen(s);
	s[len] = c;
	s[len + 1] = '\0';
}

void nodePrepare(Node* node, char* pre){
	strcpy(node->fullValue, pre);
	appendChar(node->fullValue, node->value);

	if(node->triangle != NULL){
		triPrepare(node->triangle, node->fullValue);
	}
}

void nodeSetLeft(Node* node, Node* left){
	node->left = left;
	left->parent = node;
}

void nodeSetRight(Node* node, Node* right){
	node->right = right;
	right->parent = node;
}

void triPrepare(Triangle* tri, char* pre){
	nodePrepare(tri->head, pre);
	nodePrepare(tri->left, pre);
	nodePrepare(tri->right, pre);

	nodeSetLeft(leafLeft(tri->head), leafHead(tri->left));
	nodeSetRight(leafRight(tri->head), leafHead(tri->right));
}

void nodeWalk(Node* node){
	if(node->left == NULL && node->right == NULL){
		do{
			printf("->");
			printf(node->fullValue);
			node = node->parent;
		} while(node != NULL);
		printf("\n");
		return;
	}
	if(node->left != NULL){
		nodeWalk(node->left);
	}
	if(node->right != NULL){
		nodeWalk(node->right);
	}
}

void nodeInit(Node* node){
	node->triangle = NULL;
	node->left = NULL;
	node->right = NULL;
	node->parent = NULL;
}

int main(int argc, char *argv[]){

	int a; 
	if(argc == 2){
		a = atoi(argv[1]);
		// printf("%d\n", a);
		// return 0;
	} else {
		printf("Please enter the Hanoi Tower order:");
		scanf("%d",&a); 
	}

	clock_t start,end;
    start = clock();

	int n = a;
	printf("%d\n", n);
	int m = getNum(n);
	printf("%d\n", m);

	Triangle tris[m];
	Node nodes[m*3];
	printf("%d\n", sizeof(tris));
	printf("%d\n", sizeof(nodes));
	pTri = tris;

	int j = 0;
	for(int i = 0; i < m; i++){
		Triangle* tri = &(tris[i]);
		tri->head = &(nodes[j]);
		tri->left = &(nodes[j+1]);
		tri->right = &(nodes[j+2]);
		j+=3;
		tri->head->value = 'C';
		tri->left->value = 'B';
		tri->right->value = 'A';

		nodeInit(tri->head);
		nodeInit(tri->left);
		nodeInit(tri->right);
	}


	Triangle* root = pTri++;

	for(int i = 1; i < n; i++) {
		Triangle* tri = pTri++;

		triFlip(root);
		tri->head->triangle = root;

		tri->left->triangle = triClone(root);
		triTurnRight(tri->left->triangle);

		tri->right->triangle = triClone(root);
		triTurnLeft(tri->right->triangle);

		root = tri;
	}

	triPrepare(root, "");
	Node* rNode = leafHead(root->head);
	nodeWalk(rNode);

	end = clock();
    double duration =(double)(end-start)/CLOCKS_PER_SEC;
    printf("use time:%f s\n",duration);

	return 0;
}

c语言写得少，可能写的不太好，但是c语言确实快。

附件中有代码，exe文件，和1-9阶汉诺塔的自动求解数据。

可以直接运行hanoi.exe，然后输入阶数；也可以直接带参数运行，如：hanoi.exe 5；如果要输出结果可以运行：hanoi.exe 5 >hanoi5.txt

源码打包下载