第3章 流程控制

学习要点 掌握三种流程控制 掌握简单的输入输出 了解三种循环设计方法 掌握数组、字符串和枚举类型

3.1 面向过程介绍

面向过程的程序设计，每个程序完成一个特定的功能，是通过对数据一系列的加工而实现的。面向过程编程包括两部分：数据结构设计和算法设计。 Pascal之父Nicklaus Wirth提出一个著名公式“算法+数据结构=程序”而获得图灵奖。数据结构是程序处理的对象、数据的表示和组成形式，数组、结构体变量是数据的重要表现形式。算法是对数据进行操作的方法和操作步骤。主要操作有算术运算、逻辑运算、关系运算、函数运算、位运算等操作，在第2章已经介绍。

流程是程序执行的顺序，流程控制有3种基本结构，分别是顺序结构、选择结构和循环结构。1966年Bohm和Jacopini证明：顺序、选择、循环三种结构可以构成任何的算法。面向过程编程方法要求：一个程序只能由三种基本控制结构组成。也就是说，三种基本结构可以有限次组成任何程序，解决任何可以解决的问题。

我们熟悉的C语言就是面向过程的程序设计语言。面向对象程序设计不是对面向过程的程序设计的否定，而是继承与推广。我们学习面向对象程序设计之前，需要掌握面向过程的程序设计。面向对象程序设计的具体算法实现还是要借助面向过程的思想；或者说在微观上，面向对象编程的细节就是面向过程的程序设计，在宏观上是面向对象的思想。所以学习Java面向对象程序设计之前，还是要再温习一下面向过程的程序设计部分。

3.2 数据的输入和输出

一般而言，任何程序都要有输入和输出本部分，没有输入或输出的程序意义不大。

3.2.1 输入语句

在Java 5之前，要实现从标准输入设备（比如键盘）输入数据是不容易的，从Java 5开始引入了一个新类Scanner用于基本数据的输入操作。可以将Scanner看作一个新的复合数据类型，用该类创建一个变量：

Scanner cin=new Scanner(System.in);

然后使用cin变量可以调用方法nextXxx()，其中Xxx可以替换为Boolean、Byte、Short、Int、Long、Float、Double，从命令行接收一个对应的数据。比如cin.nextInt()即可从命令行接收一个整数数据。此外，要使用Scanner类时，需通过“import java.util.Scanner;”语句将类Scanner引入当前程序，作用类似于C语言的#include。

例3.1 a+b问题：输入两个整数，输出和。

jshell> Scanner cin=new Scanner(System.in); //定义输入变量
cin ==> java.util.Scanner[delimiters=\p{javaWhitespace}+] ... \E][infinity string=\Q∞\E]

jshell> int x=cin.nextInt();   //输入第一个整数
1
x ==> 1

jshell> int y=cin.nextInt();   //输入第二个整数
2
y ==> 2

jshell> System.out.println(x+y)
3

本程序是国际大学生程序竞赛ACM训练题，请参见北京大学ACM Online Judge：http://poj.org/problem?id=1000。本程序看似简单，却隐含着计算机的基本组成原理和基本工作原理（请参加第0章）：cin.nextInt()语句体现了数据输入；System.out.printf(参数)语句体现数据输出；整型变量x和y表示存储数据，x+y进行数据运算，每个语句执行的次序需要流程控制。

[root@centos ~]# jshell
|  Welcome to JShell -- Version 9.0.1
|  For an introduction type: /help intro

jshell> import java.util.Scanner;

jshell> Scanner cin=new Scanner(System.in);
cin ==> java.util.Scanner[delimiters=\p{javaWhitespace}+] ... \E][infinity string=\Q∞\E]

jshell> int x=cin.nextInt(); //输入一个整数
100
x ==> 100

jshell> double y=cin.nextDouble(); //输入一个浮点数
3.1415926
y ==> 3.1415926

jshell> 

3.2.2 输出语句

