《RAPTOR流程图算法设计教程》课件ch5.pptx

1、第5章 用用RAPTORRAPTOR循环结循环结构实现重复操作构实现重复操作用用学习目标学习目标 掌握循环的概念及实现机理 掌握循环结构设计的方法 学会用循环结构解决实际问题目录目录5.1 RAPTOR循环结构循环结构5.2用用RAPTOR循环结构实现重复操作循环结构实现重复操作5.3 循环循环结构结构程序设计应用举例程序设计应用举例RAPTOR函函5.1 RAPTOR5.1 RAPTOR循环结构循环结构5.1.1 5.1.1 为什么使用为什么使用循环结构循环结构5.1.25.1.2RAPTORRAPTOR的的循环循环结构结构5.1.1 5.1.1 为什么为什么使用循环结构使用循环结构 到目前

2、为止，无论是顺序结构还是选择结构设计的程序语句都只执行一次，但在实际问题中会遇到很多的具有规律性的重复运算或操作，如：使用银行卡，密码只能重复输入三次，超过三次系统就自动锁定，这如何控制？猜数游戏，只有当玩家猜对数字时，游戏才停止，否则允许玩家不断猜下去。5.1.1 5.1.1 为什么使用循环结构为什么使用循环结构 这样的例子很多，它们都是重复执行某些操作，这种重复执行就是循环。【例5-1】求1+2+3+10的累加和。问题分析：这是一个简单求自然数110的累加和问题。从数学角度分析，求解110的累加和问题可以使用公式：（首项+末项）项数2的方法，但用计算机解决该问题又如何实现呢？实现方法有几种

3、呢？算法1：直接使用前面所学的顺序结构知识写出算式sum=1+2+3+4+5+10的累加和，如图5-1所示。但要是累加到1000项呢，就需要写得很长且非常繁琐，这不适合编程。算法2：要求1+2+3+.+10的累加和，可以分解成几个步骤：Step1：在一个数都没有加时，最初的和肯定是0，就有S0；Step2：初始和加上1得到第1项的累加和，即S10+1；Step3：第1项的累加和加上2得到前两项的累加和，即S2S1+2；Step11：第9项的累加和加上10得到所有项的累加结果。因此，要求解1+2+3+.+10的累加和就可以改写为(0+1)+2)+3)+10)的形式计算。算法3：从算法2中可以看出

4、一个规律，求累加和，在一个数都没有加时，最初的和肯定是0，就有S00，从第二步开始都是两个数相加，其中加数总是比前一步加数增加1后参与后一步加法运算，被加数总是前一步加法运算的和。因此，我们可以考虑用一个变量i存放加数，一个变量sum存放前一步的加法运算的和，那么每一步都可以写成sum+i，然后将sum+i的和再次存放到sum中即sum=sum+i。也就是说，sum既代表被加数又代表加法运算的和，这样就可以得到算法3。算法4：从算法3上可以看出程序重复执行的是sum=sum+i和i=i+1两条语句，而计算机对重复的操作可以用循环完成。在算法3的基础上采用循环方式实现算法4。从算法4可以看到，程

5、序重复执行累加和的操作，当重复的次数达到最后一个数字10时，就结束循环，这就是一个典型的循环结构程序。显然，使用循环方式解决该问题比前3种算法要方便得许多。5.1 RAPTOR5.1 RAPTOR循环结构循环结构5.1.1 5.1.1 为什么使用为什么使用循环结构循环结构5.1.25.1.2RAPTORRAPTOR的的循环循环结构结构5.1.2 RAPTOR5.1.2 RAPTOR的的循环循环结构结构 RAPTOR中循环结构（Loop）是用一个椭圆和一个菱形符号表示。需要重复执行的部分(循环体)由菱形符号中的条件表达式控制。在执行过程中，如果条件表达式结果为“NO”，则执行循环体，否则循环结束

6、。构成循环结构的三要素为循环初始值、循环条件以及循环体。循环结构两种不同执行情况：先判断循环条件 先执行循环体语句先判断循环条件先判断循环条件在RAPTOR循环结构中，将循环体语句（要重复执行的语句）放在菱形符号的下方。循环开始前先对循环条件测试，一旦测试结果为“No”，则执行循环体内的语句，反之测试结果为“Yes”，则不执行循环体内的语句。这种方式在RAPTOR循环结构中称之为前序测试。先执行循环体语句先执行循环体语句在RAPTOR循环结构中，将循环体语句（要重复执行的语句）放在菱形符号的上方。循环开始前先执行循环体内语句，再判断循环条件。判断结果为“No”，则继续执行循环，判断结果为“Ye

