习题课程序流程控制.ppt

程序流程控制语句习题课 第2页 流程控制语句习题课 本习题课的目的通过程序复习基本语句进行编程练习通过例题开阔思路介绍程序设计的基本思想穷举法的基本思路和关键输出简单图形 第3页 程序设计的一般步骤 分析题意 明确问题的性质数值计算 事务处理 逻辑分析 等建立问题的描述模型数学模型 过程模型设计 确定算法数学问题 分析解 数值解的求解算法非数学问题 数据结构 算法分析与设计一般方法 穷举 递推 递归 分治 回溯 编程调试分析运行结果 如有必要 进一步优化 第4页 典型数值问题 例1 例1 怎样存钱获利最多银行定期存款 假设不同期限的月息利率分别为 0 63 期限 一年0 66 期限 二年0 69 期限 三年0 75 期限 五年0 84 期限 八年利息 本金 月息利率 12 存款年限现在某人手中有2000元 请通过计算选择一种存钱方案 使得钱存入银行20年后得到的利息最多 假定银行对超过存款期限的那部分时间不付利息 第5页 典型数值问题 例1 问题分析与算法设计为了得到最多的利息 存入银行的钱应在到期时马上转存 由于存款的利率不同 所以不同的存款方法 年限组合 得到的利息也是不一样的 设2000元存20年 其中1年存i1次 2年存i2次 3年存i3次 5年存i5次 8年存i8次 则到期时应得的本利合计 2000 1 r1 i1 1 r2 i2 1 r3 i3 1 r5 i5 1 r8 i8根据题意还可得到以下限制条件 0 i8 20 80 i5 20 8 i8 50 i3 20 8 i8 5 i5 30 i2 20 8 i8 5 i5 3 i3 20 i1 20 8 i8 5 i5 3 i3 2 i2可用穷举所有的i8 i5 i3 i2和i1的组合 第6页 典型数值问题 例1 includemain inti8 i5 i3 i2 i1 n8 n5 n3 n2 n1 floatmax 0 term for i8 0 i8max 记录可能的年限组合 max term n1 i1 n2 i2 n3 i3 n5 i5 n8 i8 printf d d d d d n n8 n5 n3 n2 n1 printf Total 2f n max 第7页 典型数值问题 例2 例1 从键盘上任意输入一个正整数 要求判断该正整数是否是另一个整数的平方 问题分析与算法设计设 输入的正整数为i 若i满足 i m m 整数m 0 则i为整数的平方 可以采用试探的方法 令m从1开始逐步增加进行试探 m m 1 成立 不成立 输入一个整数i 输出m和i 开始 结束 设试探初值m 1 成立 不成立 第8页 典型数值问题 例2 scanf d inti m 第9页 典型数值问题 例2 include stdio h intmain inti m scanf d for m 1 m m i m 如果采用for语句该如何修改 表达式1 表达式2 表达式3 for语句的循环体是什么 循环体为空语句 第10页 典型数值问题 例3 例3 某地 车牌4位数字 首位非0 一辆卡车违犯交通规则逃逸 现场3人目击但都没有记住车号 只记得一些特征 甲说 牌照的前两位数字是相同的 乙说 牌照的后两位数字是相同的 但与前两位不同 丙是位数学家 他说 四位的车号刚好是一个整数的平方 请根据以上线索尝试找出车号 问题分析与算法设计按照题目的要求造出一个前两位数 i 相同 后两位数 j 相同且相互间又不同的整数 0 31 第11页 典型数值问题 例3 0 31 i 9 j 0 成立 不成立 i 1 k 1100 i 11 j i j 成立 不成立 k是平方 成立 不成立 输出 k i j j j 9 成立 不成立 i 结束 for i 1 i 9 i for j 0 j 9 j if i j k 1100 i 11 j 判断k是否平方 第12页 典型数值问题 例3 include stdio h voidmain inti j k m for i 1 i 9 i i 车号前二位的取值 for j 0 j 9 j j 车号后二位的取值 if i j 判断两位数字是否相异 k i 1100 j 11 for m 31 m m k m 31 31 961 判断是否为整数的平方 if m m k printf Lorry No is d n k 运行结果 Lorry No is7744 第13页 典型数值问题 例4 IQ游戏 设有一个数X 当X加上100后得到的数Y是一个正整数的平方 然后用Y再加上68 又是另外一个正整数的平方 你能算出X为多少吗 问题分析与算法设计根据题目直接列方程 y x 100y m m y 68 n n 取值范围 x 0 n m 10的整数采用穷举法求解 第14页 典型数值问题 例4 IQ游戏 voidmain intx y m flag flag 标志变量 for x 0 flag 1 flag x 穷举x y 100 x 计算y for m 1 m m y m if m m y 判断y是否为一个数的平方 for m m y 68 m if m m y 68 判断y 68 printf d n x flag 0 flag置0 结束循环 例200 IQ 第15页 典型数值问题 例4 IQ游戏1 voidmain inty m flag flag 标志变量 for y 101 flag 1 flag y 穷举y for m 1 m m y m if m m y 判断y是否为一个数的平方 for m m y 68 m if m m y 68 判断y 68 printf d n y 100 flag 0 flag置0 结束循环 例200 IQ1 第16页 典型数值问题 例4 IQ游戏2 includevoidmain intm n flag flag 标志变量 for m 10 flag 1 flag m 通过穷举m 直接构造平方数y for n 1 n n m m 68 n 判断m m 68是否为平方数 if n n m m 68 printf d n m m 100 flag 0 flag置0 结束循环 例200 IQ2 第17页 典型数值问题 例5 例3 求素数 求不超过整数n n 0 的最大素数 问题分析与算法设计素数 只能被1或自身整除的整数 判断整数n是否为素数 采用穷举法求解 基本算法 若k m 0则说明k不是素数 其中m的取值范围为 2 k 2 伪语言描述 标志变量flag 1为素数 0为合数 for flag 1 m 2 flag 第18页 典型数值问题 例5 例3 求素数 成立 不成立 输入一个整数n k k 1 开始 结束 设试探初值k n 是 不是 输出k 判断k的性质 伪语言描述 scanf d 第19页 典型数值问题 例6 例4 百钱百鸡问题 中国古代数学家张丘建在他的 算经 中提出了著名的 百钱百鸡问题 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 翁 母 雏各几何 问题分析与算法设计设 要买x只公鸡 y只母鸡 z只小鸡 可得到方程 x y z 100 5x 3y z 3 100 取值范围 0 x y z 100可以采用穷举法求解 将变量x y z的所有取值可能代入方程进行计算 第20页 典型数值问题 例6 穷举法基本思路当x 0 y 0 z 0时 是否满足方程z 1时 是否满足方程z 2时 是否满足方程 z 100时 是否满足方程当x 0 y 1 z 0时 是否满足方程z 1时 是否满足方程 z 100时 是否满足方程当x 0 y 2 z 0时 是否满足方程 当x 100 y 100 z 100时 z 100 z z 0 y 100 y y 0 x 100 x x 0 开始 结束 第21页 典型数值问题 例6 程序 includevoidmain intx y z j 0 for x 0 x 100 x for y 0 y 100 y for z 0 z 100 z if x y z 100 第22页 典型数值问题 例6 includevoidmain intx y z j 0 for x 0 x 100 x for y 0 y 100 y for z 0 z 100 z if x y z 100 x 运行结果 1 cock 0hen 25chicken 752 cock 3hen 20chicken 773 cock 4hen 18chicken 784 cock 7hen 13chicken 805 cock 8hen 11chicken 816 cock 11hen 6chicken 837 cock 12hen 4chicken 84 例C3 第23页 典型数值问题 例6 丢失重要条件 z应该能够被 整除 includevoidmain intx y z j 0 for x 0 x 20 x for y 0 y 33 y for z 0 z 100 z if z 3 0 运行程序 正确的结果 1 cock 0hen 25chicken 752 cock 4hen 18chicken 783 cock 8hen 11chicken 814 cock 12hen 4chicken 84 第24页 典型数值问题 例6 优化程序 for x 0 x 20 x for z 0 z 100 z 3 y 100 x z if 5 x 3 y z 3 100 printf 2d cock 2dhen 2dchicken 2d n j x y z 优化程序 for x 0 x 20 x for y 0 y 100 5 x 3 y z 100 x y if z 3 0 第25页 典型数值问题 百例8 借书方案知多少 问题小明有5本新书 要借给 三位小朋友 若每人每次只能借一本 则可有多少种不同的借法 问题分析与算法设计这是一个排列问题 即求从 中取 的排列数 对5本书从1至5编号 假设三个人分别借这5本书中的1本 当a i时 表示a借了编号为i的书 当3个人所借的书的编号都不相同时 就是满足题意的一种借阅方法 假设 三个人为a b c 则它们的取值范围为 1 a b c 5且当 a b a c b c时 即为1种借书的方法 第26页 典型数值问题 百例8 借书方案知多少 程序说明与注释voidmain inta b c count 0 for a 1 a 5 a for b 1 b 5 b for c 1 a b 60种 例C100 8 第27页 趣味程序 百例40 三色球问题 问题若一个口袋中放有12个球 其中有3个红的 3个白的和6个黑的 问从中任取8个共有多少种不同的颜色搭配 问题分析与算法设计设 任取的红球个数为i 白球个数为j 则黑球个数为 8 i j据题意红球i和白球j个数的取值范围是0 3 在红球和白球个数确定的条件下 黑球个数取值应为8 i j 6 第28页 趣味程序 百例40 三色球问题 程序说明与注释voidmain inti j count 0 printf REDBALLWHITEBALLBLACKBALL n printf n for i 0 i 3 i 任取红球的个数0 3 for j 0 j 3 j 任取白球的个数0 3 if 8 i j 6 printf 2d d d d n count i j 8 i j 例C100 40 第29页 趣味程序 百例48 新娘和新郎 问题三对情侣参加婚礼 三个新郎为 三个新娘为 有人不知道谁和谁结婚 于是询问了六位新人中的三位 但听到的回答是这样的 说他将和 结婚 说她的未婚夫是 说他将和 结婚 这人听后知道他们在开玩笑 全是假话 请编程找出谁将和谁结婚 问题分析与算法设计设 a b c三人用1 2 3表示 将x和a结婚表示为x 1 将y不与a结婚表示为y 1 则 x 1 不与 结婚x 3 的未婚夫不是 z 3 不与 结婚题意还隐含 x y且x z且y z 第30页 趣味程序 百例48 新娘和新郎 程序与说明voidmain intx y z for x 1 x 3 x 穷举X的全部可能配偶 for y 1 y 3 y 穷举Y的全部可能配偶 for z 1 z 3 z 穷举Z的全部可能配偶 if x 1 第31页 典型数值问题 穷举法的关键 数学模型适宜进行穷举的数学模型决定程序是否正确穷举的范围明确的穷举终止条件决定穷举的效率 范围过大 则效率太低 第32页 典型非数值 图型 问题 例1 例1 在一行中输出m个 号 要求 从键盘输入m值 输出一行m个 号 例 输入m 4 输出的图形如下 基本语句 输出一个 号 ptintf 或putchar 基本算法 1 输入m2 重复输出m个 3 输出一个 n scanf d 第33页 典型非数值 图型 问题 例1 includeintmain intm scanf d includevoidmain intm scanf d C语言中的一行都是以 n为标志 第34页 典型非数值 图型 问题 例2 例2 输出边长为m的正方型要求 从键盘输入m值 输出m行每行m个 号 例 输入m 4 输出的图形如下 算法分析与设计 1 输入m 2 重复输出m行 每行输出m个 细化1 1 输入m 2 for k 1 k m k 输出一行中的m个 第35页 典型非数值 图型 问题 例2 细化2 1 输入m 2 for k 1 k m k 输出m个 换新行 细化3 1 输入m 2 for k 1 k m k for j 1 j m j printf printf n 第36页 典型非数值 图型 问题 例2 整理 得到程序如下 includevoidmain intk m j scanf d j 输出一行中的m个 号 printf printf n 分析方法 逐步求精法对于比较复杂问题 不可能一下得到程序 可以先将简单的部分明确出来 再逐步对复杂部分进行细化 一步一步推出完整程序 例C3 2 第37页 典型非数值 图型 问题 例3 例3 输出边长为m的菱型例 输入m 4 输出的图形如下 算法分析与设计 在正方型每行 号的前面先多输出若干个空格 对于第k行 0 k m 则应先输出个空格 m k 第38页 典型非数值 图型 问题 例2 输出正方型程序 includeintmain intk m j scanf d for i 1 i m k i printf inti 第39页 典型非数值 图型 问题 例2 输出菱型程序 includeintmain intk m j i scanf d 第40页 典型非数值 图型 问题 例3 例3 从键盘输入h值 输出h行用 号组成等腰三角形 例 输入h 4 输出的图形如下 1 2 3 4 要输出个空格和个 分析 1 按行输出 输出h行 2 程序的关键是 找出每一行中要输出空格的数量和 的数量3 对于图形中的第k行 1 k h h k 2k 1 第41页 典型非数值 图型 问题 例3 分析 要输出h k个空格和2k 1个 算法设计1 输入h 2 重复打印h行 对于第k行 每行h k个空格和2k 1个 对第2步进行加细 2 0for k 1 k h k h行 重复打印h k个空格 重复打印2k 1个 换行 第42页 典型非数值 图型 问题 例3 程序 includevoidmain inth k j scanf d 例C3 7302 怎样输出一个等腰梯型 第43页 典型非数值 图型 问题 例3 h 4换一个思路分析 对于第k行 1 k h 需要输出h k 1个字符 空格或 号 对第k行的第j个字符 若j h k输出空格其它情况输出 算法设计for k 1 k h k 重复打印h行 for j 1 j h k 1 j 输出一行内的字符 if j h k 打印空格 else打印 号 换行 第44页 典型非数值 图型 问题 例3 程序 includevoidmain inth k j scanf d 例C3 73021 第45页 典型非数值 图型 问题 例4 例4 从键盘输入h值 输出用 号组成的正菱形 例 输入h 4 输出的图形如下 分析 1 h为上三角形的高度 总行数为 2 对于第j行 若要输出m个空格和n个 号 3 当j h时 为上三角 则 m n 4 当时 为下三角 则 m n 1234567 空格数量3 号数量1231507152331 2h 1h j2j 1h j 2h 1j h总宽度 空格 2h 1 2 j h 4h 1 2j 第46页 典型非数值 图型 问题 例4 算法设计for j 1 j 2 h 1 j 控制打印行 若为上三角j h则 m h j n 2j 1否则 m j h n 4h 1 2j重复打印m个空格重复打印n个 换行 加细循环体 if j h m h j n 2 j 1 else m j h n 4 h 1 2 j for k 1 k m k printf for k 1 k n k printf printf n 第47页 典型非数值 图型 问题 例4 程序 includevoidmain inth k j m n printf EnterH scanf d 例C3 7303 第48页 典型非数值 图型 问题 例4 程序2 includevoidmain inth k j m n printf EnterH scanf d 例C3 73031 第49页 典型非数值 图型 问题 例4 例4 从键盘输入h值 输出用 号组成的正菱形 例 输入h 4 输出的图形如下 分析 1 h为上三角形的高度 行范围 2 对于第j行 若要输出m个空格和n个 号 3 则 m n 3 2 10123 空格数量3 号数量1231507152331 h 1 h 1 j 2 h m 1 第50页 典型非数值 图型 问题 例4 程序3 includevoidmain inth k j m n printf EnterH scanf d 例C3 73032 第51页 例5 打印数字魔方 要求 从键盘输入m 输出m行的数字方阵 例 输入m 5 输出的图形如下 1234523451345124512351234分析 1 重复打印m行 典型非数值 图型 问题 例5 2 第i行的第一个数字为i 之后依次递增 但以m为模 aij i j 2 m 1 输出项aij与行i 列j的关系 第52页 典型非数值 图型 问题 例5 程序 includevoidmain inti j m printf EnterM scanf d 例C3 7304 第53页 例6 打印回形方阵要求 从键盘输入边长m 输出回形方阵 例 输入m 5 m 6 输出的图形如下 11111111111122211222211232112332112221m 5123321m 611111122221111111分析 关键是找出aij与行i和列j的关系 典型非数值 图型 问题 例6 第54页 将图形分为四个区 11111111111122211222211232112332112221m 5123321m 611111122221111111 典型非数值 图型 问题 例6 1 i m 1 2j m 1 2min i j 2 i m 1 2min i m j 1 3 i m 1 2j m 1 2min m i 1 j 4 i m 1 2j m 1 2min m i 1 m j 1 第55页 definemin x y x y x y voidmain intk j m printf EnterM scanf d 典型非数值 图型 问题 例6 例C3 7305 第56页 例7 打印数字三角形 输入高m 输出如下图形 m 6136101521259142048131971218111716 典型非数值 图型 问题 例7 分析 1 第i行打印个数字 m i 1 2 若 a1 1 1则 ai 1 1 i 1 例 a21 a11 1 1 1 2 a61 a51 5 11 5 163 若 已知ai 1 则 ai j 1 ai 1 i 例 a22 a21 2 1 2 2 1 5 a23 a22 2 2 5 2 2 9a62 a61 6 1 16 6 1 23 a63 a62 6 2 23 6 2 31 ai j i j 123456 123456 递推公式a1 1 1当 i j 1时ai 1 1 ai 1 iai j 1 ai j i j 第57页 递推公式 a1 1 1ai 1 1 ai 1 i i j 1 ai j 1 ai j i j程序voidmain inti j m n k 1 k是第一列元素的值 scanf d 计算下一行中第1个元素 典型非数值 图型 问题 例7 例C3 7306 第58页 例8 打印0 360度的sin x 曲线 典型非数值 图型 问题 例8 程序的关键在于 设计图形 第59页 算法分析 1 坐标的x轴沿列自顶向下 y轴自左向右增加2 屏幕每行为80列 y轴以第40列为0点3 sin x 的值在 1 1之间 图形中对应以40列为中心的10 70列4 将角度0 360度以10度为一个步长等分 只考察37个点sin x 函数对应点的位置 即图形总共打印37行算法设计 设定义i j分别控制行和列1 则行对应的角度为 i 10 180 PAI2 每行打印四种字符 空格 n3 行对应的sin值的位置 及 的位置为 40 30 sin i 10 180 PAI 在40列 n要视 的位置决定 取 最远 的值 典型非数值 图型 问题 例8 第60页 典型非数值 图型 问题 例8 definePAI3 14159voidmain doublex inty i yy for i 1 iy 40 y 下一行要打印的字符总数 for i 1 i yy i 控制输出图形中的一行 if i y printf i控制打印的列位置 elseif i 40 printf 打印中心的竖线 elseprintf printf n 例C3 7307 第61页 例9 打印cos x 曲线 典型非数值 图型 问题 例9 第62页 算法分析1 从图形看 x轴自左向右与行平行 y轴自下向上与列平行2 在0 360度区间内每一个y值有两个点 必须在1行中输出2个 利用图形的对称性 我们只考虑0 180度的情况3 若定义图形的总宽度为62列 对应0 360度的x轴算法设计1 程序中利用反余弦函数acos计算坐标 x y 的对应关系 2 对x点的坐标m 则在同一行与之对称的180 360度的y点的坐标就应为62 m 3 图中的y值从1 1 自上向下 我们以0 1为一个步长 共考察21个y坐标 即打印21行 4 每一行打印的字符可以分为5部分第一个 号以前的空格 第一个 号 第一个 号到第二个 号中间的空格 第二个 号回车符 典型非数值 图型 问题 例9 第63页 includemain doubley intx m for y 1 y 1 y 0 1 y为列方向 1到 1 m acos y 10 计算y对应的弧度m for x 1 x m x printf printf 控制打印左侧的 号 for x 62 m x printf printf n 控制打印同一行中对称的右侧 号 典型非数值 图型 问题 例9 例C3 7308 第64页 趣味程序 百例6 求1320的最后三位 问题分析与算法设计最直接的方法 将13累乘20次后截取最后3位即可 但由于整数的范围有限 不可能得到正确的结果 乘积的最后三位只与乘数和被乘数的后三位有关程序说明与注释main inti x y last 1 printf InputXandY X Y scanf d d 例C100 6 第65页 趣味程序 百例18 问题个位数为6且能被3整除的五位数共有多少 问题分析与算法设计满足条件的五位数的范围是10006 10016 99996 设 基础数i 1000 通过计算i 10 6即可得到个位数为6的5位候选整数 再判断该数能否被3整除 使用穷举法 1000 i 9999 第66页 趣味程序 百例18 程序说明与注释voidmain longinti intcount 0 count统计满足条件的五位数的个数 for i 1000 i 9999 i if i 10 6 3 判断能否整除 count printf count d n count 例C100 18 第67页 趣味程序 百例20 一个奇异三位数 问题一个自然数的七进制表达式是一个三位数 而这个自然数的九进制表示也是一个三位数 且这两个三位数的数码顺序正好相反 求这个三位数 问题分析与算法设计设七进制数形式为kji 则九进制表示的形式就为ijk 取值范围 1 i k 60 j 6将9进制数转化为十进制 将7进制数转化为十进制 i 9 9 j 9 k i j 7 k 7 7 使用穷举法 第68页 趣味程序 百例20 一个奇异三位数 程序说明与注释voidmain inti j k for i 1 i 7 i 穷举9进制的第1位数 for j 0 j 7 j 穷举9进制的第2位数 for k 1 k 7 k 穷举9进制的第3位数 if i 9 9 j 9 k i j 7 k 7 7 printf d d d 7 d d d 9 d 10 n k j i i j k i 9 9 j 9 k 运行结果503 7 305 9 248 10 例C100 20 第69页 趣味程序 百例21 4位反序数 问题设N是一个4位数 它的9倍恰好是其反序数 求N 反序数就是将整数的数字倒过来形成的整数 例如 1234的反序数是4321 问题分析与算法设计设整数的千 百 十 个位为i j k l 则满足 i 103 j 102 10k l 9 l 103 k 102 10j i 程序说明与注释main inti for i 1002 i 1111 i 穷举可能的值 if i 10 1000 i 10 10 100 i 100 10 10 i 1000 i 9 printf Thenumberis d n i 例C100 21 第70页 趣味程序 百例26 求3000以内的亲密数 问题如果整数A的全部因子 包括1 不包括A本身 之和等于B 且整数B的全部因子之和等于A 则将整数A和B称为亲密数 问题分析与算法设计要判断数a是否有亲密数 1 计算出a的全部因子的累加和为b 2 计算b的全部因子的累加和为n 3 判断 若n等于a 则a和b是亲密数 求整数所有因子的算法 用a依次对i 1 i a 2 进行模运算 若模运算结果等于0 则i为 a的一个因子 第71页 趣味程序 百例26 程序说明与注释voidmain inta i b n for a 1 a 3000 a for b 0 i 1 i a 2 i 计算数a的因子 if a i b i 因子之和存在b中 for n 0 i 1 i b 2 i if b i n i if n a 例C100 26 第72页 趣味程序 百例30 求素数 问题求1000以内的素数 问题分析与算法设计素数是仅能被 和它自身整除的整数 判断一个整数n是否为素数 判断整数n能否被除 和自身之外的任意整数整除 若都不能整除 则n为素数 可以从 开始 到该整数n的1 2为止 用i依次去除需要判断的整数 只要存在可以整除该数的情况 即可确定要判断的整数不是素数 第73页 趣味程序 百例30 求1000以内的素数 程序与注释说明voidmain intn1 nm i j flag count 0 flag 1是素数 do printf InputSTARTandEND scanf d d 例C100 30 注意标志变量flag的使用方法 第74页 趣味程序 百例49 委派任务 问题某侦察队接到一项紧急任务 要求在A B C D E F六个队员中尽可能多地挑若干人 但有