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

1、1,6 数据组织与处理(1) 数组,2,数组的概念、定义和初始化 筛法的解题思路 冒泡排序的思路 二维数组,学 习 目 标,3,数组：定义、初始化、操作与应用 筛法：do_while循环、 while循环、求质数 排序：冒泡排序的算法 二维数组：定义、初始化、应用,内 容 要 点,4,6.1 数 组,5,中秋佳节，有贵客来到草原，主人要从羊群中选一只肥羊宴请宾客，当然要选最重者。这样就要记录每只羊的重量，如果有成千上万只羊，不可能用一般变量来记录。可以用带有下标的变量，也就是这里要讲的数组。,问题：哪只羊最重？,我们先看例子：用键盘输入10只羊的重量存放到一个名为sheep的数组中,6,/*

2、/* 程序名：6_1.cpp（数组示例） * /* 作 者：wuwh * /* 编制时间：2002年9月20日 * /* 主要功能：找出最重的羊 * /* #include / 预编译命令 #include / 预编译命令 using namespace std; int main()/ 主函数 float sheep10;/ 数组，有10个浮点类型元素， / 用于存10只羊每一只的重量 memset ( sheep, 0 , sizeof (sheep) );/ 初始化数组元素为0 float bigsheep=0.0;/ 浮点类型变量，存放最肥羊的重量 int i=0, bigsheepN

3、o=0;/ 整型变量，i 用于计数循环， / bigsheepNo用于记录最肥羊的号,7,for ( i=0; i sheepi; / 输入第i只羊的重量 if ( bigsheep sheepi )/ 如果第i只羊比当前最肥羊大 bigsheep = sheepi;/ 让第i只羊为当前最肥羊 bigsheepNo = i; / 纪录第i只羊的编号 / 循环结束 / 输出最肥羊的重量 cout 最肥羊的重量为bigsheependl; / 输出该羊的编号 cout 最肥羊的编号为bigsheepNoendl; return 0; ,8,程 序 框 图,9,类型说明符数组名 常量表达式 例：fl

4、oat sheep10; int a20011000; 说明 1. 数组名的第一个字符应为英文字母； 2. 用方括号将常量表达式括起； 3. 常量表达式定义了数组元素的个数；,数组的定义,10,4. 数组下标从 0 开始。如果定义 5 个元素，是从第 0 个元素至第 4 个元素； 例如int a5 定义了5个数组元素如下： a0, a1, a2, a3, a4 这是 5 个带下标的变量，这5个变量的类型是相同的,11,5.常量表达式中不允许包含变量 例如int n; n = 5; int an;不合法！ 因为 n 是变量，不是常量,12,#define N 100 /宏定义，N为常数100 #

5、define M 200 /宏定义，M为常数200 int a N ; /定义有100个元素的整型数组a long b N+M ; /定义有300个元素的长整型数组b double g M+6 ; /定义有206个元素的双精度实 /型数组g 以上定义是合法的 #define N 100 为命令行，不是语句，程序在 编译时遇到N 就用100替换。在命令行中定义的符号名N，也被称为符号常量N。,13,第一种方法 直接在定义时初始化 例如 int a5 = 3, 5, 4, 1, 2 ; a0 = 3; a1 = 5; a2 = 4; a3 = 1; a4 = 2;,数组初始化,14,第二种方法 使

6、用 memset 函数 格式为 memset(数组名, 初始化值, sizeof(数组名) 举例： memset(sheep, 0, sizeof( sheep ); 含义是将名为 sheep 的数组中的全部元素均初始化为 0 。更深一层是说让系统为 sheep10 所分配的内存单元从 sheep0 为标志的地址单元到该数组的全部地址单元都赋以 0 。调用此库函数需要加入头文件 。,15,1.#include using namespace std; int main() int a4;/ 声明项 cout a0 endl; cout a1 endl; cout a2 endl; cout a

7、3 endl; return 0; 2.其他不变，改变声明项为 int a4 = 0, 1, 2, 3 ;,请自己上机做7个实验,16,3.其他不变，改变声明项为 int a4 = 3, 8 ; 4.其他不变，改变声明项为 int a4 = 2, 4, 6, 8, 10 ; 5.其他不变，改变声明项为 int a4 = 2, 4, 6, d ; 6.其他不变，改变声明项为 int d; int a4 = 2, 4, 6, d ; 7.其他不变，改变声明项为 int n=4; int an = 0, 1, 2, 3 ;,17,讨 论 问 题 使用筛法求100以内的所有素数,18,6.2 筛 法,

8、19,思路 想象将100个数看作沙子和小石头子，让小石头子权称素数；让沙子当作非素数。弄一个筛子，只要将沙子筛走，剩下的就是素数了。 非素数一定是 2、3、4 的倍数。 使用数组，让下标就是100以内的数，让数组元素的值作为筛去与否的标志。比如筛去以后让元素值为1。,20,方法的依据： 1至100这些自然数可以分为三类： 单位数：仅有一个数1。 素数： 是这样一个数，它大于1，且只有1 和它自身这样两个正因数。 合数： 除了1和自身以外，还有其他正因数。,1不是素数，除1以外的自然数，当然只有素数与合数。筛法实际上是筛去合数，留下素数。,21,为了提高筛法效率，注意到： 令 n 为合数（这里是

9、100）， c 为 n 的最小正因数， 据初等数论，只要找到 c 就可以确认 n 为合数，将其筛去。,一定注意：要进行“筛”的1100的数字是与数组prime101的下标相对应的，而每个数组元素的取值只有2个：是0或1，分别代表（标志）与下标相对应的数字是素数或不是素数。,22,程序框图如下：,请同学来分析左边程序的结构 从而了解算法的设计思路 为程序代码的实现创造条件,23,上述框图很清晰地描述了筛法的思路： 1.第一块是一个计数型的循环语句，功能是将prime数组清零。 primec = 0;c = 2, 3, ,100 2.第二块是正因数d 初始化为 d = 2。 3.第三块是循环筛数。

10、这里用了一个 do while 语句，属于一种直到型循环,24,举 例 求 的近似值,25,例.求的近似值 用变量pi表示的值。 令表示括号中的每个项 当最后一项的绝对值小于等于 时，忽略掉以后的项,26,/* /* 程 序 名：5_2.cpp * /* 作 者：wuwh * /* 编制时间：2002年9月20日 * /* 主要功能：求pi的近似值 * /* #include #include using namespace std; int main() / 主函数 int sum=0;/ 整型变量，总项数 float pi=0.0, a=1.0, b=1.0, c=1.0; / 浮点变量，

11、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=”

12、sum endl;/ 输出总项数 return 0; ,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 看看结果,提

13、问：这种循环当表达式的值永远为真时， 会如何？,30,举 例 求两个整数的最小公倍数,31,分析：假定有x ,y 且 x y，设最小公倍数为 z 1. z 一定会 = x 2. z = k x , k= 1, 2, 3. z 一定会被 y 整除 用两个最简单的数试一下就可以找到算法. 比如 x=5, y=3.,32,第一步 z = x / x=5 5 % 3 != 0 / z % y 不能整除 第二步 z = z + x 10 % 3 != 0 / z % y 不能整除 第三步 z = z + x 15 % 3 = 0 / z % y 能整除 找到了 z ，15就是5和3的最小公倍数,33,/

14、* /* 程 序 名：5_3.cpp * /* 作 者：wuwh * /* 编制时间：2002年9月20日 * /* 主要功能：求两个数的最小公倍数 * /* #include #include using namespace std; int main()/ 主函数 int x=0, y=0, z=0, w=0; / 整型变量 cout x; / 键盘输入整数 x cin y; / 键盘输入整数 y if ( x y )/ 让 x 表示两者中的大数 w = x; x = y; y = w; / “倒油瓶”方法 z = x;/ 将一个大数赋给 z while ( z % y != 0 )/ 当

15、z不能被y整除时，就让z累加x z = z + x; cout “最小公倍数为” z endl;/ 输出最小公倍数 return 0; ,34,cout x; / 键盘输入整数 x cin y; / 键盘输入整数 y if ( x y )/ 让 x 表示两者中的 大数 w = x; x = y; y = w; ,35,z = x;/ 将一个大数赋给 z / 当z不能被y整除时，就让z累加x while ( z % y != 0 ) z = z + x; cout 最小公倍数为 z endl;,36,请同学们去比较三种循环的异同之处 1. for 循环（计数型循环） 2. 当型循环（while循

16、环） 3. 直到型循环（do while 循环） 上机将筛出素数的程序完成,自学与比较,37,排 序 问 题,38,6.3 冒泡排序法,39,a 1 8 3 2 4 9 下标 1 2 3 4 5 6 希望排成： a 9 8 4 3 2 1 下标 1 2 3 4 5 6,40,冒泡排序法 问题： 将几个数从大到小排序并输出,41,42,43,从表中可以看出最小的一个数第一遍扫描就交换到a6中。如果将a1视为水底，a6视为水面： 最轻的(最小的)一个数 1 最先浮到水面，交换到a6; 次轻的 2 第二遍扫描交换到a5； 再轻的 3 第三遍扫描交换到a4； 依此类推，有6个数，前5个数到位需5遍扫描

17、，第6个最重的数自然落在a1中。因此，6个数只需5遍扫描，令 扫描编数为 J，J=n-1, n=6。,冒泡排序算法分析：,44,再看在每遍扫描中，相邻两数组元素的比较次数。 当j=1时，i=1,2,n-j。n=6时，比较5次之后a6中有一个最小数到达，这时a6不必再参与比较了。 因此在第二遍搜索时，j=2, i=1,2,n-j，即i=1,2,3,4。比较4次之后次小的一个数到达了a5。这时a5不必再参与比较了。 因此，j=3时，i=1,2,3； j=4时，i=1,2； j=5时，i=1. 理出上述规律后，程序就不难编了,45,int i = 0, j = 0, p = 0, a 7 ;/ 整型

18、变量 memset( a, 0, sizeof(a) ); / 数组初始化 for ( i = 1; i ai; / 输入整数 ,46,为了表述方便，定义以下3个变量： n 待排序的数的个数，这里 n=6 j 扫描遍数，j=1,2,n-1 i 第j遍扫描待比较元素的下标，i=1,2,n-j,冒泡排序算法设计：,47,采用两重计数型循环： 步骤1：将待排序的数据放入数组中； 步骤2：置j为1； 步骤3：让 i 从1到n-j，比较ai与ai+1， 如果 ai = ai+1，位置不动； 如果 ai ai+1 ，位置交换， 步骤4：让 j = j+1；只要 j != n 返回步骤3 ,当j=n 时执行

19、步骤5 步骤5：输出排序结果,48,/* /* 程 序 名：5_4.cpp * /* 作 者：wuwh * /* 编制时间：2002年9月22日 * /* 主要功能：冒泡排序 * /* #include / 预编译命令 #include / 预编译命令 using namespace std; int main()/ 主函数 int i=0, j=0, p=0, a7;/ 整型变量 memset( a, 0, sizeof(a) );/ 整型数组初始化 for (i=1; i ai;/ 用键盘输入整数赋给ai for ( j=1; j=5; j+)/ 冒泡排序，外层循环 for ( i=1; i=6-j; i+ )/ 内层循环 if ( ai ai+1 )/ 如果 ai ai+1 p = ai;/