System.out提供了三种标准输出：换行输出println()，不换行输出print，格式输出printf()，其中printf()是Java5新增的操作，用于与C语言的printf()函数一致，输出格式如表2.5所示。

表3.1 输出格式

例3.2 格式化输出。

jshell> import java.util.Scanner;

jshell> Scanner cin=new Scanner(System.in);
cin ==> java.util.Scanner[delimiters=\p{javaWhitespace}+] ... \E][infinity string=\Q∞\E]

jshell> double y=cin.nextDouble();//输入一个浮点数
3.1415926
y ==> 3.1415926

jshell> System.out.printf("%f\n",y);
3.141593
$14 ==> java.io.PrintStream@5025a98f

jshell> System.out.printf("%4.2f\n",y);
3.14
$13 ==> java.io.PrintStream@5025a98f

3.3 顺序结构

顺序结构，是程序语句书写的先后顺序，是流程控制语句最简单的一类。上面的两个输入输出程序就是顺序结构。从宏观上看，选择结构和循环结构，甚至是方法（函数），都属于顺序结构。

3.4 选择结构

选择结构也称为分支结构，Java中的选择结构与C语言选择结构类似，可以分为if分支语句和switch分支语句。if语句又可以分为如下3种形式：单if语句、if-else语句、if-else if-else语句，其中if-else if-else语句是if-else语句的推广形式。

3.4.1 if语句

单if语句也称单路分支语句，格式如下：

if(条件表达式)
语句;

注意，if后的小括号( )内的条件表达式的值必须是boolean型，与C语言不同。单if分支语句的流程图如图3.1所示。

graph TD
    A(开始)-->B{条件}
    B--> |true| D(语句)
    D--> E(结束)
    B--> |false| E 

图3.1 单if流程图

例3.3：通过单if语句实现计算一个数的绝对值。

jshell> import java.util.Scanner;

jshell> Scanner cin=new Scanner(System.in);
cin ==> java.util.Scanner[delimiters=\p{javaWhitespace}+] ... \E][infinity string=\Q∞\E]

jshell> double x=cin.nextDouble();  //输入一个数
-3.14
x ==> -3.14

jshell> if(x<0.0)
   ...>    x=-x;

jshell> System.out.println("|x|="+x);
|x|=3.14

3.4.2 if-else语句

if-else语句也称为二路分支语句，格式如下：

if(条件表达式){
    语句;
}
else{
    语句;
}

graph TD
    A(开始)-->B{条件}
    B--> |true| D(语句1)
    B--> |false| E(语句2) 
    D--> F(结束)
    E--> F

图3.2 if-else流程图

if-else语句的流程图如图3.2所示。如果if分支或else分支的语句只有一条语句时，可以省略大括号{}。为了提高程序可读性，大括号{}最好不要省略（本书为了节约篇幅，只有一条语句时省去{}）。 例3.4：通过if-else语句求解两数最大值问题。

jshell> int x=5,y=3;
x ==> 5
y ==> 3

jshell> if(x<y){
   ...>     System.out.println("max="+y);
   ...> }else{
   ...>     System.out.println("max="+x);
   ...> }
max=5

两数求最大值问题也可以通过三目运算符来实现。

3.4.3 if-else if-else语句

if-else if-else语句并不是新的语句，而是if-else语句嵌套形式，比如：

if(条件1){
      语句;
}
else{ 
      //嵌套格式，将else条件又细分为2个条件
      if(条件2){
           语句; 
      }
      else{
           语句; 
      }
}

嵌套形式的if-else语句可以直接写成if-else if-else形式：

if(条件1){
      语句;
}else if(条件2){
      语句; 
}else{//其他条件
      语句; 
}

上面的结构很容易看出三路分支结构，可以添加若干个else if分支，形成if-else if-else的多路分支结构，流程图如图2.20所示。

图2.20 if-else if-else流程图

例3-5：输入一个年龄数据，判定年龄的不同范围，输出对应的内容。

