汉诺塔问题的与跳蚤问题.ppt

两个例子 学习目标 java中垃圾回收机制 递归定义 枚举 汉诺塔问题 跳蚤问题 复习提问 java中的访问修饰符共有哪几种访问权限，分别是什么？ * 高级访问控制总结 访问控制 private成员 缺省的成员 protected成员 public成员 同一类中成员 ? ? ? ? 同一包中其他类 × ? ? ? 不同包中子类 × × ? ? 不同包中非子类 × × × ? java的垃圾回收机制 垃圾回收作为一种内存管理技术已经存在了很长时间，但是java使它焕发出崭新的活力。在C++等语言中，内存必须人工管理，程序员必须显示地释放不再使用的对象。这是问题产生的根源，因为忘记释放不再使用的资源，或者释放了正在使用的资源都是很常见的事情。Java代替程序员完成了这些工作，从而防止了此类问题的发生。在java中，所有的对象都是通过引用访问的，这样，当垃圾回收器发现一个没有引用的对象时，就知道此对象已经不被使用，并且可以回收了。 * Java的垃圾回收具有以下特点： 只有当对象不再被程序中的任何引用变量引用时，它的内存才可能被回收。 程序无法迫使垃圾回收器立即执行垃圾回收操作。 当垃圾回收器将要回收无用对象的内存时，先调用该对象的finalize()方法，该方法用来释放对象所占的相关资源，但也有可能是对象复活，不再回收该对象的内存。 即使显式调用垃圾收集 (System.gc( )) 方法，它也不能保证立即运行。 垃圾收集线程的运行优先级很低所以可能经常会被中断 * java的垃圾回收机制 * 方法递归 所谓递归（recursion）在数学上就是利用自身结构来描述自己。例如： 自然数：1是一个自然数；一个自然数的后继者是一个自然数。 阶乘运算：0！=1；如果n0,那么n!=n*(n-1)!。 斐波纳契数列：f(0)=1,f(1)=1; f(n)=f(n-1)+f(n-2) 而在java语言程序设计中，在一个方法内部直接或间接地调用到自身，我们称之为递归。编写递归方法必须要满足以下三个条件： 知道递归公式的描述。 必须要有递归终止条件。 每次递归调用必须使得其进程逐步接近递归的终止条件。 枚举 枚举类型（enum type）是指由一组固定的常量组成合法的类型 用法 通常只在其中定义常量 有时可重写父类方法实现一些个性化功能 高级的用法可定义私有变量，添加私有的构造方法 例子: enum Color { RED, BLUE,YELLOW; } public void showColor(Color color){ switch (color){ case RED: System.out.println(it is red); break; case BLUE: System.out.println(it is blue); break; default: System.out.println(it is a default case for White); } } public static void main(String[] args) { Color color = Color.RED; color.showColor(color); } * 【程序建模示例1】Hanoi塔问题的递归解法 在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的６４片金片，这就是所谓的汉诺塔。不论白天黑夜，总有 一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 程序建模 汉诺塔问题的关键 hanoi(int n,char a,char b,char c) 解释：把a柱上的n个盘子以b柱为临时柱移到c柱上。 关键思路 总问题：把A柱上n个盘子以B柱为临时柱移到C柱上。 问题分解： 把A柱上前n-1个盘子以C柱为临时柱移到B柱上 把A柱上最底下一个盘子移到C柱上 把B柱上n-1个盘子以A柱为临时移到C柱上 分解示例 假设要将7个金片从A移到C,B为中转, 则: 首先将