hanyeah

很多人研究汉诺塔，都是作为递归算法的案例，都是从最左侧，移动到最右侧。

对于任意状态，如何自动求解，很少有人研究。

看到一篇文章，照着做了一下。

汉诺塔杂谈（二）——汉诺塔图 - 知乎 (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();
 }
 
 
}

算法写的不太好，功能实现了，比较慢，多了太卡。

欢迎大神分享好的算法。

源码打包下载