一、循环结构回顾
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. 示例:韩信点兵问题
- 问题描述:士兵人数满足以下条件:
x % 5 == 1x % 6 == 5x % 7 == 4x % 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 == 100cock + hen + chick == 100chick % 3 == 0
- 优化:根据约束减少循环次数。
六、总结
1. 循环应用要点
- 熟练使用
break和continue控制循环流程。 - 掌握枚举法的基本思想与实现方式。
- 学会通过优化搜索策略提高程序效率。
2. 核心思想
- 循环 + 条件判断是解决枚举问题的基本模式。
- 启发式优化是提高枚举效率的关键。
- 编程不仅是实现功能,更是精益求精的过程。
七、思考题
回顾用数学方法和循环求解“物不知数”、“韩信点兵”等问题的过程,思考还有哪些问题适合用循环求解?如何结合数学知识优化枚举过程?
