中北大學(xué)算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告三（數(shù)字旋轉(zhuǎn)方陣）

1.實(shí)驗(yàn)名稱

實(shí)驗(yàn)三 分治與減治算法實(shí)驗(yàn)

2.實(shí)驗(yàn)?zāi)康?/h4>

（1）掌握分治法的設(shè)計(jì)思想；
（2）掌握數(shù)字旋轉(zhuǎn)方陣的具體實(shí)現(xiàn)過程；
（3）熟練掌握二維數(shù)組的使用方法；
（4）在掌握的基礎(chǔ)上編程實(shí)現(xiàn)數(shù)字旋轉(zhuǎn)方陣的實(shí)現(xiàn)過程。

3.訓(xùn)練知識(shí)點(diǎn)集群

（1）根據(jù)實(shí)驗(yàn)內(nèi)容設(shè)計(jì)算法偽代碼進(jìn)行算法描述；
（2）利用C++/C/Java等編程語言對(duì)算法偽代碼進(jìn)行工程化實(shí)現(xiàn)；
（3）輸入測(cè)試用例對(duì)算法進(jìn)行驗(yàn)證；
（4）列出算法時(shí)間復(fù)雜度模型并與計(jì)算機(jī)運(yùn)行統(tǒng)計(jì)時(shí)間進(jìn)行對(duì)比分析。

4.實(shí)驗(yàn)內(nèi)容

給出一個(gè)初始數(shù)據(jù)，在此數(shù)據(jù)的基礎(chǔ)上由外層向里層填寫數(shù)據(jù)，完成一個(gè)數(shù)字旋轉(zhuǎn)方陣，輸出結(jié)果，輸出時(shí)要求有文字說明。請(qǐng)任選一種語言編寫程序?qū)崿F(xiàn)上述算法，并分析其算法復(fù)雜度。

5.實(shí)驗(yàn)原理

題目1、數(shù)字旋轉(zhuǎn)方陣程序設(shè)計(jì)

（1）問題描述
給出一個(gè)初始數(shù)據(jù)，在此數(shù)據(jù)的基礎(chǔ)上由外層向里層填寫數(shù)據(jù)，完成一個(gè)數(shù)字旋轉(zhuǎn)方陣，輸出結(jié)果，輸出時(shí)要求有文字說明，并分析其算法復(fù)雜度。

（2）算法思想
用二維數(shù)組data[N][N]表示NxN的方陣，觀察方陣中數(shù)字的規(guī)律，可以從外層向里層填數(shù)。
設(shè)變量size表示方陣的大小，則初始時(shí)size=N，填完一層則size=size2;設(shè)變量begin表示每一層的起始位置，變量i和j分別表示行號(hào)和列號(hào)，則每一層初始時(shí)i=begin，j=begin。
將每一層的填數(shù)過程分為A、B、C、D四個(gè)區(qū)域，則每個(gè)區(qū)域需要填寫size-1個(gè)數(shù)字，填寫區(qū)域A時(shí)列號(hào)不變行號(hào)加1，填寫區(qū)域B時(shí)行號(hào)不變列號(hào)加1，填寫區(qū)域C時(shí)列號(hào)不變行號(hào)減1，填寫區(qū)域D時(shí)行號(hào)不變列號(hào)減1。
顯然，遞歸的結(jié)束條件是size等于0或size等于1。

（3）算法描述:
1.輸入:當(dāng)前層左上角要填的數(shù)字number，左上角的坐標(biāo)begin，方陣的階數(shù)size
2.輸出:數(shù)字旋轉(zhuǎn)方陣
3.如果size等于0，則算法結(jié)束；
4.如果size等于1，則data[begin][begin] = number，算法結(jié)束；
5.初始化行、列下標(biāo)i=begin,j=begin；
6.重復(fù)下述操作size-1次，填寫區(qū)域A
data[i][j]=number；number++；
行下標(biāo)i++；列下標(biāo)不變；
7.重復(fù)下述操作size-1次，填寫區(qū)域B
data[i][j]=number；number++行；下標(biāo)不變；列下標(biāo)j++；8.重復(fù)下述操作size-1次，填寫區(qū)域C
data[i][j]=number；number++；行下標(biāo)i–；列下標(biāo)不變；9.重復(fù)下述操作size-1次，填寫區(qū)域D
data[i][j]=number；number++；行下標(biāo)不變，列下標(biāo)j–；
10.調(diào)用函數(shù)Full在size-2階方陣中左上角begin+1處從數(shù)字number開始填數(shù)；

6.源代碼實(shí)現(xiàn)

#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階方陣，左上角的下標(biāo)為(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; //初始化左上角下標(biāo)
    for(k = 0; k < size - 1; k++){ //填寫區(qū)域A，共填寫size- 1個(gè)數(shù)
        data[i][j] = number; //在當(dāng)前位置填寫number
        number++; i++; //行下標(biāo)加1
    } 
    for(k = 0; k < size - 1; k++){ //填寫區(qū)域B,共填寫size- 1個(gè)數(shù)
        data[i][j] = number; //在當(dāng)前位置填寫number
        number++; j++;//列下標(biāo)加1
    } 
    for(k = 0; k < size- 1; k++){ //填寫區(qū)域C,共填寫size- 1個(gè)數(shù)
        data[i][j] = number; //在當(dāng)前位置填寫number
        number++; i--; //行下標(biāo)減1
    } 
    for(k = 0; k < size- 1; k++){ //填寫區(qū)域D, 共填寫size - 1個(gè)數(shù)
        data[i][j] = number; //在當(dāng)前位置填寫number
        number++;j--; //列下標(biāo)減1
    } 
    printData(maxsize);
    Full(number, begin + 1, size - 2); //遞歸求解，左上角下標(biāo)為begin + 1
}
 
int main(){ 
    int size;
    printf("輸入方陣的大小: "); 
    scanf("%d", &size);
maxsize = size;
printf("開始填充之前的數(shù)字旋轉(zhuǎn)方陣: \n"); 
    printData(maxsize);
    printf("填充過程: \n");
    Full(1 , 0, size);
    printf("最終填充完成的結(jié)果是: \n");
    printData(maxsize);
    return 0; 
}

7.實(shí)驗(yàn)結(jié)論及心得體會(huì)

（1）算法復(fù)雜度
算法SquareMatrix的復(fù)雜度如下：
如果n=0時(shí)，T(n)=0；
如果n=1時(shí)，T(n)=1；
如果n>1時(shí)，T(n)=O(n^2)；

（2）心得體會(huì)
通過本次實(shí)驗(yàn)，我理解了分治法的設(shè)計(jì)思想，學(xué)會(huì)了數(shù)字旋轉(zhuǎn)方陣的具體實(shí)現(xiàn)過程，掌握了二維數(shù)組的使用方法并且編程實(shí)現(xiàn)數(shù)字旋轉(zhuǎn)方陣的實(shí)現(xiàn)過程，更深刻地掌握了時(shí)間復(fù)雜度和空間復(fù)雜度的理解以及遞歸思想；通過一步步解決問題、編寫代碼，增強(qiáng)了動(dòng)手能力。文章來源地址http://www.zghlxwxcb.cn/news/detail-404331.html

到了這里，關(guān)于中北大學(xué)算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告三（數(shù)字旋轉(zhuǎn)方陣）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！