import java.util.LinkedList; import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MoveAction; import com.sun.corba.se.spi.orbutil.fsm.State; import com.sun.org.apache.xpath.internal.functions.Function; /** * 递归算法,递归的非递归替代算法 * */ public class TestRecursion { // 题目:计算给定文本内字符“a”的个数。分别用迭代和递归两种方式。 /** * 常规算法 */ public int countACommon(String str) { int count = 0; String tmpString = str; while (tmpString.indexOf("a") >= 0) { count++; tmpString = tmpString.substring(tmpString.indexOf("a") + 1); } return count; } /** * 递归算法 */ public int countARecursion(String str) { String tmpStr = str; if (tmpStr.indexOf("a") < 0) return 0; // 递归退出条件 else return countARecursion(tmpStr.substring(tmpStr.indexOf("a") + 1)) + 1; } /** * 斐波那契数列 项,非递归(速度快,求第10000项毫无压力) */ public int f(int n) { if (n < 1) return 0; if (n == 1) return 1; if (n == 2) return 1; int i, s = 0; int s1 = 1, s2 = 1; for (i = 3; i <= n; i++) { s = s1 + s2; s2 = s1; s1 = s; } return s; } /** * 单向递归是指递归算法中虽然有多处递归调用语句, * 但各递归调用语句的参数之间没有关系, * 并且这些递归调用语句都处在递归算法的最后。显然,尾递归是单向递归的特例。 * 斐波那契数列 项,递归(求第100项时就扛不住了) * 1 1 2 3 5 8 13 */ public int f2(int n) { if (n < 1) return 0; if (n == 1) return 1; if (n == 2) return 1; return f2(n - 2) + f2(n - 1); } /** * 求阶乘,非递归,最大求31,超过31!,int就不够用了 * @param n * @return */ public int factorial(int n) { if (n < 0) return 0; if (n == 0) return 1; if (n == 0) return 1; int s = 1; for (int i = 1; i <= n; i++) { s = s * i; } return s; } /** * 求阶乘,递归算法,最大求31,超过31!,int就不够用了 * @param n * @return */ public int factorial_R(int n) { if (n < 0) return 0; if (n == 0) return 1; if (n == 0) return 1; return n * factorial_R(n - 1); } /** * 汉诺塔,递归算法(将A上面的盘子,借助B,移动到C上面) * @param n 需要移动的盘子个数 * @param A 盘子所在的原始位置 * @param C 盘子的目标位置 * @param B 移动盘子借助的位置 */ public void hanoi_R(int n, String A, String B, String C) { if(n == 1) move(n,A,C); //只有一个盘子,直接移 else { hanoi(n - 1,A,C,B); // 先将n-1个盘子,从A移动到B,借助C move(n,A,C); //将最后一个盘子 直接 从A移动到目标位置C,此时A空下来,B上面有n-1个盘子 hanoi(n-1,B,A,C); //将B上面的n-1个盘子,借助A,移动到C } } private void move(int n,String from ,String to) { //System.out.println("move " + n + ": " + from + " --> " + to); } /** * 非递归算法,使用栈,HanoiItem栈对象,以保存相关中间信息 */ class HanoiItem { public int count; //可以直接移动的盘子的编号 public boolean flag = false; //flag = true 说明可以直接移动 public String currentPlace; //当前位置 public String assistantPlace; //辅助位置 public String destinationPlace; //目标位置 public HanoiItem(int count,boolean flag,String currentPlace,String assistantPlace,String destinationPlace) { this.count = count; this.flag = flag; //只有一个盘子表示可以直接移动 if(count==1) this.flag = true; //重要: 如果只有一个盘子,表示可以直接移动 this.currentPlace = currentPlace; this.assistantPlace = assistantPlace; this.destinationPlace = destinationPlace; } public void move() { //System.out.println("move " + this.count + ": " + currentPlace + " --> " + destinationPlace); } } /** * 将初始状态s0进栈 * while (栈不为空) * { * 退栈,将栈顶元素赋给s; * if (s是要找的结果) 返回; * else * { * 寻找到s的相关状态s1; * 将s1进栈; * } * } * */ public void hanoi(int n, String A, String B, String C) { if(n == 1) move(n,A,C); //只有一个盘子,直接移 else { //初始化一个栈,LinkedList可以当栈使用 LinkedList<HanoiItem> stack = new LinkedList<HanoiItem>(); HanoiItem initHanoi = new HanoiItem(n, false, A, B, C); stack.push(initHanoi); //将初始状态s0进栈 while(stack.size()>0) //while (栈不为空) { HanoiItem tempItem = stack.pop(); //退栈,将栈顶元素赋给s; if(tempItem.flag) //if (s是要找的结果) 返回; { tempItem.move(); } else //寻找到s的相关状态s1; 这里相关的状态有三个 { //表示需要将上面的n-1个盘子 借助于 目标位置 ,整体先移动到 中间(协助用)的 杆子 HanoiItem ItemBefore = new HanoiItem(tempItem.count - 1,false,tempItem.currentPlace,tempItem.destinationPlace,tempItem.assistantPlace); //表示将最后一个盘子移动到目标位置 HanoiItem itemCurr = new HanoiItem(tempItem.count,true,tempItem.currentPlace,tempItem.assistantPlace,tempItem.destinationPlace); //表示将 前面已经移动到中间杆子上的盘子,借助第一个杆子 移动到 目标位置 HanoiItem itemAfter = new HanoiItem(tempItem.count -1,false,tempItem.assistantPlace,tempItem.currentPlace,tempItem.destinationPlace); //将上面三个中间状态入栈,注意顺序,栈先进后出,所以入栈顺序要反过来 stack.push(itemAfter); stack.push(itemCurr); stack.push(ItemBefore); } } } } public static void main(String[] args) { String tmpString = "aaa"; TestRecursion test = new TestRecursion(); System.out.println(test.countACommon(tmpString)); System.out.println(test.countARecursion(tmpString)); System.out.println(test.factorial_R(5)); //递归汉诺塔 long s1 = System.currentTimeMillis(); test.hanoi_R(15,"A","B","C"); long e1 = System.currentTimeMillis(); System.out.println(e1 - s1); //移动,10层,0,15层 16, 20层,140,25层 3547, 30层 112830 //非递归 System.out.println("-----------------------------------"); long s2 = System.currentTimeMillis(); test.hanoi(15,"A","B","C"); long e2 = System.currentTimeMillis(); System.out.println(e2 - s2); //移动10层 16, 15层 16, 20层 110,25层 3453,30层 114596, //貌似因为递归使用了太多的中间对象,而且LinkedList效率貌似不高 } } //递归: 移动,10层 0, 15层 16, 20层 140, 25层 3547, 30层 112830 //非递归: 移动 10层 16, 15层 16, 20层 110, 25层 3453, 30层 114596,
相关推荐
对于那些为数不多的、主要具有理论研究价值的算法,通常还给出其实用的替代算法。 如果希望实现这些算法中的任何一个,就会发现,将书中的伪代码翻译成读者熟悉的某种程序设计语言,是一件相当直接的事。伪代码被...
对于那些为数不多的、主要具有理论研究价值的算法,通常还给出其实用的替代算法。 如果希望实现这些算法中的任何一个,就会发现,将书中的伪代码翻译成读者熟悉的某种程序设计语言,是一件相当直接的事。伪代码被...
目的:测试用于快速计算部分跟踪操作的算法及其基准。 结果:部分跟踪是昂贵的。 在数学上优雅的解决方案中,广泛的张量整形是不可避免的。 实现更复杂的算法涉及较少的浮点运算,但无法利用线性代数的硬件加速。 ...
1、递归算法之输出某个目录下所有文件和子目录列表 2、泛型中extends和super的区别 3、内部类的理解 4、深入理解Java的反射机制 5、深入理解Java异常体系 6、谈谈NIO的理解 7、谈一谈对JUC的理解 8、ArrayList的底层...
遗传算法的自适应代沟的替代策略研究.pdf 异步电机定子电流的内模自适应控制及实现.pdf 用PID梯度算法训练基于神经网络的广义非线性PID控制器.pdf 支持向量机多专家决策算法.pdf 最优加权系数的神经优化方法.pdf
遗传算法的自适应代沟的替代策略研究.pdf 金融数据挖掘中的非线性相关跟踪技术(英文).caj 非线性控制系统的近似化方法.pdf 非线性时延对象的神经网络控制.pdf 非线性系统的鲁棒采样最优控制.pdf 非线性系统鲁棒控制...
遗传算法的自适应代沟的替代策略研究.pdf 金融数据挖掘中的非线性相关跟踪技术(英文).caj 非线性控制系统的近似化方法.pdf 非线性时延对象的神经网络控制.pdf 非线性系统的鲁棒采样最优控制.pdf 非线性系统鲁棒控制...
遗传算法的自适应代沟的替代策略研究.pdf 金融数据挖掘中的非线性相关跟踪技术(英文).caj 非线性控制系统的近似化方法.pdf 非线性时延对象的神经网络控制.pdf 非线性系统的鲁棒采样最优控制.pdf 非线性系统鲁棒控制...
起初,我觉得这是一个非常单调乏味的过程,只是在没有替代方法来获取信息的情况下才不得已使用它。后来,一霎那间我破除了某个思维障碍,我发现自己迅速地“驰骋”于无正式文献记录的机器码中,快速地破译了代码的...
2.1.1只使用非递归的mutex . . . . . . . . . . . . . .. . . . . . . . . . 33 2.1.2死锁. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 35 2.2条件变量(condition variable). . . . . . ....