jshell> Scanner cin=new Scanner(System.in);
cin ==> java.util.Scanner[delimiters=\p{javaWhitespace}+] ... \E][infinity string=\Q∞\E]

jshell> int age=cin.nextInt(); 
20
age ==> 20

jshell> if(age>0 && age <18){   //条件1：0~18
   ...>     System.out.println("小孩");
   ...> }else if(age>=18 && age<28){  //条件2：18~28
   ...>     System.out.println("青春十年");
   ...> }else if(age>=28){  //条件3：大于28岁
   ...>     System.out.println("老了");
   ...> }else{
   ...>     System.out.println("其他");
   ...> }
青春十年

jshell>

例3-6：阶梯电价问题。 居民月用电量分为三个档次：第一档为230度，0.5283元/度；第二档为231－400度，在第一档电价的基础上，每度加价0.05元；第三档为高于400度，在第一档电价的基础上，每度加价0.3元。如果本月用电450度，需要支付多少电费？

jshell> double x=450;
x ==> 450.0

jshell> double y;
y ==> 0.0

jshell> if(x<0){
   ...>    y=0;
   ...> }else if(x<=230){
   ...>    y=x*0.5283;
   ...> }else if(x<=400){
   ...>    y=x*0.5283+(x-230)*0.05;
   ...> }else{
   ...>    y=x*0.5283+170*0.05+(x-400)*0.3;
   ...> }

jshell> System.out.println(y);
261.235

jshell> 

3.4.4 swith语句

switch语句的格式如下，其中switch语句中的“表达式”的值和“常量i”必须是byte、short、int、char、枚举型中之一。从Java 7开始，switch增加支持String类型数据。

switch(表达式){
         case 常量1:
                语句;
                break;
         . . . . . .
         case 常量n:
                语句;
                break;
         default:
                语句;
   }

例3-7：请根据一个年份和月份，求出该月的天数。

jshell> int year=2020,month=2;
year ==> 2020
month ==> 2

jshell> switch (month){
   ...>    case 2:{  //2月份，需要进行闰年判定
   ...>        if((year%4==0&&year%100!=0)||(year%400==0)){
   ...>           System.out.println("29");
   ...>        }else{
   ...>           System.out.println("28");
   ...>        }
   ...>        break;
   ...>   }case 4: case 6: case 9: case 11:{
   ...>        System.out.println("30");
   ...>        break;
   ...>   }default:{ 
   ...>       System.out.println("31"); 
   ...>   }
   ...> }
29

jshell> 

程序说明如下： 1)break语句跳出switch语句； 2)多个case可以共享同一个break语句; 3)每个case后面的语句是一个代码块，不需要{}括起来； 判定闰年的条件 if((year%4==0&&year%100!=0)||(year%400==0)) 。

3.5 循环结构

C语言具有while、do-while和for 3种循环结构，Java语言继承了这3种循环结构。

3.5.1 while循环

while循环语法结构格式：

while(循环条件){
     循环体语句;
}

while语句执行流程如图2.23所示，执行规则如下： 1)判断循环条件值，如果为true，则执行第2)步，否则执行第3)步； 2)执行循环体语句，完成后再回到第1)步； 3)结束while语句执行。

例3-8：求1+2+3+…+n的和。

可以使用while循环语句来求解，定义一个变量sum保存和（初始值为0），然后通过循环语句把1到n的整数加到sum里即可，编写代码如下

jshell> int i=1,n=100,sum=0;//求和sum存0
i ==> 1
n ==> 100
sum ==> 0

jshell> while(i<=n){
   ...>    sum+=i;
   ...>    i++;
   ...> }

jshell> System.out.println(sum);
5050

jshell>

需要注意的是：while循环中，对条件表达式的计算要比循环体多执行一次，最后一次循环执行循环条件不满足而退出循环。

3.5.2 do-while循环

do-while循环语法格式：

do{
   循环体语句;
}while(条件);

do-while执行流程如图2.24所示。当执行到do时，立即执行循环体一次，然后再判定循环条件。如果条件不成立(false)，则循环结束；则如果条件成立(true)，则继续执行循环体，然后再判断循环条件。do-while循环与while循环的区别：do-while循环至少执行一次循环体。 例3-9：求n!阶乘。

该问题可以化为求解1*2*…*n连乘积。下面使用do-while循环来求解，定义一个变量sum用于保存乘积值（初始值为1），然后通过循环语句把1到n每个数字乘到sum中，代码如下。

jshell> int i=1,n=10,sum=1;//求积sum存1
i ==> 1
n ==> 10
sum ==> 1

jshell> do{
   ...>    sum*=i;i++;
   ...> }while(i<=n);

jshell> System.out.println(sum);
3628800

jshell> 

程序说明：保存乘积的变量sum初始值为1；阶乘值增长速度很快，一般int型变量保存12以内的阶乘值。

3.5.3 for循环

for循环语法格式：

for(初始化语句; 循环条件; 迭代语句){
    循环体语句;
}

for循环语句的流程如图2.27所示，执行规则如下： 1)执行初始化语句，整个循环只执行一次； 2)判断循环条件，如果结果true，则执行第3)步，否则循环结束； 3)执行循环体语句； 4)执行迭代语句，跳转到第2)步重复执行。 其中，初始化语句可以定义for循环的循环变量。比如下面代码：

     int sum=0;
     for(int i=1;i<=100;i++)
         sum+=i;

循环变量i属于for循环，属于局部变量，在for循环以外不可见。C语言在Ｃ99标准下才支持这种形式。 相对while和do-while循环，for循环使用的频率最高，for循环可以替代while和do-while循环。在现在的软件代码中do-while循环使用越来越少，建议多使用for循环。

例3-10：求1+2!+3!+…+20!的值。该问题相当于求1+2+3+…+20之和和n!阶乘问题的复合。下面使用for循环来解决这个问题。很自然地我们想到先求前i项之和，再计算第i+1的阶乘；然后把第i+1的项加到前i 项和中。这样需要写成双重循环，效率低下。通过分析发现在求第i+1项阶乘时，其实上一步已经得知i项的阶乘，所以得到公式：

每项公式：ti+1=ti*(i+1) 求和公式：Si+1=Si+ti

编写程序如下，由于20!值很大，定义double型变量保持每项值和前i项之和。

jshell> double s=0,t=1;  //和0，积1
s ==> 0.0
t ==> 1.0

jshell> for(i=1;i<=n;i++){
   ...>    t*=i;    //第i项的值
   ...>    s+=t;    //前i项的和
   ...> }

jshell> System.out.println(s);
4037913.0

jshell> 

3.5.4 多层循环

对于一些复杂的问题需要用多重循环来解决。

例3-11：打印九九乘法表。 九九乘法表是个二维图形，需要双层循环来实现。一共九行，需要一个循环结构控制九行的输出；其中每一行（比如第i行），又可以通过一个内层循环实现“输出第i行”。编写程序，代码如下。

jshell> for(int i=1;i<=9;i++){//一共9行
   ...>    for(int j=1;j<=i;j++) //打印第i行
   ...>        System.out.print(j+"*"+i+"="+j*i+" ");
   ...>    System.out.println();//打印完第i行，换行
   ...> }
1*1=1 
1*2=2 2*2=4 
1*3=3 2*3=6 3*3=9 
1*4=4 2*4=8 3*4=12 4*4=16 
1*5=5 2*5=10 3*5=15 4*5=20 5*5=25 
1*6=6 2*6=12 3*6=18 4*6=24 5*6=30 6*6=36 
1*7=7 2*7=14 3*7=21 4*7=28 5*7=35 6*7=42 7*7=49 
1*8=8 2*8=16 3*8=24 4*8=32 5*8=40 6*8=48 7*8=56 8*8=64 
1*9=9 2*9=18 3*9=27 4*9=36 5*9=45 6*9=54 7*9=63 8*9=72 9*9=81 

