本帖最后由 段玉超 于 2012-3-4 12:54 编辑
汉诺塔问题 是典型的递归问题 ,通过递归算法解决非常的直观 ,而且使代码开起来十分的简介: 以下是根据用户输入塔的层数,程序输出 移动步骤的算法。- import java.util.Scanner;
- public class TowersOfHanoi
- {
- public static void main(String[] args)
- {
- System.out.println("汉诺塔问题 ,请输入汉诺塔的用数字表示的层数,我们将告诉你如何做");
- Scanner input = new Scanner(System.in);
- int n = input.nextInt();
- moveDisks(n,'A','B','C');
- }
- private static void moveDisks(int n,char fromTower,char toTower,char auxTower){
- if(n==1){
- System.out.println("将盘子从"+fromTower+"移动到"+toTower);
- } else {
- moveDisks(n-1,fromTower,auxTower,toTower);
- System.out.println("将盘子从"+fromTower+"移动到"+toTower);
- moveDisks(n-1,auxTower,toTower,fromTower);
- }
- }
- }
复制代码 但是递归是否意味着高效呢?递归的时间复杂度和空间复杂度如何衡量? 一个函数递归输出10000边 ”我爱××××××××××××××××××ד 和使用循环输出一千遍 同样的字符串,他们的时间复杂度与空间复杂度是一样的么?效率是一样的么?求解! |
|