《2022年螺旋矩阵 .pdf》由会员分享，可在线阅读，更多相关《2022年螺旋矩阵 .pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 螺旋矩阵问题1 按顺时针方向构建一个m * n 的螺旋矩阵（或按顺时针方向螺旋访问一个m * n 的矩阵）：2 在不构造螺旋矩阵的情况下，给定坐标i、j 值求其对应的值f(i, j) 。比如对 11 * 7 矩阵，f(6, 0) = 27 f(6, 1) = 52 f(6, 3) = 76 f(6, 4) = 63 构建螺旋矩阵对 m * n 矩阵，最先访问最外层的m * n 的矩形上的元素，接着再访问里面一层的 (m - 2) * (n - 2) 矩形上的元素最后可能会剩下一些元素，组成一个点或一条线（见图 1）。对第 i 个矩形（ i=0, 1, 2 ）， 4 个顶点的坐标为：(i,
2、i) - (i, n1-i)| | | |(m-1-i, i) - (m-1-i, n-1-i) 要访问该矩形上的所有元素，只须用4 个 for 循环，每个循环访问一个点和一边条边上的元素即可（见图1）。另外，要注意对最终可能剩下的1 * k 或 k * 1矩阵再做个特殊处理。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 2 代码：inlinevoid act ( int t ) printf( %3d , t );cons
3、tint small = col row ? col : row ;constint count = small /2;for( int i = 0; i count ;+i )constint C = col -1 - i ;constint R = row -1 - i ;for( int j = i ; j C;+j ) act ( arr i j );for( int j = i ; j i ;- j ) act ( arr R j );for( int j = R; j i ;- j ) act ( arr j i );if( small & 1)constint i = count
4、 ;if( row = col ) for( int j = i ; j col - i ; +j ) act ( arr i j );elsefor( int j = i ; j row - i ;+j ) act (arr j i );如果只是构建螺旋矩阵的话，稍微修改可以实现4 个 for循环独立：constint small = col row ? col : row ;constint count = small /2;for( int i = 0; i count ;+i )constint C = col -1 - i ;constint R = row -1 - i ;cons
5、tint cc = C - i ;constint rr = R - i ;constint s = 2 * i * ( row + col -2 * i ) + 1;for( int j = i , k = s ; j C;+j ) arr i j = k +;for( int j = i , k = s + cc ; j i ;- j ) arr R j = k +;for( int j = R, k = s + cc * 2 + rr ; j i ;- j ) arr j i = k +;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
6、 - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 3 if( small & 1)constint i = count ;int k = 2 * i * ( row + col -2 * i )+ 1;if( row = col ) for( int j = i ; j col - i ; +j ) arr i j = k +;elsefor( int j = i ; j row - i ;+j ) arr j i = k +;关于 s 的初始值取2 * i * ( row + col -2 * i )+ 1 请参考下一节。由
7、于 C+的二维数组是通过一维数组实现的。二维数组的实现一般有下面三种：静态分配足够大的数组；动态分配一个长为m*n 的一维数组；动态分配 m个长为 n 的一维数组，并将它们的指针存在一个长为m的一维数组。二维数组的不同实现方法，对函数接口有很大影响。给定坐标直接求值f(x, y)如前面所述，对第i 个矩形（ i=0, 1, 2 ）， 4 个顶点的坐标为：(i, i) - (i, n1-i)| | | |(m-1-i, i) - (m-1-i, n-1-i) 对给定的坐标 (x,y)，如果它落在某个这类矩形上，显然其所在的矩形编号为：k = minx, y, m-1-x, n-1-ym*n矩阵删
8、除访问第k 个矩形前所访问的所有元素后，可得到(m-2*k)*(n-2*k)矩阵，因此已访问的元素个数为：m*n-(m-2*k)*(n-2*k)=2*k*(m+n-2*k)，因而 (k,k)对应的值为：T(k) = 2*k*(m+n-2*k)+ 1对某个矩形，设点(x, y)到起始点 (k,k) 的距离 d = x-k + y-k = x+y-2*k 向右和向下都只是横坐标或纵坐标增加1，这两条边上的点满足f(x, y) = T(k) + d名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
9、 第 3 页，共 12 页 - - - - - - - - - 4 向左和向下都只是横坐标或纵坐标减少1， 这两条边上的点满足f(x, y) = T(k+1) - d如果给定坐标的点(x, y)，不在任何矩形上，则它在一条线上，仍满足f(x, y) = T(k) + dint getv ( int row ,int col ,int max_row,int max_col ) / row max_row, col max_colint level = min ( min( row, max_row - 1 - row ), min ( col , max_col -1 - col );int
10、distance = row + col - level * 2;int start_value = 2 * level * ( max_row + max_col -2 * level)+ 1;if( row = level | col = max_col -1 - level |( max_col max_row & level * 2 + 1 = max_col )return start_value + distance;int next_value = start_value + ( max_row + max_col - 4 * level -2)*2;return next_va
11、lue - distance;特别说明上面的讨论都是基于m*n矩阵的， 对于特例 n*n 矩阵，可以做更多的优化。比如构建螺旋矩阵， 如果 n 为奇数， 则矩阵可以拆分为几个矩形加上一个点。前面的条件判断可以优化为：if( small & 1)actcountcount;甚至可以调整4 个 for 循环的遍历元素个数 （前面代码，每个 for循环遍历 n-1-2*i个元素，可以调整为： n-2*i ，n-1-2*i, n-1-2*i,n-2-2*i）从而达到省略if判断。测试代码代码 1：/ 螺旋矩阵，给定坐标直接求值 by flyinghearts/ - - -精品资料欢迎下载 - - -
12、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 5 #includeusing std : min;using std : cout ;/*int getv2(int row, int col, int max_row, int max_col) / row max_row, col max_col * max_row) return start_value + distance; return next_value - distance;*/int getv ( int row
13、 ,int col ,int max_row,int max_col ) / row max_row, col max_colint level = min ( min( row, max_row - 1 - row ), min ( col , max_col -1 - col );int distance = row + col - level * 2;int start_value = 2 * level * ( max_row + max_col -2 * level)+ 1;if( row = level | col = max_col -1 - level |(max_col ma
14、x_row & level* 2 + 1 = max_col )return start_value + distance;/+level; int next_value = 2 * level * (max_row + max_col - 2 * level) + 1;int next_value = start_value + ( max_row + max_col - 4 * level -2)*2;return next_value - distance;int main ()名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -
15、- 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 6 int test2= 5, 5, 5,7,7,5, 4,4, 4, 6,6,4;constint sz = sizeof ( test )/ sizeof( test 0);for( int k = 0; k sz ;+k)int M = test k 0;int N = test k 1;for( int i = 0; i M;+i )for( int j = 0; j N; +j ) cout. width ( 4), cout getv ( i , j , M, N) ; co
16、ut n ; cout n ;代码 2：/ 螺旋矩阵 by flyinghearts# / counter = 0;inlinevoid act ( int & t )/std:cout.width(3), std:cout t; t = +: counter ;void act_arr( int* arr ,int row ,int col ,int max_col )/col max_colconstint small = col row ? col : row ;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理
17、 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 7 constint count = small /2;int* p = arr ;for( int i = 0; i count ;+i )constint C = col -1 -2 * i ;constint R = row -1 -2 * i ;for( int j = 0; j C;+j ) act (* p+);for( int j = 0; j R;+j ) act (* p), p += max_col ;for( int j = 0; j C;+j ) act (* p-);for(
18、int j = 0; j R;+j ) act (* p), p -= max_col ; p += max_col + 1;if( small & 1)constint i = count ;if( row = col ) for( int j = 0; j col -2 * i ;+j ) act (* p+);elsefor( int j = 0; j row -2 * i ;+j ) act (* p), p += max_col ;void act_arr( int * arr ,int row ,int col )constint small = col row ? col : r
19、ow ;constint count = small /2;for( int i = 0; i count ;+i )constint C = col -1 - i ;constint R = row -1 - i ;for( int j = i ; j C;+j ) act ( arr i j );for( int j = i ; j i ;- j ) act ( arr R j );for( int j = R; j i ;- j ) act ( arr j i );if( small & 1)constint i = count ;if( row = col ) for( int j =
20、 i ; j col - i ; +j ) act ( arr i j );名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - 8 elsefor( int j = i ; j row - i ;+j ) act (arr j i );void act_arr_2( int * arr ,int row ,int col )constint small = col row ? col : row ;constint count =
21、 small /2;for( int i = 0; i count ;+i )constint C = col -1 - i ;constint R = row -1 - i ;constint cc = C - i ;constint rr = R - i ;constint s = 2 * i * ( row + col -2 * i ) + 1;for( int j = i , k = s ; j C;+j ) arr i j = k +;for( int j = i , k = s + cc ; j i ;- j ) arr R j = k +;for( int j = R, k =
22、s + cc * 2 + rr ; j i ;- j ) arr j i = k +;if( small & 1)constint i = count ;int k = 2 * i * ( row + col -2 * i )+ 1;if( row = col ) for( int j = i ; j col - i ; +j ) arr i j = k +;elsefor( int j = i ; j row - i ;+j ) arr j i = k +;void print_arr( int* arr ,int row ,int col ,int max_col )/col max_co
23、lfor( int i = 0,* q = arr ; i row ;+i , q += max_col )for( int*p = q ; p q + col ;+p) std: cout . width ( 4), std : cout * p; std: cout n ; std : cout n ;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 9 void print_arr( int * a ,int row ,i
24、nt col )/col max_colfor( int i = 0; i row ;+i ) for( int j = 0; j col ;+j ) std: cout . width ( 4), std : cout a i j ; std: cout n ; std : cout n ;void test_1()constint M = 25;constint N = 25;int a M N;int test2= 5, 5, 5,7,7,5, 4,4, 4, 6,6,4;constint sz = sizeof ( test )/ sizeof( test 0); std : cout
25、 Test 1:n;for( int i = 0; i sz ;+i )int row = test i 0;int col = test i 1;if( row M) row = 3;if( col N) col = 3;: counter = 0; act_arr(&a 0 0, row , col , N); print_arr(&a 0 0, row , col , N);void test_2()int test2= 5, 5, 5,7,7,5, 4,4, 4, 6,6,4;constint sz = sizeof ( test )/ sizeof( test 0);名师资料总结 -
26、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 10 std : cout Test 2:n;for( int i = 0; i sz ;+i )int row = test i 0;int col = test i 1;int* arr = new int * row;for( int i = 0; i row ;+i ) arr i = new int col ;: counter = 0; act_arr( arr , row , co
27、l ); print_arr( arr , row , col );for( int i = 0; i row ;+i )delete arr i ;delete arr ;int main () test_1(); test_2();作者：flyinghearts 出处：http:/ 本文采用 知识共享署名 -非商业性使用 - 相同方式共享2.5 中国大陆许可协议进行许可，欢迎转载， 但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名
28、师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - 11 第1 题方阵填数答案：#include using namespace std; int a1010; void Fun(int n) int m = 1,j,i; for(i = 0; i n/2; i+) for(j = 0; j n-i; j+) if(aij = 0) aij = m+; for(j = i+1; j i; j-) if(an-i-1j = 0) an-i-1j = m+; for(j = n-i-1; j i; j-) if(aji = 0) aji = m+
29、; if(n%2=1) an/2n/2 = m; void main() int n, i, j; cinn; for(int i = 0; i n; i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 12 for(int j = 0; j n; j+) aij = 0; Fun(n); for(i = 0; i n; i+) for(int j = 0; j n; j+) cout aij ; cout endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -