程序设计基础(一)--第八讲.ppt

1 6数据组织与处理 1 数组 2 数组的概念 定义和初始化筛法的解题思路冒泡排序的思路二维数组 学习目标 3 数组 定义 初始化 操作与应用筛法 do while循环 while循环 求质数排序 冒泡排序的算法二维数组 定义 初始化 应用 内容要点 4 6 1数组 5 中秋佳节 有贵客来到草原 主人要从羊群中选一只肥羊宴请宾客 当然要选最重者 这样就要记录每只羊的重量 如果有成千上万只羊 不可能用一般变量来记录 可以用带有下标的变量 也就是这里要讲的数组 问题 哪只羊最重 我们先看例子 用键盘输入10只羊的重量存放到一个名为sheep的数组中 6 程序名 6 1 cpp 数组示例 作者 wuwh 编制时间 2002年9月20日 主要功能 找出最重的羊 include 预编译命令 include 预编译命令usingnamespacestd intmain 主函数 floatsheep 10 数组 有10个浮点类型元素 用于存10只羊每一只的重量memset sheep 0 sizeof sheep 初始化数组元素为0floatbigsheep 0 0 浮点类型变量 存放最肥羊的重量inti 0 bigsheepNo 0 整型变量 i用于计数循环 bigsheepNo用于记录最肥羊的号 7 for i 0 i sheep i 输入第i只羊的重量if bigsheep sheep i 如果第i只羊比当前最肥羊大 bigsheep sheep i 让第i只羊为当前最肥羊bigsheepNo i 纪录第i只羊的编号 循环结束 输出最肥羊的重量cout 最肥羊的重量为 bigsheep endl 输出该羊的编号cout 最肥羊的编号为 bigsheepNo endl return0 8 程序框图 9 类型说明符数组名 常量表达式 例 floatsheep 10 inta2001 1000 说明1 数组名的第一个字符应为英文字母 2 用方括号将常量表达式括起 3 常量表达式定义了数组元素的个数 数组的定义 10 4 数组下标从0开始 如果定义5个元素 是从第0个元素至第4个元素 例如inta 5 定义了5个数组元素如下 a 0 a 1 a 2 a 3 a 4 这是5个带下标的变量 这5个变量的类型是相同的 11 5 常量表达式中不允许包含变量例如intn n 5 inta n 不合法 因为n是变量 不是常量 12 defineN100 宏定义 N为常数100 defineM200 宏定义 M为常数200inta N 定义有100个元素的整型数组alongb N M 定义有300个元素的长整型数组bdoubleg M 6 定义有206个元素的双精度实 型数组g以上定义是合法的 defineN100为命令行 不是语句 程序在编译时遇到N就用100替换 在命令行中定义的符号名N 也被称为符号常量N 13 第一种方法直接在定义时初始化例如inta 5 3 5 4 1 2 a 0 3 a 1 5 a 2 4 a 3 1 a 4 2 数组初始化 14 第二种方法使用memset函数格式为memset 数组名 初始化值 sizeof 数组名 举例 memset sheep 0 sizeof sheep 含义是将名为sheep的数组中的全部元素均初始化为0 更深一层是说让系统为sheep 10 所分配的内存单元从sheep 0 为标志的地址单元到该数组的全部地址单元都赋以0 调用此库函数需要加入头文件 15 1 includeusingnamespacestd intmain inta 4 声明项cout a 0 endl cout a 1 endl cout a 2 endl cout a 3 endl return0 2 其他不变 改变声明项为inta 4 0 1 2 3 请自己上机做7个实验 16 3 其他不变 改变声明项为inta 4 3 8 4 其他不变 改变声明项为inta 4 2 4 6 8 10 5 其他不变 改变声明项为inta 4 2 4 6 d 6 其他不变 改变声明项为intd inta 4 2 4 6 d 7 其他不变 改变声明项为intn 4 inta n 0 1 2 3 17 讨论问题使用筛法求100以内的所有素数 18 6 2筛法 19 思路想象将100个数看作沙子和小石头子 让小石头子权称素数 让沙子当作非素数 弄一个筛子 只要将沙子筛走 剩下的就是素数了 非素数一定是2 3 4 的倍数 使用数组 让下标就是100以内的数 让数组元素的值作为筛去与否的标志 比如筛去以后让元素值为1 20 方法的依据 1至100这些自然数可以分为三类 单位数 仅有一个数1 素数 是这样一个数 它大于1 且只有1和它自身这样两个正因数 合数 除了1和自身以外 还有其他正因数 1不是素数 除1以外的自然数 当然只有素数与合数 筛法实际上是筛去合数 留下素数 21 为了提高筛法效率 注意到 令n为合数 这里是100 c为n的最小正因数 据初等数论 只要找到c就可以确认n为合数 将其筛去 一定注意 要进行 筛 的1 100的数字是与数组prime 101 的下标相对应的 而每个数组元素的取值只有2个 是0或1 分别代表 标志 与下标相对应的数字是素数或不是素数 22 程序框图如下 请同学来分析左边程序的结构从而了解算法的设计思路为程序代码的实现创造条件 23 上述框图很清晰地描述了筛法的思路 1 第一块是一个计数型的循环语句 功能是将prime数组清零 prime c 0 c 2 3 1002 第二块是正因数d初始化为d 2 3 第三块是循环筛数 这里用了一个dowhile语句 属于一种直到型循环 24 举例求 的近似值 25 例 求 的近似值用变量pi表示 的值 令表示括号中的每个项当最后一项的绝对值小于等于时 忽略掉以后的项 26 程序名 5 2 cpp 作者 wuwh 编制时间 2002年9月20日 主要功能 求pi的近似值 include includeusingnamespacestd intmain 主函数 intsum 0 整型变量 总项数floatpi 0 0 a 1 0 b 1 0 c 1 0 浮点变量 a为分母 b为分子 c为b除以a 27 do 直到型循环 循环体 开始pi pi c 累加每一项sum sum 1 a a 2 0f 计算每一项的分母 强制将2 0转换成float型b b 分子变正负号c b a 计算每一项 循环体结束while fabs c 1e 6 当c的绝对值大于10的 6次方时 继续 执行循环体 否则退出pi 4 0f pi 得到最终结果 将4 0作为float类型cout pi pi endl 输出pi值cout sum sum endl 输出总项数return0 28 do 直到型循环 循环体 开始pi pi c 累加每一项sum sum 1 a a 2 0f 计算每一项的分母b b 分子变正负号c b a 计算每一项 循环体结束while fabs c 1e 6 29 运行结果pi 3 14159 sum 500000 答 会构成死循环 即无休止地执行循环体 请实验 1 将b定义为int型看看执行结果并分析为什么2 将1e 6变为1e 7或1e 4看看结果 提问 这种循环当表达式的值永远为真时 会如何 30 举例求两个整数的最小公倍数 31 分析 假定有x y且x y 设最小公倍数为z1 z一定会 x2 z kx k 1 2 3 z一定会被y整除用两个最简单的数试一下就可以找到算法 比如x 5 y 3 32 第一步z x x 55 3 0 z y不能整除第二步z z x10 3 0 z y不能整除第三步z z x15 3 0 z y能整除找到了z 15就是5和3的最小公倍数 33 程序名 5 3 cpp 作者 wuwh 编制时间 2002年9月20日 主要功能 求两个数的最小公倍数 include includeusingnamespacestd intmain 主函数 intx 0 y 0 z 0 w 0 整型变量cout x 键盘输入整数xcin y 键盘输入整数yif x y 让x表示两者中的大数 w x x y y w 倒油瓶 方法 z x 将一个大数赋给zwhile z y 0 当z不能被y整除时 就让z累加x z z x cout 最小公倍数为 z endl 输出最小公倍数return0 34 cout x 键盘输入整数xcin y 键盘输入整数yif x y 让x表示两者中的大数 w x x y y w 35 z x 将一个大数赋给z 当z不能被y整除时 就让z累加xwhile z y 0 z z x cout 最小公倍数为 z endl 36 请同学们去比较三种循环的异同之处1 for循环 计数型循环 2 当型循环 while循环 3 直到型循环 dowhile循环 上机将筛出素数的程序完成 自学与比较 37 排序问题 38 6 3冒泡排序法 39 a183249下标123456希望排成 a984321下标123456 40 冒泡排序法问题 将几个数从大到小排序并输出 41 42 43 从表中可以看出最小的一个数第一遍扫描就交换到a 6 中 如果将a 1 视为水底 a 6 视为水面 最轻的 最小的 一个数1最先浮到水面 交换到a 6 次轻的2第二遍扫描交换到a 5 再轻的3第三遍扫描交换到a 4 依此类推 有6个数 前5个数到位需5遍扫描 第6个最重的数自然落在a 1 中 因此 6个数只需5遍扫描 令扫描编数为J J n 1 n 6 冒泡排序算法分析 44 再看在每遍扫描中 相邻两数组元素的比较次数 当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 理出上述规律后 程序就不难编了 45 inti 0 j 0 p 0 a 7 整型变量memset a 0 sizeof a 数组初始化for i 1 i a i 输入整数 46 为了表述方便 定义以下3个变量 n 待排序的数的个数 这里n 6j 扫描遍数 j 1 2 n 1i 第j遍扫描待比较元素的下标 i 1 2 n j 冒泡排序算法设计 47 采用两重计数型循环 步骤1 将待排序的数据放入数组中 步骤2 置j为1 步骤3 让i从1到n j 比较a i 与a i 1 如果a i a i 1 位置不动 如果a i a i 1 位置交换 步骤4 让j j 1 只要j n返回步骤3 当j n时执行步骤5步骤5 输出排序结果 48 程序名 5 4 cpp 作者 wuwh 编制时间 2002年9月22日 主要功能 冒泡排序 include 预编译命令 include 预编译命令usingnamespacestd intmain 主函数 inti 0 j 0 p 0 a 7 整型变量memset a 0 sizeof a 整型数组初始化for i 1 i a i 用键盘输入整数赋给a i for j 1 j 5 j 冒泡排序 外层循环for i 1 i 6 j i 内层循环if a i a i 1 如果a i a i 1 p a i 让a i 与a i 1 交换a i a i 1 a i 1 p for i 1 i 6 i 输出排序结果cout a i endl 输出a i return0 49 程序名 5 4 cpp 作者 wuwh 编制时间 2002年9月22日 主要功能 冒泡排序 include 预编译命令 include 预编译命令usingnamespacestd 50 intmain inti 0 j 0 p 0