問題描述
回形取數(shù)就是沿矩陣的邊取數(shù)，若當(dāng)前方向上無數(shù)可取或已經(jīng)取過，則左轉(zhuǎn)90度。一開始位于矩陣左上角，方向向下。
輸入格式
輸入第一行是兩個(gè)不超過200的正整數(shù)m, n，表示矩陣的行和列。接下來m行每行n個(gè)整數(shù)，表示這個(gè)矩陣。
輸出格式
輸出只有一行，共mn個(gè)數(shù)，為輸入矩陣回形取數(shù)得到的結(jié)果。數(shù)之間用一個(gè)空格分隔，行末不要有多余的空格。
樣例輸入
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
我設(shè)計(jì)了三種算法來解決此道題目，并通過對(duì)算法的分析，來看該三種算法的優(yōu)劣。
1. 算法設(shè)計(jì)：（遞歸法）
矩陣由四個(gè)邊組成，回型取數(shù)在不同的邊上取數(shù)方向不同，因此可以分為四種情況來取數(shù)。通過一個(gè)數(shù)s取余4來對(duì)應(yīng)四個(gè)狀態(tài)，通過遞歸算法來輸出每個(gè)數(shù)，當(dāng)每邊的數(shù)取完時(shí)就使s加一來取另外一邊的數(shù)（if...else..實(shí)現(xiàn)）。
遞歸時(shí)傳參傳的是每個(gè)數(shù)的行列值。例如：
當(dāng)取完a【i】【j】時(shí)，若s=0時(shí)，對(duì)應(yīng)取的是左邊即向下取數(shù)，則傳參數(shù)solve（i+1，j）；若s=3時(shí)，對(duì)應(yīng)取的是上邊即向左取數(shù)，則傳參數(shù)solve（i，j-1）。
--
程序代碼如下
重慶分公司
重慶分公司
#include
#include
#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=0&&j 2、算法設(shè)計(jì)：逐圈分析分別處理每圈的左側(cè)、下方、右方、上方的數(shù)據(jù)。先計(jì)算可分為幾圈，由于每轉(zhuǎn)一圈行上的個(gè)數(shù)會(huì)減少2個(gè)，因此看可以減少幾個(gè)2就有幾圈，用行數(shù)除以2可算出有幾圈。（若行數(shù)為奇數(shù)，也是除二向下取整可舉例實(shí)驗(yàn)）。
i 層內(nèi)輸出數(shù)據(jù)的4個(gè)過程為（四角元素分別歸四個(gè)邊）：
（1） i 列（左側(cè)），從 i 行到m-i-1 行；
（2） m-i-1行（下方），從 i 列到 n-i -1列；
（3） n-i-1 列（右側(cè)），從 m-i-1 行到 i+1 行；
（4）i 行（上方），從 n-i-1 列到 i 列；
4個(gè)過程通過4個(gè)循環(huán)實(shí)現(xiàn)，用 j 表示 i 層內(nèi)每邊中行或列的下標(biāo)。
__
程序代碼如下：
#include
#include
#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;ii;j--)
printf("%d",a[j][n-i-1]); //右側(cè)
for(j=n-i-1;j>i;j--)
printf("%d",a[i][j]); //上方
}
return 0;
} **3、算法設(shè)計(jì)：（算法設(shè)計(jì)數(shù)p.83）通過設(shè)置變量標(biāo)識(shí)一圈中不同方位的處理差別，并通過算術(shù)運(yùn)算將4個(gè)方位的處理歸結(jié)成一個(gè)循環(huán)過程。
通過輸出最外一圈的情況分析：
| j=1 | i=i+1 | 0~n-1 | k=n | //左側(cè) |
|---|---|---|---|---|
| i=n | j=j+1 | 1~n-1 | k=n-1 | //下方 |
| j=n | i=i-1 | n-2~0 | k=n-1 | //右側(cè) |
| i=1 | j=j+1 | n-2~0 | k=n-2 | //上方 |
從上面i，j 的變化可發(fā)現(xiàn)：輸出時(shí)，前半圈下標(biāo)變化一致，都加1；后半圈都減1，不同的是變化范圍，所以分兩邊前半圈和后半圈，引入t=1，每半圈改變t的正負(fù)號(hào)再進(jìn)行行列值改變。
前半圈再分左邊與下邊，可知前m個(gè)數(shù)是左邊，后n-1是下邊，在此引入兩值b【0】與b【1】，當(dāng)?shù)趇個(gè)數(shù)取余m等于0時(shí)則為左邊的數(shù)，因?yàn)椋╥從0取所以還是m個(gè)數(shù)）等于1則為下邊的數(shù)。后半圈同理。。
為表達(dá)，要統(tǒng)一表示循環(huán)變量的范圍，可發(fā)現(xiàn)當(dāng)輸出到左下角時(shí)行列數(shù)少一，右上角行列數(shù)又少一，因此在進(jìn)行半圈輸出后，要對(duì)行列值減一。**
——
程序代碼如下：
#include
#include
#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 -----
三種算法比較及學(xué)習(xí)心得：
算法 1、2比較好理解，在思考方面可以節(jié)約大量時(shí)間，算法也是相通的，體現(xiàn)了遞歸和循環(huán)的相互轉(zhuǎn)換；
算法 3 需要通過歸納，構(gòu)造循環(huán)不變式，寫出的算法節(jié)約了運(yùn)行時(shí)的時(shí)間。
比較偏向算法1，好理解，清晰明了，遞歸總是用很簡(jiǎn)單的語句實(shí)現(xiàn)了很復(fù)雜的過程，因此我很喜歡讀遞歸程序。
通過算法三了解到，要善于通過數(shù)學(xué)歸納構(gòu)造不變式，這也是一個(gè)寫算法很好的習(xí)慣。
ps：第一次寫博客，意猶未盡，之前以為完全掌握的在總結(jié)的時(shí)候還是會(huì)有磕絆的地方，通過寫博客也是將該問題又踏平了不少，以后這個(gè)習(xí)慣還是要堅(jiān)持的，是提高也是個(gè)記錄與回憶吧，今天算是個(gè)好的開端吧？嘿嘿嘿。。
對(duì)了，瀏覽過有問題的話，我們?cè)僖黄鹛接懓。?/p>
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
