MyException - 我的异常网
当前位置:我的异常网» JavaScript » 基于JavaScript的递归算法题跟动态规划题目

基于JavaScript的递归算法题跟动态规划题目

www.MyException.Cn  网友分享于:2013-11-16  浏览:0次
基于JavaScript的递归算法题和动态规划题目

前记:

这世界上总存在着那么一些看似相似但有完全不同的东西,比如雷锋和雷峰塔,玛丽和马里奥,Java和javascript….当年javascript为了抱Java大腿恬不知耻的让自己变成了Java的干儿子,哦,不是应该是跪舔,毕竟都跟了Java的姓了。可如今,javascript来了个咸鱼翻身,几乎要统治web领域,Nodejs,React Native的出现使得javascript在后端和移动端都开始占有了一席之地。

之前已经有同学讲过了递归和动态规划之间的关系。今天,我们就再来温习一遍。简单的讲述一下递归和动态规划的一些题目。今天主要就是它们是如何用JavaScript来实现的!打破常规,不单单是能用C和JAVA来a题。也能让我们这些学习前端的同学好好的使用JS来A题。

递归算法

递归的定义:

程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

简单来说:递归算法,是将问题转化为规模缩小的同类问题的子问题,每一个子问题都用一个同样的算法去解决。一般来说,一个递归算法就是函数调用自身去解决它的子问题

递归的特点:

             1)递归就是方法里调用自身。   
             2)在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。    
             3)递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
             4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等,所以一般不提倡用递归算法设计程序。

例题1:

小试牛刀:汉诺塔

"汉诺塔"是印度的一个古老传说,也是程序设计中的经典的递归问题,是一个著名的益智游戏:

  题目如下:

    塔上有三根柱子和一套直径各不相同的空心圆盘,开始时源柱子上的所有圆盘都按从大到小的顺序排列。目标是通过每一次移动一个圆盘到另一根柱子上,最终把一堆圆盘移动到目标柱子上,过程中不允许把较大的圆盘放置在较小的圆盘上。

规律:

  1)n(圆盘个数) == 1

    第一次:1号盘  A -> C      sum(移动次数) = 1

  2)n == 2

    第一次:1号盘 A -> B

    第二次:2号盘 A -> C

    第三次:1号盘 B -> C  sum = 3

  3)n == 3

    第一次:1号盘 A -> C

    第二次:2号盘 A -> B

    第三次:1号盘 C -> B

    第四次:3号盘 A -> C

    第五次:1号盘 B -> A

    第六次:2号盘 B -> C

    第七次:1号盘 A -> C  sum = 7

  以此类推...

  故不难发现规律,移动次数为:sum = 2^n - 1 

 

分析:

  把一堆圆盘从一个柱子移动另一根柱子,必要时使用辅助的柱子。可以把它分为三个子问题:

    首先,移动一对圆盘中较小的圆盘到辅助柱子上,从而露出下面较大的圆盘,

    其次,移动下面的圆盘到目标柱子上

    最后,将刚才较小的圆盘从辅助柱子上在移动到目标柱子上

   把三个步骤转化为简单数学问题:

    (1)     把 n-1个盘子由A 移到 B;

    (2)     把 第n个盘子由 A移到 C;

    (3)     把n-1个盘子由B 移到 C;

  我们创建一个JS函数,当它调用自身的时候,它去处理当前正在处理圆盘之上的圆盘。最后它回一个不存在圆盘去调用,在这种情况下,它不在执行任何操作

下面上JS代码:

/*汉诺塔函数*/
		function hanoi(disc,src,aux,dst){
		    if(disc>0){
		        hanoi(disc-1,src,dst,aux);
		        console.log(' 移动 '+ disc +  ' 号圆盘 ' + ' 从 ' + src +  ' 移动到 ' +  dst);
		        // hanoi(disc,src,aux,dst); // 栈溢出
		        hanoi(disc-1,aux,src,dst)
		    }
		}

 

 例题2:

    走楼梯:(问题描述)

    楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶或者3阶,计算共有多少种不同的走法?(注意,例如:3阶楼梯4种方法:1. 一步一步一步 2.一步两步 3.三步 4.两步一步)

 

 分析:

