程序设计中常用思维方法.ppt

迭代 归纳与循环思维 分析 解决该问题的N S图如右 例1 用牛顿迭代法求x的平方根 牛顿迭代公式为 迭代变量S1 s2 include includemain floatx s1 1 s2 err scanf f 1 err s2 s1 2 s1 s2 3 s2 0 5 s1 x s1 例2 统计输入的行数 单词的个数 设单词是一个不包含任何空白字符的字符序列 以及输入的总的字符个数 分析 1 要表示输入的行数 单词的个数和输入的总字符数 可设以下三个变量nl nw nc 初值均为0 2 对于nl 每输入一个 n 增1 对于nc 每输入一个字符 增1 而对于nw 只有当输入的字符为非空白字符 非回车且前一个字符为空或回车时才增1 3 设计变量inword 当其值0时 表示当前字符的前一字符为空白或回车 当其值为1时 表示当前字符的前一字符非空或回车 此当前字符仍为该单词中的内容 4 inword的初始值为0 5 故nw增1的条件是 当前字符非空白或回车且inword 0 defineYES1 defineNO0 includemain intc nl nw nc inword inword NO nl nw nc 0 while c getchar nc if c n nl if c c n c t inword NO elseif inword NO inword YES nw printf nl dnw dnc d n nl nw nc 归纳法与循环 1 归纳法 是从大量的特殊性中总结出规律性或一般性的结论 2 归纳 在程序设计上主要表现为递归和迭代 我们常常用递归和迭代的方式把一个复杂的计算过程化为简单过程的多次重复 这种重复很容易用循环来实现 3 归纳法的另一重要用途是用于数列和级数求和 例3 猴子第一天摘下若干桃子 当即吃了一半 还不过瘾 又多吃了一个 第二天早上又将剩下的桃子吃掉了一半 又多吃了一个 以后每天早上都吃了前一天剩下的一半零一个 到第10天早上再想吃时 发现只剩下一个桃子了 求第一天共摘多少个桃子 Sn Sn 1 1 2程序如下 main ints i s 1 for i 1 i 9 i printf s d n s 例4 有一张足够大的纸 厚0 09毫米 问将它对折多少次后可以达到珠穆朗玛峰的高度 8848米 分析 1 采用归纳法 2 设a为高度 初值为9 10 5米 3 对折后 高度为前一次高度的2倍 每次乘2后判断乘积是否已超过8848米 若已超过 则记下乘2的次数就是对折的次数 4 请读者自己编程 枚举法 就是逐一列举出可能解的各个元素 并加以判断 直到求得所需要的解 常用在排列 组合 数据分类 信息检索 多解方程的求解上 枚举法与循环思维 使用枚举法 必须掌握两条原则 确定搜索的范围 这个范围必须是有限的 选择枚举的策略 按照一条什么样的路径来逐一枚举 这两条原则使用得好坏 对程序的工作量有巨大的影响 例5 对于 5 x 11 10 y 9 6 z 18 求方程 x3 y3 z3 3的全部整数解 程序如下 includemain intx y z for x 5 x 12 x for y 10 y 10 y for z 6 z 19 z if printf 5d 5d 5d n x y z x x x y y y z z z 3 例6 百钱百鸡问题 用100元钱买100只鸡 每只公鸡5元 每只母鸡3元 每3只小鸡1元 要求每种鸡至少买一只 且必须是整只的 问各种鸡各买多少只 分析 1 这是一个组合问题 归根到底是求三元一次方程的一组解 2 设i j k分别表示公鸡 母鸡和小鸡的只数 为了确定i j k的取值范围 可以有不同方法 不同的方法 程序的计算量相差甚远 3 方法一 i 1 20 j 1 33 k 1 100 4 方法二 i 1 18 j 1 31 k 100 i j 5 方法三 由i j k 100及5i 3j k 3 100得14i 8j 200 由此可得 i 1 13 j 1 23 k 100 i j 6 方法四 由方法三中的14i 8j 200得7i 4j 100可得 i 1 13 j 100 7i 4 k 100 i j main inti j k for i 1 i 20 i for j 1 j 33 j k 100 i j if printf k d j d i d n k j i i 5 j 3 k 3 100 例7 求整数a和b的最小公倍数 分析 1 如果i是a和b的最小公倍数 则i必能被a和b整除 同时i必须是自然数 所以其取值范围是 2 方法一 i从1开始 依次增加 直到第一个能被a和b整除为止 这个i就是a和b的最小公倍数 3 方法二 令从i从a开始 并使i每次增加a而不是增加1 这就保证了i总是a的倍数 故每次只要判断i能否被b整除就可以了 一旦判断成立 i就是a和b的最小公倍数 程序一 includemain inta b i scanf d d 程序二 includemain inta b i scanf d d 例8 用循环语句打印下列图案 程序如下 main inti j for i 1 i 6 i for j 1 j 20 i j printf for j 1 j 2 i 1 j printf printf n 例 用循环语句打印下列