回形取數

問題描述
　　回形取數就是沿矩陣的邊取數，若當前方向上無數可取或已經取過，則左轉90度。一開始位于矩陣左上角，方向向下。
輸入格式
　　輸入第一行是兩個不超過200的正整數m, n，表示矩陣的行和列。接下來m行每行n個整數，表示這個矩陣。
輸出格式
　　輸出只有一行，共mn個數，為輸入矩陣回形取數得到的結果。數之間用一個空格分隔，行末不要有多余的空格。
樣例輸入
3 3
1 2 3
4 5 6
7 8 9
樣例輸出
1 4 7 8 9 6 3 2 5
樣例輸入
3 2
1 2
3 4
5 6
樣例輸出
1 3 5 6 4 2
我設計了三種算法來解決此道題目，并通過對算法的分析，來看該三種算法的優劣。

1. 算法設計：（遞歸法）
矩陣由四個邊組成，回型取數在不同的邊上取數方向不同，因此可以分為四種情況來取數。通過一個數s取余4來對應四個狀態，通過遞歸算法來輸出每個數，當每邊的數取完時就使s加一來取另外一邊的數（if...else..實現）。
遞歸時傳參傳的是每個數的行列值。例如：
當取完a【i】【j】時，若s=0時，對應取的是左邊即向下取數，則傳參數solve（i+1，j）；若s=3時，對應取的是上邊即向左取數，則傳參數solve（i，j-1）。

--

程序代碼如下

#include <stdio.h>
#include <string.h>
#define N 10
#define M 10

int s=0;
int m,n;
int a[M][N],b[M][N];
void solve(int i,int j){
    if(i>=0&&i<m&&j>=0&&j<n&&b[i][j]==0)
    {printf("%d ",a[i][j]);
    b[i][j]=1;
    }
    else  s++;
    if (s%4==0)
        solve(i+1,j);
    if(s%4==1)
        solve(i,j+1);
    if(s%4==2)
        solve(i-1,j);
    if(s%4==3)
        solve(i,i-1);

}

int main()
{ 
 int i,j;
 scanf("%d%d",&m,&n);
 memset(b,0,sizeof(b));
 for(i=0;i<m;i++)
    { for (j=0;j<n;j++)
         scanf("%d",&a[i][j]);
     printf("\n");
 }

 solve(0,0);

    return 0;

}

2、算法設計：逐圈分析分別處理每圈的左側、下方、右方、上方的數據。先計算可分為幾圈，由于每轉一圈行上的個數會減少2個，因此看可以減少幾個2就有幾圈，用行數除以2可算出有幾圈。（若行數為奇數，也是除二向下取整可舉例實驗）。
i 層內輸出數據的4個過程為（四角元素分別歸四個邊）：
（1） i 列（左側），從 i 行到m-i-1 行；
（2） m-i-1行（下方），從 i 列到 n-i -1列；
（3） n-i-1 列（右側），從 m-i-1 行到 i+1 行；
（4）i 行（上方），從 n-i-1 列到 i 列；
4個過程通過4個循環實現，用 j 表示 i 層內每邊中行或列的下標。
__
程序代碼如下：

#include <stdio.h>
#include <string.h>
#define M 10
#define N 10

void solve()
{

}
int main(){
    int a[M][N];
    int m,n,i,j;
    scanf("%d%d",&m,&n);

    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);

//開始取數
 for(i=0;i<m/2;i++)
{
    for(j=i;j<m-i-1;j++)          //左側
        printf("%d",a[j][i]);
    for(j=i;j<n-i-1;j++)
        printf("%d",a[m-i-1][j]); //下方
    for(j=m-i-1;j>i;j--)
        printf("%d",a[j][n-i-1]); //右側
    for(j=n-i-1;j>i;j--)
        printf("%d",a[i][j]);     //上方
}

    return 0;
}

**3、算法設計：（算法設計數p.83）通過設置變量標識一圈中不同方位的處理差別，并通過算術運算將4個方位的處理歸結成一個循環過程。
通過輸出最外一圈的情況分析：

從上面i，j 的變化可發現：輸出時，前半圈下標變化一致，都加1；后半圈都減1，不同的是變化范圍，所以分兩邊前半圈和后半圈，引入t=1，每半圈改變t的正負號再進行行列值改變。
前半圈再分左邊與下邊，可知前m個數是左邊，后n-1是下邊，在此引入兩值b【0】與b【1】，當第i個數取余m等于0時則為左邊的數，因為（i從0取所以還是m個數）等于1則為下邊的數。后半圈同理。。
為表達，要統一表示循環變量的范圍，可發現當輸出到左下角時行列數少一，右上角行列數又少一，因此在進行半圈輸出后，要對行列值減一。**
——
程序代碼如下：

#include <stdio.h>
#include <string.h>
#define M 10
#define N 10
int main(){
    int a[M][N];
    int b[2];

    int m,n,x,y,i,j;
    int t=1;
    b[0]=-1;
    b[1]=0;
    scanf("%d%d",&m,&n);
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);
    //開始取數
    while(x<=m*n)
    {for(y=0;y<(m+n-1);y++)
    { b[y/m]+=t;
      printf("%d",a[b[0]][b[1]]);
      x++;
    }
    m--;
    n--;
    t=-t;
    }
    return 0;
}

-----
三種算法比較及學習心得：
算法 1、2比較好理解，在思考方面可以節約大量時間，算法也是相通的，體現了遞歸和循環的相互轉換；
算法 3 需要通過歸納，構造循環不變式，寫出的算法節約了運行時的時間。
比較偏向算法1，好理解，清晰明了，遞歸總是用很簡單的語句實現了很復雜的過程，因此我很喜歡讀遞歸程序。
通過算法三了解到，要善于通過數學歸納構造不變式，這也是一個寫算法很好的習慣。

ps：第一次寫博客，意猶未盡，之前以為完全掌握的在總結的時候還是會有磕絆的地方，通過寫博客也是將該問題又踏平了不少，以后這個習慣還是要堅持的，是提高也是個記錄與回憶吧，今天算是個好的開端吧？嘿嘿嘿。。
對了，瀏覽過有問題的話，我們再一起探討啊！