C++编程数据组织1-数组.ppt

6数据的组织与处理 一 数组 1 递推的解题思路数组的概念 定义和初始化字符数组 字符串处理筛法的解题思路数组元素的查找 线性查找与二分查找 数组排序的思路 冒泡排序法 多维数组 维以上 学习目标 2 任务一 A B C D E五人合伙夜间捕鱼 凌晨时都疲惫不堪 各自在湖边的树丛中找地方睡着了 日上三竿 A第一个醒来 他将鱼平分作五份 把多余的一条扔回湖中 拿自己的一份回家去了 B第二个醒来 也将鱼平分为五份 扔掉多余的一条 只拿走自己的一份 接着C D E依次醒来 也都按同样的办法分鱼 问五人至少合伙捕到多少条鱼 每个人醒来后看到的鱼数是多少条 3 为了解决上面这种类型的问题 需要学习和运用 递推 的思想 以及如何使用 数组 这种数据组织的形式来实现递推的过程 下面先来介绍 递推 的算法思想 4 递推是计算机数值计算中的一个重要算法 可以将复杂的运算化为若干重复的简单运算 以便充分发挥计算机长于重复处理的特点 通常 使用循环结构来实现重复处理 解决此类问题的关键是 分析简单情况 归纳总结出前后项的关系 通项公式 递推 5 任务A 求自然数n的阶乘 任务分析 令fact n 表示n的阶乘 依据后项与前项的关系 可以写出下面的 递推 公式 fact 1 1 起始条件 边界条件 fact n n fact n 1 通项公式算法实现 根据前后项的关系 显然 用循环结构来实现这种递推关系是非常自然的 请看下面的代码实现 6 includeusingnamespacestd intmain intN cout N intfact for intn 1 n N n if n 1 fact 1 elsefact n fact fact n n fact n 1 cout fact N fact endl return0 7 任务B 王小二自夸刀功不错 有人放一张饼在砧板上 问他 饼不许离开砧板 如果切 刀 你最多能将饼分成多少块 刀 刀 刀 刀 8 在编程之前要找到规律分析 令q n 表示切n刀能分成的块数 从前面的图中可以找出下列关系 q 1 1 1 2q 2 1 1 2 4q 3 1 1 2 3 7q 4 1 1 2 3 4 11由于要求最多的块数 所以每刀都是让每两条线都有交点 用归纳法不难得到 q 0 1 初始条件 边界条件 q n q n 1 n 通项公式 9 includeusingnamespacestd intmain intq for intn 0 n 100 n if n 0 q 1 elseq n q q n n q n 1 cout q 100 q endl return0 10 11 数组是计算机语言提供的组织多个数据的一种重要方式 提供了多个同类型的数据 值 在内存中连续存放的工具提供了对无限量内存单元进行高效 命名 的途径提供了在程序运行过程中动态改变 变量名称 的手段是一些重要算法思想的实现基础 数组 12 类型说明符数组名 常量表达式 TYPEarray name const expr 例 floatsheep weight 10 int a2001 1000 charstudent name 20 说明1 数组变量的名称 必须符合语言对变量命名的要求 2 用方括号将常量表达式括起 3 常量表达式定义了数组元素的个数 数组的定义 13 注意 在使用VC 6 0进行编程时 数组元素的数目 要使用常量表达式 其中不能包含变量例如intn n 5 inta n 不合法 因为n是变量 不是常量 VC 6 0 errorC2057 expectedconstantexpression 14 数组中每个元素所在的内存单元 可以通过 数组名 位置下标 来访问 赋值 读取 数组元素的位置下标从0开始计数 例如 inta 5 定义了一个含有5个整数的数组 各元素的 变量名称 分别为 a 0 a 1 a 2 a 3 a 4 是5个带下标的变量 它们的类型是相同的 该数组的效果与下面的变量定义相同 inta0 a1 a2 a3 a4 数组中元素的 名称 15 数组元素的位置关系与内存地址 aa 0 a 1 a 2 a 3 a 4 说明 a 0 元素的内存地址 即 a 0 也被称为 数组的地址 元素首地址 数组名与下标一起使用时 是一个变量 表示下标值指定位置的元素 数组名单独使用时 表示数组首地址 是一个指针常量 也称常量指针 sizeof a sizeof a 0 number 16 所有类型均可以用下面的格式来初始化数组 变量 type namearray name N v1 v2 vN 其中 v1 v2等表示常量表达式 例如 inta 5 3 5 4 1 2 charb 5 c h i n a 如果是由字符 char 组成的数组 则还可以使用 chararray name N 各种字符 例如 chara 5 china 其初始化结果为 a 0 c a 1 h a 4 a 数组变量的初始化 17 includeusingnamespacestd intmain 在定义时设定值 被称为 变量初始化 charA 10 B e i J i n g 一共只给出了7个字符for inti 0 i 10 i cout A i int A i endl 强制类型转换 将字符值转换成整数值 即其ASCII码 语法格式 dst type src value return0 char test cpp 阅读示例代码1 注意总结 18 19 includeusingnamespacestd intmain 在定义时设定值 被称为 变量初始化 charA 10 BeiJing 一共只给出了7个字符for inti 0 i 10 i cout A i int A i endl 强制类型转换 将字符值转换成整数值 即其ASCII码 语法格式 dst type src value return0 char test 2 cpp 阅读示例代码2 注意总结 20 21 includeusingnamespacestd intmain 在定义时设定值 被称为 变量初始化 charA BeiJing 一共给出了7个字符intB 1 2 3 4 5 一共给出了5个整数for inti 0 i 10 i cout A i int A i cout B i endl return0 char test 3 cpp 阅读示例代码3 注意总结 22 23 includeusingnamespacestd intmain 在定义时设定值 被称为 变量初始化 charA1 BeiJing 一共给出了7个字符intB1 1 2 3 4 5 一共给出了5个整数cout sizeof A1 sizeof A1 endl cout sizeof B1 sizeof B1 endl charA2 10 BeiJing 一共给出了7个字符intB2 10 1 2 3 4 5 一共给出了5个整数cout sizeof A2 sizeof A2 endl cout sizeof B2 sizeof B2 endl return0 char test 4 cpp 阅读示例代码4 猜猜输出 24 A1 25 总结说明 数组变量在 初始化 时 即至少提供了一个初始值 如果提供的初始值数目少于数组元素的个数 则依下标大小顺序 从下标为0的元素开始 逐一设定初始值 缺少初始值的数组元素 将被编译器自动设置成0 以字符串常量方式对字符数组进行 初始化 时 也同样遵循上述规则 如果初始化时不设定数组大小 元素数目 则编译器自动根据初始值的数目来设定数组的大小 如果是字符数组 则编译器设定的数组大小是 字符串常量长度 1 即不遵循上述规则 26 数组变量的赋值 27 28 这是一个伪命题 数组变量的赋值 29 所有类型的数组变量均不可以直接赋值 数组变量的赋值 30 inta 5 charb 5 a 1 2 3 4 5 b CHINA 数组变量的赋值 31 单独一个一个进行赋值inta 5 a 0 1 a 3 23 使用for语句 连续赋值chara 5 for inti 0 i 5 i a i A i 数组中各元素的赋值 32 使用一些特殊的库函数 使用memset函数 格式为memset 起始地址 初始值 空间大小 举例 memset sheep 0 sizeof sheep 将名为sheep的数组中的全部元素均初始化为0 调用此库函数需要加入头文件 使用字符串处理函数 例如 strcpy 字符数组名 字符串常量或变量 举例 charschool name 20 strcpy school name Tsinghua 数组中各元素的赋值 33 includeusingnamespacestd intmain charh 123456 h abcdef cout h endl return0 程序会出什么问题 Line6 error ISOC forbidsassignmentofarrays 34 includeusingnamespacestd intmain charh 123456 h abc ef cout h endl return0 strcpy h abcdef 35 通过cin操作 对字符数组变量进行 赋值 数组中各元素的赋值 includeusingnamespacestd intmain charh 123456789 cin h 设键入的是abcdefcout h endl 则程序输出abcdefreturn0 如果键入的是123456789012345则程序会输出什么 36 如果是字符数组 变量 则cout会将数组的所有元素一齐输出出来 字符之间无空格 如果是其他类型的元素组成的数组 变量 则cout只会输出该数组变量的地址 也即数组第一个元素所在内存单元的地址 cout是如何根据数据类型来决定输出方式的呢 这个问题 将在下学期 面向对象程序设计 中予以解答 数组变量的 cout输出 37 includeusingnamespacestd intmain charh tsinghua h 0 a h 1 b h 2 4 h 3 7 h 4 c cout h endl inta 1 2 3 4 5 a 0 79 a 1 88 a 2 34 a 3 64 a 4 99 cout a endl cout 38 上述结果说明 数组a的第一个元素的地址 与a的值相等 即cout a 与cout 等效 39 字符数组 字符串 的应用示例 老张开车去东北 撞了 肇事司机耍流氓 跑了 目击者对交警说 肇事汽车的号码为4位完全平方数 且数字从左到右一个比一个大 请帮交警算出肇事车的号码 40 include includeusingnamespacestd voidfind it intmain find it return0 41 思路I 令n为车号n为4位数n i i i 32 33 99 31 31 961 对i进行枚举 得不同的n 对每个n 检查n的各位 从高位到低位 是否一个比一个大 即 低位的数值最大 n n3n2n1n0n3 n2 n1 n0 42 voidfind it for inti 32 i 100 i intn i i if n 1000 n 100 10 四位数的千位数字n3 n 1000 百位数字n2 n 100 10 十位数字n1 n 10 10 个位数字n0 n 10 43 现在 车号升级啦 变成了五位 闯祸的车号居然还是一个完全平方数 依然还是从高位到低位一个比一个大 越来越大 这时 程序该怎么编 或修改 呢 44 思路II 还是以四位数的车号为例说明 令n为车号n为4位数 n i ii 32 33 99 31 31 961 枚举i到n 查n从高位到低位 是否一个比一个小将n分解为4个数字字符 char itoa intvalue char string intradix value 待转换整数string 存放转换结果的字符串指针radix 2 16进制整数 45 n i ii33n1089itoa n buf 10 buf1089 001234 46 include includeusingnamespacestd intmain charbuf 5 定义数组inti 0 n 0 定义整数变量 47 for i 32 i 100 i 计数循环n i i 构造4位数nitoa n buf 10 把10进制数n转换为字符串放入buf数组if buf 0 buf 1 能把程序改得更简洁清晰吗 48 for i 32 i buf j 1 break 若n符合要求 则FOR循环会全部执行完 if j 3 cout 肇事汽车号码为 n endl for return0 修改后的程序 是不是更简洁清晰了 49 for i 32 i buf j 1 break 若n符合要求 则FOR循环会全部执行完 if j 3 cout 肇事汽车号码为 n endl for return0 想一想 如何把程序改成能解决五位数 或更多 的车号呢 50 for i 32 i buf j 1 break 若n符合要求 则FOR循环会全部执行完 if j 3 cout 肇事汽车号码为 n endl for return0 这些地方需要修改 51 52 任务一的解题思路 假定A B C D E五人的编号分别为1 2 3 4 5 整数数组fish k 表示第k个人所看到的鱼数 fish 1 表示A所看到的鱼数 fish 2 表示B所看到的鱼数 fish 1 A所看到的鱼数 合伙捕到鱼的总数fish 2 fish 1 1 4 5B所看到的鱼数fish 3 fish 2 1 4 5C所看到的鱼数fish 4 fish 3 1 4 5D所看到的鱼数fish 5 fish 4 1 4 5E所看到的鱼数 53 写成一般式fish i fish i 1 1 4 5i 2 3 5 这个公式可用于已知A看到的鱼数去推算B看到的 再推算C看到的 现在要求的是A看到的 能否倒过来 先知E看到的再反推D看到的 直到A看到的 为此将上式改写为 fish i 1 fish i 5 4 1i 5 4 2 54 分析上式 当i 5时 fish i 表示E醒来所看到的鱼数 该数应满足被 整除后余 所以初值设为 2 当i 5时 fish i 1 表示D醒来所看到的鱼数 这个数要满足fish 4 fish 5 5 4 1显然 fish 4 必须是整数 所以fish 5 必须满足fish 5 4 0这个结论同样可以用至fish 3 fish 2 和fish 1 55 3 按题意要求5人合伙捕到的最少鱼数 可以从小往大枚举 即 可以先让E所看到的鱼数最少为6条 即fish 5 初始化为6来试 之后每次增加5再试 直至递推到fish 1 均为整数 根据上述思路 我们可以构思如下的程序框图 56 fish 5 fish 5 5 for i 4 i 1 i fish i 1 4 0truefalesbreak fish i 1 fish i 1 5 4 dowhile i 1 定义数组并初始化 输出计算结果 57 上图的说明 该图可分为三部分 1 是说明部分 包含定义数组fish 6 并初始化为1和定义循环控制变量i 并初始化为0 2 是do while直到型循环 其循环体又含两块 2 1 是枚举过程中的fish 5 的初值设置 一开始fish 5 1 5 以后每次增5 2 2 是一个for循环 i的初值为4 终值为1 步长为 1 该循环的循环体是一个分支语句 如果fish i 1 不能被4整除 则跳出for循环 使用break语句 否则 从fish i 1 算出fish i 58 当break语句让程序退出循环时 意味着某人看到的鱼数不是整数 当然不是所求 必须令fish 5 加5后再试 即重新进入直到型循环dowhile的循环体 当正常退出for循环时 一定是控制变量i从初值4 一步一步执行到终值1 每一步的鱼数均为整数 最后i 0 表示计算完毕 且也达到了退出直到型循环的条件 3 输出计算结果 59 includeusingnamespacestd intmain intfish 6 1 1 1 1 1 1 记录每人醒来后看到的鱼数inti 0 do fish 5 fish 5 5 让E看到的鱼数增5 for i 4 i 1 i if fish i 1 4 0 break 跳出for循环elsefish i fish i 1 5 4 1 计算第i人看到的鱼数 while i 1 当i 1继续做do循环 输出计算结果for i 1 i 5 i cout fish i endl return0 60 程序名 9 cpp 五人合伙捕鱼 作者 wuwh 编制时间 2002年10月2日 主要功能 递推算法的实现 include 预编译命令usingnamespacestd intmain 主函数 intfish 6 1 1 1 1 1 1 整型数组 记录每人 醒来后看到的鱼数inti 0 61 do fish 5 fish 5 5 for i 4 i 1 i i 1 if fish i 1 4 0 break 跳出for循环elsefish i fish i 1 5 4 1 while i 1 62 初始化E 1E E 5breakyes递EE 4 0D E 5 4 1no推yesDD 4 0方C D 5 4 1noyes向CC 4 0B C 5 4 1noyesBB 4 0A B 5 4 1noA 63 31212496199615961276 输出结果 64 includeusingnamespacestd intmain intfisher 6 五个人看到的鱼数for intnum 6 num 5 对各种可能性进行枚举intn for n 5 n 1 n 对五个人看到的鱼数进行递推if n 5 fisher n num else fisher n 1 fisher n 1 5 4 if fisher n 1 4 0 break 鱼数num不满足条件 要尝试下一个num 停止递推else 下式所得fisher n 必然满足fisher n 5 1fisher n fisher n 1 5 4 1 if n 0 说明鱼数num满足所有人的条件break 找到最小鱼数了 停止枚举 输出各个人看到的鱼数for intn 1 n 5 n cout fisher n fisher n endl return0 第 种算法实现 65 includeusingnamespacestd intmain intfisher 6 五个人看到的鱼数for intnum 6 num 5 对各种可能性进行枚举intn for n 1 n 5 n 对五个人看到的鱼数进行递推if n 1 fisher n num else 下式所得fisher n 必然是整数fisher n fisher n 1 1 5 4 if fisher n 5 1 break 鱼数num不满足条件 要尝试下一个num 停止递推 if n 6 说明鱼数num满足所有人的条件break 找到最小鱼数了 停止枚举 输出各个人看到的鱼数for intn 1 n 5 n cout fisher n fisher n endl return0 第 种算法实现 66 includeusingnamespacestd boolIsOK intnum intfisher 6 for intn 1 n 5 n 对五个人看到的鱼数进行递推if n 1 fisher n num else 下式所得fisher n 必然是整数fisher n fisher n 1 1 5 4 if fisher n 5 1 returnfalse 鱼数num不满足条件 停止递推 returntrue intmain intfisher 6 五个人看到的鱼数for intnum 6 num 5 对各种可能性进行枚举if IsOK num fisher break found 输出各个人看到的鱼数for intn 1 n 5 n cout fisher n fisher n endl return0 第 种算法实现 67 任务二 求100以内的所有素数 6 2筛法 68 什么是 筛法 想象将100个数看作沙子和小石头子 让小石头子权称素数 让沙子当作非素数 弄一个筛子 只要将沙子筛走 剩下的就是素数了 非素数一定是2 3 4 的倍数 使用数组 让下标就是100以内的数 让数组元素的值作为筛去与否的标志 比如筛去以后让元素值为1 69 方法的依据 1至100这些自然数可以分为三类 单位数 仅有一个数1 素数 是这样一个数 它大于1 且只有1和它自身这样两个正因数 合数 除了1和自身以外 还有其他正因数 1不是素数 除1以外的自然数 当然只有素数与合数 筛法实际上是筛去合数 留下素数 70 为了提高筛法效率 注意到 令n为合数 这里是100 c为n的最小正因数 据初等数论 只要找到c就可以确认n为合数 将其筛去 一定注意 要进行 筛 的1 100的数字是与数组prime 101 的下标相对应的 而每个数组元素的取值只有2个 是0或1 分别代表 标志 与下标相对应的数字是素数或不是素数 71 0010101010101012345678910111213141516 0010101110101112345678910111213141516 寻找2的倍数寻找3的倍数寻找4的倍数 72 程序框图如下 请分析左边程序的结构从而了解算法的设计思路为程序代码的实现创造条件 73 上述框图很清晰地描述了筛法的思路 STEP1 将prime数组清零 使用了一个计数型的循环语句 STEP2 将正因数d初始化为d 2 STEP3 循环筛数 这里用了一个dowhile语句 也称为 直到型循环 STEP4 输出 筛 过后的数组 即剩下的所有素数 这里使用了标识数组 74 补充说明 在do while语句中 检测prime k 是否为零 若是零 则说明k是质数 这是因为sqrt k k 所以 当检测到k时 2 sqrt k 必然已全部测试过了 如果在 sqrt k 中有整除k的数 则prim