前段时间学习算法方面的知识看了一下用C语言写的一些简单的算法自己用js模拟实现一遍现在整理出来和大家分享一下。
河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时
北越的首都，即现在的胡志明市；1883年法国数学家Edouard Lucas曾提及这个故事，据说创世
纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64
个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根
石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬
运完毕之时，此塔将毁损，而也就是世界末日来临之时。
let hanoi = function(n,a,b,c){
if( n == 1 ){
console.log( n,a,c )
}else{
hanoi( n -1 ,a,b,c );
console.log( n,a,c );
hanoi( n-1,b,a,c );
}
}
hanoi( 3,'a','b','c' );
Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到：「若有一只免子每个月生一只小免
子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三
只免子，三个月后有五只免子（小免子投入生产）......。
如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生
产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例
如以下： 1、1 、2、3、5、8、13、21、34、55、89......
//递归
let fibonacci = function(n){
if( n == 1 || n == 2 ) return 1;
return fibonacci(n - 1 ) + fibonacci( n - 2 );
}
// console.log( fibonacci(10) );
//非递归
let fib = function(n){
//第i项为前两项之和
var res = [1,1];
if( n == 1 || n ==2 ){
return 1;
}
for( var i = 2; i < n; i++ ){
res[i] = res[i - 1] + res[i - 2];
}
return res[n - 1];
}
console.log( fib( 5 ) );
巴斯卡三角形
let combi = function (n,r){
var i,p = 1;
for( i=1; i<= r;i++ ){
p = p* ( n - i + 1 )/i;
}
return p;
}
let paint = function(N){
var n,r,t;
for( n = 0;n <= N; n++ ){
for( r = 0;r <= n;r++ ){
//排版设定开始
if( r == 0 ){
var i;
for( i = 0;i <= (N - n);i++ ){
document.write(" ");
}
}else{
document.write(" ");
}//排版设定结束
document.write(combi(n,r));
}
document.write( "<br/>" );
}
}
paint( 5)
console.log( "%30d",5 );
AlgorithmGossip:三色棋
三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰
人)，而多数的作者则使用Three-Color Flag来称之。
假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您
希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上
进行这个动作，而且一次只能调换两个旗子。
//交换函数
let swap = function(obj,x,y){
var temp = obj[x];
obj[x] = obj[y];
obj[y] = temp;
}
let threeColorFlags = function(){
var color = ['r','w','b','w','w','b','r','b','w','r'];
var leftColor = 'b';
var rightColor = 'r';
var lindex = 0,rindex = color.length - 1;
for( var i = 0 ; i <= rindex;i++ ){
if( color[i] == leftColor){
swap( color,lindex,i );
lindex++;
}else if ( color[i] == rightColor ){
while( rindex > i ){
if( color[rindex] == rightColor){
rindex--;
}else{
break;
}
}
swap( color,rindex,i );
rindex--;
i--;
}
}
console.log( color );
}
threeColorFlags();