jshell> 

读者可能发现上面结果输出有点小缺陷，第4行与第5行没有对齐，大家可以通过System.out.printf()格式输出来解决。

例3-12：打印出以下图形：

*******************
 *****************
  ***************
   *************
    ***********
     *********
      *******
       *****
        ***
         *

分析上面图形，发现一共10行；然后分析每一行，先输出一定量空格，再输出一定量的“*”号。可以得到外层循环结构：

for(int i=1;i<10;i++){
    输出一定量空格;
    输出一定量“*”号;
    输出换行;
}

对于第i行，空格与“”的数量关系是：空格i-1个，“”号19-2i个。可以通过2个循环实现输出。

根据上面思路编写程序如下:

jshell> for(int i=1;i<10;i++){//一共10行
   ...>    for(int j=0;j<i-1;j++)        //输出i-1个空格
   ...>        System.out.print(" ");
   ...>    for(int k=0;k<19-2*i;k++)   //输出19-2i个“*”号
   ...>        System.out.print("*");
   ...>    System.out.println();       //完成第i行，换行
   ...> }
*****************
 ***************
  *************
   ***********
    *********
     *******
      *****
       ***
        *

jshell> 

3.6 控制转移

控制转移语句有return语言、break语句、continue语句以及标号，其中ruturn语句用于方法的返回，下面重点介绍其他三个。

3.6.1 break语句

在switch语句中，break用来跳出switch，前面已经演示过了。break语句也可以在循环语句for、while、do-while中使用，表示跳出当前循环。

例3-13：素数判定。

素数又称质数，是一个大于1的自然数，除了1和它本身外没有其他的因子，素数在数论和密码学中有着很重要的地位。对于一个自然数n，最为简单的素数判定算法就是在2~ n-1中查找是否有一个数能整除n；若存在则说明n不是素数；若不存在这样的数，则n就是素数。 根据这个思路，使用循环结构和break语句即可完成素数判定算法，编写程序Prime1.java，代码如下。

jshell> int n=97;
n ==> 97             

jshell> for(int i=2;i<n;i++){//循环查找因子
   ...>    if(n%i==0){  //找到因子，说明n不是素数
   ...>       flag=false;
   ...>       break;
   ...>    }
   ...> }

jshell> System.out.println(flag)
true

jshell>

例3-14：素数判定优化算法。

上面程序时间复杂度是O(n)。进一步分析素数，大于1的自然数n可能的因子：

1      n
2      n/2
3      n/3
…      …
\sqrt{n} \sqrt{n} 

读者朋友可以发现，因子是成对出现的，如果出现因子2，那一定有因子n/2。所以只需要验证2~之间是否存在因子即可，如果存在一个数i满足条件n%i==0，则说明i是因子，可以判定n不是素数。优化素数判定算法代码如下。

jshell> int n=97;
n ==> 97

jshell> for(int i=2;i<=Math.sqrt(n);i++) { 
   ...>     if(n%i==0){
   ...>        flag=false;
   ...>        break;
   ...>     }
   ...> }

jshell> System.out.println(flag);
true

jshell> 

优化后的素数判定算法的时间复杂度降为O(n1/2)。

3.6.2 continue语句

continue语句用在循环语句中，可以结束本次循环，进入当前循环的下一次循环。

例3-15：求1到100不能被7整除的数之和。可以通过循环语句与continue语句实现，当i%7 = = 0时，说明i被7整除，结束本次循环当，进入i+1次循环。根据这个思路编写程序代码如下。

jshell> int sum=0;
sum ==> 0

jshell> for(int i=1;i<=100;i++){
   ...>    if(i%7==0)    continue;   //被7整除，跳过
   ...>    sum+=i;
   ...> }

jshell> System.out.println(sum)
4315

jshell> 

3.6.3 标记

