螺旋矩阵实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
-
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目描述:
螺旋矩阵实验报告
题目描述:
C语言作业
将螺旋方阵存放在N*N的二维数组中,并把它打印输出,要求程序自动生成螺旋方阵(而非人为初始化逐个赋值)
实验目的及要求:
实验步骤(流程图):
算法描述:
螺旋方阵实例如下:
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
由上述实例直观可知,以顺时针方向从外围开始递增的填充映射矩阵, 每填充一个外围 , 问题即被分解为与此相同更小的问题,重复的从外围填充相应子矩
. 阵,即可完成
递归解法:
设原问题为 “ n 阶的螺旋方阵 , 起始值为 n_s , 终止值为 N*N , 则映射矩阵也为n 阶的矩阵 , 起始行为 row_s , 起始列维 col_s “.
递归开始:
第一步: 从映射矩阵的第一行开始开始向右填充n 个螺旋方阵中的值(从传入
的起始值开始 , 值递增变化)
第二步: 从映射矩阵的最后一列第二行开始向下填充 n-1 个螺旋方阵中的值
(值递增变化)
第三步: 从映射矩阵的最后一行最后一列开始向左填充 n-1 个螺旋方阵中的
值(值递增变化)
第四步: 从映射矩阵的倒数第二行第一列开始向左填充 n-2 个螺旋方阵中的
值(值递增变化)
此时映射矩阵的最外围被填充完毕 , 原问题转化为 “ n-2 阶的螺旋方阵 , 最小值为 n_s(一直递增变化) , 最大值为 N*N , 则映射矩阵也为n-2 阶的矩阵 , 起始行为 row_s+1 , 起始列为 col_s+1 “ 的子问题 , 用此解法递归的解决子问题 , 直到传入的螺旋矩阵起始值大于等于终止值时 , 递归调用结束 ,
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
退出 , 问题解决 .
预测结果 :
N = 4的情况 (初始值均赋为0) 第一次遍历结果:
1 2 3 4 12 0 0 5 11 0 0 6 10 9 8 7
第二次遍历结果:
1 2 3 4 12 13 14 5 11 15 16 6 10 9 8 7
最终结果:
1 2 3 4 12 13 14 5 11 15 16 6 10 9 8 7
实验内容(程序):
# include
# include
/* 参数
说明
关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书
* N , 螺旋方阵的最大阶数
* n , 映射子矩阵的阶数
* n_s , 递归遍历螺旋矩阵时,当前计数的值
* arr , 映射矩阵
* row_s , 本次遍历 , 映射矩阵的开始行
* col_s , 本次遍历 , 映射矩阵的开始列
* 无返回值 , 递归遍历
*/
void SortArr( int N , int n , int n_s , int ** arr , int row_s , int col_s );
/* 参数说明
* n , n 阶矩阵的阶数
* arr , 欲打印的 n 阶矩阵
*/
void PrintArr( int n , int ** arr );
int main( int argc , char * argv[] ) {
int N ; /* 螺旋方阵的阶数*/
int ** arr ; /* 映射矩阵 */
printf("Input (N必须大于0) N=");
scanf("%d",&N);
/* 为映射矩阵的存储分配空间 */
arr = (int **)malloc(N*sizeof(int *));
for( int i = 0 ; i < N ; i++ )
{
arr[i] = (int *)malloc(N*sizeof(int));
}
/* 为映射矩阵的存储分配空间 */
for( int i = 0 ; i < N ; i++ )
for( int j = 0 ; j < N ; j++ )
arr[i][j] = 0 ;
/* 递归遍历螺旋方阵填充映射矩阵 */
SortArr( N , N , 1 , arr , 0 , 0 );
/* 打印映射矩阵 */
PrintArr( N , arr );
system("pause");
return 0 ;
}
void SortArr( int N , int n , int n_s , int ** arr , int row_s , int col_s ) /* 围绕递归解法 , 从 0 , 0 开始 */
{
if( n_s > N*N ) return ;
int row = row_s ;
int col = col_s ;
int c = n_s ;
col = col - 1 ;
for( int i = 0 ; i < n ; i++ ) /* 从子矩阵的第1行开始向右遍历 */
{
col = col + 1 ;
arr[row][col] = c ;
if( c >= N*N ) return ; /* 当前值大于螺旋矩阵的最大值,则跳出 */
c = c + 1 ;
}
for( int i = 0 ; i < n-1 ; i++ ) /* 从子矩阵的最右列第2行开始向下遍历 */
{
row = row + 1 ;
arr[row][col] = c ;
if( c >= N*N ) return ;
c = c + 1 ;
}
for( int i = 0 ; i < n-1 ; i++ ) /* 从子矩阵的最后一行的右侧开始向左遍历 */
{
col = col - 1 ;
arr[row][col] = c ;
if( c >= N*N ) return ;
c = c + 1 ;
}
for( int i = 0 ; i < n-2 ; i++ ) /* 从子矩阵的最左列从下向上遍历 */
{
row = row - 1 ;
rr[row][col] = c ; a
if( c >= N*N ) return ;
c = c + 1 ;
}
PrintArr( N , arr ); /* 追踪映射数组的填充情况 */
SortArr( N , n - 2 , c , arr , row , col + 1 );
}
void PrintArr( int n , int ** arr ) /* 打印矩阵函数 */
{
printf("****************************************\n");
for( int i = 0 ; i < n ; i++ )
{
for( int j = 0 ; j < n ; j++ )
{
printf(" %d" , arr[i][j] );
}
printf("\n");
}
printf("****************************************\n");
}
实验结果:
1 , 输入值(螺旋矩阵阶数为 3 的 跟踪实验结果
2 , 输入值(螺旋矩阵阶数为 4 的 跟踪实验结果
3 , 输入值(螺旋矩阵阶数为 5 的 跟踪实验结果
实验总结:
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
SortArr 的算法复杂度得如下结果:
空间复杂度 S = O( N );
时间复杂度 T = O(N*N);
此算法采用直观的方式,递归地遍历填充矩阵,没有加大算法的复杂度开销. 可以根据螺旋矩阵的代数或几何特征设计更精炼的算法.