4迭代与重复-循环程序设计(1).ppt

高级语言程序设计 第4章迭代与重复 循环程序设计 学习目标 理解循环的思想掌握循环结构的三要素熟练控制循环的方法 计数器控制 标记控制 迭代条件控制等 熟悉三种循环结构while do while for的使用学会用多重循环 引言 重复似乎很乏味 但重复给人以希望 重复可以重头再来 重复可以绚丽多彩 很难想象世界要是没有了重复该会变成什么样子 在前面的问题求解过程中 为了丰富求解过程 已经多次使用了重复无条件循环while 1 有条件循环while scanf d grade EOF 要解决的问题 1 打印规则图形2 自然数求和与阶乘计算求解这些问题如果不用重复的思想就比较难解决 问题1 打印规则图形 问题描述 打印如下的规则图案 分析 问题的目标就是输出一个图案 没有输入怎么做 设计你的算法 用重复 循环的思想解决 三要素 重复要做的事情是什么 重复多少次 如何控制重复的次数 控制重复的次数是关键重复要做的事情是核心 控制重复的方法之一 如果已知要重复的次数可以通过计数来控制重复 计数控制 怎么样让计算机数数呢 intcounter 定义一个计数器counter 0 初始化counter counter 1 每重复一次 计数器加1 算法设计 1计数器counter初始化为0 2如果counter 循环次数则执行 3 否则循环结束 执行 5 3输出一行 4计数器counter增加1 转到 2 5输出结果 算法实现 程序代码 计数控制的while循环结构 计数器初始化while 计数器 循环次数 重复执行的语句计数器增加1 计算器更新 while循环中有三个重要的要素 计数器初始化 循环条件 计数器 重复的次数为真 计数器更新 思考题 如果计数器初始化为1 循环的另外两个要素是否要做相应的变化 怎么变化 自增自减运算 单目运算 计数器加1或减1是经常要做的事counter counter 1 可以写成counter 或 counter 注意必须是一个变量才可以5 counter 1 都是错误的 前缀和后缀的区别 自增 自减运算单独出现时 前缀和后缀的效果相同当自增 自减运算与其它运算混合出现时前缀和后缀截然不同m n 相当于m n n n 1 m n 则等价于n n 1 m n 的结合性 右结合 设intm n 3 m n 因此与m n 等价结果是m 3 n 4 建议不要过多地使用自增或自减 宁愿使用与其等效的简单的多个语句 这样会增加可读性 问题2 自然数求和 问题描述 求100以内的自然数之和 即求1 2 3 100 类似的还有 求10的阶乘 即10 10 9 8 2 1 分析 先考虑求和问题 你怎么求解 等差数列前n项和公式s 1 100 100 2 还是写s 1 2 3 100或者s 1 2 3 写完整 100有更好的思想方法吗 迭代重复的思想 不要一口吃个胖子可以先求一个数的和s1 0 1再求s2 s1 2s3 s2 3 s100 s99 100显然这是一个重复的过程 重复的次数确定重复的内容明确 累加 重复求和 统一为s s i i 1 100这里有两个量 计数器i 累加器s 算法设计 step1 计数器和累加器初始化step2 如果计数器的值小于等于重复的次数 执行step3 否则执行step6step3 迭代累加step4 计算器加1step5 回到step2step6 输出计算结果 思考 为什么这里的计数器从1开始 计数控制条件为什么变成了i 100 包括等于在内 如果离开循环后打印出计数器i的值应该是多少 阶乘计算 10 10 9 8 2 1 大家分析一下设计一个算法 阶乘程序实现 思考题 可以算100 吗 大整数该如何计算 再看一个典型的问题 兔子繁殖问题 裴波纳契 Fibonacci 数列13世纪意大利数学家斐波那契在他的 算盘书 中提出这样一个问题 有人想知道一年内一对兔子可繁殖成多少对 便筑了一道围墙把一对兔子关在里面 已知一对兔子每一个月可以生一对小兔子 而一对兔子出生后第二个月就开始生小兔子 假如一年内没有发生死亡 则一对兔子一年内能繁殖成多少对 1 1 2 3 5 8 13 21 34 55 89 它以1 1开头 从第3个数开始 每个数都前两个数之和 斐波纳契数列还暗含着许多有趣的数字规律 如从第3个数开始每隔两个必是2的倍数 从第4个数开始每隔3个必是3的倍数 从第5个数开始每隔4个必是5的倍数 另外 这个数列最具有和谐之美的地方是 越往后 相邻两项 前一项与后一项 的比值会趋向于黄金分割比0 61803 分析一下 设f1存储一个已经求得的裴波纳契数 初始值为1 f2存储另一个相邻的裴波纳契数 初始值为1 f存储f1与f2之和 是一个后继的裴波纳契数 初始序列 f1 f2迭代关系 f f1 f2 f1 f2 f变更角色f1f2f即令f1 f2 f2 f 再次求新的f 算法设计 step1 f1初始化为1 f2初始化为1 计数器初始化为1 第一个月不用计算 step2如果计数器不超过要重复的次数 一年12个月 计算11次 执行step3 否则执行step6step3计算新的Fibonacii数f f1 f2 step4变更f1和f2的角色 即f1 f2 f2 f 把刚刚求得的那个Fibonacii数f作为下一次计算的f2 step5计数器加1 回到 step2 step6输出计算结果 思考题 计算裴波纳契数还有其它迭代方法吗 更多的赋值运算 复合赋值运算 经常做像s s i p p i这样的计算C C 引进新的更简单的赋值运算 等 s s i p p i可以写成s i p i还有 和 等 for循环 重复次数事先可以确定的问题很多很多 为了使用更方便 C C 提供了for循环使得这类的程序更加简洁 for循环结构的一般形式 for 表达式1 表达式2 表达式3 当表达式2为真时执行的语句或语句块 它与while循环是完全对等的 例如 for求和 for i 1 i 100 i s i 或for i 1 i 100 i s i 大家写出 for求阶乘for求裴波纳契数 for循环的使用非常灵活 通常3个表达式都是全的 不省略的 但实际使用的时候允许省略某个表达式 形成很多变化的形式 达到不同的效果 8种特殊的情况 1 表达式1可以省略 但是第一个分号不可以省略inti 1 s 0 for i 10 i s i printf s d n s 2 表达式1可以是用 号连接起来的多个赋值表达式组成inti s for i 1 s 0 i 10 i s i printf s d n s 逗号运算 逗号表达式逗号运算是依次计算各个组成部分 取最后那部分的计算结果作为整个逗号表达式的值 例如printf d n i 1 s 0 的结果为0 3 表达式2可以省略 但是第二个分号不可以省略inti s for i 1 s 0 i if i 100 break 离开循环elses i printf s d n s 4 表达式3可以是一个逗号表达式inti s 1 for i 1 i 10 i s i printf s d n s 空语句 该循环的空语句不可以省略 5 表达式三可以省略 但它前面的分号不能省略inti 1 s 0 for i 10 s i i printf s d n s 6 三个表达式都可以省略 但是两个分号不能丢掉 inti 1 s 0 for if i 100 break 离开循环else s i i printf s d n s 7 表达式3可以是循环控制变量增加 也可以是循