a2水 Lecture8 8-1 数据结构 与 算法 30m Programming in Java JAVA
8-1 Programming in Java 数据结构 与 算法 Lecture8
a2水 提纲 8-2 ·算法 >递归算法 >排序算法 ·数据结构 >链表 >队列 >堆栈 >树 Programming in Java JAVA
8-2 Programming in Java 提纲 • 算法 ➢递归算法 ➢排序算法 • 数据结构 ➢ 链表 ➢ 队列 ➢堆栈 ➢ 树
递阳 8-3 递归是常用的编程技术，实现技术为直接或间接 地调用自身的方法 ·递归算法的步骤： >求得范围缩小的同性质问题的结果 >利用已得到的结果和一个简单的操作求得问题的最 后解答 >例如：求n的阶乘n! ·递归算法的主要内容： •定义递归头 •定义如何从同性质的简化问题求得当前问题 AVA
8-3 Programming in Java 递归 • 递归是常用的编程技术，实现技术为直接或间接 地调用自身的方法 • 递归算法的步骤： ➢求得范围缩小的同性质问题的结果 ➢利用已得到的结果和一个简单的操作求得问题的最 后解答 ➢ 例如：求n的阶乘n！ • 递归算法的主要内容： •定义递归头 •定义如何从同性质的简化问题求得当前问题
阶乘计算示例(1) 8-4 ·简单实现： public class Factorial{ public static int factorial(int x){ int fact 1; for (inti=2;i <=x;i++) /1o0P fact *i; //shorthand for:fact=fact*i; return fact; 3 public class ComputingFactorial{ public static void main(String arg[]){ int a Factorial.factorial(Integer.parselnt(arg[O]); System.out.println(a); Programming in Java JAVA
8-4 Programming in Java 阶乘计算示例（1） public class Factorial { public static int factorial(int x) { int fact = 1; for (int i =2; i <= x; i ++) //loop fact *= i; //shorthand for: fact=fact*i; return fact; } } public class ComputingFactorial { public static void main(String arg[]) { int a = Factorial.factorial(Integer.parseInt(arg[0])); System.out.println(a); } } • 简单实现:
阶乘什算示例(2) 8-5 ·改进 public class Factorial2{ //create an array to cache values 0!Through 20! Static long[]table new long[21]; Static {table[0]1;} //factorial of 0 is 1 //Remember the highest initialized value in the array static int last 0; public static long factorial(int x){ while (last x){ table [last 1]table[last]*(last 1); last++; Programming in Java JAVA
8-5 Programming in Java public class Factorial2 { //create an array to cache values 0! Through 20! Static long[] table = new long[21]; Static {table[0] = 1;} //factorial of 0 is 1 //Remember the highest initialized value in the array static int last = 0; public static long factorial(int x) { while (last < x) { table [last + 1] = table[last]*(last + 1); last++; } } 阶乘计算示例（2） • 改进