中北大学算法分析与设计实验报告三（数字旋转方阵）

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)；

（2）心得体会
通过本次实验，我理解了分治法的设计思想，学会了数字旋转方阵的具体实现过程，掌握了二维数组的使用方法并且编程实现数字旋转方阵的实现过程，更深刻地掌握了时间复杂度和空间复杂度的理解以及递归思想；通过一步步解决问题、编写代码，增强了动手能力。