这其实就是一个斐波那契数列的一种实现。我们分析的时候,可以转化成小规模的子类问题。当到达指定阶梯的最后一步的时候,可以有三种种情况,一是上一步,二是上两步,三是上三步。所以总的方法是F(n) = F(n-1) + F(n-2) + F(n-3)。然后自然就成了各自的小计算,不断循环下去,直到判断条件的发生。

下面上代码

/*走楼梯问题*/
		function getMethods(n) {
			if (n <= 0) {
				return 0;
			}
			if (n <= 1) {
				return 1;
			}
			if (n <= 2) {
				return 2;
			}
			if (n <= 3) {
				return 4;
			}
			return arguments.callee(n-1) + arguments.callee(n-2) + arguments.callee(n-3);
		}
console.log(getMethods(5));

 注意:argument.callee

 

在函数内部,有两个特殊的对象:arguments 和 this。其中, arguments 的主要用途是保存函数参数, 但这个对象还有一个名叫 callee 的属性,该属性是一个指针,指向拥有这个 arguments 对象的函数。一般来说,它会和匿名函数一起结合来用。但是不建议使用,因为访问 arguments 是个很昂贵的操作,因为它是个很大的对象,每次递归调用时都需要重新创建。影响现代浏览器的性能,还会影响闭包。

例题3:(具有JS特色的递归)

DOM树的递归:(问题描述)

获取一个节点的所有父节点的tagName

比较简单就直接上代码了:

/*DOM树的递归问题*/
		var arr = [];  
		function getParent(node) {  
		    node = node.parentNode;  
		    if (node.tagName) {  
		        arr.push(node.tagName);  
		        getParent(node);  
		    }  
		}  
		getParent(document.getElementById("node"));  
		console.log(arr); 

 到此呢,递归就告一段落,希望大家能有更深的理解。虽然题目都是最基本的,但是我们通过打断点,能发现这个代码执行的步骤,也理解什么时候该执行什么。便于我们理解吧!

 

动态规划:

动态规划也是五大常用算法之一(贪婪算法,动态规划,分治算法,回溯,分支限界)。

基本思想:

它的思想就是把一个大的问题进行拆分,细分成一个个小的子问题,且能够从这些小的子问题的解当中推导出原问题的解。同时还需要满足以下两个重要性质才能进行动态规划

  • 最优子结构性: 既所拆分的子问题的解是最优解。

  • 子问题重叠性质: 既在求解的过程当中,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的解题效率

我认为,上面讲的楼梯问题,也算是动态规划的一种,自底向上,只考虑这0阶楼梯,1阶楼梯,2阶楼梯,3阶楼梯。总方案数都是由,0种方案,1种方案,2种方案,4种方案这四个数字加起来的。话不多说,我们看一个例子吧。

例子1:

最长公共子串:

问题描述:什么是最长公共子串呢?举个简单的例子吧,一个数列S,若分别是两个或多个已知序列的子序列,且是所有符合条件序列中最长的,则S称为已知序列的最长公共子串。

举例:比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB,它们的长度都是2

解决方法:

蛮力法:即对S的每一个子序列,检查是否为T的子序列,从而确定它是否为S和T的公共子序列,并且选出最长的公共子序列。指数级别的时间复杂度o(2^n*2^m)n和m代表两个序列的长度。

当然,我们也可以使用动态规划的方法!

