第 6 讲：让计算机做复杂的事情——循环应用

一、循环结构回顾

1. 循环四要素

• 循环体：循环中重复执行的核心操作。
• 循环初始条件：循环控制变量的初始化。
• 循环控制表达式：构建循环控制条件。
• 循环控制变量的修改：构建循环退出机制。

2. 三种循环语句

• for循环：for(E1; E2; E3) 语句S;
• while循环：while(E2) { 语句S; E3; }
• do...while循环：do { 语句S; E3; } while(E2);

3. 循环结构与选择结构的区别

• 循环结构：用于重复执行某段代码。
• 选择结构：用于根据条件选择执行不同的代码。

4. 多重循环的执行过程

• 外层循环每执行一次，内层循环从头执行一遍。
• 循环嵌套时，内层循环是外层循环体中的一条语句。

二、灵活退出循环：break与continue

1. break语句

• 功能：强制中断循环，立即退出当前循环。

• 语法：

  while(表达式1) {
      语句1;
      if(表达式2) break;
  }
  

• 注意事项：

  • 只能用于循环语句和switch语句中。
  • 在多重循环中，break只能跳出一层循环。

2. continue语句

• 功能：跳过本次循环中剩余语句，直接进入下一次循环。

• 语法：

  while(表达式1) {
      语句1;
      if(表达式2) continue;
      语句2;
  }
  

• 区别：

  • break：终止整个循环。
  • continue：终止本次循环，继续下一次循环。

三、枚举法（穷举法）

1. 概念

• 枚举法是指对问题域中所有可能的解进行穷举搜索，并根据条件筛选出符合要求的解。

2. 基本模式

while (在搜索空间内) {
    if (满足判决条件) {
        输出解；
    }
    更新可能的解；
}

3. 示例：韩信点兵问题

• 问题描述：士兵人数满足以下条件：
  1. x % 5 == 1
  2. x % 6 == 5
  3. x % 7 == 4
  4. x % 11 == 10
• 解法：从1开始逐一枚举，直到找到满足所有条件的数。

四、枚举法的优化策略

1. 启发式搜索

• 利用问题信息引导搜索，减少搜索范围。
• 示例：韩信点兵问题中，利用x % 5 == 1，可令x每次增加5，而不是1。
• 优化效果：
  • 原始搜索：10000次循环。
  • 优化1（增加5）：2111次循环。
  • 优化2（增加11）：423次循环。
  • 优化3（增加55）：192次循环。

2. 优化思路

• 根据约束条件，调整搜索步长，减少无效枚举。
• 示例：结合多个约束条件，选择最大公约数或最小公倍数作为步长。

五、综合应用：百钱百鸡问题

1. 问题描述

• 鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。
• 百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

2. 解法思路

• 使用三重循环枚举鸡翁、鸡母、鸡雏的数量。
• 约束条件：
  • 5 * cock + 3 * hen + chick / 3 == 100
  • cock + hen + chick == 100
  • chick % 3 == 0
• 优化：根据约束减少循环次数。

六、总结

1. 循环应用要点

• 熟练使用break和continue控制循环流程。
• 掌握枚举法的基本思想与实现方式。
• 学会通过优化搜索策略提高程序效率。

2. 核心思想

• 循环 + 条件判断是解决枚举问题的基本模式。
• 启发式优化是提高枚举效率的关键。
• 编程不仅是实现功能，更是精益求精的过程。

七、思考题

回顾用数学方法和循环求解“物不知数”、“韩信点兵”等问题的过程，思考还有哪些问题适合用循环求解？如何结合数学知识优化枚举过程？