Presentation is loading. Please wait.

Presentation is loading. Please wait.

专题研讨课二: 数组在解决复杂问题中的作用

Similar presentations


Presentation on theme: "专题研讨课二: 数组在解决复杂问题中的作用"— Presentation transcript:

1 专题研讨课二: 数组在解决复杂问题中的作用
专题研讨课二: 数组在解决复杂问题中的作用

2 Part I 要点提示

3 一维数组 类型名 数组名[数组长度] int a[5],b[10]; float x[7]; double y[20]; 定义:
类型名 数组名[数组长度] 每个元素的类型 数组变量的名称,合法的标识符 数组的大小,整型常量表达式 为什么数组长度不能是变量? int N=10; int a[N]; int a[5],b[10]; float x[7]; double y[20];

4 一维数组 初始化:类型名 数组名[数组长度] = {初值表};
初始化:类型名 数组名[数组长度] = {初值表}; int a[10] = { 0,1, 2, 3, 4, 5, 6, 7, 8, 9 }; int a[ ] = { 0, 1, 2, 3, 4, 5, 6, 7, 9, 9 }; 部分初始化: int a[10] = { 0, 1, 2, 3, 4 }; 没有初始化的元素值是什么?

5 一维数组 引用:数组名[下标]; 数组变量的名称 整型表达式 例如:int a[10], i; 那么:a[ i ] 引用数组a的第i个元素

6 一维数组 int a[10]; 存储方式: 连续存放于内存(RAM) 数组名代表其首元素的地址 元素a[ i ] 的地址记为:a + i
2 3 4 5 6 7 8 9 a 内存 int a[10]; 元素a[ i ] 的地址记为:a + i a[ i ] 的实际地址是什么?

7 对于 <0 或者 >N-1 的k, a[k]是哪个元素?
一维数组 存储方式: 连续存放于内存(RAM) 数组名代表其首元素的地址 1 2 3 4 5 6 7 8 9 a 内存 对于长度为N的数组,末尾元素为a[N-1] 对于 <0 或者 >N-1 的k, a[k]是哪个元素? 修改a[k]有何后果?

8 可执行程序 指令:运算指令、控制指令 数据:常量、变量 由编译器根据源程序编译链接生成 处理数据时,必须要知道其大小 简单变量类型
数据变量类型和长度 自定义结构先定义

9 数组越界 对于<0的k:改变a[k]可能导致数组前面的数据/代码异常
内存 对于<0的k:改变a[k]可能导致数组前面的数据/代码异常 对于>=N的k:改变a[k]可能导致数组后面的数据/代码异常 数组a 长度N 试图修改系统相关的数据和代码 将会被阻止执行

10 二维数组 类型名 数组名[行长][列长] int a[2][4]; float x[5][10]; double y[1][1]; 定义:
类型名 数组名[行长][列长] 每个元素的类型 数组变量的名称,合法的标识符 数组的大小,整型常量表达式 int a[2][4]; float x[5][10]; double y[1][1];

11 二维数组 部分初始化: 初始化: int a[3][2] = { {1}, {3, 4} }; 初始化了两行 第一行只初始化部分元素
int b[3][2] = { , {1, ,3 }}; 那些被初始化了?

12 二维数组 存储方式:逐行连续存放于RAM中 int a[3][2]; 二维数组的元素在内存中按行方式存放 a[0][0] a[0][1]
3 行 2 列, 6 个元素 表示1个3行2列的矩阵 二维数组的元素在内存中按行方式存放 a[0][0] a[0][1] a[1][0] a[1][1] a[2][0] a[2][1] 第0行a[0] 第1行a[1] 第2行a[2] a[0][0] a[0][1] a[1][0] a[1][1] a[2][0] a[2][1]

13 数组应用 —— 存储数据 大量数据 … 相同类型 循环遍历 文字信息、数据统计、图像视频 所有元素具有相同的类型/结构 处理方式相同
一般利用循环语句进行处理

