算法与程序设计基础.ppt

1 第3章算法与程序设计基础 3 1算法3 2算法的常用表示方法3 3结构化程序设计方法3 4C语句概述补充 顺序结构程序设计3 5选择结构程序设计3 6循环程序设计3 7综合程序应用举例 目录 实验三 实验四 2 3 1算法 3 1 1算法的概念3 1 2算法的特性 本章 3 3 1 1算法的概念当我们要编写一个程序的时候 我们总要首先想好程序是干什么的 应该如何实现这些目标 应该先进行什么处理 后进行什么处理 所处理的数据的格式是什么 遇到一些复杂的问题 我们可能还需要考虑采用什么数学方法 这一切都涉及一个专业名词 算法 算法 为解决一个实际问题而采取的方法和步骤很多时候 程序设计者所面临的问题就是寻找一个合适的算法 例如 一个熟练的程序员 要设计一个下 五子棋 的游戏程序 对他而言 C语言的编程规则已经清楚 他所面对的核心问题是寻找一种可以模拟人下棋的算法 因此 算法在软件设计中具有重要的地位 正如著名的计算机科学家沃思 NikiklausWirth 所指出的如下公式 程序 数据结构 算法 4 例3 1 求1 2 3 4 100 算法1步骤1 1 2 3步骤2 3 3 6步骤3 6 4 10 步骤99 4950 100 5050算法2步骤1 0 100 100步骤2 1 99 100步骤3 2 98 100 步骤50 49 51 100步骤51 100 50 5000步骤52 5000 50 5050算法3步骤1 k 1 s 0步骤2 如果k 100 则算法结束 s即为所求的和 输出s 否则转向步骤3步骤3 s s k k k 1步骤4 转向步骤2 本节 5 3 1 2算法的特性一个方法要成为我们可以在程序设计中所使用的算法 需要具备如下特征 1 有穷性一个算法要在有限的步骤内解决问题 这里所说的步骤是指计算机执行步骤 计算机程序不能无限地运行下去 甚至不能长时间地运行下去 所以一个无限执行的方法不能成为程序设计中的 算法 例如 求某一自然数N的阶乘 n 1 2 3 n这是一个算法 因为对任何一个自然数而言 无论这个数多大 总是有限的 用这个公式计算n 总是需要有限的步骤 但是 以下计算公式则不能作为算法 因为其计算步骤是无限的 sum 1 1 1 1 2 1 3 1 n 6 2 确定性算法中操作步骤的顺序和每一个步骤的内容都应当是确定的 不应当是含糊不清的 它也不能有不同的解释存在 即不能具有 二义性 不应当产生两种或多种以上的含义 3 可行性每一个算法是可行的 即算法中的每一个步骤都可以有效地执行 并得到确定的结果 例如 b 0 执行a b 4 有零个或多个输入输入就是从外界取得必要的信息 一个算法可以有零个或多个输入 例如 输入一个年份 判断其是否是闰年 同时一个算法可以没有输入 例如 计算出5 是多少 5 有一个或多个输出算法的目的就求解 解 就是我们想要得到的最终结果 输出是同输入有着某些特定关系的量 一个算法得到的最终结果就是输出 没有输出的算法是没有意义的 本节 7 3 2算法的常用表示方法 3 2 1自然语言表示法3 2 2流程图3 2 3N S结构流程图3 2 4伪代码表示法3 2 5用计算机语言表示算法 本章 8 3 2 1自然语言表示法自然语言是指人们在日常生活中使用的语言 如汉语 英语等 比如对于以下这句话 如果A大于B 就给它加1 在理解时就可能出现歧义 是给A加1 还是给B加1 对于以上的一段话 如果我们用C语言进行编程则为 if A B A A 1 对于某些程序员来说 自然语言通俗易懂 缺点是 很冗长 不直观 而且容易发生歧义 例3 2 求m 如果m 6 即求1 2 3 4 5 6 我们先设s代表累乘之积 以t代表乘数 自然语言表示m 的算法为 使s 1 t 1 使s t 得到的积仍放在s中 使t的值加1 如果t m 返回第 步重新执行 如果t m 则不再返回 而停止循环 此时s中的值就是m 输出s 本节 9 3 2 2流程图流程图表示法就是用各种图框表示各种操作 这种表示法的优点是直观易于理解 流程图表示法是美国国家标准化协会ANSI AmreicanNationalStandardInstitute 规定的 一些常用的流程图符号在Word中都可以通过 绘图 命令来绘制 结构化程序设计中采用三种基本结构 即顺序结构 选择结构和循环结构 这三种基本结构有以下共同特点 只有一个入口 只有一个出口 结构内的每一部分都有机会被执行到 结构内不存在 死循环 无终止的循环 10 顺序结构A和B两个框是顺序执行的 选择结构选择结构或称分支结构 条件结构 此结构中必包含一个判断框 根据给定的条件P是否成立来进行选择 若P成立 则执行A框中的操作 否则 执行B框中的操作 循环结构循环结构又称重复结构 有两种 当型循环 直到型循环 11 用流程图表示例3 2 本节 12 3 2 3N S结构流程图1973年美国学者I Nassi和B Shneiderman提出了一种新的流程图形式 在这种流程图中 完全去掉了带箭头的流程线 全部算法都是在一个矩形框内 在该框内还包含其它的从属于它的框 或者说由一些基本的框组成一个大框 这种方法就以这两位学者的名字缩写而成 被称为 N S图 N S图可以表示的三种典型结构 13 用N S结构流程图表示例3 2 本节 14 3 2 4伪代码表示法伪代码是用介于自然语言和计算机语言之间的文字和符号来表示算法 即计算机程序设计语言中具有的语句关键字用英文表示 其他的可用汉字 也可用英文 只要便于书写和阅读就可 用伪代码表示算法并无固定的 严格的语法规则 只要求把意思表达清楚 并且书写的格式清晰易懂即可 例3 3 求m 用伪代码表示的算法如下 开始从键盘输入一个正整数给m置s的初值为1置t的初值为1当t m 执行下面操作 使s s t使t t 1 循环体到此结束 输出s的值结束 本节 15 3 2 5用计算机语言表示算法用流程图或其他方法表示了算法 还要用计算机实现算法 借助计算机语言编写程序 被计算机执行 用计算机解决一个问题 包括设计算法和实现算法两个部分 计算机语言描述算法必须严格遵循所用语言的语法规则 例3 4 将求m 的算法用C语言表示 includevoidmain intt s m printf nPleaseinputaintegertom scanf d 本节 16 3 3结构化程序设计方法 要解决实际问题 编写程序的步骤是 从目前的编程实践看 结构化程序设计的思路已经被绝大多数程序员所接受 人们普遍认为 必须采用结构化的程序设计方法 因为结构化程序具有结构清晰 便于阅读 便于修改和便于维护的优点 结构化程序设计的基本思路是 把一个复杂的问题的求解过程分阶段进行 每个阶段处理的问题都控制在人们容易理解的范围之内 17 保证结构化程序采取的方法 自顶向下逐步细化 求精 模块化设计结构化编码模块化 将一个大任务分成若干个较小的任务 较小的任务又细分为更小的任务 直到只能解决功能单一的任务为止 模块 由函数来实现 例如 工资管理系统 18 例3 5 输入10个整数 每个数都 3 打印出其中的素数 19 本章 20 3 4C语句概述 一个C语言程序的执行部分由语句组成 程序的各种功能 如输入 输出 计算 打印等 也由语句实现的 C语言的语句可分为声明语句 函数调用语句 表达式语句 复合语句 控制语句以及不执行任何操作的空语句 声明语句说明语句用来定义变量的数据类型 如 ints i 函数调用语句函数调用语句由函数名 实际参数加上分号组成 其一般形式为 函数名 实际参数表 执行函数语句就是调用函数体并把实际参数赋予函数定义中的形式参数 然后执行被调函数体中的语句 可以返回也可以不返回函数值 它相当于其他语言中的调用子程序 例 printf ns d s 21 表达式语句表达式语句由表达式加上分号 组成 其一般形式为 表达式 如 a b c y x y 执行表达式语句就是计算表达式的值 注意 赋值语句和赋值表达式的区别 空语句空语句就是什么也没有的语句 也就是只有分号的语句 空语句不执行任何操作 但仍然有一定的用途 比如 预留位置或用来作空循环体 例 while getchar n 这段程序的作用是 等待键盘输入 若输入非则继续等待重新输入 只有输入才结束 循环体只有一个空语句 如果没有这一个空语句 则会出现错误 22 复合语句把多个语句用大括号 括起来组成的一个语句称复合语句 C语言的编译系统把复合语句作为是单条语句对待 例 b c d a e f printf d d b a 复合语句中的各条语句都以分号 结尾 注意 在大括号 之后不要加分号 控制语句控制语句用于控制程序的流程 以实现程序的顺序 分支 循环等各种结构方式 控制语句分为三类共九种 1 条件判断语句 if switch语句2 循环执行语句 do while while和for语句3 转向语句 break goto continue和return语句 本章 23 补充 顺序结构程序设计 顺序结构的程序设计是最简单的 只要按照解决问题的顺序写出相应的语句就行 它的执行顺序是自上而下 依次执行 顺序结构可以独立使用构成一个简单的完整程序 常见的输入 计算 输出三部曲的程序就是顺序结构 例如计算圆的面积 其程序的语句顺序就是输入圆的半径r 计算s 3 14159 r r 输出圆的面积s 不过大多数情况下顺序结构都是作为程序的一部分 与其它结构一起构成一个复杂的程序 例如选择结构中的复合语句 循环结构中的循环体等 24 实验 以下的程序用于计算一个矩形的周长和面积 程序运行时提示输入长和宽的值 然后计算并输出该矩形的周长和面积 请将程序补充完整 includevoidmain floatlength floatwidth floatperimeter 周长 floatarea 面积 25 补充例1 从键盘输入一个大写字母 要求改用小写字母输出 includevoidmain charc1 c2 c1 getchar printf c d n c1 c1 c2 c1 32 printf c d n c2 c2 运行情况 A A 65a 97 26 补充例2 输入三角形的三边长 求三角形面积 假设 三边长a b c能构成三角形 已知面积公式 其中 s a b c 2 27 include includevoidmain floata b c s area scanf f f f 本章 运行情况 28 3 5选择结构程序设计 3 5 1关系运算符和关系表达式3 5 2逻辑运算符和逻辑表达式3 5 3if语句3 5 4if语句的嵌套3 5 5条件运算符和条件表达式3 5 6switch语句3 5 7选择结构程序设计举例 本章 29 3 5 1关系运算符和关系表达式 C语言提供6种关系运算符 大于 大于或等于 等于 不等于 用关系运算符将两个表达式连接起来的式子 称关系表达式 如 a b a b b c a 3 b 5 a b bb值为1 a b c值为1d a bd的值为1f a b cf的值为0 本节 优先级相同 高 优先级相同 低 30 3 5 2逻辑运算符和逻辑表达式 C语言提供3种逻辑运算符 逻辑非 逻辑与 逻辑或 逻辑运算的真值表 31 算术运算符 关系运算符 逻辑运算符和赋值运算符的优先级 如 a b x y a b x y a b x y a b x y a a b a a b 用逻辑运算符将关系表达式或逻辑量连接起来的式子称为逻辑表达式 逻辑表达式的值是一个逻辑 真 或 假 C语言编译系统在给出逻辑运算结果时 以数值1代表 真 以数值0代表 假 但在判断一个量是否为 真 时 以0代表 假 以非0代表 真 例 若a 4 则 a的值为0 若a 4 b 5 则a b的值为1 a b的值为1 a b的值为1 例 将数学关系式 0 x 100 表达成逻辑式 x 0 x 100逻辑运算符两侧的运算对象还可以是任何类型的数据 如 c d 32 在逻辑表达式的求解中 并不是所有的逻辑运算符都执行 只是在必须执行下一个逻辑运算符才能求出表达式的解时 才执行该运算符 如 a逻辑表达式 m a b n c d 使m 0 而n 1 33 例 要判断某一年是否是闰年 闰年的条件是符合下面二者之一 能被4整除 但不能被100整除 或能被400整除 C语言的表达式 year 4 0 year 100 0 year 400 0 本节 34 3 5 3if语句选择结构往往依赖于所给出的条件 决定从给出的操作中选择一组去执行 格式1 if 表达式 语句 功能 如果表达式的值为真 做语句的内容 否则什么都不做 任何类型 35 例3 7 输入一个字符c 若c是字母 则输出 Yes includevoidmain charc c getchar if c a 运行情况 x Yes 思考题 完善 补充例1 36 例 includevoidmain ints printf nInputyourscore 输入提示信息 scanf d 如果s 60 输出pass 运行结果 Inputyourscore 70 yourscore 70 pass 37 补充例3 已知两个变量x和y 比较它们的大小 使得x中的值大于y includevoidmain intx y t printf x scanf d x y 两个数交换过程 思考题 从键盘输入3个整数a b和c 编写程序将它们按从大到小排序 38 补充例 从键盘输入3个整数a b和c 编写程序将它们按从大到小排序 includevoidmain inta b c temp printf Pleaseinputthreenumbers scanf d d d 39 格式2 if 表达式 语句1 else 语句2 其意义为 若表达式的值为真 则执行 语句1 否则执行 语句2 若 语句1 或 语句2 为一条语句时 则可以去掉相应的 例 if h 1 1 price 0 elseprice 50 或 if h 1 1 price 0 elseprice 50 任何类型 40 例3 9 输入两个数并判断两数是否相等 includevoidmain inta b printf Enterintegera scanf d Enterintegera 5 Enterintegerb 7 a b Enterintegera 10 Enterintegerb 10 a b 运行结果 41 补充例4 判断一个年份是否是闰年 并把结果输出 includevoidmain intyear printf 请输入一个年份 scanf d 思考题 判断一个整数是奇数还是偶数 并把结果显示出来 42 补充例 判断一个数是奇数还是偶数 并把结果显示出来 includevoidmain intx printf nPleaseinputaintegertox scanf d 43 补充例5 从键盘输入3个整数a b和c 编写程序找出其中的最大数 输出结果 includevoidmain inta b c max printf Pleaseinputthreenumbers scanf d d d 44 例3 10 输入一个整数 若该数不为零 则输出 includevoidmain intx scanf d 运行结果 5 x 5 45 if语句中应注意的问题 分支语句的复杂性关键在于表达式 表达式通常是逻辑表达式或关系表达式 但是也可以是其它表达式 甚至也可以是一个变量 例如 if a 8 if x 只要表达式的值为非0 即为 真 就执行其后的语句 在if语句中的表达式必须用括号括起来 如果要想在if语句中满足条件时执行一组 多个 语句 则必须把这一组语句用 括起来组成一个复合语句 注意复合语句的 之后不能加分号 本节 46 3 5 4if语句的嵌套前二种形式的if语句一般都用于两个分支的情况 当有多个分支选择时 可采用if else if语句 其一般形式如下 if 表达式1 if 表达式2 语句1 else语句2 elseif 表达式3 语句3 else语句4 47 例3 11 编写程序 求下列分段函数的值 1 x0 include includevoidmain floatx doublez printf nx scanf f if语句嵌套包含在else的后面 48 改写 例3 11 将if语句的嵌套包含在if的后面 include includevoidmain floatx doublez printf nx scanf f if语句嵌套包含在if的后面 49 if 表达式1 if 表达式2 语句1 elseif 表达式3 语句2 else语句3 上面的语句中的第1个else是与第2个if配对的 如果要改变这种默认的配对关系 可以在相应if条件选择语句上加上左 右花括号来确定新的配对关系 如 if 表达式1 if 表达式2 语句1 elseif 表达式3 语句2 else语句3 else总是与它上面最近的且又没有配对的if语句进行配对 50 例3 12 写出下面程序的运行结果 includevoidmain inta b c a 5 b 3 c 0 if c if a b printf nmax d a elseprintf nmax d b elseprintf nc d c 本节 51 3 5 5条件运算符和条件表达式条件表达式的一般形式为 表达式1 表达式2 表达式3表达式的执行顺序 计算表达式1的值 若为真 则计算表达式2的值 作为条件表达式的结果 否则计算表达式3的值 作为条件表达式的结果 优先级 高于赋值运算符 低于算术和关系运算符 例 max a b a b相当于max a b a b a b a b 1相当于 a b a b 1 条件运算符的结合方向为 自右至左 例 a b a c d c d相当于a b a c d c d 例 if a b max a elsemax b 可以用条件运算符来表示为 max a b a b 本节 52 3 5 6switch语句判断语句可以实现两个分支的程序流程 但编程中往往要求实现多个分支的程序流程 这就要使用多分支语句 其一般形式为 switch 表达式 case常量表达式1 语句1 case常量表达式2 语句2 case常量表达式n 语句n default 语句n 1 整型 字符型 枚举型 53 执行过程是 1 首先计算表达式的值 然后把表达式的值与其后的常量表达式值逐个相比较 2 当表达式的值与某个常量表达式的值相等时 即执行该case后的语句 3 如表达式的值与所有case后的常量表达式均不相同时 则执行default后的语句 4 若没有default语句 则退出此开关语句 注意 程序在执行完毕相应的case语句后不能退出 而是继续执行其后的其它语句 格式中的表达式的作用为控制程序的流程 它的数值类型必须与case语句中常量表达式的类型一致 所有常量表达式的类型必须相同 而它们的值必须不同 54 若要执行完一个case的语句后 转到switch后的语句去执行 则要在该case语句的最后加上break语句 跳转语句 跳转到switch后的语句去执行 switch语句与break语句连用图解 55 例3 14 编写一个程序 要求输入学生的分数 输出其成绩的分数段 用A B C D E分别表示90分以上 80 89分 70 79分 60 69分和不及格 0 59分 5个分数段 includevoidmain intscore grade printf nInputascore 0 100 scanf d 56 case6 printf grade D n break case7 printf grade C n break case8 printf grade B n break case9 case10 printf grade A n break default printf Thescoreisoutofrange n 运行结果如下 Inputascore 0 100 50 grade E 再运行一次 Inputascore 0 100 90 grade A 57 例3 15 从键盘输入一个日期 判断这一天是这一年中的第几天 includevoidmain intday month year sum leap printf nPleaseinputyear month day n scanf d d d 58 case12 sum 31 28 31 30 31 30 31 31 30 31 30 break default printf inputerrorofmonth sum sum day 再加上该月的天数 if year 400 0 year 4 0 本节 运行结果如下 Pleaseinputyear month day2008 7 19 Itisthe201thday 59 3 5 7选择结构程序设计举例 例3 16 求一元二次方程ax2 bx c 0的实数解 并显示结果 假设a 0 include includevoidmain floata b c d scanf f f f 60 例3 17 输入两个正整数a b 其中a不大于31 b最大不超过三位数 使a在左 b在右 拼成一个新的数c 例如a 23 b 30 则c为2330 若a 1 b 15 则c为115 算法分析 抽象分析出以下数学模型 决定c值的计算公式如下 当b为一位数时 c a 10 b当b为二位数时 c a 100 b当b为三位数时 c a 1000 b求c的公式 c a k b k的取值可以为 10 100或1000 61 includevoidmain inta b c k printf nInputtwopositiveintegernumber scanf d d 62 例3 18 个体工商户的生产经营所得 以每一纳税年度的收入总额 减除成本 费用以及损失后的余额 为全年应纳税所得额 其所得税税率表如下 级数全年应纳税所得额税率 1不超过5000元的52超过5000元至10000元的部分103超过10000元至30000元的部分204超过30000元至50000元的部分305超过50000元的部分35 includevoidmain longintr ints doublef printf Inputaintegertor scanf ld 63 if r 0 s r 1 5000 switch s case0 f r 0 05 break case1 f 5000 0 05 r 5000 0 1 break case2 case3 case4 case5 f 5000 0 05 5000 0 1 r 10000 0 2 break case6 case7 case8 case9 f 5000 0 05 5000 0 1 20000 0 2 r 30000 0 3 break default f 5000 0 05 5000 0 1 20000 0 2 20000 0 3 r 50000 0 35 printf f f f elseprintf Inputadataerror 64 例3 19 编程 输入两个实数a b 再输入一个运算符 可以是 或 根据运算符计算并输出a b两个数的和 差 积和商 includevoidmain floata b charc scanf f f 65 例3 20 给一个不多于5位的正整数 编程求 它是几位数 逆序打印出各位数字 若为两位以上的数 则判断该数是否为回文数 includevoidmain inta b c d e longx do printf nPleaseinputapositiveintegernumbertox scanf ld 分解出个位数 66 if a 0 printf thereare5 d d d d d n e d c b a if e a 67 elseif c 0 printf thereare3 d d d n e d c if e c printf thisnumberisahuiwen n elseprintf thisnumberisnotahuiwen n elseif d 0 printf thereare2 d d d n e d if e d printf thisnumberisahuiwen n elseprintf thisnumberisnotahuiwen n elseif e 0 printf thereare1 d n e 本节 68 3 6循环程序设计 循环结构就是当给定条件成立时 反复执行某程序段 直到条件不成立为止 给定的条件称为循环条件 反复执行的程序段称为循环体 在C语言中提供了四种实现循环结构的方法 1 用if语句和goto语句构成的循环 2 用while语句 3 用do while语句 4 用for语句 69 3 6 1goto语句以及用goto语句构成的循环3 6 2while语句3 6 3do while语句3 6 4for语句3 6 5多重循环3 6 6break语句3 6 7continue语句3 6 8循环程序设计举例 本章 70 3 6 1goto语句以及用goto语句构成的循环在结构化程序设计中一般不主张使用goto语句 以免造成程序流程的混乱 能避免使用goto则应避免使用 确实不得不用时 才使用goto goto语句称为无条件转向语句 其一般格式如下 goto语句标号 goto语句的语义是改变程序流向 立即跳转到标号所标识的语句 语句标号是按标识符规定书写的符号 放在某一语句行的前面 标号后加冒号 语句标号起标识语句的作用 并不影响该语句的执行 标号只起与goto句配合的作用 C语言不限制程序中使用标号的次数 但各标号不得重名 一般情况下 使用goto语句有两种情况 与if语句一起构成循环结构 从循环体中跳转到循环体外 71 使用goto语句时应该注意以下几点 跳转到一个循环内是非常危险的 应该极力避免这样做 不能跳转到本函数外 goto语句越少用越好 通常不主张向程序的前面跳转 例3 21 用if语句和goto语句构成循环 求 i includevoidmain inti 1 存放自然数 intsum 0 存放和 loop if i 100 sum i i gotoloop printf n1 2 3 100 d sum 运行结果 1 2 3 100 5050 本节 72 3 6 2while语句while语句 当循环语句 其形式如下所示 while 表达式 循环体语句 或while 表达式 循环体语句 其中表达式是循环条件 while语句的执行过程 计算表达式的值若表达式的值为真 非0 时 则转到第 步若表达式的值为假 0 转到第 步 执行循环体语句 转到第 步执行 结束循环 执行while语句后的第一条语句 73 例3 22 用while语句来实现求 i includevoidmain inti 1 intsum 0 while i 100 sum i i printf n1 2 3 100 d sum 说明 while语句一般用于事先不知道循环次数 在循环执行的过程中 根据条件来决定循环是否结束 在循环体语句中可以是一条简单的语句 也可以是复合语句 若为复合语句则要用花括号括起来 在循环体语句中 一定要有改变循环条件的语句 使循环能终止 本节 74 3 6 3do while语句dowhile语句 直到型循环 其一般形式为 do 循环体语句 while 表达式 其中表达式是循环条件 do while语句的执行过程是 执行循环体语句 判别表达式的值 若表达式的值为真 非0 则转到第 步若表达式的值为假 0 则转到第 步 结束循环 执行dowhile语句后的第一条语句 75 例3 23 用dowhile语句来实现求 i includevoidmain inti 1 intsum 0 do sum i i while i 100 printf n1 2 3 100 d sum 76 说明 do while语句一般用于事先不知道循环次数 在循环执行的过程中 根据条件来决定循环是否结束 在循环体语句中可以是一条简单的语句 也可以是复合语句 若为复合语句则要用花括号括起来 在循环体语句中 一定要有改变循环条件的语句 使循环能终止 while 表达式 的后面一定要加分号 表示do while语句的结束 do while语句和while语句的区别在于 dowhile是先执行后判断 即dowhile至少执行一次循环体 while是先判断后执行 如果条件不满足 则一次循环体语句也不执行 while语句和do while语句一般都可以相互改写 77 例3 24 while循环和dowhile循环的比较 include includevoidmain voidmain intm n 1 intm n 1 scanf d 程序运行结果 5 n 46 m 11再运行一次的结果 11 n 12 m 12 程序运行结果 5 n 46 m 11再运行一次的结果 11 n 1 m 11 本节 78 3 6 4for语句for语句也是一种循环语句 其功能是把某些语句重复执行若干次 不仅可以用于循环次数确定 而且也可以用于循环次数不确定的循环 其一般形式为 for 表达式1 表达式2 表达式3 循环体语句for语句的执行过程 计算表达式1的值 计算表达式2的值若表达式2的值为真 非0 则执行循环体 然后转到第 步 若表达式2的值为假 0 则转到第 步 计算表达式3的值 转回第 步重复执行 循环结束 执行for语句后面的第一条语句 在整个for循环过程中 表达式1只计算一次 表达式2和表达式3则可能计算多次 循环体可能多次执行 也可能一次都不执行 79 例3 25 求1000以内的奇数和 includevoidmain inti longintsum 0 for i 1 i 1000 i 2 sum i printf nsum ld n sum 80 说明 for语句可用如下易理解的形式来描述 for 循环变量初值 循环条件 循环变量增值 循环体语句也即表达式1相当于给循环变量赋初值 表达式2是一个条件表达式 表达式3是改变循环变量的值 for语句的一般形式中的 表达式1 可以省略 此时应在for语句之前给循环变量赋初值 表达式1省略 其后的分号不能省略 执行时跳过 求解表达式1 这一步 其它不变 includevoidmain inti 1 longintsum 0 for i 1000 i 2 sum i printf nsum ld n sum 81 表达式2 也可省略 其后的分号不能省略 此时等于没有循环条件 执行for语句时 就不要判断循环条件 也就认为表达式2始终为真 此时循环体一定要有一条语句能够跳出循环否则就是一个死循环 includevoidmain inti longintsum 0 for i 1 i 2 if i 1000 break break跳转语句 跳出for循环语句 sum i printf nsum ld n sum 82 表达式3 也可省略 此时应在循环体中有语句可以改变循环变量的值 否则循环也会变成死循环 includevoidmain inti longintsum 0 for i 1 i 1000 sum i i 2 printf nsum ld n sum 83 表达式1 表达式2 表达式3可以省略一个或两个 也可同时全部省略 如 for 循环体语句 表达式1 2 3可以是任何类型的表达式 包括逗号表达式 可以是与循环变量有关的表达式 也可以是与循环变量无关的表达式 如 for sum 0 i 1 ivoidmain inti charc for i 0 c getchar n i printf c c printf Thesumis d n i 循环体可以是空语句 空语句可以用来实现延时 也就是在程序执行中等待一定的时间 如下为延时程序 for i 1 i 1000 i 84 例3 28 中国剩余定理 有物不知几何 三三数余一 五五数余二 七七数余三 问 物有几何 编程求1000以内所有解 编程思路 采用 穷举法 来解此题 具体做法是 从所有可能解中 逐个进行试验 若满足条件 就得到一个解 否则不是 直到条件满足或判别出无解为止 includevoidmain intm count 0 for m 1 m 1000 m if m 3 1 每行输出5个数 运行结果如下 52157262367472577682787892997 85 补充例6 输出所有水仙花数 水仙花数是指一个三位数 其各位数字的立方和等于该数本身 例如 153是一个水仙花数 因为153 13 53 33 穷举法 includevoidmain intm intx y z for m 100 m 999 m x m 100 分解出百位数 y m 10 10 分解出十位数 z m 10 分解出个位数 if x x x y y y z z z m printf d n m 153370371407 本节 86 3 6 5多重循环在循环语句中又包含另一个循环语句时 我们称其为循环嵌套 在多重循环中 处于内部的循环称为内循环 处于外部的循环称为外循环 按循环嵌套的层数 可分别称二重循环 三重循环等等 语言规定 内循环必须完全嵌套于外循环中 内 外循环不能交叉 并且内 外循环的循环控制变量不能同名 在C语言中 凡是可以出现语句的地方 都可以出现循环语句 例3 29 打印如图下图所示的 九 九 乘法表 87 算法分析 外循环是输出行 用i作为循环控制变量i 1 9 内循环是输出列 用j作为循环控制变量j 1 9 includevoidmain inti j for i 1 i 9 i 外循环 控制行 for j 1 j 9 j 内循环 控制列 printf d d d t i j i j printf n 88 includevoidmain inti j for i 1 i 9 i for j 1 j i j printf d d d t i j i j printf n 思考题 在屏幕上输出如下图所示乘法口诀表 要保证输出的是三角的格式 必须满足列坐标 j 不大于行坐标 i 即 j i 如何输出 89 补充例 输出所有水仙花数 多重循环 穷举法 算法分析 设这三位数的百位数为x 十位数为y 个位数为z 按水仙花数的定义有 x3 y3 z3 100 x 10y z 1 x 9 0 y 9 0 z 9 且x y z都是整数 includevoidmain intx y z for x 1 x 9 x for y 0 y 9 y for z 0 z 9 z if x x x y y y z z z 100 x 10 y z printf d n 100 x 10 y z 153370371407 90 例3 30 有1 2 3 4个数字 能组成多少个互不相同且无重复数字的三位数 都是多少 includevoidmain inti j k count 0 printf n for i 1 i 5 i 以下为三重循环 for j 1 j 5 j for k 1 k 5 k if i k 本节 91 3 6 6break语句break语句只用在switch语句或循环语句中 其作用是无条件跳出switch语句或跳出本层循环 转去执行后面的程序 break语句的一般形式为 break 使用break语句可以使循环语句有多个出口 使程序避免了一些不必要重复 提高了程序效率 break语句与while循环语句连用格式 while 表达式1 语句1 if 表达式2 break 语句2 break与while连用 92 例3 31 求当半径r为何值时 圆的面积大于100 includevoidmain intr floatarea pi 3 1415927 for r 1 r area pi r r if area 100 break printf f n area printf r d n r 注意 break语句不能用于switch和循环语句之外的任何其它语句中 程序运行结果 3 14159312 56637128 27433450 26548478 539818r 6 93 补充例7 韩信点兵问题 韩信有一队士兵 他想知道有多少人 便让士兵排队报数 按从1到5报数 最末一个士兵报的数为1 按从1到6报数 最末一个士兵报的数为5 按从1到7报数 最末一个士兵报的数为4 最后再按从1到11报数 最末一个士兵报的数为10 编程计算韩信至少有多少兵 break应用 算法分析 设兵数为x 则按题意x应满足 x 5 1 x 6 5 x 7 4 x 11 10采用穷举法对x从1开始逐个试验 第一个使得上述关系式成立的x值即为所求 94 includevoidmain intx for x 1 x if x 5 1 x 2111 练习 有一条长阶梯 若每步跨2阶 最后剩下1阶 若每步跨3阶 最后剩下2阶 若每步跨5阶 最后剩下4阶 若每步跨6阶 则最后剩下5阶 只有每步跨7阶 最后才正好1阶不剩 编程计算这条阶梯共有多少阶 本节 95 3 6 7continue语句continue语句只能用在循环体中 其一般格式是 continue 其语义是 结束本次循环 即不再执行循环体中continue语句之后的语句 而是立即转入对循环条件的判断与执行 应特别注意的是 continue语句只结束本层本次的循环 并不跳出循环 continue语句与while循环语句连用格式 while 表达式1 语句1 if 表达式2 contimue 语句2 continue与while连用 96 例3 32 从键盘输入整数 显示出其中的正整数 若输入的是100 则退出 includevoidmain intx do scanf d 97 例3 33 求连续的奇数和 当奇数和刚好超过1000时停止计算 并按运行结果输出 程序中有两空 请读者补充 使之能实现上述功能 includevoidmain inti sum 0 for i 1 i if i 2 0 sum i if sum 1000 printf 1 3 5 d d n i sum 本节 continue break 98 3 6 8循环程序设计举例 补充例8 男 女生总计18个人 在一家饭店里吃饭 共花了74元 每个男生各花5元 每个女生各花3元 利用穷举法编程计算男 女生各有多少人 穷举法 算法分析 设男生x人 女生y人 根据题意有 x y 185x 3y 74且x y应为整数 并满足下列条件 1 x y 18 includevoidmain intx y for x 1 x 18 x 男生人数的取值 for y 1 y 18 y 女生人数的取值 if x y 18 思考题 鸡兔同笼问题 已知鸡和兔总头数为30 总脚数为90 求鸡兔各有多少只 男生 10女生 8 99 补充例 求鸡兔同笼问题 已知鸡和兔总头数为30 总脚数为90 求鸡兔各有多少只 算法分析 设鸡有x只 兔有y只 则鸡兔同笼有 x y 302x 4y 90且x y应为整数 并满足下列条件 1 x y 30 includevoidmain intx y for x 1 x 30 x 鸡数的取值 for y 1 y 30 y 兔数的取值 if x y 30 鸡 15兔 15 100 例3 35 某人想将手中一张100元的人民币换成5元 1元和0 5元面值的零钞 但要求最后的零钞总数为100张 且要求每种零钞的数量不少于1张 问有哪几种组合 算法分析 这是一个数学问题 我们先抽取它的数学模型 设5元的票i张 1元的票j张 0 5元票k张 可以列出 i j k 1005i j 0 5k 100 也可写成 10i 2j k 200 三个变量只能列出两个方程式 不能解 通过计算机用穷举法 5元1元5角i 1j 1k 1 98j 2k 1 98 j 94k 1 98i 2j 1k 1 98 j 94k 1 98i 19 101 includevoidmain inti j k printf nijk n for i 1 i 20 i for j 1 j 95 j for k 1 k 98 k if i j k 100 运行结果如下 ijk1918282163732446432555406464873756828649197210108011188 思考题 百鸡问题 一只公鸡5元 一只母鸡3元 三只小鸡1元 现要求用100元买100只鸡 且要求每种鸡的数量不少于 只 问公鸡 母鸡 小鸡各买多少只 102 补充例 百鸡问题 一只公鸡5元 一只母鸡3元 三只小鸡1元 现要求用100元买100只鸡 且要求每种鸡的数量不少于 只 问公鸡 母鸡 小鸡各买多少只 算法分析 假设买公鸡x只 买母鸡y只 买小鸡z只 根据题意得方程组 x y z 100 按100只鸡计算 5x 3y z 3 100 按100元钱计算 且x y z应为整数 并满足下列条件 1 x 19 公鸡5元一只 其总数不能超过19只 1 y 31 母鸡3元一只 其总数不能超过31只 3 z 96 小鸡1元三只 其总数不能超过96只 根据上面的分析 可以采用对x y z三个变量在各自的范围内 用各种不同的组合方式逐个计算 看是否满足条件的结果输出来 103 includevoidmain intx y z for x 1 x 19 x 公鸡的取值 for y 1 y 31 y 母鸡的取值 for z 3 z 96 z z 3 小鸡的取值 if 5 x 3 y z 3 100 可买4只公鸡 18只母鸡 78只小鸡 可买8只公鸡 11只母鸡 81只小鸡 可买12只公鸡 4只母鸡 84只小鸡 104 例3 34 从键盘输入一个整数n 判断n是否为素数 编程思路 让n被2到n 1除 如果n能被2 n 1之中任何一整数整除 则n非素数 如果n不能被2 n 1之间的任一整数整除 则n是素数 素数即质数 指只能被1和它本身整除的数 最佳方法 让n被2到除 如果n能被2 之中任何一整数整除 n非素数 如果n不能被2 之间的任一整数整除 则n是素数 105 include includevoidmain intn j k printf nInputaintegerton scanf d sqrt n 思考题 编写一个程序 输出100以内的所有素数 106 include includevoidmain intn j k for n 2 n k 1 printf 5d n 107 例3 36 利用格里高利公式求 直到最后一项的值小于10 6为止 算法分析 第1 3 5等奇数项为正数 偶数项为负数 分母