stack_hanoi.html

---
title: '栈的应用--递归解决汉诺塔问题(交互式介绍)'
date: 2016-9-23 17:00:00
tags: ['栈', '递归', 'Interactive']
---

<style>
	p {
		/*text-indent: 2em;*/
	}
	svg {
		display: block;
		margin: auto;
	}
	select {
		display: block;
	}
	.grid line{
		stroke-dasharray: 2 2;
		stroke: rgba(0,0,0,0.5);
		stroke-width: 2;
	}
	.canvas_wrapper {
		text-align: center;
	}
</style>
<p>递归是一种自己调用自己的的算法，常见的递归就是斐波那契。</p>
<pre>1 2 3 5 8 13 21 ...</pre>
<p>下一个数等于前两个数之和。</p>
<p>我们来看看这个算法如何实现：</p>
<pre>
function fibonacci(n) {
	if(n == 1) {
		return 1
	} else if(n == 2) {
		return 2
	} else {
		return fibonacci(n - 1) + fibonacci(n - 2)
	}
}
</pre>
<div class="divider"></div>
<p>下面的这个交互式的svg图像就是形象的绘画斐波那契是如何工作的，如何进行递归的：</p>
<p><strong>记住<code>Fobi(1) == Fibo(2) == 1</code></strong></p>
<form class="form form-horizontal">
	<div class="form-group col-md-9">
		<label class="col-md-8 control-label">请输入你想获得第几个斐波那契数：</label>
		<div class="col-md-4">
			<select id="num" class="form-control">
				<option value="3">3</option>
				<option value="4">4</option>
				<option value="5">5</option>
				<option value="6">6</option>
				<option value="7">7</option>
				<option value="8">8</option>
			</select>
		</div>
	</div>
	<div class="form-group col-md-2">
		<button class="btn btn-primary" id="spawn">生成树</button>
	</div>
</form>
<svg id="svg" width="700" height="700" viewbox="0 0 700 700" xmlns="http://www.w3.org/2000/svg">
	<defs>
		<path id="tree" d="m 0,0 l5,0 s20,0,20,-20 l0,-35 s0,-20,20,-20 M5,0 s20,0,20,20 l0,35 s0,20,20,20" stroke-width="2" stroke="blue" fill="none"/>			
	</defs>
	<text x="0" y="15" fill="black">图形ID:1</text>
	<g id="graphics">
	</g>
</svg>
<p>递归介绍完毕。当然还有很多递归的例子，比如雪花，数字的排序方法也会用到递归，后期我会介绍。</p>
<div class="divider"></div>
<p>接下来我们讨论下汉诺塔的问题：</p>
<p>我们先来简单看下汉诺塔的形状：</p>
<div class="hanoiShape">
	<svg width="400" height="200" xmlns="http://www.w3.org/2000/svg">
		<defs>
			<rect id="pillar" x="0" y="0" width="20" height="80"/>
		</defs>
		<text x="0" y="15" fill="black">图形ID:2</text>
		<g id="pillars">
			<use xlink:href="#pillar" x="125" y="60" fill="green" />
			<text x="129" y="60" fill="red">A</text>
			<use xlink:href="#pillar" x="190" y="60" fill="skyblue" />
			<text x="194" y="60" fill="red">B</text>
			<use xlink:href="#pillar" x="255" y="60" fill="purple" />
			<text x="259" y="60" fill="red">C</text>
		</g>
		<g id="foundation">
			<rect x="80" y="140" width="240" height="20" fill="blue" />
		</g>
	</svg>
</div>
<p>由上图我们可以看到有三个柱子，我们在<strong>A</strong>柱子上放<strong>N</strong>个盘子，下面的最大，往上递减。</p>
<p>我们将这<strong>N</strong>个金片从<strong>A</strong>借助<strong>B</strong>移动到<strong>C</strong>，移动的时候大的盘子不能覆盖小的盘子。</p>
<p>我们从最简单的开始，假设我们只有一个盘子，Easy，直接移动到<strong>C</strong>就可以了。</p>
<p>这是处于最简单的汉诺塔状态：</p>
<div class="canvas_wrapper one_dish">
	<canvas width="400" height="200" id="one_dish"></canvas><br>
	<button class="btn green darken-1 z-depth-4">移动</button>