14 数组应用 数值计算 向量运算 矩阵运算 多元方程 算法设计 制作查找表 简化程序结构

15 数组使用 设计函数处理数组 数组作为函数参数 void ReverseIntArray( int array[], int n ) {
int i, k, tmp; for (i = 0, k=n-1; i < k; i++, k--) { tmp = array[i]; array[i] = array[k]; array[k] = tmp; }

16 形参数组array(的地址值)等于实参数组a(的地址值),于是它们指向同一块内存。因此,对array的操作等价于对a的操作。
1000 1000 1002 1004 1006 1008 1010 1012 1014 1494 1496 1498 1 2 3 4 5 . a [0] a [1] a [2] a [3] a [4] a [5] a [6] a [7] a [247] a [248] a [249] array[0] array[1] array[2] array[3] array[4] array[5] array[6] array[7] array[247] array[248] array[249] array 1000 假设a数组的首地址为1000,当执行 ReverseIntArray(a, 5) 形参数组array(的地址值)等于实参数组a(的地址值),于是它们指向同一块内存。因此,对array的操作等价于对a的操作。

17 Part II 应用举例

18 1:数组排序 输入n个数,将它们从小到大排序后输出。 3 5 2 8 1 选择法排序:选择最小的元素,交换到前列 3 5 2 8 1
(1) (2) (3) (4)

19 一般地, (1) a[0] ~ a[n-1] 中找最小数,与 a[0] 交换
(k) ……(第k轮) (n-k个数中最小的) (n-1) a[n-2],a[n-1]中最小数,与 a[n-2] 交换 (2个数中最小的)

20 排序主程序 SortArray void SortArray(int array[ ], int n) { int k, iMin;
for (k = 0; k < n-1; k++) { /* 找到第k次最小值的下标 */ iMin = FindMinIndex( array, k, n ); if ( k != iMin ) /*交换*/ SwapArrayElements(array, iMin, k); }

21 找最小值 FindMinIndex int FindMin(int a[ ], int start, int n) { int k, m;
m = start; /*初始化为起始元素的下标*/ for ( k = start+1; k < n; k++ ) if ( a[k] < a[m] ) m = k; /*找到更小的,更新下标*/ return m; }

22 交换 SwapArrayElements void SwapArrayElements(int a[ ], int i, int j) {
int tmp; tmp = a [i]; a [i] = a [j]; a [j] = tmp; }

23 思考 如何将数组从大到小进行排序? 想想排序的其他方法?

24 2:数组查找 在一个整数数组a[ ]中,查找给定的整数x int Find( int a[ ], int n, int x)
返回整数x在数组a中的下标。 如不存在,则返回-1。 n是数组a中元素的个数

25 Naïve方法 逐个查询 int Find( int a[ ], int n, int x ) { int i;
for( i=0; i<n; i++ ) if( a[i]==x ) return i; return -1; }

26 二分查找 假设数组a具有从小到大的顺序 思想:将数据一分为二,在包含x的1/2数组中继续查找。直至找到或查找范围为空 s t k
s、t是数组的首尾下标(不包括t) k k为中分下标 s t a[k] < x t s a[k] > x a[k]==x return k

27 二分查找 int Find( int a[ ], int n, int x ) { int s = 0, t = n, k; if( n<1 || x<a[0] || x>a[n-1] ) return -1; while( s < t ) { k = (s + t) / 2; if( a[k]<x ) s = k+1; else if ( a[k]>x ) t = k; else return k; } s t k s t t s

28 二分查找 利用了数组结构的优点 连续存放 随机存取

29 3:数组循环移位 将一个长度为n的数组A[ ],向右循环m个位置: A[0] A[1] A[2] …….. … A[n-2] A[n-1]
变成 A[n-m] …A[n-1] A[0] A[1]…A[n-m-1] (1)不能使用额外的数组 (2)不妨假设0<m<n,否则取m=m%n

30 Naïve方法 重复执行m次,每次将数组向右移动1位 总的移位次数为m*n void shift( int A[], int n ) {
int i, e = A[n-1]; for( i=n-1; i>0; i-- ) A[i] = A[i-1]; A[0] = e; } void main() { for( i=0; i<m; i++ ) shift(A,n); } 总的移位次数为m*n

31 翻转方法 A[0] A[1] A[2] A[3] … A[n-2] A[n-1] 整体翻转 A[n-1]… A[n-m] A[n-m-1]…A[1] A[0] 分段翻转 A[n-m] …A[n-1] A[0] A[1] … A[n-m-1]

32 翻转方法 void reverse(int A[ ], int s, int t) { int temp; while (s<t ) { temp = A[s]; A[s++] = A[t]; A[t--] = temp; } void main() { reverse(A, 0, n-1 ); reverse(A, 0, m-1); reverse(A, m, n-1 ); } 总的移位次数为2*n

33 移位次数比较: m*n VS 2*n 当m>2时,翻转法的效率更高 思考更好的方法?(移位次数为n) 处理大数组(大数据)时,审慎考虑算法效率

34 4:扑克牌计算24点 4张扑克牌,各代表1~13之间的1个整数 采用+,-,*,/ 四种算术运算,得到24。
(利用数组建立查找表,简化代码) 4张扑克牌,各代表1~13之间的1个整数 采用+,-,*,/ 四种算术运算,得到24。 如能,输出算式;如不能,输出NO。 可以添加括号,改变运算优先级

35 解决思路 a P b Q c R d 考虑4个整数算式的各种组合情况 操作数 a,b,c,d 可以任意排列
24种情况 运算符P,Q,R都可以4种运算之一 64种情况

36 解决思路 a P b Q c R d 考虑4个整数算式的各种组合情况 P,Q,R的运算顺序有6种情况
PQR,PRQ,QPR,QRP,RPQ, RQP PRQ和RPQ的结果是一样的 (a P b)Q(c R d) 所以只需要考虑5种: PQR,PRQ,QPR,QRP,RQP

37 解决思路 逐个情况,分别处理  建立查找表,循环处理  分析各种情况, 将参数保存在数组中 操作数、运算符

38 程序设计 运算符数组:char op[64][3]; char opc[] = “+-*/”; n=0;
for( i=0; i<4; i++) for( j=0; j<4; j++) for(k=0; k<4; k++) { op[n][0]=opc[ i ]; op[n][1]=opc[ j ]; op[n][2]=opc[ k]; n++; }

39 程序设计 操作数数组:int abcd[24][4]; /* 4张牌的点数保存在 int a[4] 中*/ n=0;
for( i=0; i<4; i++) for( j=0; j<4; j++) for( k=0; k<4; k++) for(m=0; m<4; m++) { if( i==j || i==k || i==m || j==k || j==m || k==m ) continue; abcd[n][0] = a[i]; abcd[n][1] = a[j]; abcd[n][2] = a[k]; abcd[n][3] = a[m]; n++; }

40 程序设计 运算测试 found = 0; for( n=0; n<24 && !found; n++ )
for( m=0; m<64 && !found; m++ ) { /*提取运算符和操作数*/ a = abcd[n][0]; b = abcd[n][1]; c = abcd[n][2]; d = abcd[n][3]; P = op[m][0]; Q = op[m][1]; R = op[m][2]; if( found = test(a,b,c,d,P,Q,R) ) break; }

41 测试函数 int test( int a, int b, int c, int d, char P, char Q, char R) {
/* PQR: ((a P b) Q c) R d */ if( calc( calc( calc(a,P,b), Q, c), R, d)==24 ) { printf(…….); return 1; } /* PRQ: (a P b) Q (c R d) */ if( calc( calc(a, P, b), Q, calc(c, R, d) )==24 ) { printf(…….); return 1; } 【其他情况雷同处理,略…】 }

42 calc函数 double calc( double a, char op, double b) {
if( op==‘+’ ) return a+b; if( op==‘-’ ) return a-b; if( op==‘*’ ) return a*b; if( op==‘/’ && b!=0 ) return a/b; else return 1.0E10; }

43 4:扑克牌计算24点 程序的运算量是多少? 如何找出所有、不同的算式? 扩展:N张扑克牌 N-1个运算符 得到结果M

44 The End!

45 5:扩展的扑克牌问题 难度转移 操作数排列情况急剧增加:N! 运算符情况急剧增加:4^(N-1)
存储空间急剧增长 测试函数的处理的优先级情况急剧增加:(N-1)! 无法采用固化的分支程序处理

46 N元算式的优先级分析与计算 a0 P1 a2 P2 … Pn an 每执行一个运算之后,算式减少一元 适合采用递归方法进行测试和计算

47 N元算式的递归计算 int test( double a[], char p[], int N, int M ) { int i; double s, a1[54], p1[54]; if( N==2 ) { if( (s = calc(a[0], p[0], a[1]) )==M ) printf(…); return s==M; } for( i=0; i<N-1; i++ ) { s = calc(a[i], p[i], a[i+1]); 构造对应的N-1元算式,并存储到数组a1[ ]和p1[ ]中 if ( test( a1, p1, N-1, M ) ) return 1; return 0;

48 5:扩展的扑克牌问题 参考上述的递归的test函数,编写程序解决扩展的扑克牌问题。 假设N<10 打印算式

49 6:螺旋方阵 如下图,已知N*N(3<=N<=25)的方阵,从左上角第1个格子开始,按顺时针螺旋方向将1、2、3……的数据布满整个方阵。

50 基本思路: 螺旋方阵数据的产生有一定规律。从外到内,可以圈为单位生成数据。比如N=4时,刚好就是两圈数据: 第1圈: 1 2 3 4
第2圈: 13 14 16 15 基本规律是:当N为偶数时,需要N/2圈;当N为奇数时,也需要N/2圈,但是最后还生成一个数据就是N*N。 实现要点:使用二维数组存储螺旋方格子中的数据;二维数组所有数据的生成,可应用循环,根据所需要的圈数,从左右下左上,四个方向来产生数据。

51 [main] #define MAX_SCREW 20 /*螺旋最大边长*/ int InputScrewArray();
void GenScrewArray(int ScrewArray[MAX_SCREW][MAX_SCREW], n); void PrintScrewArray(ScrewArray[MAX_SCREW][MAX_SCREW], n); main() { int ScrewArray[MAX_SCREW][MAX_SCREW];/*二维螺旋矩阵*/ int n;/*实际边长*/ n = InputScrewArray(); /*输入螺旋边长*/ GenScrewArray(ScrewArray, n); /*生成螺旋矩阵*/ PrintScrewArray(ScrewArray, n);/*打印螺旋矩阵*/

52 [GenScrewArray] void GenScrewArray(int ScrewArray[MAX_SCREW][MAX_SCREW], int n) { int row, col; /*每一圈的左上角起始坐标*/ int len; /*每一圈的边长*/ int count; /*螺旋计数,每填上一个数,自增1*/ int i, k; row = col = 0; /*起始位置(0,0)*/ len = n; /*最外圈边长*/ count = 1;/*第一个数是1*/ for (i = 0; i < n/2; i++) { /*圈数循环*/ for (k=col;k<col+len-1;k++) ScrewArray[row][k]=count++;/*上:左到右*/ for (k=row;k<row+len-1;k++) ScrewArray[k][col+len-1]=count++;/*右:上到下*/ for (k=col+len-1;k>col;k--) ScrewArray[row+len-1][k]=count++;/*下:右到左*/ for (k=row+len-1;k>row;k--) ScrewArray[k][col]=count++;/*下:右到左*/ row++; col++; len -= 2;/*下一圈的左上角起始位置与边长调整*/ } if (n%2) ScrewArray[n/2][n/2] = count; /*奇数边长,补填中心元素值n*n */


Download ppt "专题研讨课二: 数组在解决复杂问题中的作用"

Similar presentations


Ads by Google