很多人研究汉诺塔，都是作为递归算法的案例，都是从最左侧，移动到最右侧。
对于任意状态，如何自动求解，很少有人研究。
看到一篇文章，照着做了一下。
汉诺塔杂谈（二）——汉诺塔图 - 知乎 (zhihu.com)
之前写过一个3阶，自动求解的。也是照着上面这篇文章，只不过是提前手动写好了路径，然后搜索路径。
汉诺塔
这里，参考上面的文章，用代码自动生成任意阶的汉诺塔的自动求解路径。
效果如下。
代码如下：
package {
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.MovieClip;
import flash.display.SimpleButton;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.KeyboardEvent;
import flash.events.MouseEvent;
import flash.events.TextEvent;
import flash.geom.Matrix;
import flash.geom.Rectangle;
import flash.net.FileReference;
import flash.system.System;
import flash.ui.Keyboard;
import flash.text.TextField;
import flash.utils.ByteArray;
import com.adobe.images.PNGEncoder;
public class HanoiGraph extends MovieClip {
public var tf: TextField;
public var btn1: SimpleButton;
public var btn2: SimpleButton;
public var btn3: SimpleButton;
public var btn4: SimpleButton;
private var con: Sprite;
private var graph: Graph;
private var path: Array;
public function HanoiGraph() {
// constructor code
con = new Sprite();
addChildAt(con, 0);
con.x = 400;
con.y = 400;
/*
graph = new Graph(3);
con.addChild(graph.print());
// trace(graph.getPath().join('\n'));
*/
/*
var xi: Number = 0;
var wi: Number = 0;
var t: Number = new Date().getTime();
for (var i: int = 1; i <= 4; i++) {
var g: Graph = new Graph(i);
var sp: Sprite = g.print();
sp.x = xi + wi / 2 + sp.width * 0.7 / 2;
wi = sp.width * 0.7;
xi += sp.x;
con.addChild(sp);
var pt: Array = g.getPath();
var tf0: TextField = new TextField();
tf0.text = pt.join('\n');
con.addChild(tf0);
tf0.x = sp.x - tf0.textWidth / 2;
tf0.y = sp.y + sp.height / 3;
tf0.width = tf0.textWidth;
tf0.height = tf0.textHeight;
}
trace("用时:" + (new Date().getTime() - t) + 'ms');
*/
// var node:Node = new Node("A");
// con.addChild(node.print());
//var tri: Triangle = new Triangle();
//con.addChild(tri.print());
stage.addEventListener(MouseEvent.MOUSE_WHEEL, mouseWheelHandler);
stage.addEventListener(MouseEvent.MOUSE_DOWN, mouseDownHandler);
stage.addEventListener(MouseEvent.MOUSE_UP, mouseUpHandler);
btn1.addEventListener(MouseEvent.CLICK, onClickHandler);
onClickHandler(null);
btn2.addEventListener(MouseEvent.CLICK, onExport1Handler);
btn3.addEventListener(MouseEvent.CLICK, onExport2Handler);
btn4.addEventListener(MouseEvent.CLICK, onClipBoardHandler);
}
private function onClipBoardHandler(e:MouseEvent):void
{
System.setClipboard(path.join('\n'));
}
private function onExport2Handler(e:MouseEvent):void
{
var bmp: Bitmap = drawSp(con.getChildAt(0) as Sprite);
saveToLocal(bmp.bitmapData);
}
private function onExport1Handler(e:MouseEvent):void
{
var bmp: Bitmap = drawSp(con);
saveToLocal(bmp.bitmapData);
}
private function saveToLocal(bmd: BitmapData): void {
try{
var bytes: ByteArray = PNGEncoder.encode(bmd);
var fs: FileReference = new FileReference();
if(fs['save'])fs['save'](bytes, 'hanoi-' + tf.text + '.png');
} catch (e: Error){
}
}
private function drawSp(sp: Sprite): Bitmap {
var bmd: BitmapData = new BitmapData(sp.width, sp.height);
var rect: Rectangle = sp.getBounds(sp);
bmd.draw(sp, new Matrix(1, 0, 0, 1, -rect.x, -rect.y), null, null, null, true);
var bmp: Bitmap = new Bitmap(bmd);
return bmp;
}
private function onClickHandler(e:MouseEvent):void
{
var n: int = parseInt(tf.text);
if (isFinite(n) && n > 0) {
createN(n);
}
}
private function createN(n: int): void {
while (con.numChildren){
con.removeChildAt(0);
}
var t: Number = new Date().getTime();
var g: Graph = new Graph(n);
var sp: Sprite = g.print();
con.addChild(sp);
var pt: Array = g.getPath();
var tf: TextField = new TextField();
tf.text = pt.join('\n');
con.addChild(tf);
tf.x = -tf.textWidth / 2;
tf.y = sp.height / 3;
tf.width = tf.textWidth;
tf.height = tf.textHeight;
trace("用时:" + (new Date().getTime() - t) + 'ms');
path = pt;
}
private function mouseUpHandler(e:MouseEvent):void
{
con.stopDrag();
}
private function mouseDownHandler(e:MouseEvent):void
{
if (e.target == tf || e.target == btn1 || e.target == btn2 || e.target == btn3 || e.target == btn4){
return;
}
con.startDrag();
}
private function mouseWheelHandler(e:MouseEvent):void
{
con.scaleX = con.scaleY = con.scaleX * (1 + e.delta * 0.05);
}
}
}
import flash.display.DisplayObjectContainer;
import flash.display.Graphics;
import flash.display.Sprite;
import flash.geom.Point;
import flash.text.TextField;
class Graph {
public var root: Triangle;
public function Graph(n: int){
root = new Triangle();
for (var i: int = 1; i < n; i++){
var tri:Triangle = new Triangle();
var hrad: Triangle = root.clone().flip();
tri.head.triangle = hrad;
tri.left.triangle = hrad.clone().turnRight();
tri.right.triangle = hrad.clone().turnLeft();
root = tri;
}
}
public function print(): Sprite {
return root.print('');
}
public function getPath(): Array {
var arr: Array = [];
root.prepare();
var node: Node = root.head.leafHead();
node.walk(function(no: Node){
// trace(no.fullVale);
var a:Array = [];
do{
a.push(no.fullVale);
}while (no = no.parent)
arr.push(a.join('->'));
});
return arr;
}
}
class Triangle {
public var head: Node;
public var left: Node;
public var right:Node;
public var r: Number = 100;
public var view: Sprite;
public function Triangle(){
head = new Node("B");
left = new Node("A");
right = new Node("C");
turnLeft(); // 和之前手写的一致
view = new Sprite();
}
public function clone(): Triangle {
var tri:Triangle = new Triangle();
tri.head = head.clone();
tri.left = left.clone();
tri.right = right.clone();
return tri;
}
public function flip(): Triangle {
var t: Node = right;
right = left;
left = t;
head.flip();
right.flip();
left.flip();
return this;
}
public function turnRight(): Triangle {
var t: Node = head;
head = left;
left = right;
right = t;
head.turnRight();
left.turnRight();
right.turnRight();
return this;
}
public function turnLeft(): Triangle {
var t: Node = head;
head = right;
right = left;
left = t;
head.turnLeft();
left.turnLeft();
right.turnLeft();
return this;
}
public function prepare(pre: String = ''): void {
head.prepare(pre);
left.prepare(pre);
right.prepare(pre);
head.leafLeft().left = left.leafHead();
head.leafRight().right = right.leafHead();
//
}
public function print(pre: String = ''):Sprite {
var sp: Sprite = view;
var spHead: Sprite = head.print(pre);
var spLeft: Sprite = left.print(pre);
var spRight: Sprite = right.print(pre);
sp.addChild(spHead);
sp.addChild(spLeft);
sp.addChild(spRight);
var r0: Number = left.r;
r = r0 * 2;
var a0: Number = r0 * Math.sqrt(3);
spHead.x = 0;
spHead.y = -r;
spLeft.x = -a0;
spLeft.y = r0;
spRight.x = a0;
spRight.y = r0;
if (!head.triangle){
sp.graphics.lineStyle(1, 0.000000, 1.0);
sp.graphics.moveTo(head.view.x, head.view.y);
sp.graphics.lineTo(left.view.x, left.view.y);
sp.graphics.lineTo(right.view.x, right.view.y);
sp.graphics.lineTo(head.view.x, head.view.y);
} else {
var pArr: Array = [
head.leafLeft().view,
left.leafHead().view,
head.leafRight().view,
right.leafHead().view,
left.leafRight().view,
right.leafLeft().view
];
sp.graphics.lineStyle(1, 0.000000, 1.0);
for (var i: int = 0; i < pArr.length; i += 2){
var p0: Point = toLocal(pArr[i]);
var p1: Point = toLocal(pArr[i + 1]);
sp.graphics.moveTo(p0.x, p0.y);
sp.graphics.lineTo(p1.x, p1.y);
}
}
return sp;
}
private function toLocal(sp: Sprite): Point{
var p:Point = new Point();
while (sp != view){
p.x += sp.x;
p.y += sp.y;
sp = sp.parent as Sprite;
}
return p;
}
}
class Node {
public var value: String;
public var triangle: Triangle;
public var r: Number = 50;
public var view: Sprite;
public var fullVale: String = '';
public var parent: Node;
private var _left:Node;
private var _right: Node;
public function Node(v: String){
value = v;
view = new Sprite();
}
public function get left(): Node {
return this._left;
}
public function set left(no: Node): void {
this._left = no;
no.parent = this;
}
public function get right(): Node {
return this._right;
}
public function set right(no: Node): void {
this._right = no;
no.parent = this;
}
public function clone(): Node {
var no: Node = new Node(value);
if (triangle) {
no.triangle = triangle.clone();
}
return no;
}
public function flip():void {
if (triangle){
triangle.flip();
}
}
public function turnRight():void {
if (triangle){
triangle.turnRight();
}
}
public function turnLeft():void {
if (triangle){
triangle.turnLeft();
}
}
public function prepare(pre: String): void {
fullVale = pre + value;
if (triangle) {
triangle.prepare(fullVale);
}
}
public function walk(callback: Function): void {
if (!left && !right){
callback(this);
} else {
if (left){
left.walk(callback);
}
if (right) {
right.walk(callback);
}
}
}
public function print(pre: String = ''): Sprite {
var sp: Sprite = view;
if (triangle) {
var spTri: Sprite = triangle.print(pre + value);
sp.addChild(spTri);
r = triangle.r;
} else {
var tf:TextField = new TextField();
sp.addChild(tf);
tf.text = pre + value;
tf.x = -tf.textWidth / 2;
tf.y = -tf.textHeight / 2;
r = tf.textWidth * 0.8;
sp.graphics.lineStyle(1, 0x000000, 1.0);
sp.graphics.beginFill(0xfffffff, 1.0);
sp.graphics.drawCircle(0, 0, r);
sp.graphics.endFill();
}
return sp;
}
public function leafHead(): Node {
if (!triangle) {
return this;
}
return triangle.head.leafHead();
}
public function leafLeft(): Node {
if (!triangle) {
return this;
}
return triangle.left.leafLeft();
}
public function leafRight(): Node {
if (!triangle) {
return this;
}
return triangle.right.leafRight();
}
}算法写的不太好，功能实现了，比较慢，多了太卡。
欢迎大神分享好的算法。
发表评论:
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。