</div>
<p>一个似乎有点太简单了，我们加一个，两个盘子，我们就需要借助辅助的柱子<strong>B</strong>。</p>
<p>我们先来看看两个盘子的动画演示：</p>
<div class="canvas_wrapper two_dish">
	<canvas width="400" height="200" id="two_dish"></canvas><br>
	<button class="btn green darken-1 z-depth-4">移动</button>
</div>
<pre><code>Hanoi(2, A, B, C) >> 这代表我们将两个盘子从<strong>A</strong>借助<strong>B</strong>移动到<strong>C</strong></code></pre>
<p>我们既然要满足大的不能覆盖小的，我们需要先把最大的盘子上面的盘子移到辅助的柱子<strong>B</strong>上面，此时我们的要求就变成现在的样子：</p>
<pre><code>Hanoi(1, A, C, B) >> 这代表我们将一个盘子从<strong>A</strong>借助<strong>C</strong>移动到<strong>B</strong></code></pre>
<p>我们将最大的上面的盘子移动到辅助的柱子(<strong>B</strong>)上面之后我们就可以移动最大的到目标柱子<strong>C</strong>上面。</p>
<pre><code>源柱子&nbsp;<strong>A</strong>&nbsp;上面最大的盘子 >> 目标柱子&nbsp;<strong>C</strong>&nbsp;</code></pre>
<p>除了最大的盘子之外的盘子都在辅助的柱子(<strong>B</strong>)上面，接下来，我们的要求又成了将辅助柱子<strong>B</strong>上面的所有盘子移动到<strong>C</strong>。</p>
<pre><code>Hanoi(1, B, A, C) >> 这代表我们将一个盘子从<strong>B</strong>借助<strong>A</strong>移动到<strong>C</strong></code></pre>
<p><strong>看到了么，我们的要求是那么的相似。</strong></p>
<p>我们可以来个更复杂的了(我不详细解释，仔细看动画)：</p>
<div class="canvas_wrapper five_dish">
	<canvas width="400" height="200" id="five_dish"></canvas><br>
	<button class="btn green darken-1 z-depth-4">移动</button>
</div>
<pre><code>
	//栈的构造函数
	function Stack() {
		var items = []
		this.push = function(element) {
			items.push()
		}
		this.pop = function() {
			return items.pop()
		}
		this.peek = function() {
			return items[items.length]
		}
		this.isEmpty = function() {
			return items.length == 0
		}
		this.size = function() {
			return items.length
		}
	}
	var A = new Stack()
	var B = new Stack()
	var C = new Stack()

	A.push(1)
	A.push(2)
	A.push(3)
	A.push(4)
	A.push(5)

	function Hanoi(n) {
		if(n > 0) {
			Hanoi(n - 1, A, C, B)
			C.push(A.pop());
			Hanoi(n - 1, B, A, C)
		}
	}
