清华大学C语言教学第4个ppt课件

1 计算机程序设计基础 第四讲数组 2 三 数组 中秋佳节 有贵客来到草原 主人要从羊群中选一只肥羊宴请宾客 当然要选最重者 这样就要记录每只羊的重量 如果有成千上万只羊 不可能用一般变量来记录 可以用带有下标的变量 也就是这里要讲的数组 问题 哪只羊最重 3 我们先看例子 用键盘输入10只羊的重量存放到一个名为sheep的数组中 includevoidmain 主函数 floatsheep 10 数组 有10个浮点类型元素 用于存10只羊每一只的重量floatmax 浮点类型变量 存放最肥羊的重量inti k 整型变量 i用于计数循环 k用于记录最肥羊的号max 0 0 赋初值0for i 0 i 10 i i 1 计数循环 循环 开始printf 请输入羊的重量sheep d i 提示用scanf f 输出最肥羊的编号 4 程序框图 5 三 数组 数组的定义类型说明符数组名 常量表达式 例 floatsheep 10 inta2001 1000 说明1 数组名的第一个字符应为英文字母 2 用方括号将常量表达式括起 3 常量表达式定义了数组元素的个数 6 三 数组 4 数组下标从0开始 如果定义5个元素 是从第0个元素至第4个元素 例如inta 5 定义了5个数组元素如下 a 0 a 1 a 2 a 3 a 4 这是5个带下标的变量 这5个变量的类型是相同的5 常量表达式中不允许包含变量 例如intn n 5 inta n 不合法 7 三 数组 数组初始化是定义数组完成赋初值的任务例如inta 5 3 5 4 1 2 a 0 3 a 1 5 a 2 4 a 3 1 a 4 2 8 1 includevoidmain inta 4 声明项printf a 0 d a 1 d a 2 d a 3 d n a 0 a 1 a 2 a 3 2 其他不变 改变声明项为inta 4 0 1 2 3 请自己上机做6个实验 9 3 其他不变 改变声明项为inta 4 3 8 4 其他不变 改变声明项为inta 4 2 4 6 8 10 5 其他不变 改变声明项为inta 4 2 4 6 d 6 其他不变 改变声明项为intn 4 inta n 0 1 2 3 10 讨论问题 使用筛法求100以内的所有素数 三 数组 思路1 想象将100个数看作沙子和小石头子 让小石头子权称素数 让沙子当作非素数 弄一个筛子 只要将沙子筛走 剩下的就是素数了 2 非素数一定是2 3 4 的倍数 3 使用数组 让下标就是100以内的数 让数组元素的值作为筛去与否的标志 比如筛去以后让元素值为1 11 方法的依据 1至100这些自然数可以分为三类 单位数 仅有一个数1 素数 是这样一个数 它大于1 且只有1和它自身这样两个正因数 合数 除了1和自身以外 还有其他正因数 1不是素数 除1以外的自然数 当然只有素数与合数 筛法实际上是筛去合数 留下素数 为了提高筛选法效率 注意到 令n为合数 这里是100 c为n的最小正因数 则据初等数论只要找到c就可以确认n为合数 将其筛去 12 程序框图如下 13 上述框图很清晰地描述了筛法的思路 1 第一块是一个计数型的循环语句 功能是将prime数组清零 prime c 0 c 2 3 1002 第二块是正因数d初始化为d 2 3 第三块是循环筛数 这里用了一个dowhile语句 属于一种直到型循环 其一般形式为 do 循环体语句块 while 表达式 14 直到型循环框图如下 直到表达式为假时才退出循环 15 三 数组 例 求 的近似值用变量pi表示 的值 令表示括号中的每个项当最后一项的绝对值小于等于时 忽略掉以后的项 16 include includevoidmain 主函数 intsum 整型变量 总项数floatpi a b c 浮点变量 a为分母 b为分子 c为b除以api 0 sum 0 初始化a 1 0 b 1 0 c 1 0 初始化do 直到型循环 循环体 开始pi pi c 累加每一项sum sum 1 a a 2 0 计算每一项的分母b b 分子变正负号c b a 计算每一项 循环体结束while fabs c 1e 6 当c的绝对值大于10的 6次方时 继续 执行循环体 否则退出pi 4 pi 得到最终结果printf pi f n pi 输出pi值printf sum d n sum 输出总项数 参考程序如下 17 运行结果pi 3 141594 sum 500001提问 这种循环当表达式的值永远为真时 会如何 答 会构成死循环 即无休止地执行循环体请实验 1 将b定义为int型看看执行结果并分析为什么2 将1e 6变为1e 7或1e 4看看结果 18 下面还要介绍另一种循环 当循环 一般形式 while 表达式 语句块 循环体 19 分析 假定有x y且x y 设最小公倍数为z1 z一定会 x2 z kx k 1 2 3 z一定会被y整除用两个最简单的数试一下就可以找到算法 比如x 5 y 3 举例 求两个整数的最小公倍数 20 第一步z x z y 0不能整除 5 5 3 0第二步z z x不能整除 10 10 3 0第三步z z x 15 15 3 0能整除找到了z 15就是5和3的最小公倍数 21 include includevoidmain 主函数 intx y z w 整型变量scanf d d 输出最小公倍数 参考程序如下 22 请同学们去比较三种循环的异同之处1 for循环 计数型循环 2 当型循环 while循环 3 直到型循环 dowhile循环 上机将挑肥羊的程序和筛出素数的程序完成 自学与比较 23 问题 将几个数从大到小排序并输出 介绍冒泡排序法 24 25 从表中可以看出最小的一个数第一遍扫描就交换到a 6 中 如果将a 1 视为水底 a 6 视为水面 最轻的 最小的 一个数1最先浮到水面 交换到a 6 次轻的2第二遍扫描交换到a 5 再轻的3第三遍扫描交换到a 4 依此类推 有6个数 前5个数到位需5遍扫描 第6个最重的数自然落在a 1 中 因此 6个数只需5遍扫描 即j n 1 n 6 冒泡排序算法分析 26 再看在每遍扫描中 相邻两数组元素的比较次数 当j 1时 i 1 2 n j n 6时 比较5次之后a 6 中有一个最小数到达 这时a 6 不必再参与比较了 因此在第二遍搜索时 j 2 i 1 2 n j 即i 1 2 3 4 比较4次之后次小的一个数到达了a 5 这时a 5 不必再参与比较了 因此 j 3时 i 1 2 3 j 4时 i 1 2 j 5时 i 1 理出上述规律后 程序就不难编了 冒泡排序算法分析 27 为了表述方便 定义以下3个变量 n 待排序的数的个数 这里n 6j 扫描遍数 j 1 2 n 1i 第j遍扫描待比较元素的下标 i 1 2 n j 冒泡排序算法设计 28 采用两重计数型循环 步骤1 将待排序的数据放入数组中 步骤2 置j为1 步骤3 让i从1到n j 比较a i 与a i 1 如果a i a i 1 位置不动 如果a i a i 1 位置交换 即p a i a i a i 1 a i 1 p 步骤3结束后a n j 1 中的数为最小的数步骤4 让j j 1 只要j n就返回步骤3 将a n j