3.3　循环结构

循环结构是指重复地执行算法中的某些步骤，直到满足某个条件时，才结束循环操作。在编程中，循环结构是经常被使用的一种基本结构。例如，在判断自然数在1000以内的所有质数时，需要重复判断每个自然数是否为质数，这种重复操作就适合使用循环结构来完成。一般情况下，循环结构不会单独使用，通常配合顺序结构或选择结构一起使用。这3种结构就是程序的基本结构，任何复杂的程序都能使用这3种基本结构组合而成。

在Scratch的控制指令面板中，提供如图3-3-1所示的一些指令积木用于创建循环结构的程序脚本。这些指令积木是：“重复执行直到…”积木、“重复执行…次”积木和“重复执行”积木，可以将需要重复执行的一组指令积木作为循环体嵌入到循环指令积木内部。

3.3.1　跟我做：冰雹猜想

在程序中使用循环结构，能够执行一些重复性的操作。在本案例中，我们编程验证“冰雹猜想”，以此讲解循环结构在编程中的应用。

1．例题

“冰雹猜想”是一种有趣的数字黑洞，它的规则描述如下。

任意取一个正整数n。如果n是奇数，则把n变为3n+1；如果n是偶数，则把n变为n÷2。按此规则不断重复操作，最终一定会得到1。

请设计一个验证“冰雹猜想”的算法，并画出程序框图和编写程序。

2．算法分析

我们以正整数52为例，按照“冰雹猜想”的规则对它进行变换操作，整个变换过程是：26、13、40、20、10、5、16、8、4、2、1。可以看到，把正整数52经过11步变换之后就能得到1。

由于变换操作需要重复进行，适合使用循环结构来描述算法。为了便于观察整个变换过程，需要把每次变换的值记录下来，这些数值可用Scratch中的列表来存放。为此，我们需要使用“数据”指令面板中的“建立一个列表”按钮来创建一个名为“日志”的列表。

使用自然语言将验证“冰雹猜想”的算法描述如下。

第1步，清空“日志”列表。

第2步，输入一个正整数n。

第3步，判断n是否等于1，如果是，则结束循环；如果不是，则执行第4步。

第4步，如果n是偶数，则使n=n/2；如果是奇数，则使n=3n+1。

第5步，将变换后的n值输出到“日志”列表中，返回到第3步重复执行。

使用程序框图描述上述算法，如图3-3-2所示。

3．编写程序

根据上述算法的描述，使用“重复执行直到…”积木、“如果…那么…否则”积木、列表积木等来创建循环结构的程序脚本，如图3-3-3所示。

在这个脚本中使用一个名为“日志”的列表来存放数据，可以通过“数据”指令面板中的“建立一个列表”按钮来创建这个列表。之后，在“数据”指令面板中就会显示“删除第（全部）项于［日志］”积木和“将…加到［日志］”积木，如图3-3-4所示。

运行这个程序，输入任意正整数，总是可以变换得到1。如图3-3-5所示，这是输入27时在“日志”列表中记录的各个变换数值，这个列表共记录了111个数值，最后一个数是1。由此可认为，“冰雹猜想”验证通过。

3.3.2　循环结构的程序设计

在程序设计中，算法的某些操作步骤会被设计为在一定条件下能够被重复执行的部分，这就是算法中的循环结构，反复执行的操作步骤称为循环体。循环体是由若干个操作步骤组成的，它们可以是顺序结构的，也可以是选择结构的，或者是循环结构的，还可以是这些基本结构的嵌套组合。

1．循环结构介绍

在程序框图中，循环结构使用判断框和流程线表示。在判断框内写上条件，它的两个出口分别指向条件成立和条件不成立时所执行的不同操作步骤。其中一个出口指向循环体，再从循环体回到判断框的入口处；另一个出口指向循环结构之外的其他操作步骤。根据条件满足时是跳出循环还是进入循环，可以将循环结构分为直到型循环和当型循环。

如图3-3-6所示，在这种循环结构中，先执行循环体内的操作步骤，再判断给定条件是否成立，若给定条件不成立，则再次执行循环体；如此反复，直到给定条件成立时就结束循环。因此，这样的循环结构称为直到型循环。

如图3-3-7所示，在这种循环结构中，先判断所给条件是否成立，若给定条件成立，则执行循环体内的操作步骤；再判断给定条件是否成立；若给定条件成立，则再次执行循环体；如此反复，直到某一次给定条件不成立时为止。因此，这样的循环结构称为当型循环。

简单地说，直到型循环和当型循环的区别如下。

区别1：直到型循环先执行后判断，当型循环先判断后执行。

区别2：直到型循环至少执行一次循环体，当型循环可以不执行循环体。

区别3：对同一算法来说，直到型循环和当型循环的条件互为反条件。

大多数编程语言都提供以上两种基本的循环结构控制指令（语句）。但是，Scratch是个例外，它支持的是一种将判断条件前置的直到型循环结构，对应的是Scratch控制指令面板中的“重复执行直到…”指令积木。如图3-3-8所示，在这种直到型循环结构中，判断条件被放置在循环体的前面。当给定条件不成立时，就执行循环体；如此反复，直到给定条件成立时就结束循环。

2．循环结构示例

1）例题

设计一个算法，计算1+2+3+…+100的值，并画出程序框图和编写程序。

2）算法分析

对于这个问题，如果能像高斯那样发现其中的规律，就可以使用“50*101=5050”这种简洁的方法快速计算出结果。但是，很多人采用的求解方法可能就是从1加到100，从而得到结果，计算过程如下。