</code></pre>
<script src="http://code.createjs.com/easeljs-0.7.1.min.js"></script>
<script src="http://cdn.bootcss.com/gsap/latest/TweenMax.min.js"></script>
<script>
function Stack() {
	var items = []
	this.push = function(element) {
		items.push(element)
	}
	this.pop = function() {
		return items.pop()
	}
	this.peek = function() {
		return items[items.length - 1]
	}
	this.isEmpty = function() {
		return items.length == 0
	}
	this.size = function() {
		return items.length
	}
}
// 从匿名函数中暴露出来的函数  模块化处理
var jx_module = {};
/****************************************svg处理**********************************************/
(function() {
	function gridSvg(element) {
		const blockSize = 50
		//计算网格
		var width = element.getAttribute('width')
		var height = element.getAttribute('height')
		// console.log("%cwidth:" + width + ",%cheight:" + height, "color:red", "color:white")
		var horizontal = Math.ceil(height / blockSize)
		var vertical = Math.ceil(width / blockSize)
		// 创建网格组
		var group = document.createElementNS('http://www.w3.org/2000/svg', 'g')
		var horiLine = document.createElementNS('http://www.w3.org/2000/svg', 'line')
		// 水平网格
		horiLine.setAttribute('x1', 0)
		horiLine.setAttribute('y1', 2)
		horiLine.setAttribute('x2', width)
		horiLine.setAttribute('y2', 2)
		group.appendChild(horiLine)
		group.setAttribute('class', 'grid')
		for(var i = 1; i < horizontal; i++) {
			var horiLine = document.createElementNS('http://www.w3.org/2000/svg', 'line')
			horiLine.setAttribute('x1', 0)
			horiLine.setAttribute('y1', i * blockSize)
			horiLine.setAttribute('x2', width)
			horiLine.setAttribute('y2', i * blockSize)
			group.appendChild(horiLine)
		}
		var horiLine = document.createElementNS('http://www.w3.org/2000/svg', 'line')
		horiLine.setAttribute('x1', 0)
		horiLine.setAttribute('y1', height - 2)
		horiLine.setAttribute('x2', width)
		horiLine.setAttribute('y2', height - 2)
		group.appendChild(horiLine)
		group.setAttribute('class', 'grid')
		// 水平网格结束
		// 垂直网格
		var vertiLine = document.createElementNS('http://www.w3.org/2000/svg', 'line')
		vertiLine.setAttribute('x1', 2)
		vertiLine.setAttribute('y1', 0)
		vertiLine.setAttribute('x2', 2)
		vertiLine.setAttribute('y2', height)
		group.appendChild(vertiLine);
		for(var i = 1; i < vertical; i++) {
			var vertiLine = document.createElementNS('http://www.w3.org/2000/svg', 'line')
			vertiLine.setAttribute('x1', i * blockSize)
			vertiLine.setAttribute('y1', 0)
			vertiLine.setAttribute('x2', i * blockSize)
			vertiLine.setAttribute('y2', height)
			group.appendChild(vertiLine);
		}
		var vertiLine = document.createElementNS('http://www.w3.org/2000/svg', 'line')
		vertiLine.setAttribute('x1', width - 2)
		vertiLine.setAttribute('y1', 0)
		vertiLine.setAttribute('x2', width - 2)
		vertiLine.setAttribute('y2', height)
		group.appendChild(vertiLine);
		// 垂直网格结束
		element.appendChild(group);
	}
	var svg = document.getElementById('svg')
	gridSvg(svg)

	var graphics = document.getElementById('graphics')
		/*
		 *@param coordinate Array 坐标[x,y]
		 *@param height Number 分支的高度
		 *@param direction String 确定是上支还是下支（某一个分支的，而不是整体的）
		 *@return          Array 计算好的坐标
		 */
		function caculateCoordinate(coordinate, height, direction) {
			var horizontal = coordinate[0] + 100
			var vertical = (direction == "up") ? (coordinate[1] - height / 2) : (coordinate[1] + height / 2)
			return [horizontal, vertical]
		}
		function fibonacci_1(m, n, coordinate, height) {
			if(n <= 2) {
				return 
			} else {
				/*
				 *私有变量 m 代表现在是属于第几竖列，从0开始计数
				 *私有变量 n 代表当前的分支上应该显示的数字
				 *私有变量 coordinate 代表当前的环境的坐标
				 *私有变量 height 代表当前的环境的高度 320 160 80 40 20 10
				 */
				var m = m
				var n = n
				var coordinate = coordinate
				var height = 320 / Math.pow(2, m)
				graph_1(m, n, coordinate, height)
				fibonacci_1(m + 1, n - 1, caculateCoordinate(coordinate, height, "up"), height / 2)
				fibonacci_1(m + 1, n - 2, caculateCoordinate(coordinate, height, "down"), height / 2)
			}

		}
		function graph_1(m, n, coordinate, height) {
			console.log("m:" + m + ",n:" + n + ",coordinate:" + coordinate + ",height:" + height)
			// 缩放比例
			var scale = height / 150
			//上分支的文字的偏移量
			var upTextX = coordinate[0] + 45
			var upTextY = coordinate[1] - height / 2
			//下文字的偏移量
			var downTextX = coordinate[0] + 45
			var downTextY = coordinate[1] + height / 2
			// 每个树枝的缩放的中心点应该是开始绘画的点
			var transformOrigin = `${coordinate[0]}px ${coordinate[1]}px`
				var html = `
			<g>
				<use xlink:href="#tree" x="${coordinate[0]}" y="${coordinate[1]}" style="transform: scaleY(${scale});transform-origin: ${transformOrigin};"/>
				<!-- 上分支 -->
				<text x="${upTextX}" y="${upTextY}" textLength="55px" text-anchor="left" dominant-baseline="middle">Fibo(${n - 1})</text>
				<!-- 下分支 -->
				<text x="${downTextX}" y="${downTextY}" textLength="55px" text-anchor="left" dominant-baseline="middle">Fibo(${n - 2})</text>
			</g>`
				// console.log(m);
				graphics.innerHTML = graphics.innerHTML + html;
		}

		// fibonacci_1(0, 5, [45, 250])

		/*2016-9-25 10:30:00
		 *不辜负这两天的奋斗，终于将问题解决，下面谈谈思路
		 *1.第一次尝试解决问题，我使用判断上支还是下支的方法来解决，
		 *  但是这是一个树形结构，无论我怎么去传参数判断该支属于上支还是下支
		 *  树形结构是无限延展的，而我的参数不能无限传参，因此我无法判断该支到底属于上支
		 *  还是属于下支，有时候参数的数量会影响生效的数量，比如3，4，5正常，到了6就会出现
		 *  我无法预知的情况，所以这种方法行不通
		 *2.经过一夜的思考，第二种方法出来了，我决定根据上一个分支坐标来确定
		 *  当前分支的坐标，这样分支的坐标是相对的，每一个分支的坐标根据上一个分支的坐标
		 *  和高度来确定，
		 *  我在递归的时候将所有的私有变量全部保存到函数中，并且不再在函数内破坏
		 *  需要改变参数的时候在传递的时候改变而不是在函数内部改变，这样可以保持当前函数
		 *  的所有私有变量在递归回来的时候和进去的时候一样
		 *  并且在我根据上一个坐标来计算下一个坐标的时候，用字符串确定该分支应该是在上一个
		 *  分支高度的上半部分还是下半部分
		 */


		var spawn = document.getElementById('spawn')
		spawn.onclick = function(e) {
		 	var num = document.getElementById('num').value
		 	e.preventDefault()
		 	graphics.innerHTML = ""
		 	graphics.innerHTML = `
				<text x="0" y="350" textLength="55px" text-anchor="left" dominant-baseline="middle">Fibo(${num})</text>
		 	`
		 	fibonacci_1(0, num, [45, 350])
		}
		//将该方法暴露出去
		jx_module.fibonacci_1 = fibonacci_1
})()
/****************************************svg处理结束**********************************************/
/****************************************canvas处理**********************************************/
//这也是匿名函数的写法  有点像C语言
void function(){
	/*
	 *@param id String canvas的ID，也就是舞台的ID
	 *@param n Number 要进行几个盘子的动画
	 *@param controlElement HTMLButtonElement 控制动画的button元素 
	 */
	function hanoi(id, n, controlElement, imgNum) {
		//draw main stage ←-----------------------------------------------←
		var stage = new createjs.Stage(id) 								//|
		// draw base       												//|
		var base = new createjs.Shape 									//|
		base.graphics.beginFill('red').drawRect(40, 150, 320, 10)       //|
		// let base into main stage  -------------------------------------↑
		stage.addChild(base)
		//draw graphics ID
		var graphicsID = new createjs.Text(`图形ID:${imgNum}`, '16px Arial', '#000000')
		graphicsID.x = 0
		stage.addChild(graphicsID)
		//pillars Container
		var pillars = new createjs.Container
		pillars.x = 40
		pillars.y = 150
		//built pillar
		for(let i = 0; i < 3; i++) {
			let pillar = new createjs.Shape
			let pillarNum = String.fromCharCode(65 + i) //动态生成柱子序号  Unicode码 65--A 66--B 67--C 
			let numObject = new createjs.Text(pillarNum, '14 px Arial', 'black')
			numObject.x = 50 + i * 105 + 1
			numObject.y = -100
			pillar.graphics.beginFill('green').drawRect(50 + i * 105, -90, 10, 90)
			pillars.addChild(numObject)
			pillars.addChild(pillar)
		}
		//let pillars into stage
		stage.addChild(pillars)
		//-----------draw dish-------------------
		//盘子的栈
		var dishsStack = [
			new Stack,
			new Stack,
			new Stack
		]
		var dishsArray = [];
		var dishs = new createjs.Container
		dishs.x = 95
		dishs.y = 150
		for(let i = 0; i < n; i++) {
			let color = 'rgb(' + Math.round(Math.random() * 255) + ',' + Math.round(Math.random() * 255) + ',' +Math.round(Math.random() * 255) + ')' 
			let dish = new createjs.Shape
			dish.graphics.beginFill(color).drawRect(0, 0, 100 - 10 * i, 10)
			dish.x = 0
			dish.y = -10 * i
			dish.regX = (100 - 10 * i) / 2
			dish.regY = 10
			dishsStack[0].push(dish)
			dishsArray.push(dish)
			dishs.addChild(dish)
		}
		stage.addChild(dishs)
		//-----------draw dish end-------------------
		// 更新舞台
		stage.update()
		console.log(pillars, dishsArray, controlElement, dishsStack[0].size())
		//------以上属于绘画舞台，接下来进行动画的绘画
		function animate() {
			stage.update()
			requestAnimationFrame(animate)
		}
		var delay = -2.0
		function moveHanoi(n, a, b, c) {
			if(n > 0) {
				moveHanoi(n - 1, a, c, b)
				var dish = dishsStack[a].pop()
				var resourceX = a * 105
				var targetX = c * 105
				var targetY = -10 * dishsStack[c].size()
				var tl = new TimelineLite({
					delay: delay += 2
				})
				tl.append(TweenLite.to(dish, .5, {
					y: -100
				}))
				tl.append(TweenLite.to(dish, 1, {
					bezier: [
						{
							x: (resourceX + targetX) / 2,
							y: -120
						},{
							x: targetX,
							y: -100
						}
					]
				}))
				tl.append(TweenLite.to(dish, .5, {
					y: targetY
				}))
				dishsStack[c].push(dish)
				moveHanoi(n - 1, b, a, c)
			}
		}
		function restart() {
			delay = -2.0
			dishsStack = [
						new Stack,
						new Stack,
						new Stack
					]
			dishs.removeAllChildren();
			for(let i = 0; i < n; i++) {
				let color = 'rgb(' + Math.round(Math.random() * 255) + ',' + Math.round(Math.random() * 255) + ',' +Math.round(Math.random() * 255) + ')' 
				let dish = new createjs.Shape
				dish.graphics.beginFill(color).drawRect(0, 0, 100 - 10 * i, 10)
				dish.x = 0
				dish.y = -10 * i
				dish.regX = (100 - 10 * i) / 2
				dish.regY = 10
				dishsStack[0].push(dish)
				dishsArray.push(dish)
				dishs.addChild(dish)
			}
		}
		controlElement.onclick = function() {
			restart()
			animate()
			moveHanoi(n, 0, 1, 2)
		}
	}

	jx_module.hanoi = hanoi;
}()
/****************************************canvas处理结束**********************************************/


jx_module.hanoi('one_dish', 1, document.querySelector('.one_dish button'), 3)
jx_module.hanoi('two_dish', 2, document.querySelector('.two_dish button'), 4)
jx_module.hanoi('five_dish', 5, document.querySelector('.five_dish button'), 5)
</script>