add algorithm

xuwenmin · xuwenmin · commit a9b058c1aa49 · 2014-08-28T22:09:51.000+08:00
diff --git a/_posts/JavaScript/2014-08-29-一个计算数字的步数算法.md b/_posts/JavaScript/2014-08-29-一个计算数字的步数算法.md
@@ -0,0 +1,124 @@
+---
+layout: post
+category : JavaScript
+tagline: ""
+tags : [算法]
+---
+{% include JB/setup %}
+
+这两天看了下某位大神的github,知道他对算法比较感兴趣,看了其中的一个计算数字的步数算法,感觉这个有点意思,所以就自己实现了一个
+
+### 算法描述与实现原理
+
+给出一个整型数字,统计出有多少种走法可以到达目标,比如一个数字`4`,可以有下面几种走法
+
+```html
+
+	[ 1, 3 ]
+		[ 4 ]
+	[ 1, 1, 2 ]
+		[ 2, 2 ]
+	[ 1, 1, 1, 1 ]
+
+```
+其实通过上面的组合可以得出下面的结论
+
+* 先列出所有项是1的组合
+
+* 依次从左到右项为1的组合
+
+* 递归上面的集合,找出项里1的索引,然后计算左起2项的值,结果递归此操作
+
+* 排队1和2的情况
+
+下面先提供两个工具函数
+
+```js
+
+// 计算数组内的值
+function calculate(arg){
+	return eval(arg.join('+'));
+}
+
+// 输出数组的值
+function print(arg){
+	for(var i = 0; i < arg.length; i++){
+		console.log(arg[i]);
+	}
+}
+
+```
+
+下面贴出算法的实现
+
+```js
+function countSteps(n){
+	var counts = 0,i,j = 0;
+	var result = [];
+	var newresult = [];
+	var source = [];
+	var temparg = [];
+	// 生成项全为1的数组
+	for(i = 1; i <= n ; i++){
+		source.push(1);
+	}
+	if(n > 2){
+		for(j = 1; j < n - 1; j++){
+			temparg.length = 0;
+			if(j < n - 1){
+				// 生成从左到右项为1递增的数组
+				// 1.. 11.. 111..
+				Array.prototype.push.apply(temparg, source.slice(0, j));
+				temparg.push(calculate(source.slice(j,n)));
+				result.push(temparg.slice(0));
+				// 递归数组里的内容,直到项里没有1为止
+				combine(temparg.slice(0));
+			}
+		}
+	}
+	// 组合包含1的数组项
+	// 111->21->3
+	function combine(arg){
+		var linearg = [];
+		for(var i = 0; i < arg.length; i++){
+			if(arg[i] == 1){
+				if(i ==0 || i == 1){
+					linearg.push(calculate(arg.slice(0,2)));
+					Array.prototype.push.apply(linearg, arg.slice(2, arg.length));
+					result.push(linearg);
+					js1(linearg.slice(0));
+					return;
+				}
+				
+			}
+		}
+	}
+	//为2的时候比1要多一项
+	if(n == 2){
+		result.push([2]);
+	}
+	// 添加全为1的情况
+	result.push(source);
+	// 输出所有步
+	print(result);
+	console.log('总共有:' + result.length + '种走法');
+}
+
+// 运行
+countSteps(4);
+
+// 输出下面内容
+/*
+	[ 1, 3 ]
+	[ 4 ]
+	[ 1, 1, 2 ]
+	[ 2, 2 ]
+	[ 1, 1, 1, 1 ]
+	总共有:5种走
+*/
+
+```
+
+### 总结
+
+这个算法其实可以应用到某类游戏中去,当两个物体之前的距离一定的话,对所有的可能进行业务处理,当然也可以应用到别的地方,虽然大部分前端工程师对算法的实践比较少,不过它还是有存在的价值的,很多UI细节方面其实都运用了算法,以后有空还会贴更多关于算法相关的文章,欢迎大家多提些宝贵意见.
