A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 段玉超 中级黑马   /  2012-3-4 13:19  /  1420 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

汉诺塔问题 是典型的递归问题 ,通过递归算法解决非常的直观 ,而且使代码开起来十分的简介: 以下是根据用户输入塔的层数,程序输出 移动步骤的算法。
  1. import java.util.Scanner;

  2. public class TowersOfHanoi
  3. {
  4.         public static void main(String[] args)
  5.         {
  6.                 System.out.println("汉诺塔问题 ,请输入汉诺塔的用数字表示的层数,我们将告诉你如何做");
  7.                 Scanner input = new Scanner(System.in);
  8.                 int n = input.nextInt();

  9.                 moveDisks(n,'A','B','C');
  10.         }

  11.         private static void moveDisks(int n,char fromTower,char toTower,char auxTower){
  12.                 if(n==1){
  13.                         System.out.println("将盘子从"+fromTower+"移动到"+toTower);
  14.                 } else {
  15.                         moveDisks(n-1,fromTower,auxTower,toTower);
  16.                         System.out.println("将盘子从"+fromTower+"移动到"+toTower);
  17.                         moveDisks(n-1,auxTower,toTower,fromTower);
  18.                 }
  19.         }
  20. }
复制代码
但是递归是否意味着高效呢?递归的时间复杂度和空间复杂度如何衡量?  一个函数递归输出10000边 ”我爱××××××××××××××××××ד 和使用循环输出一千遍 同样的字符串,他们的时间复杂度与空间复杂度是一样的么?效率是一样的么?求解!

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马