＋设为首页 ＋添加到收藏夹
java/j2me/code/ target=_blank>程序设计中,有一种特殊的程序——递归程序,递归程序是直接调用自己或通过一系列的过程间接调用自己的程序.递归程序在程序设计中经常出现,因此应该学会使用递归程序求解问题,但递归程序运行的效率一般都比较低,因此应对递归程序进行优化.
一．递归程序的实现 【程序编程相关:区分引用类型和原始类型】
下面结合旅行家问题谈谈递归的优化. 【推荐阅读:合格的程序员】
要得到n个城市依次经历的最短路径,应把各个对n个城市的经历所经过的路程相比较,选出其中的最小值作为返回结果. 【扩展信息:Java故事】
旅行家问题如下:旅行家要旅行n个城市,要求各个城市经历且仅经历一次,并要求所走的路程最短.该问题又称为货郎担问题.邮递员问题.售货员问题,是有名的n—p难题之一.在n很大时,并不采用本文所用的递归遍历方法,而是采用其他方法,如神经网络.遗传算法等,得到问题的解.
用递归程序解决旅行家问题时,思路与循环方法一样:找出各种可能的经历顺序,比较在各个顺序下所走的路程,从中找出最短路程所对应的经历顺序.该问题中如何通过递归得到对所有可能路径的经历应作为重点,而对路程的计算.比较.更新与循环方法类似.在该问题的递归调用中,第n对第n-1层传递过来的已经经历的城市进行判断,以决定是否已经遍历,如果n个城市已经遍历,则计算.比较.更新路程,然后向上一层返回;如果没有遍历,则选择一个未经历的城市加入已经历的城市并一同传递给第n+1层.在这里,第n层调用传入的参数可以看成已经经历的城市与已确定的最短路程,返回的结果可以看成经更新的最短路程与经历顺序.
在java中定义一个类
classcities
... 下一页