7、s”，则结束循环。这种方式在RAPTOR循环结构中称之为后序测试。从以上2种RAPTOR循环结构测试模式可以看出，循环体语句可以放置到菱形符号上方或下方，放置位置不同会影响算法的执行效率和执行结果，所以什么时候进行判断循环条件是循环结构的十分关键之处。循环结构应用实例循环结构应用实例 循环结构常用于解决累加求和、累乘求积、数据分类统计等这类问题。在解决这类问题中，往往又需要通过循环次数来控制循环结构的执行，通常有3种常用的循环结构应用实例。计数循环 输入循环 输入验证循环计数计数循环循环循环结构常见形式就是按照特定的次数执行循环，即循环之前可以预知循环的次数。为了控制循环次数，在程序中设置一个

8、循环控制变量，每次循环，该变量执行一次加法运算操作，当变量值累加到大于设定的上限值时，循环自动结束，这种方式就是计数循环。其操作要点包括：循环开始前需要对计数变量进行初始化；在循环过程中要对计数变量的值进行修改；将计数变量使用在循环条件中，用于终止循环。输入输入循环循环输入循环的问题是指循环之前不可预知循环需要执行多少次，需要通过用户输入一系列值后才能循环次数。一般情况下，它有两种方法：让用户输入一个“特殊”的值表示用户完成数据的输入 事先询问用户要输入多少个值，该值可用于实现计数循环中控制循环的次数输入验证循环输入验证循环如果用户输入的数据需要满足一定的约束，如输入人的年龄，程序要验证用户的

9、输入，确保满足约束条件后，才可以执行循环。目录目录5.1 RAPTOR循环结构循环结构5.2用用RAPTOR循环结构实现重复操作循环结构实现重复操作5.3 循环循环结构结构程序设计应用举例程序设计应用举例RAPTOR函函5.2 RAPTOR5.2 RAPTOR循环结构实现重复操作循环结构实现重复操作5.2.1 5.2.1 单单循环循环结构结构5.2.25.2.2多重多重循环结构循环结构5.2.1 5.2.1 单重循环单重循环结构结构 单重循环结构 只包含一个循环体的RAPTOR循环结构。单重循环结构多用于解决级数问题（数列累加和、累乘求积）、数据处理、分类统计等问题。5.2.1 5.2.1 单

10、重循环结构单重循环结构 级数问题 级数问题解决的关键是：观察数列中的相邻项，找出规律，将规律转化为若干通式(所谓通式是指在循环体中被反复执行的语句)。分母的通式：m=m+i；循环控制变量的通式：i=i+1；当前项的通式：t=1/m；求和的通式：s=s+t。其算法可以表示如下：Step1：输入n值；Step2：对循环控制变量i、分母变量m、求和变量s赋初值；Step3：判断in是否成立，若成立，则执行Step6，否则执行Step4和Step5；Step4：进行求分母m、当前项t、和s；Step5：循环控制变量i加1，转去执行Step3；Step6：分别输出n值、数列求和结果s值。5.2.1 5.

11、2.1 单重循环结构单重循环结构 数据处理问题【例5-7】水仙花数求出所有的“水仙花数”。所谓“水仙花数”是指一个三位正整数，其各个数字立方和等于该数本身，例如：153=13+53+33，153就是“水仙花数”。问题分析：首先要确定“水仙花数”的范围要在100999之间；然后分离出这个数的百位i、十位j、个位k；最后判断这个数是否等于i3+j3+k3，即可知道该数是否为“水仙花数”。其算法可以表示为：Step1：对三位正整数变量num赋初值；Step2：判断num999是否成立，若成立，则结束循环，否则执行Step3和Step4；Step3：对三位正整数各个数位进行分离；Step4：判断num

12、=i3+j3+k3是否成立，若成立，则该三位正整数num为“水仙花数”，并输出该数；Step5：三位正整数num加1，转去执行Step2。5.2.2 5.2.2 多多重重循环结构循环结构在循环结构中如果一个循环体内又包含了另一个完整的循环结构，即循环套循环，这种结构称为多重循环，也称之为嵌套循环。一般将处于内部的循环称为内循环，处于外部的循环称为外循环。5.2.2 5.2.2 多多重循环结构重循环结构 多重循环结构执行过程：程序从外循环进入到内循环后，先执行内循环中的语句，直到内循环结束后再继续执行外循环，这样反复地执行，直到外循环结束后，多重循环结构执行才结束。由此可见，多重循环的执行顺序是