相对C语言，Java的break和continue语句功能增强。单独是break或continue时，只能跳出一层循环，只能从循环体内向外跳转；当break或continue和标记结合使用时，可以跳到标记所处位置。标记是用户自定义的标识符，标记语句必须和某一循环体匹配使用，且在该循环体上方。

例3-16：求解n~m之间的素数，n

jshell> int n=10,m=20,r;
n ==> 10
m ==> 20
r ==> 0

jshell> next:      //标号，外层循环
   ...> for(int i=n;i<=m;i++){
   ...>    for(int j=2;j<=r;j++)
   ...>        if(i%j==0) continue next; //i不是素数，进入下次循环验证i+1
   ...>    System.out.print(i+"  ");      //以字符串形式输出素数
   ...> }
11  13  17  19  
jshell> 

程序说明：当遇到i%j==0时，执行“coninue next;”语句，跳转到“next:”标号标记的外层循环，也就是结束外层循环的当次循环，进入外层循环的下一次循环。如果是“break next;”语句，则跳转到next标记的外层循环，结束外层循环。

3.7 循环设计

循环设计是计算机解决问题的一个重要特征。对人来说，循环结构是三种流程控制中最复杂的语句，复杂的程序算法一般都离不开循环结构，人们对于周而复始的动作会产生严重的疲惫感，缺乏激情。对计算机来说，循环结构是强项，可以高效率不厌其烦的重复做某件事。在程序设计中，人们习惯于将复杂的难以解决的问题求解过程转化为易于理解的操作的多次重复。 在循环算法设计中，比较常见的方法有穷举法、迭代法和递推法。

3.7.1穷举法

穷举法就是对问题的所有可能状态进行一一测试，直到找到问题的解或者全部可能状态测试完为止（无解）。也就是，通过循环语句遍历（穷举）所有可能的情况，通过选择结构语句判定当前循环条件是否为所求问题的解。

例3-17：爱因斯坦阶梯问题。 大物理学家爱因斯坦曾给他的朋友出了这样一道题：有一个阶梯，若每步跨2阶，最后余1阶；若每步跨3阶，最后余2阶；若每步跨5阶，最后余4阶；若每步跨6阶，最后余5阶。当每步跨7阶时，刚好达到阶梯顶。问共有多少阶梯。 算法设计：设变量ladders表示阶梯数，根据已知条件有：

1)ladder % 2 = = 1
2)ladder % 3 = = 2
3)ladder % 5 = = 4
4)ladder % 6 = = 5
5)ladder % 7 = = 0

由5)条件知阶梯数是7的倍数，可知阶梯数是7，14，21，28，…数列中的某个项，并且阶梯数满足条件是“ladder%2= =1 && ladder%3= =2 && ladder%5= =4 &&ladder%6= =5”，可以进行穷举测试。由于不知道循环的次数，可以将循环条件设置为true进行“永真循环”；当阶梯判定条件满足时，使用break结束循环即可。 按照这个思路编写程序Ladders1如下，编译执行结果如图2.35所示。

jshell> for(int ladder=7;true;ladder+=7){ //永真循环，穷举测试
   ...>      //满足阶梯条件，结束循环
   ...>      if(ladder%2==1 && ladder%3==2 && ladder%5==4 &&ladder%6==5){
   ...>          System.out.println("ladders="+ladder);
   ...>          break;
   ...>      }
   ...> }
ladders=119

jshell> 

可以对上面程序进一步优化，由条件1)知道阶梯数一定为奇数，可以将7，14，21，28，…数列中的数去掉一半，那么算法执行时间减半，优化后的代码如下。

jshell> int ladder=7;
ladder ==> 7

jshell> while(ladder%3!=2 || ladder%5!=4 ||ladder%6!=5){  //不是阶梯数的条件
   ...>     ladder+=14;     //每次递增14，执行时间减半
   ...> }

jshell> System.out.println("ladders="+ladder);
ladders=119

jshell> 

判定条件“ladder%3!=2 || ladder%5!=4 ||ladder%6!=5”表示不是阶梯数的条件。

3.7.2 递推法

对于一个数列，如果已知它通项公式，那么求出数列的某项的值是很容易的。但是许多情况下，数列的通项公式是难以得到的，甚至无法得到。对于一些数列，虽然通项公式难以找到，但可以找到相邻的若干项之间的关系。由已知项，再借助这个特定的关系可以逐项推算出后继项或前驱项的值，这种关系即是递推公式。递推公式又可以分为顺推和逆推两种方式。递推法关键是找到起点（已知项）和递推公式。

（1）顺推

由已知项和递推公式，逐项求出后继项，称为顺推。比如著名的Fibonacci数列（也称黄金分割数列）的递推公式就可以由已知项逐项推出后继项。

例3-18：数学家Fibonacci在《算盘全集》中提出一个兔子繁殖的问题：设有一对新生兔子，从第三个月开始它们每月都生产一对小兔子。假设兔子没有死亡，按此规律一年后共有多少只兔子。其中，每对兔子均是一公和一母。 先列举出前面若干月兔子数：

第一个月，1对小兔子；
第二个月，1对小兔子，就是上个月的小兔子；
第三个月，这一对老兔子生成一对小兔子，老兔子数加上小兔子数一共2对；
第四个月，第一对老兔子又生了一对小兔子，共有3对（1+2=3）兔子；
第五个月，第一对老兔子又生了一对小兔，第三个月出生的小兔成熟也生下了一对小兔，所以新生兔2对；再加上老兔子数，也就是上个月的兔子数，本月5（2+3=5）对兔子。
第六个月，第一对兔子以及第三、四月生下的兔子也都各生下了一对小兔，新生兔3只；再加上这个月和原先的5对兔子共有8对（3+5=8）兔子。
……

分析这个数列：1，1，2，3，5，8，……。可以发现从第三个月开始每个月的兔子数是两部分组成，老兔子数加上本月新兔子数。老兔子数即是上个月的兔子数；本月新生兔子数为上上月兔子数，因为上上月的兔子在本月均可生成一对小兔子，而上个月新生兔子在本月还不能生产小兔子。可以得到该数列的递推公式：

fib_{1}=fib_{2}=1

fib_{n}=fib_{n-1}+fib_{n-2} , n>=3

有了起点和递推公式很容易写出求解Fibonacci数列的程序，代码如下。

jshell> int f1,f2,f;
f1 ==> 0
f2 ==> 0
f ==> 0

jshell> f1=f2=1;
f1 ==> 1

jshell> for(int i=3;i<=12;i++){   //从第三项开始，递推求出下一项的值
   ...>    f=f2+f1;           //第i项的值
   ...>    f1=f2;
   ...>    f2=f;
   ...>    System.out.print(" "+f);
   ...> }
 2 3 5 8 13 21 34 55 89 144
jshell>

（2）逆推 由已知项和递推公式，逐项求出前驱项，称为逆推。比如猴子吃桃问题就是逆推。

例3-19：猴子吃桃问题。有一堆桃子，第一天猴子吃了一半，还嫌不够又多吃了一个；第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求最初这堆桃子有多少个？

分析： 设xn 表示某一天桃子数，则这天的前一天桃子数为

x_{n-1}=(x_{n}+1)*2

获得递推公式；又知第十天桃子数x10=1 ，即是起点值。

按照这个思路编写程序代码如下

jshell> int i,a=1;
i ==> 0
a ==> 1

jshell> for(i=9;i>=1;i--)  //逆推
   ...>    a=(a+1)*2;

jshell> System.out.println(a);
1534

jshell> 

3.7.3迭代法

在《数值分析》中，迭代是重要的算法基础。许多数学问题都可以转化为解方程F(x)=0的实数根的问题。求根可以直接从方程出发，逐步缩小根所在的区间，把根的近似值逐步精确到指定的精度为止，这就是迭代算法。

（1）二分迭代法

