第3章-基本算法和流程控制

第3章基本算法和流程控制,本章重要介绍Java语言中的基本算法、分支结构和分支结构语句、循环结构和循环结构语句以及结构嵌套。本章要点3.1算法和控制结构3.2选择结构语句3.3循环结构语句思考与练习3,本章逻辑结构,3.1算法和控制结构3.1.1算法3.1.2算法的描述方法实例12用流程图描述算法3.2选择结构语句3.2.1if语句3.2.2switch语句实例13批改数学试题实例13批改数学试题实例15输出期末总评成绩,本章逻辑结构,3.3循环结构语句3.3.1while语句实例16买彩票中大奖3.3.2for语句3.3.3跳转语句3.3.4多重循环语句实例17求1!+2!+10!的值实例18求两数之间所有偶数的和实例19猜年龄,3.1算法和控制结构,3.1.1算法一般来说，所谓算法是指解决一个特定问题采用的特定的、有限的方法和步骤。利用计算机来解决问题需要编写程序，在编写程序前要对问题进行充分的分析，设计解题的步骤与方法，也就是设计算法。没有算法，对要解决的问题就无从下手。有了算法，才有可能设计程序，最终让计算机执行程序，完成所要求的任务。算法的好坏决定了程序的优劣，因此，算法的设计是程序设计的核心任务之一。从计算机应用的角度来说，算法是用于求解某个特定问题的一些指令的集合。用计算机所能实现的操作或指令，来描述问题的求解过程，就得到了这一特定问题的计算机算法。一个算法的功能不仅与选用的操作有关，而且与这些操作之间的执行顺序有关。算法的控制结构给出了算法的执行框架，它决定了算法中各种操作的执行次序。博姆(Bohm)和雅可比尾(Jacopini)两位学者于1966年提出程序有三种基本结构：顺序结构、选择结构和循环结构。这三种基本结构都具有只有一个入口和一个出口的特点，不会出现死循环。,3.1算法和控制结构,3.1.1算法（1）顺序结构：它是一种线性结构，也是程序设计中最简单、最常用的基本结构。顺序结构程序是把计算机要执行的各种处理依次排列起来。程序运行后，便从左至右、从上向下地顺序执行这些语句(一个语句行中，从左至右顺序执行各条语句)，直至执行完所有语句行的语句或执行至END语句止。一个程序通常可分为3个部：输入、处理和输出。（2）选择结构：它是一种常用的主要基本结构，是计算机科学用来描述自然界和社会生活中分支现象的重要手段。在实际工作中，常常需要根据某个条件是否成立，来决定下一步应做什么工作。编写程序让计算机工作，同样存在这种情况。在这种情况下，程序不再按照行号的顺序来执行各语句行的语句，而是根据给定的条件来决定选取哪条路径，执行哪些语句。选择结构的特点是：在各种可能的操作分支中，根据所给定的选择条件是否成立，来决定选择执行某一分支的相应操作，并且任何情况下均有“无论分支多少，仅选其一”的特性。,3.1算法和控制结构,3.1.1算法（3）循环结构算法中有时需要反复地执行某组操作，循环控制就是指由特定的条件决定某些语句重复执行次数的控制方式。它具有封闭型的单入单出性质，也就是说进入循环结构后，只要循环条件未达到结束状态，就始终执行循环体内的操作。,3.1算法和控制结构,3.1.2算法的描述方法算法有许多描述方法，例如：使用日常语言描述解决问题的步骤与方法的自然语言法。这种描述方法通俗易懂，但比较繁琐，且对条件转向等的描述欠直观。针对自然语言法描述的缺点，又产生了流程图法、N-S图法和PAD图等方法。计算机的算法有数值型运算算法和非数值型运算算法。例如，计算N!的算法就属于数值型运算算法；而进行数据检索、分类、排序和计算机绘图、制表等都属于非数值型算法。下面我们介绍三种在计算机算法中常用的描述方法。1流程图流程图也称为框图，它是用各种几何图形、流程线及文字说明来描述计算过程的框图。用流程图表示算法的优点是：用图形来表示流程，直观形象，各种操作一目了然，不会产生“歧义性”，流程清晰。但缺点是：流程图所占面积大，而且由于允许使用流程线，使流程任意转移，容易使人弄不清流程的思路。,3.1算法和控制结构,3.1.2算法的描述方法书中的表3.1所示为用传统流程图描述算法时常用的符号。例如：赋值、数学运算等判断框根据框中给定的条件是否满足，选择执行两条路径中的某一条路径流程线表示流程的路径和方向连接点表示两段流程图流程的连接点用流程图描述程序的三种基本结构如书中图3.1所示。其中循环结构有两种形式：当型循环和直到型循环。当型循环是先进行判断，再执行循环体内的操作。直到型循环是先执行循环体内的操作，再进行判断。如果采用直到型循环结构，则不论条件是否成立，循环体内的操作都会被至少执行一次。,3.1算法和控制结构,3.1.2算法的描述方法,图3.1流程图描述程序3种基本结构,3.1算法和控制结构,3.1.2算法的描述方法2N-S图N-S结构化流程图是在美国学者INassi和BSchneiderman1973年提出的方法的基础上形成的一种以他们的名字命名的流程图，其主要特点是取消了流程线，即不允许流程任意转移，而只能从上到下顺序进行，从而使程序结构化。它规定了3种基本结构作为构造算法的基本单元，如图3.3所示。,3.1算法和控制结构,3.1.2算法的描述方法2N-S图图3.3N-S图描述程序3种基本结构图中的A和B分别代表某些操作，例如：数据赋值、数据的输入或输出等，也可以是3种基本控制结构中的某一种。顺序结构是最简单的一种结构，先执行A然后再执行B。选择结构则根据条件是否满足决定执行A或B。循环结构中的“直到型循环”，是先执行一次A，然后检查条件是否满足，如不满足则再执行一次A，直到某一次在执行完A后条件满足为止。循环结构中的“当型循环”，是先检查给定的循环条件是否满足，若满足则执行A，然后再检查一次条件满足否，直到某一次条件不满足为止。N-S图的不足之处是，当算法存在着较多层嵌套的选择结构时，图中的每个选择结构框会越分越窄，可能难以写下所需要的操作内容。,3.1算法和控制结构,3.1.2算法的描述方法2N-S图图3.3N-S图描述程序3种基本结构,图3.3N-S图描述程序3种基本结构,3.1算法和控制结构,3.1.2算法的描述方法2N-S图图中的A和B分别代表某些操作，例如：数据赋值、数据的输入或输出等，也可以是3种基本控制结构中的某一种。顺序结构是最简单的一种结构，先执行A然后再执行B。选择结构则根据条件是否满足决定执行A或B。循环结构中的“直到型循环”，是先执行一次A，然后检查条件是否满足，如不满足则再执行一次A，直到某一次在执行完A后条件满足为止。循环结构中的“当型循环”，是先检查给定的循环条件是否满足，若满足则执行A，然后再检查一次条件满足否，直到某一次条件不满足为止。N-S图的不足之处是，当算法存在着较多层嵌套的选择结构时，图中的每个选择结构框会越分越窄，可能难以写下所需要的操作内容。,3.1算法和控制结构,3.1.2算法的描述方法3PAD图PAD是英文ProblemAnalysisDiagram的缩写，其原意是问题分析图。它是近年来在软件开发中被推广使用的一种描述算法的图形方法。它是一种二维图形，从上到下各框功能顺序执行，从左到右表示层次关系。这种描述算法的方法，层次清楚，逻辑关系明了，在有多次嵌套时，不易出错。用PAD图描述程序的三种基本结构如书中图3.5所示。在为具体问题设计算法时，选用何种算法描述工具并不重要，重要的是一定要把算法描述得简洁、正确，不会产生理解上的“歧义性”。,3.1算法和控制结构,3.1.2算法的描述方法3PAD图,图3.5用PAD图描述程序的3种基本结构,3.2选择结构语句,3.2.1if语句1if语句形式之一（1）if形式流程图：可以根据表达式的值来判断应该执行哪一条或者哪些条语句，其语句的流程图如书中图3.6所示。,图中判断框内的条件是if语句中的表达式，处理框A是if语句中的子语句体，处理框B是if语句下面所有的语句。当程序执行到if语句时，计算机首先计算表达式的值，如果值是true，则执行if语句中的子语句体，然后再执行if语句下面的一条语句；如果值是false，则不执行if语句中的子语句，直接执行if语句下面的语句。,3.2选择结构语句,3.2.1if语句1if语句形式之一（2）if语句形式。if语句形式为：if(表达式)子语句体;其中，表达式的值必须是布尔类型的，可以是布尔类型的常量或者变量、关系表达式、或者逻辑表达式。子语句体可以是一条语句或者多条语句，但是多条语句要用一对大括号括起来。子语句体中可包含Java语言中的任何语句。,3.2选择结构语句,3.2.1if语句1if语句形式之二（1）if-else形式流程图：可以根据表达式的值来判断是执行if语句中的子语句体，还是执行else语句中的子语句体，如书中图3.7所示。,当程序执行到if-else语句时，计算机首先计算表达式的值，如果值是true，则执行if语句中的子语句体A，然后跳过else语句执行下面的一条语句C；如果值是false，则不执行if语句中的子语句体A，而执行else语句中的子语句体B，然后再继续向下执行语句C。,3.2选择结构语句,3.2.1if语句1if语句形式之二（2）if语句形式。if-else语句形式：if(表达式)语句体;else语句体;其中表达式的值必须是布尔类型的，可以是布尔类型的常量或者变量、关系表达式、或者逻辑表达式。语句体可以是一条语句或者多条语句，但是多条语句要用一对大括号括起来。else语句不能单独作为一个独立的语句使用，它必须和if语句配对使用。,3.2选择结构语句,3.2.1if语句3if语句形式之三（1）if-elseif-else形式流程图：可以根据多个表达式的值来判断执行哪一条或者哪些条语句，而不执行其他语句体，如书中图3.8所示。图中判断框内的条件1是if语句中的表达式，条件2是elseif语句中的表达式。处理框A是if语句中的子语句体，处理框B是elseif语句中的子语句体，处理框C是else语句中的子语句体，处理框D是if-elseif-else语句下面的语句。,3.2选择结构语句,3.2.1if语句3if语句形式之三当程序执行到if-elseif-else语句时，计算机首先计算表达式1的值，如果值是true，则执行if语句中的子语句体A，然后跳过elseif语句和else语句，继续执行下面的语句D。如果表达式1的值为false，则执行elseif语句。如果elseif语句中的表达式2的值为true，则执行elseif语句中的子语句体B，然后跳过else语句，继续执行下面的语句D。如果表达式2的值为false，则执行else语句的字语句体C，然后再继续执行下面的语句D。在实际应用中，elseif语句可以多次使用，但是else语句只有一个。,3.2选择结构语句,3.2.1if语句3if语句形式之三（2）if-elseif-else语句形式。if-elseif-else语句基本格式为：if(表达式1)语句体1elseif(表达式2)语句体2elseif(表达式n)语句体nelse语句体n+1,3.2选择结构语句,3.2.1if语句3if语句形式之三其中表达式的值必须是布尔类型的，可以是布尔类型的常量或者变量、关系表达式、或者逻辑表达式。语句体可以是一条语句或者多条语句，但是多条语句要用一对大括号括起来。一个if语句可以跟随任意多个elseif语句，但只能有一个else语句。,图3.8if-elseif-else形式流程图,3.2选择结构语句,3.2.2switch语句1switch语句形式switch语句的完整形式为：switch(表达式)case常量1:语句体1;break;case常量2:语句体2;break;case常量3:语句体3;break;case常量n:语句体n;break;default:语句体n+1;,3.2选择结构语句,3.2.2switch语句1switch语句形式在使用时要注意以下几点：（1）表达式的值必须是整型或者字符型数据，并且要与各个语句中case之后的常量值类型相同。（2）一个switch语句中，可以有任意多个case语句，但是每个case之后的常量值不能相同。case语句中的子语句体可以是一条或者多条任意Java语句。（3）一般情况下，每个case语句的最后是break语句，用来从整个switch语句中，跳出，继续执行switch语句下面的语句。如果没有使用break语句，则继续执行下面的case语句中的字语句体，直到遇到break语句，或者整个switch语句结束。（4）当所有case语句中的常量值都与表达式的值不相同时，则执行default语句中的子语句体，如果没有default语句，则不执行任何内容。,3.2选择结构语句,3.2.2switch语句2switch语句执行顺序当执行到switch语句时，首先计算表达式的值，然后依次与下面大括号中case语句中的常量作比较。当找到和表达式值相同的常量值后，将不在继续查找，并以此处作为进入大括号中case语句的子语句体的插入点。插入点之前的子语句体不会再被执行，而插入点之后到第一个break语句之前的所有子语句体都会被执行。遇到break语句时，结束整个switch语句的执行，跳到其下面的语句，继续运行程序。switch语句执行顺序可以这样比喻：switch语句中的表达式值是一把钥匙，每个case语句的常量值代表一个房间的门锁。只有当钥匙和门锁吻合时，我们才能打开门，进入房间。如果没有吻合的门锁，我们将直接进入default房间。进入某个房间后，我们执行房间中的命令，然后一直向下走，依次进入其后的每个房间并执行其中的命令。直到遇到出口，也就是break语句，走出房间，完成整个switch语句的执行。,3.2选择结构语句,3.2.2switch语句2switch语句执行顺序从上面的描述中，我们可以看出break语句的重要性。break语句的位置会影响到输出结果。例如，下面是某个程序的switch语句部分，如果变量i的值为1，则会输出“键入的数字是1”的文字，然后继续执行switch语句后边的语句。但是如果case1中没有break语句，则当变量i的值为1时，会执行case1和case2中的打印语句，而不是只执行case1中的打印语句，输出结果为“键入的数字是1”和“键入的数字是2”两行文本。,3.2选择结构语句,3.2.2switch语句switch(i)case1:System.out.println(键入的数字是1);break;case2:System.out.println(键入的数字是2);break;case3:System.out.println(键入的数字是3);break;case4:System.out.println(键入的数字是4);break;case5:System.out.println(键入的数字是5);break;case6:System.out.println(键入的数字是6);break;default:System.out.println(输入的数字超出范围!);一般情况下，每个case语句的最后都会使用break语句。如果有default语句，则放置在所有case语句的最后，不需要使用break语句。,3.2选择结构语句,3.2.2switch语句3合并case语句如果不同case语句中的常量之后的语句体相同，则可以合并多个case语句，合并的形式为：case常量1:case常量2:case常量n:语句体;例如，下面显示2005年某个月份天数的程序中的switch语句就合并了某些case语句。因为1、3、5、7、8、10和12月的天数都是31天；4、6、9和11月的天数都是30天，而2月份为28天，switch语句简化为：switch(month)case1:case3:case5:case7:case8:case10:case12:System.out.println(“31天”);break;case4:case6:case9:case11:System.out.println(“30天”);break;case2:System.out.println(“28天”),3.3循环结构语句,3.3.1while语句1while循环语句形式之一（1）while形式流程图：while形式可以反复执行某些特定的子语句体，并根据表达式的值来判断什么时候结束循环，继续执行while语句下面的语句，其语句的流程图如书中图3.12所示。,1while循环语句形式之一,3.3循环结构语句,3.3.1while语句1while循环语句形式之一图中判断框内的条件是while语句中的表达式，处理框A是while语句中的子语句体，也就是循环体。处理框B是while语句下面的语句。当程序执行到while语句时，首先计算其表达式的值，如果值是true，则执行while语句中的循环体A，然后再次计算while语句中表达式的值，如果值是true，则再次执行while语句中的循环体A，如此反复循环下去。当小括号中表达式的值为false时，则不再执行while语句中的循环体A，而是直接执行while语句下面的语句B。,3.3循环结构语句,3.3.1while语句1while循环语句形式之一（2）while语句形式。while语句的形式为：while(表达式)循环体；其中表达式的值必须是布尔类型的，可以是布尔类型的常量或者变量、关系表达式、或者逻辑表达式。循环体可以是一条或者多条语句。多条语句时，要用大括号括起。如果在程序执行过程中，while语句中表达式的值始终为true，则循环体会被无数次执行，进入到无休止的“死循环”状态中。这种情况在编写程序时一定要避免。例如，表示式尽量不要使用布尔类型的常量。如果在第一次执行while语句时，表示式的值为false，则不执行循环体，直接执行while语句下面的语句。,3.3循环结构语句,3.3.1while语句1while循环语句形式之一例如，下面的程序是使用while语句求1+2+99+100的和。publicclassSumpublicstaticvoidmain(Stringargs)intsum=0,n=1;while(n=100)sum=sum+n;/累加器n=n+1;System.out.println(1+2+99+100=+sum);在上面的程序中，sum=sum+n;语句中的变量sum又叫累加器，用来保存变量n从1一直累加到100的和，也可以写为sum+=n;的形式。一般来说，累加器的初始值为0。,3.3循环结构语句,3.3.1while语句2while循环语句形式之二（1）do-while形式流程图：它与while语句很相似，它是先执行循环体，然后再判断的循环语句，其语句的流程图如书中图3.13所示。,图3.13do-while形式流程图,3.3循环结构语句,3.3.1while语句2while循环语句形式之二图中判断框内的条件是do-while语句中的表达式，处理框A是do-while语句中的子语句体，也就是循环体。处理框B是do-while语句下面的语句。当执行到do-while语句时，先执行do-while语句的循环体A，然后判断do-while语句中表达式的值。如果值是true，则再次执行循环体A，然后再次计算表达式的值，如果值是true，则继续执行循环体A，如此反复循环下去。当表达式的值为false时，则不再执行循环体A，循环结束，直接执行下面的语句B。,3.3循环结构语句,3.3.1while语句2while循环语句形式之二（2）do-while语句形式。do-while语句的形式为：do循环体;while(表达式);其中表达式的值必须是布尔类型的，可以是布尔类型的常量或者变量、关系表达式、或者逻辑表达式。循环体可以是一条或者多条语句。多条语句时，要用大括号括起。不论表达式的值是true还是false，循环体中的语句至少被执行一次。要注意：在do-while形式中，while(表达式)后边要有分号，而在while形式中，则不需要分号。while语句和do-while语句没有本质的区别，在大多数情况下可以互相代替。,3.3循环结构语句,3.3.1while语句2while循环语句形式之二例如，下面的程序是使用do-while语句求1+2+3+99+100的和。publicclassSumpublicstaticvoidmain(Stringargs)sum=0;n=1;dosum=sum+n;n=n+1;while(n=100);System.out.println(使用do-while语句求和：+sum);,3.3循环结构语句,3.3.1while语句3设计循环语句在编写循环语句之前，需要先设计好循环语句的内容，以确保运行程序后达到预期的效果。设计循环语句主要有4个步骤，介绍如下。（1）设计循环体。首先要确保循环体中的语句可以被执行，然后要有规律地改变与表达式有关的变量的值，从而使表达式的值在特定的循环次数完成后，可以变成false，结束循环。（2）设计表达式。使用表达式来控制什么时候结束循环。在使用关系表达式时，要注意大于和大于等于、小于和小于等于关系符号的使用，以确保循环次数不会少一次或者多一次。例如，在上面求和的程序中，如果while语句中的表达式写为n100，则程序变为求1+2+3+99的和。（3）循环的初始化：一般要在循环语句之前定义在循环体中所要使用的变量，并且给变量赋初值。初值的不同，会影响到最终的运行结果。例如，在上面的程序中，如果将变量n的初值从1改为30，则变成求30+31+99+100的和。（4）结束循环：确保表达式的值最终会变为false，避免出现“死循环”。,3.3循环结构语句,3.3.2for语句1for循环语句（1）for语句流程图：与while语句类似，for语句也可以反复执行某些特定的子语句体，并根据表达式的值来判断什么时候结束循环，继续执行for语句下面的语句。所不同的是，for语句的形式更加简单明了，其语句的流程图如书中图3.15所示。,图3.15for语句流程图,3.3循环结构语句,3.3.2for语句1for循环语句图中判断框内的条件是for语句中的表达式2，处理框初始化循环变量是for语句中的表达式1，处理框增量是for语句中的表达式3，处理框A是for语句中的子语句体，也就是循环体。处理框B是for语句下面的语句。当程序执行到for语句时，先执行for语句中的表达式1，给循环变量赋初值。如果在for语句之前没有定义循环变量，则该表达式可以定义循环变量并赋初值。循环变量与其他变量在使用上没有区别，只是该变量主要是用来控制for语句的循环次数，并且在某些情况下参与循环体中的计算。完成初始化后，再对表达式2进行判断，如果其值为true，则执行循环体A；如果其值为false，则跳出整个for语句，执行其下面的语句B。执行完循环体A后，按照表达式3来修改循环变量的值，然后重新计算表达式2的值，开始第2轮循环。,3.3循环结构语句,3.3.2for语句1for循环语句（2）for语句的形式。for语句的形式为：for(表达式1;表达式2;表达式3)循环体；循环体可以是一条或者多条语句。多条语句时，要用大括号括起。表达式1：表达式1是循环变量赋初值的表达式，循环体内使用的变量也可以在此定义或者赋初值。表达式1中可以并列多个表达式，但它们之间要用逗号隔开。,3.3循环结构语句,3.3.2for语句1for循环语句例如：for(sum=0,n=1;n=100;n+)循环体；在for语句的表达式1中，给变量sum和n赋初值。表达式2：必须为布尔类型的常量或者变量、关系表达式、或者逻辑表达式。因为表达式2是循环结束的条件，所以编写表达式时要避免程序陷入“死循环”。当表达式的值为true时，继续执行循环体；当表达式的值为false时，结束循环，执行for语句下面的程序内容。表达式3：一般是增量表达式，每次执行完循环体后，都要执行该表达式改变其中变量的值。,3.3循环结构语句,3.3.2for语句3for语句的特殊形式除了上面介绍的for语句的标准形式外，for语句还具有一些特殊的形式。（1）空循环体：for语句可以没有循环体，也就是说循环过程什么都不执行，仅仅产生一个时间延迟的效果。例如：下面的语句for(intn=1;n=80000;n+)该语句没有循环体。当程序执行到该语句时，只会执行80000次对表达式n=80000的判断和n+;语句。（2）减量表达式：for语句中的表达式3不仅可以是增量表达式，还可以是减量表达式，也就是说循环变量的值不仅可以由小到大，还可以由大到小。,3.3循环结构语句,3.3.2for语句3for语句的特殊形式（3）省略表达式：for语句中的3个表达式都可以省略，但是其中的分号不可以省略。如果省略表达式1，则不对循环变量赋初值，使用其默认值，或者在for语句之前赋初值。如果省略表达式2，则不再进行判断选择形成“死循环”。我们也可以在循环体中添加与表达式2相同功能的语句，控制循环结束的条件。如果省略表达式3，则不对循环变量的值进行改变。我们也可以在循环体中添加与表达式3相同功能的语句，改变循环变量的值。如果3个表达式都省略，则for语句不对循环进行控制。我们也可以在循环体中添加语句来控制循环。,3.3循环结构语句,3.3.2for语句3for语句的特殊形式（4）简化循环体：如果循环体中的语句只有一两条，可以放在表达式3之前，两者用逗号隔开，for语句的最后要添加一个分号。例如，求数字1到100平方数的和，其程序可以写成如下形式：publicclassSqaurepublicstaticvoidmain(Stringargs)for(intn=1;n=100;System.out.print(n*n+),n+);,3.3循环结构语句,3.3.3跳转语句1break语句break语句通常用在循环语句和switch语句中。它的作用是使程序从一个语句体的内部跳出去，继续执行该语句体下面的语句。例如，从switch语句的case语句中跳出，或者从循环体内跳出。在循环语句中，break语句一般与if语句一起使用，满足一定条件时跳出循环。例如：publicclassExamplepublicstaticvoidmain(Stringargs)for(intd=1;d30)break;System.out.println(area);,3.3循环