13、由内向外逐层展开。目录目录5.1 RAPTOR循环结构循环结构5.2用用RAPTOR循环结构实现重复操作循环结构实现重复操作5.3 循环循环结构结构程序设计应用举例程序设计应用举例RAPTOR函函5.3 5.3 循环结构程序设计应用举例循环结构程序设计应用举例5.3.1 5.3.1 枚举法求解枚举法求解不定方程不定方程5.3.25.3.2递推递推问题求解问题求解5.3.3 5.3.3 逻辑问题求逻辑问题求解解5.3.1 5.3.1 枚举法求解不定方程枚举法求解不定方程【例5-11】百钱百鸡问题古代数学家在算经中有一道题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、

14、雏各几何？”意思是：公鸡5文钱1只，母鸡3文钱1只，小鸡1文钱3只。用100文钱买100只鸡，问公鸡、母鸡、小鸡各有几只？5.3 5.3 循环结构程序设计应用举例循环结构程序设计应用举例5.3.1 5.3.1 枚举法求解枚举法求解不定方程不定方程5.3.25.3.2递推递推问题求解问题求解5.3.3 5.3.3 逻辑问题求逻辑问题求解解5.3.2 5.3.2 递推问题求解递推问题求解 递推法根据具体问题，建立递推关系，在通过递推关系求解问题的方法。利用递推法求解问题的一般步骤包括：Step1：确定递推变量；Step2：建立递推关系式；Step3：确定边界条件；Step4：利用循环结构实现递推求

15、解问题。【例5-14】楼梯走法问题有一段楼梯有10级台阶，规定每一步只能跨一级或两级，问：要登上第10级台阶有多少种不同的走法？问题分析：依据题意进行分析可知：首先确定递推关系。设k级台阶的不同登法共f(k)种，那么登上10级台阶共f(10)种不同的爬法。登上第10级台阶之前在哪一级呢？只能是位于第9级台阶（共f(9)种不同的登法），跳1级台阶即可完成上山，或位于第8级台阶（共f(8)种不同的爬法），跳2级台阶即可完成上山。因此，f(10)=f(9)+f(8)。依次类推，得到递推关系：f(k)=f(k-1)+f(k-2)（k2）5.3 5.3 循环结构程序设计应用举例循环结构程序设计应用举例5

16、.3.1 5.3.1 枚举法求解枚举法求解不定方程不定方程5.3.25.3.2递推递推问题求解问题求解5.3.3 5.3.3 逻辑问题求逻辑问题求解解5.3.3 5.3.3 逻辑逻辑问题求解问题求解【例5-15】谁做的好事已知有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。A说：“不是我。”B说：“是C。”C说：“是D。”D说：“C胡说。”已知其中3个人说的是真话，1个人说的是假话。现在要根据这些信息，编写程序，找出做了好事的人。问题分析：为了解决这道题，需要逻辑思维与判断，下面把这4个人说的4句话写成关系表达式，使用变量Thisman表示要找的人，关系运算符“=

17、”表示“是”，用“!=”表示“不是”。则这4个人说的4句话使用关系表达式分别为：A说：不是我。写成关系表达式为Thisman!=A；B说：是C。写成关系表达式为Thisman=C；C说：是D。写成关系表达式为Thisman=D；D说：C胡说。写成关系表达式为Thisman!=D。如何找到该人，一定是“先假设该人是做好事的人，然后到每句话中去测试看有几句是真话”，有3句是真话就确定是该人，否则换一人再试。【例5-16】谁在说谎参与银行抢劫案的三个人A、B、C被拘捕调查，通过审讯，这三个人对案件供述分别如下：A说：“B在说谎。”B说：“C在说谎。”C说：“A和B都在说谎。”现在问：这三人中到底谁说

18、的是真话，谁说的是假话？问题分析：根据对题目理解，这三个人都有可能说的是真话，也有可能说的是假话，这样就需要对每个人所说的话进行分别判断，那如何判断他们到底谁在说谎呢？由问题描述可以得到如下：由于“A说B在说谎”，因此，如果A说的是真话，则B就在说谎；反之，如果A说的是谎话，则B就在说真话；由于“B说C在说谎”，因此，如果B说的是真话，则C就在说谎；反之，如果B说的是谎话，则C就在说真话；由于“C说A和B都在说谎”，因此，如果C说的是真话，则A和B都在说谎；反之，如果C说的是谎话，则A和B至少一人说真话。本章小结本章小结循环结构是程序设计中非常重要的内容，应该熟练掌握。本章介绍了循环的概念及实现机理，也介绍了两种RAPTOR循环结构、单重循环结构以及多重循环结构，并通过实际案例讲解各种类型问题如何应用循环结构实现。