二分迭代法是一种简单的迭代法，基本思想如图2.39所示。对于方程y=f(x)，先确定一个范围（x1，x2），使得f(x1)与f(x2)的符号相反，则方程f(x)=0在（x1，x2）内至少存在一个根。取

x_3=\frac{1}{2}(x_1+x_2)

作为近似根。然后在x1 与x2中舍去函数值与f(x3)同号者，比如图中x2的函数值与f(x3)同符号，舍去x2，则根必然存在于（x1，x3）区间内。然后重复上面过程，当xn与xn+1差距小于给定的误差时，可以认为xn 就是所求方程的一个逼近根。

显然二分迭代法的迭代公式就是：

x_{n+1}=\frac{1}{2}(x_n+x_{n-1})

例3-20：用二分迭代法求解方法2x3- 4x2 +3x- 6=0在（-10，10）之间的根。

f(x)=2x3- 4x2 +3x- 6的图像如图2.40所示。f(-10)= -2436，f(10)=1624，f(-10)与f(10)符号相反，则说明在（-10，10）区间内必然存在一个根。运用二分迭代法，编写程如下。

jshell> double x0,x1,x2,f0,f1,f2;
x0 ==> 0.0
x1 ==> 0.0
x2 ==> 0.0
f0 ==> 0.0
f1 ==> 0.0
f2 ==> 0.0

jshell> x1=-10;x2=10;    //输入2个区间
x1 ==> -10.0
x2 ==> 10.0

jshell> f1=((2*x1-4)*x1+3)*x1-6;
f1 ==> -2436.0

jshell> f2=((2*x2-4)*x2+3)*x2-6;
f2 ==> 1624.0

jshell> do{
   ...>    //求二分点（x0 , f0）
   ...>    x0=(x1+x2)/2;
   ...>    f0=((2*x0-4)*x0+3)*x0-6;
   ...>    if(f0*f1<0){  //二分点f0与f1异号，根存在于(x1,x0)内
   ...>        x2=x0;
   ...>        f2=f0;
   ...>    }else{        //f0与f同号号，根存在于(x0，x2)内
   ...>        x1=x0;
   ...>        f1=f0;
   ...>    }
   ...> }while(Math.abs(f0)>=1e-6);   //根的函数值的精度是0.000001

jshell> System.out.printf("x=%6.2f\n",x0);
x=  2.00
$12 ==> java.io.PrintStream@3bfdc050

jshell>

（2）牛顿切线法

牛顿切线法也称为切线迭代法，这是一种比一般迭代法（比如二分迭代法）收敛速度更快的迭代法，其基本思想如图2.42所示。

设xn是方程f(x)=0的根x0附近的一个猜测根，通过点（xn,f(xn)）做f(x)的切线。切线方程为：

y = f(x_n)+{f(x_n)}'(x-x_n)

它与x轴的交点是方程

f(x_n)+{f(x_n)}'(x-x_n)=0

的根，为

x_{n+1}=x_n-\frac{f(x_n)}{{f(x_n)}'}

这就是牛顿迭代法的迭代公式。

例3-21：用牛顿迭代法求解方法2x3- 4x2 +3x- 6=0在1.5附近的根。

f(x)=2x^{3}-4x^{2}-6=((2x-4)x+3)x-6

{f(x)}'=6x^{2}-8x+3=(6x-8)x+3

即可使用牛顿迭代公式求解，编写程序如下。

jshell> double x0,x=1.5,f,f1;
x0 ==> 0.0
x ==> 1.5
f ==> 0.0
f1 ==> 0.0

jshell> do{
   ...>    x0=x;
   ...>    f=((2*x0-4)*x0+3)*x0-6;   //函数值f(x0)
   ...>    f1=(6*x0-8)*x0+3;         //导数值f'(x0)
   ...>    x=x0-f/f1;
   ...> }while(Math.abs(x-x0)>=1e-6);  //根的精度是0.000001

jshell> System.out.printf("x=%6.2f\n",x);
x=  2.00
$6 ==> java.io.PrintStream@3e6fa38a

jshell>