动态规划方法的分析:

  1. 假设两个字符串分别为s和t,s[i]t[j]分别表示其第i和第j个字符(字符顺序从0开始),再令L[i, j]表示以s[i]t[j]为结尾的相同子串的最大长度。应该不难递推出L[i, j]L[i+1,j+1]之间的关系,因为两者其实只差s[i+1]t[j+1]这一对字符。若s[i+1]t[j+1]不同,那么L[i+1, j+1]自然应该是0,因为任何以它们为结尾的子串都不可能完全相同;而如果s[i+1]t[j+1]相同,那么就只要在以s[i]t[j]结尾的最长相同子串之后分别添上这两个字符即可,这样就可以让长度增加一位。合并上述两种情况,也就得到L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0)这样的关系。

    最后就是要小心的就是临界位置:如若两个字符串中任何一个是空串,那么最长公共子串的长度只能是0;当i0时,L[0,j]应该是等于L[-1,j-1]再加上s[0]t[j]提供的值,但L[-1,j-1]本是无效,但可以视s[-1]是空字符也就变成了前面一种临界情况,这样就可知L[-1,j-1]==0,所以L[0,j]=(s[0]==t[j]?1:0)。对于j0也是一样的,同样可得L[i,0]=(s[i]==t[0]?1:0)

下面上代码:
<script type="text/javascript">
                /*最长子串*/
		var str1="abcdefghijklname123what";  
		var str2="defghiwhatisyourname";  
		var L=[];//备忘录 记录L[i][j]最大长度子串L[i][j]=max(L[i-1][j-1]+1,0)  
		getMaxSubStr();  
		function getMaxSubStr(){  
		   for (var i=0;i<str1.length+1;i++)  
		   {  
		     L[i]=[];  
		     L[i][0]=0;  
		   }  
		   for (var j=0;j<str2.length+1;j++ )  
		   {   
		     L[0][j]=0;  
		   }  
		   var max=-1;  
		   var x=-1;  
		   var y=-1;  
		   for (var i=1;i<str1.length+1;i++ )  
		   {  
		      for (var j=1;j<str2.length+1;j++ )  
		      {  
		         //alert(str1[i-1]+":"+str2[j-1]);  
		         if(str1.charAt(i-1)==str2.charAt(j-1)){  
		            L[i][j]=L[i-1][j-1]+1;  
		         }  
		         else{  
		            L[i][j]=0;  
		         }  
		           
		         //document.write(L[i][j]);  
		         if(L[i][j]>max){  
		            max=L[i][j];  
		            x=i-1;  
		            y=j-1;  
		            document.write("i="+i+";j="+j+";max="+max+"<br/>");  
		         }  
		      }  
		   }  
		   //输出共同的子串  
		   var str=[];  
		   while(x>=0&&y>=0){  
		      if(str1.charAt(x)==str2.charAt(y)){  
		         str[--max]=str1.charAt(x);  
		         x--;  
		         y--;  
		      }  
		      else  
		         break;  
		   }  
		   var str_out="";  
		   for (var i=0;i<str.length;i++ )  
		   {  
		     str_out+=str[i];  
		   }  
		   document.write(str_out);  
		} 
	</script>
 到这呢,基本就结束了。
 有什么意见请多批评指教!

文章评论

要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
10个调试和排错的小建议
10个调试和排错的小建议
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员应该关注的一些事儿
程序员应该关注的一些事儿
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
中美印日四国程序员比较
中美印日四国程序员比较
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
Java程序员必看电影
Java程序员必看电影
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
鲜为人知的编程真相
鲜为人知的编程真相
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
漫画:程序员的工作
漫画:程序员的工作
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
一个程序员的时间管理
一个程序员的时间管理
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
我是如何打败拖延症的
我是如何打败拖延症的
如何成为一名黑客
如何成为一名黑客
我的丈夫是个程序员
我的丈夫是个程序员
总结2014中国互联网十大段子
总结2014中国互联网十大段子
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员必看的十大电影
程序员必看的十大电影
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员都该阅读的书
程序员都该阅读的书
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
旅行,写作,编程
旅行,写作,编程
 程序员的样子
程序员的样子
为什么程序员都是夜猫子
为什么程序员都是夜猫子
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
编程语言是女人
编程语言是女人
那些争议最大的编程观点
那些争议最大的编程观点
每天工作4小时的程序员
每天工作4小时的程序员
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有