中北大学算法分析与设计实验报告三（数字旋转方阵）
1.实验名称
实验三 分治与减治算法实验
2.实验目的
（1）掌握分治法的设计思想；
（2）掌握数字旋转方阵的具体实现过程；
（3）熟练掌握二维数组的使用方法；
（4）在掌握的基础上编程实现数字旋转方阵的实现过程。
3.训练知识点集群
（1）根据实验内容设计算法伪代码进行算法描述；
（2）利用C++/C/Java等编程语言对算法伪代码进行工程化实现；
（3）输入测试用例对算法进行验证；
（4）列出算法时间复杂度模型并与计算机运行统计时间进行对比分析。
4.实验内容
给出一个初始数据，在此数据的基础上由外层向里层填写数据，完成一个数字旋转方阵，输出结果，输出时要求有文字说明。请任选一种语言编写程序实现上述算法，并分析其算法复杂度。
5.实验原理
题目1、数字旋转方阵程序设计
（1）问题描述
给出一个初始数据，在此数据的基础上由外层向里层填写数据，完成一个数字旋转方阵，输出结果，输出时要求有文字说明，并分析其算法复杂度。
（2）算法思想
用二维数组data[N][N]表示NxN的方阵，观察方阵中数字的规律，可以从外层向里层填数。
设变量size表示方阵的大小，则初始时size=N，填完一层则size=size2;设变量begin表示每一层的起始位置，变量i和j分别表示行号和列号，则每一层初始时i=begin，j=begin。
将每一层的填数过程分为A、B、C、D四个区域，则每个区域需要填写size-1个数字，填写区域A时列号不变行号加1，填写区域B时行号不变列号加1，填写区域C时列号不变行号减1，填写区域D时行号不变列号减1。
显然，递归的结束条件是size等于0或size等于1。
（3）算法描述:
1.输入:当前层左上角要填的数字number，左上角的坐标begin，方阵的阶数size
2.输出:数字旋转方阵
3.如果size等于0，则算法结束；
4.如果size等于1，则data[begin][begin] = number，算法结束；
5.初始化行、列下标i=begin,j=begin；
6.重复下述操作size-1次，填写区域A
data[i][j]=number；number++；
行下标i++；列下标不变；
7.重复下述操作size-1次，填写区域B
data[i][j]=number；number++行；下标不变；列下标j++；8.重复下述操作size-1次，填写区域C
data[i][j]=number；number++；行下标i–；列下标不变；9.重复下述操作size-1次，填写区域D
data[i][j]=number；number++；行下标不变，列下标j–；
10.调用函数Full在size-2阶方阵中左上角begin+1处从数字number开始填数；
6.源代码实现
#include <stdio.h>
int data[100][100]={0};
int maxsize = 0;
void printData(int size){
for(int i=0;i<size;i++){
for(int j=0;j<size;j++)
printf("%4d",data[i][j]);
printf("\n");
}
printf("\n");
}
void Full(int number, int begin, int size){ //从number开始填写size阶方阵，左上角的下标为(begin, begin)
int i,j, k;
if (size == 0) //递归的边界条件，如果size等于0，则无须填写
return;
if (size == 1){ //递归的边界条件，如果size等于1
data[begin][begin] = number; //则只须填写number
printData(maxsize);
return;
}
i = begin; j = begin; //初始化左上角下标
for(k = 0; k < size - 1; k++){ //填写区域A，共填写size- 1个数
data[i][j] = number; //在当前位置填写number
number++; i++; //行下标加1
}
for(k = 0; k < size - 1; k++){ //填写区域B,共填写size- 1个数
data[i][j] = number; //在当前位置填写number
number++; j++;//列下标加1
}
for(k = 0; k < size- 1; k++){ //填写区域C,共填写size- 1个数
data[i][j] = number; //在当前位置填写number
number++; i--; //行下标减1
}
for(k = 0; k < size- 1; k++){ //填写区域D, 共填写size - 1个数
data[i][j] = number; //在当前位置填写number
number++;j--; //列下标减1
}
printData(maxsize);
Full(number, begin + 1, size - 2); //递归求解，左上角下标为begin + 1
}
int main(){
int size;
printf("输入方阵的大小: ");
scanf("%d", &size);
maxsize = size;
printf("开始填充之前的数字旋转方阵: \n");
printData(maxsize);
printf("填充过程: \n");
Full(1 , 0, size);
printf("最终填充完成的结果是: \n");
printData(maxsize);
return 0;
}
7.实验结论及心得体会
（1）算法复杂度
算法SquareMatrix的复杂度如下：
如果n=0时，T(n)=0；
如果n=1时，T(n)=1；
如果n>1时，T(n)=O(n^2)；文章来源：https://www.toymoban.com/news/detail-404331.html
（2）心得体会
通过本次实验，我理解了分治法的设计思想，学会了数字旋转方阵的具体实现过程，掌握了二维数组的使用方法并且编程实现数字旋转方阵的实现过程，更深刻地掌握了时间复杂度和空间复杂度的理解以及递归思想；通过一步步解决问题、编写代码，增强了动手能力。文章来源地址https://www.toymoban.com/news/detail-404331.html
到了这里，关于中北大学算法分析与设计实验报告三（数字旋转方阵）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