第1步，0+1=1。

第2步，1+2=3。

第3步，3+3=6。

⋮

第100步，4950+100=5050。

从上述过程中可以看到，虽然每一步计算的数字都在变化，但它的计算方式却是有规律的，这适合使用循环结构来描述。

假设以S表示累加的和（初始为0），i表示从1到100变化的加数，那么上述计算过程的规律就是，每一步都是用上一步累加的和S加上每一步变化的加数i。这个计算规律可用公式S=S+i来表示，它可作为循环结构中被重复执行的循环体。

使用Scratch支持的条件前置直到型循环结构将求解这个问题的算法描述如下。

第1步，将变量S设定为0，变量i设定为1。

第2步，判断如果变量i大于100不成立，那么就执行第3步，否则就执行第5步。

第3步，计算S=S+i。

第4步，将变量i加1，并返回第2步。

第5步，输出累加和S。

使用程序框图来描述上述算法，如图3-3-9所示。

3）编写程序

根据上述算法的描述，使用“重复执行直到…”指令积木创建循环结构的程序脚本，如图3-3-10所示。

由上可见，循环结构本身非常简单，但在解决实际问题中，将循环结构用于需要重复执行某些步骤的算法中，能极大地简化编程。只要设计好循环体中可重复执行的步骤，并设置好循环的退出条件，剩下的事情就可以交给计算机去执行。

3．直到型循环转为当型循环

Scratch提供一个“重复执行直到…”指令积木用来创建条件前置直到型循环结构的程序，而没有提供用于创建当型循环的指令积木。因为对于同一算法来说，直到型循环和当型循环的条件互为反条件，所以，使用能够进行逻辑非运算的“…不成立”积木与“重复执行直到…”积木的组合，就能够间接地实现当型循环结构。

举例来说，假设要创建一个循环结构，让循环变量i从1开始逐一递增，使循环体被重复执行3次。那么，直到型循环结构的循环结束条件是，再根据这个条件创建一个直到型循环结构，如图3-3-11所示。

而当型循环结构的循环进入条件是，对这个条件使用“…不成立”积木进行逻辑取反运算，并使用“重复执行直到…”积木建立一个循环结构，就得到一个与当型循环结构等价的直到型循环结构，如图3-3-12所示。

4．其他循环结构

Scratch还提供另外两个循环指令积木：“重复执行…次”积木和“重复执行”积木。前者有一个数字参数用于设定循环体被执行的次数；而后者是一个没有循环条件的循环结构，它会无限次地重复执行循环体，这在其他语言中被称为“死循环”，除非明确地知道这种“死循环”是有意义的，否则应该尽量避免使用。

3.3.3　动手练：肖像在哪里

1．练习重点

循环结构、关系运算和逻辑运算的应用。

2．问题描述

富家少女鲍西娅品貌双全，贵族子弟、公子王孙纷纷向她求婚。鲍西娅按照其父遗嘱，由求婚者猜盒订婚。鲍西娅有金、银、铅3个盒子，分别刻有3句话，其中只有1个盒子放有鲍西娅肖像。求婚者通过这3句话，谁猜中鲍西娅的肖像放在哪个盒子里，她就嫁给谁。3个盒子上刻的3句话分别如下。

金盒子：肖像不在此盒子中。

银盒子：肖像在铅盒子中。

铅盒子：肖像不在此盒子中。

鲍西娅告诉求婚者，上述3句话中，只有1句是真的。请问鲍西娅的肖像究竟放在哪个盒子里？请分析这个问题画出程序框图，并编写程序求解答案。

3．解题分析

这个问题是一道逻辑推理题，需要用到关系运算、逻辑运算和循环结构。假设用变量n代表盒子编号，金、银、铅3个盒子的编号分别为1、2、3，然后将题目中的3个已知条件转为能够进行关系运算和逻辑运算的表达式，如表3-3-1所示。

由于关系运算和逻辑运算的结果是布尔值（true或false），如果对布尔值进行加法运算，布尔值会被自动转为1或0后再参与运算。因此，要表示3句话中只有1句话是真的，可以把表3-3-1中的3个表达式进行关系运算或逻辑运算后的结果值相加，然后判断它们的和是否为1。假设变量p1、p2和p3代表3个表达式的值，将表3-3-1中的表达式用Scratch的指令积木来描述，如图3-3-13所示。

解决这个逻辑推理问题的思路是，在一个循环结构中，使代表盒子编号的变量n从1到3变化。在循环体中，将变量n的值代入3个表达式中运算，再判断如果3个表达式的运算结果相加等于1，就能找到该问题的解。

使用自然语言来描述解决这个逻辑推理问题的算法，具体步骤如下。

第1步，将变量n设定为1。

第2步，判断如果变量n大于3成立，就结束循环；如果不成立，就执行第3步。

第3步，设置变量p1为“n=1不成立”、变量p2为“n=3”、变量p3为“n=3不成立”。

第4步，判断如果“p1+p2+p3=1”不成立，就执行第5步；如果成立，就执行第6步。

第5步，使变量n增加1，并返回第2步重复执行。

第6步，输出变量n值，并结束脚本。

4．练习内容

（1）在图3-3-14所示算法流程图中的程序框内写上文字说明。

（2）把图3-3-15所示程序脚本中的空白积木替换为真实积木。

（3）运行程序，得到结果为：______，由此可知，鲍西娅的肖像放在______盒里。