随笔 - 47  文章 - 15  trackbacks - 0
<2020年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

因为口渴,上帝创造了水;
因为黑暗,上帝创造了火;
因为我需要朋友,所以上帝让你来到我身边
Click for Shaanxi xi'an, Shaanxi Forecast
╱◥█◣
  |田|田|
╬╬╬╬╬╬╬╬╬╬╬
If only I have such a house!
〖总在爬山 所以艰辛〗
Email:myesjoy@yahoo.com.cn
NickName:yesjoy
MSN:myesjoy@hotmail.com
QQ:150230516

〖总在寻梦 所以苦痛〗

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

Hibernate在线

Java友情

Java认证

linux经典

OA系统

Spring在线

Structs在线

专家专栏

企业信息化

大型设备共享系统

工作流

工作流产品

网上购书

搜索

  •  

最新评论

阅读排行榜

评论排行榜

转自:http://www.blogjava.net/dengyin2000/archive/2006/03/12/34902.html
大学的数据结构和算法根本就是混过来的,某天在某某论坛里有个关于数据结构和算法到底在日常的编程到底有多大的用处。对于我来说,我并不觉得我用上了那些讲的数据结构和算法。Java Collection Framework已经跟我们做了这些。我已经能非常熟练的使用Collection里面的类库。但是我们用的基本上都是那些线性集合(堆栈,队列,列表,Set),非线性集合(树,堆,散列和图)我感觉比较少用到。我也主要是想对非线性集合做一些比较。线性集合比较简单。

 

 第一章到第九章都是讲线性集合, 也比较容易理解, 在这里就忽略掉。第十章是讲递归算法。我对这章比较感兴趣,用递归实现某个算法真的感觉非常优雅,代码短而少,许多非线性集合都是用递归来实现的。但也有他的缺点, 对方法的每次递归调用都会生成新的局部变量和局部参数。假如递归层次太多的话,就会消耗太多的stack

 

任何递归定义都必须有一个非递归部分;这个非递归部分叫做基本情况,它使的递归跳出无穷循环递归。

Ex 1 1~N的累加过程,数值1N的累加可以看成是1N1的累加加上N

 

       public int sum(int num){

              
int result = 0;

              
if (num == 1){

                     
return 1;

              }


              
return result + num + sum(num - 1);

       }

 

这里的基本情况就是但num==1的时候。 当然这个可以不用递归来处理,用一个for就行了(而且比用递归更直观)。我们必须能判断什么时候使用递归,什么时候不使用递归,所有问题都可以使用迭代(for循环)解决问题。不过有些情况下,迭代方式过于复杂,对某些问题,递归可以写出短小而优雅的代码。

 

 

直接递归和间接递归,方法调用自己,这就是直接递归(如上个例子)。方法调用另一个方法,最终导致再调用原方法。这就是间接递归。

 

河内塔问题(Towers of Hanoi)(可以上网找找这个经典问题的描述)

规则:

l         一次只能移动一张圆盘

l         不能将大盘放在小盘的上方

l         除了那张在柱子之间搬动的圆盘之外,所有圆盘都必须在某根柱子上

 

策略:

l         将最上方的N1张圆盘从最初的柱子移到那根多处的柱子上

l         将最大的圆盘从最初的柱子移动到最终的柱子上

l         再将那个多出柱子上的N1张圆盘移到最终的柱子上

 

public      class TowersOfHanoi{

              
private int totalDisks;

              
// ------------------------------------------------------

              
// Sets up the puzzle with the specified number of disks

              
// ------------------------------------------------------

              
public TowersOfHanoi(int disks){

                     
this.totalDisks = disks;

              }


              
// ----------------------------------------------------------

              
// Performs the initial call to moveTower to solve the puzzle.

              
// Moves the disks from tower 1 to tower 3 using tower 2

              
// ----------------------------------------------------------

              
public void solve(){

                     moveTower(totalDisks, 
13,2);

              }


              
// -----------------------------------------------------------------

              
// Moves the specified number of disks from one tower to another by 

              
// moving a subtower of n-1 disks out of the way, moving one disk, 

              
// then moving the subtower back, Base case of 1 disk.

              
// -----------------------------------------------------------------

              
private void moveTower(int numDisks, int start, int end, int temp) {

                     
if (numDisks == 1){

                            moveOneDisk(start, end);

                     }
else{

                            moveTower(numDisks
-1, start, temp, end);

                            moveOneDisk(start, end);

                            moveTower(numDisks
-1, temp, end, start);

                     }


              }


              
private void moveOneDisk(int start, int end) {

                     System.out.println(
"Move one disk from " + start + " to " + end);

              }


       }

posted on 2007-06-19 15:20 ★yesjoy★ 阅读(237) 评论(0)  编辑  收藏 所属分类: 算法总结

只有注册用户登录后才能发表评论。


网站导航: