第3 章算法基础: 穷举、迭代与递归 课程练习 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令。 算法具有以下五个重要的特征。 (1)有穷性(Finitenes):算法必须能在执行有限个步骤之后终止。 (2)确切性(Definitenes):算法的每一步骤必须有确切的定义。 (3)输入项(nu:一个算法有零个或多个输入, Ipt)输入是在执行算法时需要从外界取 得的一些必要信息。 (4)输出项(Output):一个算法有一个或多个输出,以反映对输入数据加工后的结果。 没有输出的算法是毫无意义的。 (5)可行性(Efectivenes):算法中执行的任何计算步骤都是可以被分解为基本的可 执行的操作步骤,即每个计算步骤都可以在有限时间内完成(也称之为有效性)。 算法的描述与所采用的工具有关。这里讨论的是采用电子数字计算机进行问题求解的 算法,它通常由操作、控制结构和数据结构3要素组成。其中,操作包括算术逻辑操作、关系 操作和输入/输出操作;控制结构包括模块结构和流程控制结构(顺序、分支和重复);数据结 构指数据的组织形式。通常,求解同一类问题,算法也会由于思维模式不同而不同。这些不 同的算法,往往会表现出不同的执行时间和不同的系统资源(主要是存储空间)占用,分别称 为算法的时间效率和空间效率。 本章介绍三种最常用、最基本的算法:穷举、迭代和递归。 3.素数序列产生器 1 1 素数序 3.1.问题描述与对象建模 列产生器3.1 素数又称质数,是指在大于1的整数中除了1和它本身外不再有其他约数的数。素数 序列产生器的功能是输出一个自然数区间中的所有素数。 1.素数序列产生器建模 1)现实世界中的素数序列计算对 象 本题的意图是建立一个自然数区间,如图3. 所示的[350,5500 ]、[等区间 1 11,101 ]、[3,1000] 内的素数序列。每一个正整数区间的素数序列就 是一个对象。 2)用类图描述的素数序列产生器 对这个问题建模,就是考虑定义一个具有一 般性的素数产生器———PrimeGenerator类。这 个类的区间下限为lowerNaturalNumber,区间图3.不同的求素数对象 1 ·60· 上限为upperNaturalNumber。这两个值分别用一个变量存储,作为类PrimeGenerator的 两个成员变量。 图3.2 PrimeGenerator类 初步模型 类PrimeGenerator成员方法除了构造器和主方法外,还 需要getPrimeSequence()———给出素数序列,于是可以得到如 图3.2所示的PrimeGenerator类初步模型。 2.getPrimeSequence()方法的基本思路 getPrimeSequence()方法的功能是给出[lowerNatural- Number,upperNaturalNumber]区间内的素数序列。基本思路是 从lowerNaturalNumber到upperNaturalNumber逐一对每一个数 进行测试,看其是否为素数,如果是则输出(用不带回车的输出,以 便显示出一个序列);否则继续对下一个数进行测试。 每次测试使用的代码相同,只是被测试的数据不同,也就是说,这样一个方法中的代码 要不断重复执行,直到达到目的为止,这种程序结构称为重复结构,也称循环结构。 在实现getPrimeSequence()方法时有以下两种考虑。 (1)用isPrime()判定一个数是否为素数。 为了将getPrimeSequence()方法设计得比较简单,把测试一个数是否为素数的工作也 用一个方法isPrime()进行,所以getPrimeSequence()方法就是重复地对区间内的每个数用 isPrime()方法进行测试。 isPrime()方法用来对某个自然数进行测试,看其是否为素数。其原型应当为: boolean isPrime(int number); 测试一个自然数是否为素数的基本方法是把这个数number依次用2~number/2 去 除,只要有一个能整除,该数就不是素数。 所以,这两个方法都要采用重复结构。 (2)在getPrimeSequence()方法中直接判定一个数是否为素数。 3.1.2 isPrime()判定素数方法的实现 1.复合赋值运算符 复合赋值是指先执行运算符指定的运算,然后再将运算结果存储到运算符左边操作数 指定的变量中。在Java中,表达式m=m+1可以简化为m+=1。+=是加和赋值的组 合操作符,称为赋值加。例如,i+=5相当于i=i+5。除赋值加外,复合赋值操作符还有 -=、*=、/= 等,见表3.1。 表3.1 复合赋值运算符 操作符含 义示 例 += 加和赋值操作符,它把左操作数和右操作数相加赋值给左操作数a+=40等同于a=a+40 -= 减和赋值操作符,它把左操作数和右操作数相减赋值给左操作数a-=40等同于a=a-40 *= 乘和赋值操作符,它把左操作数和右操作数相乘赋值给左操作数a*=40等同于a=a*40 /= 除和赋值操作符,它把左操作数和右操作数相除赋值给左操作数a/=40等同于a=a/40 %= 取模和赋值操作符,它把左操作数和右操作数取模后赋值给左操作数a%=40等同于a=a%40 ·61· 复合赋值运算符同简单赋值运算符一样,也是双目运算符,需要两个操作数。不同的 是,复合赋值运算符要先执行运算符自身要求的运算后,再将运算后的结果赋值给左边的操 作数指定的变量。例如,a*=b+20的等价形式是a=a*(b+20),而不是a=a*b+20。 注意,在变换时右边表达式要先加上括号。复合赋值操作符的优先级别与赋值操作符相同。 2.自增/自减运算符 自增(++)/自减(--)运算符是一种特殊的算术运算符,在算术运算符中需要两个操 作数来进行运算,而自增/自减运算符是一个操作数。++ 与-- 的作用是使变量的值增 1或减1。操作数必须是一个整型或浮点型变量。自增、自减运算的含义及其使用实例如 表3.2所示。 表3.2 自增、自减运算的含义及其使用实例 操作符含 义示 例运算结果 i++ 将i的值先使用,再加1赋值给i变量本身inti=1; intj=i++; i=2 j=1 ++i 将i的值先加1赋值给变量i本身后,再使用inti=1; intj= ++i; i=2 j=2 i-- 将i的值先使用,再减1赋值给变量i本身inti=1; intj=i--; i=0 j=1 --i 将i的值先减1后赋值给变量i本身,再使用inti=1; intj= --i; i=0 j=0 说明: (1)运算的基本规则为:前缀自增/自减法(++a,--a),先对变量a进行自增或者自 减运算,再引用变量a的值进行表达式运算;后缀自增/自减法(a++,a--),先引用变量a 的值进行表达式运算,再对变量a进行自增或者自减运算。 (2)自增/自减只能作用于变量,不允许对常量、表达式或其他类型的变量进行操作。 (3)自增/自减运算可以用于整数类型byte、short、int、long,浮点类型float、double,以 及字符类型char。 图3.3 do-while结构的 程序流程图 (4)在Java1.5以上版本中,自增/自减运算可以用于基本类型 对应的包装器类Byte、Short、Integer、Long、Float、Double 和 Character。 (5)自增/自减运算结果的类型与被运算的变量类型相同。 3.采用do-while结构的isPrime()方法 while结构的执行特点是“符合条件才进入”;do-while结构的执 行特点是“先执行一次再说”。所以while结构的循环体可能一次也 不执行,而do-while结构最少要执行一次。图3.3为do-while结构 的程序流程图。其基本格式如下: do { 循环体 } while (循环条件); 注意:do-while结构的最后要以分号结束。 ·62· 下面先实现素数序列产生器的isPrime()方法,然后再实现整个PrimeGenerator类。 isPrime()方法的基本思路是用2~number/2中的数m 依次去除被检测的数number, 只要有一次能被整除,就证明number不是素数,循环除就不再进行,这种解决问题的方法 就是穷举法。 穷举法的基本思路是:对于要解决的问题,列举出它所有可能的情况,逐个判断有哪些 是符合问题所要求的条件,从而得到问题的解。穷举一般采用重复结构,并由以下3个要素 组成。 (1)穷举范围:问题所有可能的解,应尽可能缩小穷举范围。 (2)判定条件:用于判断可能的解是否是问题真正的解。 (3)穷举结束条件:用于判断是否结束穷举。 穷举算法是一种最简单、最直接且易于实现的算法,但运算量大,其依赖于计算机的强 大计算能力来穷尽每一种可能的情况,从而达到求解的目的。穷举算法效率不高,但适用于 解决一些规模不是很大的问题。 【代码3-1】 采用do-while结构实现isPrime()方法。 1 public class PrimeGenerator { 2 /**主方法*/ 3 public static void main(String[]args) { 4 PrimeGenerator ps1 =new PrimeGenerator(); 5 System.out.println(ps1.isPrime(2)); 6 System.out.println(ps1.isPrime(14)); 7 } 89 /**判定素数方法*/ 10 private boolean isPrime(int number) { 11 int m =2; 12 13 //1 及小于1 的数都不是素数,2 是素数 14 if (number <=1) { 15 return false; 16 } else if (number ==2) { 17 return true; 18 } 19 20 do { 21 //若能找到用来整除number 的数m,则number 不是素数 22 if (number %m ==0) { 23 return false; 24 } 25 //取下一个数 26 ++m; 27 } while (m 0) (3) ì . í .. .. 其中,式(1)和式(2)给出了递归的终止条件,称为递归出口,式(1)或式(2)皆可作为递 归出口;式(3)给出了fact(n)和fact(n-1)之间的关系,称为递归体。 一般地,一个递归模型由递归出口和递归体两部分组成,前者确定递归何时结束,后者 确定递归求解时的递归关系。递归模型必须有明显的结束条件,即至少有一个递归出口,这 样就不会产生无限递归的情况了。 3.3.3 用递归实现阶乘计算器 用递归实现阶乘计算器,主要是将fact()方法改为用递归实现。 【代码3-6】 用递归实现的fact()方法。 1 public class FactorialCalculator { 2 /**主方法*/ 3 public static void main(String[]args) { 4 //创建FactorialCalculator 类对象 5 FactorialCalculator fc =new FactorialCalculator(5); 6 //调用对象的fact()方法计算阶乘 7 System.out.println(fc.getN() +"!=" +fc.fact(fc.getN())); 8 } 9 10 private int n; 11 12 /**带参构造器*/ 13 public FactorialCalculator(int n) { 14 this.n =n; 15 } 16 17 /**用递归法计算阶乘*/ 18 public long fact(int n) { 19 long factorial =1; 20 21 if (n <0) { 22 //抛出不合理参数异常 23 throw new IllegalArgumentException("必须为非负整数!"); 24 } else if (n ==0) { 25 return 1; 26 } else { 27 factorial =n * fact(n -1); 28 return factorial; 29 } 30 } 31 32 public int getN() { 33 return n; 34 } 35 ·70· 36 public void setN(int n) { 37 this.n =n; 38 } 39 } 程序运行结果: 5!=120 说明: (1)递归由两个过程组成:递推和回归。递推就是把复杂问题的求解推到比原问题简 单一些的问题的求解;当获得最简单的情况后,逐步返回,依次得到复杂的解,就是回归。将 求n! 转换成求(n-1)!,而(n-1)! 又可以转换成(n-2)!,(n-1)! =(n-1)×(n-2)!, …,重复这个过程,直至0! =1。0! =1称为结束条件。这个过程称为“递推”。当“递推” 到结束条件时,就可以开始“回归”,通过0! 求出1!,通过1! 求出2!,…,通过(n-2)! 求 出(n-1)!,最后通过(n-1)! 求出n!。这个过程称为“回归”。“回归”就是一个值“回代” 的过程。图3.7体现了求fact(4)的递归计算过程。 图3.7 求fact(4)的递归计算过程 (2)递归过程不应无限制地进行下去,当调用有限次后,就应当到达递归调用的终点得 到一个确定值(例如图3.7中的fact(0)=1),然后进行回代。在这样的递归过程中,程序员 要根据数学模型写清楚调用结束的条件。 习题 1.编写程序。输入两个正整数m 和n,使用递归求其最大公约数。 2.编写程序。一个人赶着鸭子去每个村庄卖,每经过一个村子卖去所赶鸭子的一半又 一只。这样他经过了七个村子后还剩两只鸭子,问他出发时共赶了多少只鸭子? 经过每个 村子卖出多少只鸭子? 要求使用递归实现。 3.4 内容扩展 3.4.1 用静态成员变量记录素数的个数 若想记录素数序列产生器对象所生成的素数总个数,可用静态成员变量来存储不同素 数序列产生器对象生成的素数个数总和。 1.静态成员变量的性质 不用static修饰的成员变量称为实例变量,而用static修饰的成员变量称为静态成员变 ·71· 3.4 内容 扩展 量(简称静态变量、静态域、静态属性、静态字段等)。静态成员变量具有如下一些重要特性。 (1)具有类共享性。静态成员变量不用作区分一个类的不同对象,而是为该类的所有 对象共享,所以也称为类属变量(简称类变量)。当要使用的变量与对象无关又不是一个方 法中的局部变量时,就需要定义一个静态成员变量。static成员的这一特性使得可以使用 一个静态变量count作为素数序列产生器对象之间的共享变量,存储素数生成的个数。 同样,类的static方法(静态方法)也称为类方法,即当一个方法与生成的对象无关时可 以将其定义为静态方法,最典型的静态方法是main()。 (2)静态成员变量可以被任何(静态或非静态)方法直接使用,可以由类名直接调用,也 可以用对象名调用。例如,System.in、System.out和System.err表明in、out和err是 System 的静态成员。这是与实例变量的不同之处,实例变量只能由类的实例调用。但是, 静态方法只能对静态变量进行操作。 (3)静态成员变量不用区分不同对象,所以不通过构造器初始化,而是在类声明中直接 显式初始化。若不直接显式对其进行初始化,编译器将对其进行默认初始化。如果是对象 引用,则默认初始化为null;如果是基本类型,则初始化为基本类型相应的默认值。 (4)静态成员变量每个类只存储一份,为该类所有对象共享;而实例变量每个对象都会 存储一份,为该类每个对象私有。 (5)类中的静态成员变量,在该类被加载到内存时,就分配了相应的内存空间,并且所 有对象的这个静态变量都分配给相同的一处内存,以达到共享的目的;而实例变量只有在创 建对象时才会分配内存空间,并且分配到不同的内存空间。 2.带有静态成员变量的PrimeGenerator类定义 【代码3-7】 带有静态成员变量的PrimeGenerator类定义。 1 public class PrimeGenerator { 2 /**主方法*/ 3 public static void main(String[]args) { 4 PrimeGenerator ps1 =new PrimeGenerator(2, 20); 5 ps1.getPrimeSequence(); 6 //用类名PrimeGenerator 调用其静态变量count 7 System.out.println("\n 已生成素数个数: "+PrimeGenerator.count); 8 PrimeGenerator ps2 =new PrimeGenerator(40, 70); 9 ps2.getPrimeSequence(); 10 System.out.println("\n 已生成素数个数: "+PrimeGenerator.count); 11 } 12 13 /**存储素数产生的个数*/ 14 static int count=0; 15 16 /**区间下限*/ 17 private int lowerNaturalNumber; 18 /**区间上限*/ 19 private int upperNaturalNumber; 20 21 /**带参构造器*/ 22 public PrimeGenerator(int lowerNaturalNumber, int upperNaturalNumber) { 23 this.lowerNaturalNumber =lowerNaturalNumber; 24 this.upperNaturalNumber =upperNaturalNumber; 25 } 26 27 private void getPrimeSequence() { ·72· 28 System.out.print(lowerNaturalNumber +"到" +upperNaturalNumber + 29 "之间的素数序列为: "); 30 //循环控制 31 for (int m =lowerNaturalNumber; m <=upperNaturalNumber; m++) { 32 if (isPrime(m)) { 33 //记录素数个数 34 count++; 35 System.out.print(m +","); 36 } 37 } 38 } 39 40 /**判定素数方法*/ 41 private boolean isPrime(int number) { 42 //其他代码 43 } 44 } 程序运行结果: 2 到20 之间的素数序列为: 2,3,5,7,11,13,17,19, 已生成素数个数: 8 40 到70 之间的素数序列为: 41,43,47,53,59,61,67, 已生成素数个数: 15 说明: (1)lowerNaturalNumber、upperNaturalNumber属于实例变量。创建类的对象时,不 同对象的实例变量,有不同的副本,它们存储在相互独立的内存空间中。一个对象的数据成 员的值的改变不会影响到另一个对象中同名的数据成员。 (2)count属于类变量。一个类的类变量(静态变量),所有由这个类生成的对象都共用 这个类变量,类装载时就分配存储空间。静态变量将变量值存储在一个公共的内存地址。 因为它是公共的地址,所以如果一个对象修改了静态变量的值,则所有对象中这个变量的值 都会发生改变。若想让一个类的所有实例共享数据,就要使用静态变量。 图3.8反映了实例变量及静态变量的存储情况。从图中可以看出,属于实例的实例变 量(lowerNaturalNumber和upperNaturalNumber)存储在互不相关的内存中,静态变量 (count)是被同一个类的所有实例所共享的。 图3.8 实例变量及静态变量存储情况 ·73· 3.4.2 静态成员方法———类方法 1.静态成员方法的性质 在Java类中不仅可以有静态成员变量———类属性,还可以有静态方法———类方法,就 是用static修饰的方法,它们与类属性一样对于所有的类对象是公共的。没有被static修饰 的方法就是非静态方法,也称为实例方法。 (1)静态成员方法可以由类名直接调用,也可以用对象名调用。而实例方法必须用对 象名访问。 (2)静态方法只能直接访问静态成员(静态变量和静态方法),而不能直接访问非静态 成员(实例变量和实例方法);而非静态方法既可以直接访问静态成员,也可以直接访问非静 态成员。静态成员和实例成员的关系总结如表3.3所示。 表3.3 静态成员和实例成员的关系 √:能访问 ×:不能访问 实例成员静态成员 实例方法实例属性静态方法静态属性 实例方法√ √ √ √ 静态方法× × √ √ 【代码3-8】 静态成员和实例成员访问示例。 StaticInstMethodDemo.java 1 public class StaticInstMethodDemo { 2 /**主方法*/ 3 public static void main(String[]args) { 4 StaticInstMethodDemo simd =new StaticInstMethodDemo(); 5 //用对象名调用实例方法 6 simd.print11(); 7 //用对象名调用静态方法 8 simd.print21(); 9 //用类名调用静态方法 10 StaticInstMethodDemo.print21(); 11 } 12 13 /**实例变量*/ 14 int a =3; 15 /**静态变量*/ 16 static int b =5; 17 18 /**实例方法*/ 19 public void print11() { 20 //能访问实例变量a 21 System.out.println("in print11 method: a=" +a); 22 //能访问静态变量b 23 System.out.println("in print11 method: b=" +b); 24 25 //能访问实例方法print12 26 print12(); 27 //能访问静态方法print22 28 print22(); 29 } 30 31 /**实例方法*/ 32 public void print12() { 33 System.out.println("in print12 method: 实例方法"); ·74· 34 } 35 36 /**静态方法*/ 37 public static void print21() { 38 //不能访问实例变量a 39 //System.out.println("a="+a); 40 //能访问静态变量b 41 System.out.println("in print21 method: b=" +b); 42 43 //不能访问实例方法print12 44 //print12(); 45 //能访问静态方法print22 46 print22(); 47 } 48 49 /**静态方法*/ 50 public static void print22() { 51 System.out.println("in print22 method: 静态方法"); 52 } 53 } 运行结果: in print11 method: a=3 in print11 method: b=5 in print12 method: 实例方法 in print22 method: 静态方法 in print21 method: b=5 in print22 method: 静态方法 in print21 method: b=5 in print22 method: 静态方法 说明:如果类的成员没有使用任何访问权限修饰符,那么该成员只能被同包的其他类 成员访问,如StaticInstMethodDemo类的数据成员a和b。 (3)静态方法中不能使用this、super关键字。 (4)类的静态方法和实例方法在内存中都只存储一份,同一类的多个对象在内存中共 用这一份方法代码。不过,两者分配入口地址的时机不一样。对于静态方法,在该类被加载 到内存时就分配了相应的入口地址。从而静态方法不仅可以被类创建的任何对象调用执 行,也可以直接通过类名调用。静态方法的入口地址直到程序退出才被取消。对于实例方 法,只有该类创建对象后才会分配入口地址,从而实例方法可以被类创建的任何对象调用。 需要注意的是,当创建第一个对象时类中的实例方法会分配入口地址,当再次创建对象时就 不再分配入口地址。也就是说,方法的入口地址被所有的对象共享,当所有的对象都不存在 时,方法的入口地址才被取消。 main()方法就是一个静态方法,当所在的类加载时即分配了入口地址,因而使JVM (JavaVirtualMachine)无须创建对象即可直接调用它。 如何判断一个变量或方法应该是实例的还是静态的? 如果一个变量或方法依赖于类的 某个具体实例,那就应该将它定义为实例变量或实例方法。如果一个变量或方法不依赖于 类的某个具体实例,就应该将它定义为静态变量或静态方法。 2.将isPrime()定义为静态方法 分析素数序列产生器的isPrime()方法可以发现,在这个方法中不对任何实例变量进行 操作,即它与类的实例无关,仅与类有关。或者说,isPrime()方法为类的所有实例共享。这 ·75· 样的方法可以定义为静态方法。 【代码3-9】 将isPrime()定义为静态方法。 1 public class PrimeGenerator { 2 /**主方法*/ 3 public static void main(String[]args) { 4 PrimeGenerator ps1 =new PrimeGenerator(); 5 //用对象名调用静态方法 6 System.out.println(ps1.isPrime(2)); 7 //用类名调用静态方法 8 System.out.println(PrimeGenerator.isPrime(14)); 9 } 10 11 /**判定素数方法*/ 12 private static boolean isPrime(int number) { 13 int m =2; 14 15 //1 及小于1 的数都不是素数,2 是素数 16 if (number <=1) { 17 return false; 18 } else if (number ==2) { 19 return true; 20 } 21 22 do { 23 //若能找到用来整除number 的数m,则number 不是素数 24 if (number %m ==0) { 25 return false; 26 } 27 //取下一个数 28 ++m; 29 } while (m