第四章循环结构程序设计2资料.ppt

01 52 复习与拓展 求1 2 3 n voidfactorial doublesum 0 term 1 inti n scanf d 01 52 编写程序统计键盘输入的一行字符中的数字字符个数 英文字母个数 其他字符个数 总的字符个数 voidline char charch intn1 0 n2 0 n3 0 计数器置零for ch getchar ch n ch getchar if ch 0 Ab12 cD3 n1 3 n2 4 n3 4 总数为11 第四章循环结构程序设计 续 多重循环常用算法 01 52 循环结构程序设计常用算法 迭代法 不断用新值代替旧值的操作过程 称为迭代 用迭代法完成的加法操作 称为累加 用迭代法完成的乘法操作 称为累乘 解题要点 1 定义变量作累加器 累加器初始化为02 按下式循环计算 累加器当前值 累加器原来的值 新的要加的数据3 根据累加数的变化规律 修改循环控制变量 确定循环次数 例1 用for循环计算12 22 32 42 1002 01 52 参考程序 includevoidEx1 intk intresult 0 for k 1 k 100 k result k k printf result d n result 01 52 分析 寻找规律性正 负交替前项 分子 是后项的 分母 前项的 分子 分母 是后项的 分子 变量的设计 flag标记正负 初值为1 fz记录当前项的分子 初值为2fm记录当前项的分母 初值为1s记录当前和 初值为0n记录循环次数 初值为1 循环体 s s flag fz fm flag flag 1 t fm fm fz fz fz t 为下一项准备数据 01 52 voidsum before10 doubles 0 fz 2 fm 1 t intflag 1 n for n 1 n 10 n s s flag fz fm flag flag 1 t fm fm fz fz fz t printf s lf n s 例2 循环体 s s flag fz fm flag flag 1 t fm fm fz fz fz t 01 52 编写成灵活性更好的函数floatsum beforeN intN floats 0 f1 2 f2 1 t 累加器赋初值 intflag 1 n for n 1 n N n s s flag f1 f2 flag flag 1 t f2 f2 f1 f1 fz t return s 例2 01 52 强力推荐 巧妙使用 参变量 如何用循环结构实现求n 修改项目中的训练模块 实现M以内的算术训练M为10 即为10以内M为100 即为100以内M为1000 即为1000以内总之 是想花很小的力气灵活应对更多的局面 01 52 2 枚举法 按问题本身的性质 一一列举出该问题所有可能的解 并在逐一列举的过程中 检验每个可能解是否是问题的真正解 若是 我们采纳这个解 否则抛弃它 对于所列举的值 既不能遗漏也不能重复 笨人之法 把所有可能的情况一一测试 筛选出符合条件的各种结果进行输出 01 52 百钱买百鸡 公元五世纪末 我国古代数学家张丘建在 算经 中提出了如下问题 鸡翁一值钱五 鸡母一值钱三 鸡雏三值钱一 凡百钱买百鸡 问鸡翁 母 雏各几何 01 52 问题分析 设公鸡为cocks只 母鸡为hens只 小鸡为chicks只 这是个不定方程 三元一次方程组问题 三个变量 两个方程 cocks hens chicks 1005cocks 3hens chicks 3 100 01 52 下面考虑如何寻找另外的约束条件 按常识 cocks hens chicks都应为正整数 且它们的取值范围分别应为 cocks 0 20 假如100元全买cocks 最多20只 hens 0 33 假如100元全买hens 最多33只 chicks 0 100 假如全买chicks 最多100只 01 52 在上述对cocks hens chicks有限的取值范围内的每一种组合进行试探 找到满足前面两个方程的组合 就是本题的解了 01 52 参考程序 voidmain intcocks hens chicks for cocks 0 cocks 20 cocks 穷举cocks for hens 0 hens 33 hens chicks 100 cocks hens if 5 cocks 3 hens chicks 3 0 100 printf d t d t d n cocks hens chicks 01 52 运行结果 公鸡数母鸡数小鸡数02575418788118112484 01 52 使用符号常数增强程序的可读性 defineMuch100 defineMany100voidBuy 100 intcocks hens chicks for cocks 0 cocks Much 5 cocks for hens 0 hens Much 3 hens chicks Many cocks hens if 5 cocks 3 hens chicks 3 0 Much printf d t d t d n cocks hens chicks 01 52 例 编程求三个数字x y z 0 9 满足 xyz zyx 1231 注 xyz是由三个数字组成的三位数 分析 在这个组合中 有 101个x 101个z 20个y 示例 01 52 include stdio h main inti j k for i 0 i 9 i for j 0 j 9 j for k 0 k 9 k if 101 i 20 j 101 k 1231 printf x d y d z d n i j k 01 52 3 递推法 所谓递推法就是从初值出发 归纳出新值与旧值间的关系 直到求出所需值为止 新值的求出依赖于旧值 不知道旧值 无法推导出新值 数学上递推公式正是这一类问题 智人之法 通过分析归纳 找出从变量旧值出发求新值的规律 01 52 猴子吃桃子 问题 一天一只小猴子摘下一堆桃子 当即吃去一半 还觉得不过瘾 又多吃了一个 第二天接着吃了前一天剩下的一半 馋不忍罢又多吃了一个 以后每天如此 到第十天小猴子去吃时 只剩下一个桃子了 问小猴子共摘了多少桃子 01 52 问题分析 已知第10天的桃子数为1 就可倒推出第9天的第10天 X10 1第9天 X9 X10 1 2第8天 X8 X9 1 2 第1天 X1 X2 1 2得出计算模型 若某天为Xn 则前一天Xn 1 Xn 1 2 倒推法 01 52 voidMonkey Eat Peach intday xn xn 1 xn 1 第10天的桃子数 for day 9 day 1 day 前一天的桃子数是这一天桃子数加1后的2倍 xn 1 xn 1 2 xn xn 1 printf Thetotalis d n xn 1 参考程序 运行结果 Thetotalis1534 01 52 Fibonacci数列 Fibonacci是中世纪意大利的一位极有才华的数学家 他的代表作是1202年出版的 算盘的书 在这本书中 Fibonacci提出一个问题 假定一对新出生的兔子一个月后成熟 并且再过一个月开始生出一对小兔子 按此规律 在没有兔子死亡的情形下 一对初生的兔子 到一年头上 可以繁殖成多少对兔子 01 52 问题分析 用F1 F2 F3 F4 表示各月兔子的数量 则有 F1 1 最初的一对兔子 F2 1 第2个月 原来的兔子长成 还未生育 F3 2 最初的一对兔子开始生育 F4 3 上个月的小兔子刚长成 还不能生育 原来的老兔子又生一对 F5 5 上个月的小兔子刚长成 还不能生育 有两对兔子各生育一对 01 52 显然 各月的兔子数组成数列 1 1 2 3 5 8 13 21 34 55 89 从第3个月开始 本月的兔子数为上月的兔子数加上上月的兔子数 即Fn Fn 1 Fn 2 n 3 这就是C语言可以使用的计算模型 01 52 求解 如果要求出一个Fibonacci数列 就应当用一个循环递推过程 初始值 Fn 1 1 Fn 2 1求递推数列的下一个数Fnfor n 3 n 12 n Fn Fn 1 Fn 2 Fn 2 Fn 1 Fn 1 Fn 01 52 参考程序 defineMonths12voidFibonacci intn Fn Fn 1 1 Fn 2 1 for n 3 n Months n Fn Fn 1 Fn 2 Fn 2 Fn 1 Fn 1 Fn printf nF d d n Fn 课后练习 1 累加 国王的许诺 相传国际象棋是古印度舍罕王的宰相达依尔发明的 舍罕王十分喜欢象棋 决定让宰相自己选择何种赏赐 这位聪明的宰相指着8 8共64格的象棋盘说 陛下 请您赏给我一些麦子吧 就在棋盘的第一个格子中放1粒 第2格中放2粒 第3格放4粒 以后每一格都比前一格增加一倍 依此放完棋盘上的64个格子 我就感恩不尽了 舍罕王让人扛来一袋麦子 他要兑现他的许诺 国王能兑现他的许诺吗 试编程计算舍罕王共要多少麦子赏赐他的宰相 这些麦子合多少立方米 已知1立方米麦子约1 42e8粒 总粒数为 sum 1 2 22 23 263 方法1 include include defineCONST1 42e8voidmain intn doubleterm sum 0 累加求和变量赋初值 for n 1 n 64 n term pow 2 n 1 根据累加项的规律计算累加项 sum sum term 作累加运算 printf sum e n sum 打印总麦粒数 printf volum e n sum CONST 打印折合的总麦粒体积数 方法2 include defineCONST1 42e8 定义符号常量CONST值为1 42e8 voidmain intn doubleterm 1 sum 1 累乘求积 累加求和变量赋初值 for n 2 n 64 n term term 2 根据后项总是前项的2倍计算累加项 sum sum term 作累加运算 printf sum e n sum 打印总麦粒数 printf volum e n sum CONST 打印折合的总麦粒体积数 课后练习 2 穷举法 马克思手稿中有一道趣味数学题 有30个人 其中有男人 女人和小孩 在一家饭馆里吃饭共花了50先令 每个男人各花3先令 每个女人各花2先令 每个小孩各花1先令 问男人 女人和小孩各有几人 解方程组穷举法 方法1 采用三重循环穷举x y z的全部可能的组合 includemain intx y