循環設計中要注意算法的效率:
循環體的特點是：“以不變應萬變”。
所謂“不變”是指循環體内運算的表現形式是不變的，而每次具體的執行内容卻是不盡相同的。在循環體内用不變的運算表現形式去描述各種相似的重複運算。
【例1】求1/1!-1/3!+1/5!-1/7!+…+（-1）n+1/(2n-1)!
分析：此問題中既有累加又有累乘，準确地說累加的對象是累乘的結果。
數學模型1：Sn=Sn-1+（-1）n+1/(2n-1)!
算法設計1：多數初學者會直接利用題目中累加項通式，構造出循環體不變式為：
S=S+（-1）n+1/(2n-1)!
需要用二重循環來完成算法，算法1如下：
main( )
{int i,n,j,sign=1;
float s,t=1;
input(n);
s=1；
for(i=2;i<=n;i=i+1)
{t=1; \求階乘\
for(j=1;j<=2*i-1;j=j+1)
t=t*j;
sign =1; \求（-1）n+1\
for(j=1;j<=i+1;j=j+1)
sign = sign *(-1);
s=s+ sign/t;
}
print(“Snm=”,s);
} 算法分析：
以上算法是二重循環來完成 ，但算法的效率卻太低是O（n2）。
其原因是，目前一次循環已求出7！，當這次要想求9！時，沒必要再從1去累乘到9，隻需要充分利用前一次的結果，用7！*8*9即可得到9！，模型為An=An-1*1/((2*n-2)*(2*n-1)。另外運算sign = sign *(-1);總共也要進行n*(n-1)/2次乘法，這也是沒有必要的。下面我們就進行改進。
數學模型2：Sn=Sn-1+（-1）n+1An；
An=An-1 *1/((2*n-2)*(2*n-1))
算法2如下：
main( )
{int i,n, sign;
float s,t=1;
input(n);
s=1；
sign=1;
for(i=2;i<=n;i=i+1) 或 for(i=1;i<=n-1;i=i+1)
{sign=-sign; { sign=-sign;
t= t*(2*i-2)*(2*i-1)} t= t*2*i*(2*i+1)};
s=s+sign/t; } s=s+ sign/t; }
print(“Sum=”,s);
}
算法說明2：
構造循環不變式時，一定要注意循環變量的意義，如當i不是項數序号時（右邊的循環中）有關t的累乘式與i是項數序号時就不能相同。
算法分析：按照數學模型2，隻需一重循環就能解決問題
算法的時間複雜性為O（n）。
【例2】編算法找出1000以内所有完數
例如，28的因子為1、2、4、7，14，而28=1+2+4+7+14。是以28是“完數”。編算法找出1000之内的所有完數，并按下面格式輸出其因子：28 it’s factors are 1，2，4，7，14。
1）這裡不是要質因數，是以找到因數後也無需将其從資料中“除掉”。
2）每個因數隻記一次，如8的因數為1，2，4而不是1，2，2，2，4。（注：本題限定因數不包括這個數本身）
1）頂層算法
for(i=0;i<n;i=i+1)
{找第i行上最小的元素t及所在列minj;
檢驗t是否第minj 列的最大值，是則輸出這個鞍點;}
2）找第i行上最小的元素t及所在列minj
t=a[i][0]; minj=1;
for(j=1;j<n;j=j+1)
if(a[i][j]<t)
{t=a[i][j];
minj=j;}
3）進一步細化——判斷i是否“完數”算法
s=1
for(j=2;j<i;j=j+1)
if (i mod j=0) (j是i的因數) s=s+j;
if （s=i） i是“完數”;
4）考慮輸出格式——判斷i是否“完數”算法
考慮到要按格式輸出結果，應該開辟數組存儲資料i的所有因子，并記錄其因子的個數，是以算法細化如下：
定義數組a，s=1; k=0;
if (i mod j=0) (j是i的因素)
{s=s+j; a[k]=j;k=k+1;}
if （s=i）
{按格式輸出結果}
算法如下：
main( )
{int i,k,j,s,a[20];
for(i=1;i<=1000;i++)
{s=1; /*兩個賦初值語句s=1,k=0
k=0; 一定要位于外部循環的内部*/
for(j=2;j<i;j++)
if (i mod j)==0)
{s=s+j; a[k]=j; k++;}
if(i==s)
{print(s, “it’s factors are :”,1);
for(j=0;i<k;j++)
print(“,”,a[k]);
}
}
}
【例3】求一個矩陣的鞍點
(即在行上最小而在列上最大的點)。
算法設計：
1）在第一行找最小值，并記錄其列号。
2）然後驗證其是否為所在列的最大值，如果是，則找到問題的解；否則，則繼續在下一行找最小值 …… 。
1）頂層算法
2）找第i行上最小的元素t及所在列minj
t=a[i][0];
minj=1;
3）檢驗t是否第minj 列的最大值，是，則輸出這個鞍點;
for(k=0;k<n;k=k+1)
if(a[k][minj]>t) break;
if(k<n) continue;
print(“the
result is a[“,i ，“][” ,minj, “]=”，t);
考慮到會有無解的情況，設定标志量kz，kz=0代表無解，找到一個解後，kz被指派為1，就不再繼續找鞍點的工作。請讀者考慮是否有多解的可能性嗎？若有，請改寫算法，找出矩陣中所有的鞍點。
buck( )
{int a[10][10]; int i,j,k,minj,t,n=10,kz=0;
/*minj代表目前行中最小值的列下标；設定标志量kz*/
readmtr(a,n);
prntmtr(a,n);
for(i=0;i<n;i++)
{t=a[i][0]; minj=1;
for(j=1;j<n;j++)
if(a[i][j]<t)
{t=a[i][j];minj=j;}
for(k=0;k<n;k++)
if(a[k][minj]>a[i][minj]) break;
if(k<n) continue;
print(“the result is a[“,i ,“][”,minj,“]=”，a[i][minj]);
kz=1;
break;
}
if(kz==0) print(“no solution!”);
}
由具體到抽象設計循環結構
對于不太熟悉的問題，其數學模型或“機械化操作步驟”的不易抽象，下面看一個由具體到抽象設計循環細節的例題。
【例4】編寫算法：列印具有下面規律的圖形。
1
5 2
8 6 3
10 9 7 4
算法設計：容易發現圖形中自然數在矩陣中排列的規律，題目中1，2，3，4所在位置我們稱為第1層（主對角線），例圖中5，6，7所在位置我們稱為第二層，……。一般地，第一層有n個元素，第二層有n-1個元素……
基于以上資料變化規律，以層号作為外層循環，循環變量為i（範圍為1——n）；以層内元素從左上到右下的序号作為内循環，循環變量為j（範圍為1——n+1-i）。這樣循環的執行過程正好與“擺放”自然數的順序相同。用一個變量k模拟要“擺放”的資料，下面的問題就是怎麼樣将資料存儲到對應的數組元素。
數組元素的存取，隻能是按行、列号操作的。是以下面用由具體到抽象設計循環的“歸納法”，找出數組元素的行号、列号與層号i及層内序号j的關系：
1.每層内元素的列号都與其所在層内的序号j是相同的。因為每層的序号是從第一列開始向右下進行。
2.元素的行與其所在的層号及在層内的序号均有關系,具體地：
第一層行号1——n，行号與j同；
第二層行号2——n，行号比j大1；
第三層行号3——n，行号比j大2；
……
行号起點随層号i增加而增加，層内其它各行的行号又随層内序号j增加而增加，由于編号起始為1，i層第j個資料的列下标為i-1+j。
綜合以上分析,i層第 j個資料對應的數組元素是a[i-1+j][j]。
main( )
{int i,j,a[100][100],n,k;
input(n);
k=1;
for(i=1;i<=n;i=i+1)
for( j=1;j<=n+1-i;j=j+1)
{a[i-1+j][j]=k;
k=k+1;}
for(i=1;i<=n;i=i+1)
{print( “換行符”);
for( j=1;j<=i;j=j+1)
print(a[i][j]);
}
}
遞歸設計要點
遞歸算法是一個子產品（函數、過程）除了可調用其它模 塊（函數、過程）外，還可以直接或間接地調用自身的算法。
遞歸是一種比疊代循環更強、更好用的循環結構。
隻需要找出遞歸關系和最小問題的解。
遞歸方法隻需少量的步驟就可描述出解題過程所需要的多次重複計算，大大地減少了算法的代碼量。
遞歸的關鍵在于找出遞歸方程式和遞歸終止條件。
遞歸定義：使問題向邊界條件轉化的規則。遞歸定義必須能使問題越來越簡單。
遞歸邊界條件：也就是所描述問題的最簡單情況，它本身不再使用遞歸的定義。
遞歸算法解題通常有三個步驟：
1）分析問題、尋找遞歸：找出大規模問題與小規模問題的關系，這樣通過遞歸使問題的規模逐漸變小。
2）設定邊界、控制遞歸：找出停止條件，即算法可解的最小規模問題。
3）設計函數、确定參數：和其它算法子產品一樣設計函數體中的操作及相關參數。
【例1】漢諾塔問題描述：
古代有一個梵塔，塔内有3個基座A、B、C，開始時A基座上有64個盤子，盤子大小不等，大的在下，小的在上。有一個老和尚想把這64個盤子從A座移到B座，但每次隻允許移動一個盤子，且在移動過程中在3個基座上的盤子都始終保持大盤在下，小盤在上。在移動過程中可以利用C基座做輔助。請程式設計列印出移動過程 。
用歸納法解此題，約定盤子自上而下的編号為1，2，3，……，n。
首先看一下2階漢諾塔問題的解，不難了解以下移動過程：
初始狀态為 A（1,2） B（）
C（）
第一步後 A（2）
B（）
C（1）
第二步後 A（） B（2）
第三步後 A（） B（1,2） C（）
如何找出大規模問題與小規模問題的關系，進而實作遞歸呢？
把n個盤子抽象地看作“兩個盤子”，上面“一個”由1——n-1号組成，下面“一個”就是n号盤子。移動過程如下：
第一步：先把上面“一個”盤子以a基座為起點借助b基座移到c基座。
第二步：把下面“一個”盤子從a基座移到b基座。
第三步：再把c基座上的n-1盤子借助a基座移到b基座。
把n階的漢諾塔問題的子產品記作hanoi(n,a,b,c)
a代表每一次移動的起始基座，
b代表每一次移動的終點基座，
c代表每一次移動的輔助基座
則漢諾塔問題hanoi(n,a,b,c)等價于以下三步：
第一步，hanoi(n-1,a,c,b)；
第二步，把下面“一個”盤子從a基座移到b基座；
第三步， hanoi(n-1,c,b,a)。
至此找出了大規模問題與小規模問題的關系。
hanoi (int n,char a,char b,char c)
/ a,b,c 初值為”A”,”B”,”C”/
1) if(n>0) /*0階的漢諾塔問題當作停止條件*/
2) hanoi(n-1,a,c,b);
3) 輸出 “ Move dise” ,n.”from pile”,a,” to”b);
4) haboi(n-1,c,b,a);
5) endif }
【例2】整數的分劃問題
對于一個正整數n的分劃就是把n寫成一系列正整數之和的表達式。例如，對于正整數n=6，它可以分劃為：
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1
根據例子發現“包括第一行以後的資料不超過6，包括第二行的資料不超過5，……，第六行的資料不超過1”。
是以，定義一個函數Q(n,m)，表示整數n的“任何被加數都不超過m”的分劃的數目，n的所有分劃的數目P(n)=Q(n,n)。
模型建立：
一般地Q(n.m)有以下遞歸關系：
1)Q(n,n)=1+Q(n,n-1) （m=n）
Q(n,n-1)表示n的所有其他分劃，即最大被加數m<=n-1的劃分。
2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (m<n)
Q(n,n-1)表示被加數中不包含m的分劃的數目；
Q(n-m,m)表示被加數中包含(注意不是小于)m的分劃的數目，
遞歸的停止條件：
1)Q(n,1)=1，表示當最大的被加數是1時，該整數n隻有一種分劃，即n個1相加；
2)Q(1,m)=1，表示整數n=1隻有一個分劃，不管最大被加數的上限m是多大。
Divinteger(n, m)
{if （n < 1 or m
< 1 or m > n ）
Error(“輸入參數錯誤”)； /*n<m Q(n,m)是無意義的*/
else if （n = 1 or m = 1）
return（1）；
else if （ n < m ）
return Divinteger(n, n)
else if （n = m ）
return(1 + Divinteger(n,
n-1))
else return(Divinteger(n,m-1)+Divinteger(n-m,m));
}
遞歸與循環的比較
◆遞歸與循環都是解決“重複操作”的機制。
◆遞歸使一些複雜的問題處理起來簡單明了。
◆就效率而言，遞歸算法的實作往往要比疊代算法耗費更多的時間（調用和傳回均需要額外的時間）與存貯空間（用來儲存不同次調用情況下變量的目前值的棧棧空間），也限制了遞歸的深度。
◆每個疊代算法原則上總可以轉換成與它等價的遞歸算法；反之不然 。
◆遞歸的層次是可以控制的，而循環嵌套的層次隻能是固定的，是以遞歸是比循環更靈活的重複操作的機制。
下面通過幾個具體的例子來說明循環和遞歸的差異和優劣。
【例1】任給十進制的正整數，請從低位到高位逐位輸出各位數字。
循環算法設計：從題目中我們并不能獲知正整數的位數，再看題目的要求，算法應該從低位到高位逐位求出各位數字并輸出。詳細設計如下：
1） 求個位數字的算式為
n mod 10
2） 為了保證循環體為“不變式”，求十位數字的算式仍舊為n mod 10，這就要通過算式n=n\10，将n的十位數變成個位數。
循環算法如下：
f1(n)
{while(n>=10)
{ print( n mod 10);
n=n\10;}
print(n);
}
遞歸算法設計：
1）同上，算法從低位到高位逐位求出各位數字并輸出，求個位數字的算式為 n mod
10，下一步則是遞歸地求n\10的個位數字。
2）當n<10時，n為一位數停止遞歸。
遞歸算法如下：
f2(n)
{if(n<10)
else
{ print( n mod 10);
f(n\10);}
}
【例2】任給十進制的正整數，請從高位到低位逐位輸出各位數字。
循環算法設計：本題目中要求“從高位到低位”逐位輸出各位數字，但由于我們并不知道正整數的位數，算法還是“從低位到高位”逐位求出各位數字比較友善。這樣就不能邊計算邊輸出，而需要用數組儲存計算的結果，最後倒着輸出。
f3(n)
{int
j,i=0,a[16];
while(n>=10)
{ a[i]=n mod 10;
i=i+1;
n=n\10;}
a[i]=n;
for(j=i;j>=0;j=j-1)
print(a[j]);
與f2不同，遞歸算法是先遞歸地求n\10的個位數字，然後再求個位數字n的個位數字并輸出。這樣輸出操作是在回溯時完成的。遞歸停止條件與f2相同為n<10。
f4(n)
{ f(n\10);
print( n mod 10); }
由于遞歸算法的實作包括遞歸和回溯兩步，當問題需要“後進先出”的操作時，還是用遞歸算法更有效。如資料結構課程中樹各種周遊、圖的深度優先等算法都是如此。是以不能僅僅從效率上評價兩個控制重複機制的好壞。
事實上，無論把遞歸作為一種算法的政策，還是一種實作機制，對我們設計算法都有很好的幫助。看下面的例子：
【例3】找出n個自然數(1,2,3,…,n)中r個數的組合。
例如，當n=５,r=3時，所有組合為：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
total=10 {組合的總數}
算法設計1：
1）n個數中r的組合，其中每r個數中，數不能相同；
2）任何兩組組合的數，所包含的數也不應相同。
例如，５、４、３與３、４、５。為此，約定前一個數應小于後一個數。将上述兩條作為限制條件；
3）當r=3時，可用三重循環進行枚舉。
算法1如下：
constitute1（）
{int n=5,i,j,k,t;
t=0;
for(i=1;i>=n;i--)
for(j=1;j>=n;j--)
for(k=1;k>=n;k--)
if(i<>j)and(i<>k)and(i<j)and(j<k)
{t=t+1;
print(i,j,k);}
print('total=',t);
}
或者
constitute2（）
{int n=5,r=3,i,j,k,t;
t=0;
for(i=1;i<=n-r+1; i=i+1)
for(j=i+1;j<= n-r+2;j=j+1)
for(k=j+1;k<=n-r+3;k=k+1)
{t=t+1;
print(i,j,k);}
print('total=',t);
用遞歸法設計此題：
在循環算法設計中，對n=5的執行個體，每個組合中的資料從小到大排列或從大到小排列一樣可以設計出相應的算法。但用遞歸思想進行設計時，每個組合中的資料從大到小排列卻是必須的；因為遞歸算法設計是要找出大規模問題與小規模問題之間的關系。
５ ４ ３
５ ４
２
１
５ ３
５ ２
４ ３
４ ２
３ ２
total=10
分析n=5,r=3時的10組組合數。
1）首先固定第一個數５，其後就是n=4,r=2的組合數，共6個組合。
2）其次固定第一個數4，其後就是n=3,r=2的組合數，共3個組合。
3）最後固定第一個數3，其後就是n=2,r=2的組合數，共1個組合。
至此找到了“５個數中３個數的組合”與“４個數中２個數的組合、3個數中２個數的組合、2個數中２個數的組合”的遞歸關系。
則遞歸算法的三個步驟為：
1）一般地：n個數中r個數組合遞推到“n-1個數中r-1個數有組合，n-2個數中r-1個數有組合，……,r-1個數中r-1個數有組合”，共n-r+1 次遞歸。
2）遞歸的邊界條件是的r=1。
3）函數的主要操作就是輸出，每當遞歸到r=1時就有一組新的組合産生，輸出它們和一個換行符。
注意n=5,r=3的例子中的遞歸規律，先固定5，然後要進行多次遞歸也就是說，數字5要多次輸出，是以要用數組存儲以備每一次遞歸到r=1時輸出。同樣每次向下遞歸都要用到數組，是以将數組設定為全局變量 。
int a[100];
comb(int m,int k)
{ int i,j;
for (i=m;i>=k;i--)
{ a[k]=i;
if (k>1)
comb(i-1,k-1);
else
{ for (j=a[0];j>0;j--)
print(a[j]);
print(“換行符”);
}
}
}
comb(int m,int k)
{ int i,j;
for (i=m;i>=k;i--)
{ a[k]=i;
if (k>1)
comb(i-1,k-1);
else
{ for (j=a[0];j>0;j--)
print(a[j]);
print(“換行符”);
}
}
}
分析：算法2遞歸的深度是r，每個算法要遞歸m-k+1次，是以的時間複雜性是O（r*n）。
遞歸是一種強有力的算法設計方法。遞歸是一種比循環更強、更好用的實作“重複操作”的機制。因為遞歸不需要程式設計者（算法設計者）自己構造“循環不變式”，而隻需要找出遞歸關系和最小問題的解。遞歸在很多算法政策中得以運用，如：分治政策、動态規劃、圖的搜尋等算法政策。
![微信小程式前端解密擷取使用者資訊[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)