lh-05 循环结构程序设计1.ppt

设有两个正整数m和n 如何求其最大公约数 有多种方法 例如 令k等于从m和n中较小的数 用k去除m和n 若不能整除 则令k的值减去1 直到某个值能同时将m和n整除 求最大公约数 求最大公约数 笨办法 includeintmain intm n k scanf d d 设有两个正整数m和n 如何求其最大公约数 有多种方法 例如 令k等于m和n中的较小者 用k去除m和n 若不能整除 则令k的值减去1 直到某个值能同时将m和n整除 求解速度最快的方法是辗转相除法 辗转相除法 欧几里得算法 给定两个正整数m和n 求它们的最大公约数 公因子 步骤1 求余数 以n除m并令r为所得余数 0 r n 步骤2 余数为0 若r 0 则算法结束 n即为答案步骤3 互换 置m n n r 转向步骤1 求最大公约数 求最大公约数 求最大公约数流程图 求最大公约数程序 includeintmain return0 Y N r不等于0 输出n的值 输入正整数m和n 开始 结束 m n n rr m n r m n while r 0 m n n r r m n printf inputtwointegers scanf d d r m n intm n r printf ngcd d n n 主要内容 for语句break语句continue语句do while语句 C的循环语句 C语言提供了描述循环计算的语句 while语句for语句do while语句 学习循环结构程序设计就是掌握以上语句的使用方法 分析问题 在求解过程中 存在一个 些 运算 动作 需要重复进行 循环 若干次 重复的次数是事先确定的 或者是根据条件确定的 处理循环计算需要明确的三个问题 循环体 哪些运算 动作 是需要重复进行的 循环条件 重复这些运算的条件是什么 即在什么情况下终止 继续这个重复的过程 循环准备 在进行重复的运算处理之前 需要进行的准备工作是什么 循环结构程序的编写要点 for语句 for语句的格式和含义 for语句的基本格式 for 表达式1 表达式2 表达式3 循环体语句A for语句的含义 1 计算表达式1 2 计算表达式2 若表达式2的值为 假 则结束for语句的执行 转4 否则 执行循环体语句A 3 计算表达式3 然后转2 4 执行for语句之后的第一条语句 for语句 1 2 100 includemain inti s printf d n s B Y N I 1S 0 I 100 S S I 输出S的值 开始 结束 I I 1 A C for i 1 s 0 i 100 i s i includeintmain inti s i 1 s 0 while i 100 s i i printf d n s return0 for语句中的表达式 for语句的基本格式 for 表达式1 表达式2 表达式3 循环体语句A 一般情况下表达式1进行循环计算的初始化处理表达式2是循环的条件表达式3进行的计算能够对表达式2的值产生影响 求最大公约数程序 for includemain intm n r printf inputtwointegers scanf d d Y N r不等于0 输出n的值 输入正整数m和n 开始 结束 m n n rr m被n除的余数 r m被n除的余数 for r m n r 0 r m n m n n r for语句与while语句的等价关系 for语句的基本格式 for 表达式1 表达式2 表达式3 循环体语句A 表达式1 while 表达式2 循环体语句A 表达式3 Y N K 2 K不能整除n K K 1 输出n是素数 输入n的值 开始 结束 Y N K等于n 输出n不是素数 判断素数算法及程序 includemain intk n printf inputaninteger scanf d TC2 0 includemain intk n printf inputaninteger scanf d for k 2 n k 0 k for语句小结 表达式1可放置在for语句之前 for 表达式1 表达式2 表达式3 循环体语句A 表达式1 for 表达式2 表达式3 循环体语句A 表达式3可放置在for语句的循环体中 for 表达式1 表达式2 循环体语句A 表达式3 for语句中的表达式可以是C语言允许的任何表达式 for语句小结 续 进一步 表达式2可以没有 表示无休止地循环 for 表达式1 表达式3 循环体语句A 三个表达式都省略 for 循环体语句A break语句 break语句的作用 在switch语句中使用 grade score 10 百分制成绩score转换为等级分制 switch grade case10 case9 printf grade A n break case8 printf grade B n break case7 printf grade C n break case6 printf grade D n break case5 case4 case3 case2 case1 case0 printf grade E n break default printf Invaliddata n break语句的作用 续 在循环语句中使用 强行中止循环 break语句的作用 续 在循环语句中使用 强行中止循环 计算正整数m和n的最大公约数 for k m k 1 k if n k 0 continue语句 continue语句的作用 执行流程到达continue语句时 结束本轮循环 开始下一轮循环 continue语句的应用举例 输出100 200之间所有不能被3整除的整数 includemain intn for n 100 n 200 n if n 3 0 continue printf d t n endoffor 循环语句应用举例 已知鸡兔共笼 头共45个 脚共120只 问鸡 兔各几何 includeintmain intchicken rabbits for chicken 0 chicken 45 chicken rabbits 45 chicken if chicken 2 rabbits 4 120 break endoffor printf chicken d trabbits d n chicken rabbits return0 a 0 b 45 while 2 a 4 b 120 a b 单重循环和多重循环 for语句和while语句 for语句的基本格式 for 表达式1 表达式2 表达式3 循环体语句A while语句的格式 while 表达式p 循环体语句A 循环语句应用举例 已知鸡兔共笼 头共45个 脚共120只 问鸡 兔各几何 includeintmain intchicken rabbits for chicken 0 chicken 45 chicken rabbits 45 chicken if chicken 2 rabbits 4 120 break endoffor printf chicken d trabbits d n chicken rabbits return0 循环体语句可以是语言允许的任何语句 多于一条语句时必须用 括起来 例如 艰难旅程 浮点误差 乌龟要去环球 第1秒爬1米 第2秒爬1 2米 第3秒爬1 3米 第4秒爬1 4米 问一小时能爬出多远 爬20米需多少秒 这里只考虑爬20米需要多少时间 写出下面的代码 include includeintmain longi doublex 0 0 路程for i 1 x 20 i x x 1 0 i printf ld n i 1 return0 运行开始运行后 很长时间看不到输出 例如 艰难旅程 浮点误差 乌龟要去环球 第1秒爬1米 第2秒爬1 2米 第3秒爬1 3米 第4秒爬1 4米 问一小时能爬出多远 爬20米需多少秒 include includeintmain longi 1 floatx 0 0 a 0 0 for x 10 0 x 20 0 x 1 0 for a x i a 1 0 i printf lds lfm n i 1 a return0 分别观察 爬10米所用的时间爬11米所用的时间 爬20米所用的时间 输出 12367s 10 000000m33617s 11 000000m91328s 12 000000m248695s 13 000000m662167s 14 000000m1673859s 15 000000m之后有一会儿没反应 然后输出错误的数据 因为溢出 例如 艰难旅程 浮点误差 乌龟要去环球 第1秒爬1米 第2秒爬1 2米 第3秒爬1 3米 第4秒爬1 4米 问一小时能爬出多远 爬20米需多少秒 include includeintmain longi 1 doublex 0 0 a 0 0 for x 10 0 x 20 0 x 1 0 for a x i a 1 0 i printf lds lfm n i 1 a return0 很快就输出 12367s 10 000043m33617s 11 000018m91380s 12 000003m248397s 13 000001m675214s 14 000001m1835421s 15 000000m4989191s 16 000000m13562027s 17 000000m36865412s 18 000000m100210581s 19 000000m272400600s 20 000000m 将上面代码中的float改为double 20亿秒时还增长 输出 2000000000s 21 993629m经过大约63年半 乌龟爬了近22米 在大约2亿5千万秒 约8年 爬过了20米 这是题目第二部分的答案 由于long为32位表示 在此范围内没找到用double类型的增长结束点 但一定比用float大得多 特殊情况中浮点误差积累可能更迅速 有两个重要情况 将一批小的数加到很大的数上 会导致丢掉小的数的重要部分 甚至小数整个被丢掉 例中情况 两个值接近的数相减 可能导致精度大大下降 百钱百鸡问题 中国古代数学家张丘建在他的 算经 中曾提出著名的 百钱百鸡问题 其题目如下 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 翁 母 雏各几何 百钱百鸡问题 解 设i j k分别代表公鸡 母鸡 小鸡的数量 根据题意列方程 根据题意可知 i j k的范围一定是0到100的正整数 那么 最简单的解题方法是 穷举i j k每一种可能的取值组合 直接代入方程组 若满足该方程组则是一组解 这样即可得到问题的全部解 百钱百鸡问题 i 0 i 20 买母鸡和小鸡 开始 结束 i i 1 i 0 while i 20 i inti j k i j k分别表示公鸡 母鸡和小鸡的数目 j 0 while j 34 j k 0 while k 100 if i j k 100 百钱百鸡问题 while 输出 02575320774187871380811811168312484 for i 0 i 20 i 设定公鸡的数目 intmain inti j k i j k分别表示公鸡 母鸡和小鸡的数目 return0 for j 0 j 34 j 设定母鸡的数目 for k 0 k 100 k 设定小鸡的数目 if i j k 100 百钱百鸡问题 for 输出 02575418788118112484 for i 0 i 20 i 设定公鸡的数目 intmain inti j k i j k分别表示公鸡 母鸡和小鸡的数目 return0 for j 0 j 34 j 设定母鸡的数目 k 100 i j if i 15 j 9 k 300 printf d d d n i j k 百钱百鸡问题 for续 直到型循环结构和do while语句 p A a b 循环结构2 until p A 成立 不成立 a b 循环结构1 while until循环结构 循环结构当型循环结构 while型循环 重复地判断条件p 若成立 则执行计算A 条件p不成立时 终止该重复过程 如图循环结构1所示直到型循环结构 Until型循环 先执行计算A 然后判断条件p是否成立 如图循环结构2所示 do while语句的格式和含义 do while语句的使用格式 do循环体语句Awhile 表达式p do while语句的含义 1 执行循环体语句A 2 计算表达式p 若表达式的值为 假 则结束do while语句的执行 否则 执行循环体语句A 然后转1 求最大公约数程序 includemain intm n r printf inputtwointegers scanf d d Y N r不等于0 输出m的值 输入正整数m和n 开始 结束 r m被n除的余数m n n r do r m n m n n r while r 0 Y N K 2 K不能整除n K K 1 输出n是素数 输入n的值 开始 结束 Y N K等于n BEGINinputn 输入正整数n k 2 while nmodk 0 do k k 1 if k n thenprint n是素数 elseprint n不是素数 END 输出n不是素数 判断素数算法及程序 includemain intk n printf inputaninteger scanf d Y N K 2 K不能整除n K K 1 输出n是素数 输入n的值 开始 结束 Y N K等于n 输出n不是素数 判断素数程序 includemain intk n printf inputaninteger scanf d TC2 0 includemain intk n printf inputaninteger scanf d while语句和do while语句 while语句的循环体执行0次或多次do while语句的循环体执行1次或多次 while 表达式p 循环体语句A do while语句可看作是while语句的变体用do while语句表达的计算过程都可以用while语句表示 do 循环体语句A while 表达式p 关于while语句和do while语句的比较 请仔细阅读教材P109例6 4 do while语句的使用 do while语句常用于 为确保输入的数据满足要求而进行循环输入例如 确保是对正整数进行素性判别 do printf inputapositiveinteger 1 scanf d do while语句的使用 续 printf inputapositiveinteger 1 scanf d do printf input