迭代學習演算法的定義

① 神經網路控制的書籍目錄

第1章神經網路和自動控制的基礎知識
1.1人工神經網路的發展史
1.1.120世紀40年代——神經元模型的誕生
1.1.220世紀50年代——從單神經元到單層網路，形成第一次熱潮
1.1.320世紀60年代——學習多樣化和AN2的急劇冷落
1.1.420世紀70年代——在低迷中頑強地發展
1.1.520世紀80年代——AN2研究熱潮再度興起
1.1.620世紀90年代——再現熱潮，產生許多邊緣交叉學科
1.1.7進入21世紀——實現機器智能的道路漫長而又艱難
1.2生物神經元和人工神經元
1.2.1生物神經元
1.2.2人工神經元
1.3生物神經網路和人工神經網路
1.3.1生物神經網路
1.3.2人工神經網路
1.4自動控制的發展史
1.4.1從傳統控制理論到智能控制
1.4.2智能控制的產生與基本特徵
1.4.3智能控制系統
1.5模糊集與模糊控制概述
1.5.1模糊集
1.5.2模糊隸屬函數
1.5.3模糊控制
1.6從生物神經控制到人工神經控制
1.6.1生物神經控制的智能特徵
1.6.2人工神經控制的模擬范圍
1.7小結
習題與思考題
第2章神經計算基礎
2.1線性空間與范數
2.1.1矢量空間
2.1.2范數
2.1.3賦范線性空間
2.1.4L1范數和L2范數
2.2迭代演算法
2.2.1迭代演算法的終止准則
2.2.2梯度下降法
2.2.3最優步長選擇
2.3逼近論
2.3.1Banach空間和逼近的定義
2.3.2L2逼近和最優一致逼近
2.3.3離散點集上的最小二乘逼近
2.4神經網路在線迭代學習演算法
2.5Z變換
2.5.1Z變換的定義和求取
2.5.2Z變換的性質
2.5.3Z反變換
2.6李雅普諾夫意義下的穩定性
2.6.1非線性時變系統的穩定性問題
2.6.2李雅普諾夫意義下的漸進穩定
2.6.3李雅普諾夫第二法
2.6.4非線性系統的穩定性分析
2.7小結
習題與思考題
第3章神經網路模型
3.1人工神經網路建模
3.1.1MP模型
3.1.2Hebb學習法則
3.2感知器
3.2.1單層感知器
3.2.2多層感知器
3.3BP網路與BP演算法
3.3.1BP網路的基本結構
3.3.2BP演算法及步長調整
3.4自適應線性神經網路
3.5自組織競爭型神經網路
3.5.1自組織競爭型神經網路的基本結構
3.5.2自組織競爭型神經網路的學習演算法
3.6小腦模型神經網路
3.6.1CMAC的基本結構
3.6.2CMAC的工作原理
3.6.3CMAC的學習演算法與訓練
3.7遞歸型神經網路
3.7.1DTRNN的網路結構
3.7.2實時遞歸學習演算法
3.8霍普菲爾德（Hopfield）神經網路
3.8.1離散型Hopfield神經網路
3.8.2連續型Hopfield神經網路
3.8.3求解TSP問題
3.9小結
習題與思考題
第4章神經控制中的系統辨識
4.1系統辨識基本原理
4.1.1辨識系統的基本結構
4.1.2辨識模型
4.1.3辨識系統的輸入和輸出
4.2系統辨識過程中神經網路的作用
4.2.1神經網路辨識原理
4.2.2多層前向網路的辨識能力
4.2.3辨識系統中的非線性模型
4.3非線性動態系統辨識
4.3.1非線性動態系統的神經網路辨識
4.3.2單輸入單輸出非線性動態系統的BP網路辨識
4.4多層前向網路辨識中的快速演算法
4.5非線性模型的預報誤差神經網路辨識
4.5.1非動態模型建模，
4.5.2遞推預報誤差演算法
4.6非線性系統逆模型的神經網路辨識
4.6.1系統分析逆過程的存在性
4.6.2非線性系統的逆模型
4.6.3基於多層感知器的逆模型辨識
4.7線性連續動態系統辨識的參數估計
4.7.1Hopfield網路用於辨識
4.7.2Hopfield網路辨識原理
4.8利用神經網路聯想功能的辨識系統
4.8.1二階系統的性能指標
4.8.2系統辨識器基本結構
4.8.3訓練與辨識操作
4.9小結
習題與思考題
第5章人工神經元控制系統
5.1人工神經元的PID調節功能
5.1.1人工神經元PID動態結構
5.1.2人工神經元閉環系統動態結構
5.2人工神經元PID調節器
5.2.1比例調節元
5.2.2積分調節元
5.2.3微分調節元
5.3人工神經元閉環調節系統
5.3.1系統描述
5.3.2Lyapunov穩定性分析
5.4人工神經元自適應控制系統
5.4.1人工神經元自適應控制系統的基本結構
5.4.2人工神經元自適應控制系統的學習演算法
5.5人工神經元控制系統的穩定性
5.6小結
習題與思考題
第6章神經控制系統
6.1神經控制系統概述
6.1.1神經控制系統的基本結構
6.1.2神經網路在神經控制系統中的作用
6.2神經控制器的設計方法
6.2.1模型參考自適應方法
6.2.2自校正方法
6.2.3內模方法
6.2.4常規控制方法
6.2.5神經網路智能方法
6.2.6神經網路優化設計方法
6.3神經辨識器的設計方法
6.4PID神經控制系統
6.4.1PID神經控制系統框圖
6.4.2PID神經調節器的參數整定
6.5模型參考自適應神經控制系統
6.5.1兩種不同的自適應控制方式
6.5.2間接設計模型參考自適應神經控制系統
6.5.3直接設計模型參考自適應神經控制系統
6.6預測神經控制系統
6.6.1預測控制的基本特徵
6.6.2神經網路預測演算法
6.6.3單神經元預測器
6.6.4多層前向網路預測器
6.6.5輻射基函數網路預測器
6.6.6Hopfield網路預測器
6.7自校正神經控制系統
6.7.1自校正神經控制系統的基本結構
6.7.2神經自校正控制演算法
6.7.3神經網路逼近
6.8內模神經控制系統
6.8.1線性內模控制方式
6.8.2內模控制系統
6.8.3內模神經控制器
6.8.4神經網路內部模型
6.9小腦模型神經控制系統
6.9.1CMAC控制系統的基本結構
6.9.2CMAC控制器設計
6.9.3CMAC控制系統實例
6.10小結
習題與思考題
第7章模糊神經控制系統
7.1模糊控制與神經網路的結合
7.1.1模糊控制的時間復雜性
7.1.2神經控制的空間復雜性
7.1.3模糊神經系統的產生
7.2模糊控制和神經網路的異同點
7.2.1模糊控制和神經網路的共同點
7.2.2模糊控制和神經網路的不同點
7.3模糊神經系統的典型結構
7.4模糊神經系統的結構分類
7.4.1鬆散結合
7.4.2互補結合
7.4.3主從結合
7.4.4串列結合
7.4.5網路學習結合
7.4.6模糊等價結合
7.5模糊等價結合中的模糊神經控制器
7.5.1偏差P和偏差變化率Δe的獲取
7.5.2隸屬函數的神經網路表達
7.6幾種常見的模糊神經網路
7.6.1模糊聯想記憶網路
7.6.2模糊認知映射網路
7.7小結
習題與思考題
第8章神經控制中的遺傳進化訓練
8.1生物的遺傳與進化
8.1.1生物進化論的基本觀點
8.1.2進化計算
8.2遺傳演算法概述
8.2.1遺傳演算法中遇到的基本術語
8.2.2遺傳演算法的運算特徵
8.2.3遺傳演算法中的概率計算公式
8.3遺傳演算法中的模式定理
8.3.1模式定義和模式的階
8.3.2模式定理（Schema）
8.4遺傳演算法中的編碼操作
8.4.1遺傳演算法設計流程
8.4.2遺傳演算法中的編碼規則
8.4.3一維染色體的編碼方法
8.4.4二維染色體編碼
8.5遺傳演算法中的適應度函數
8.5.1將目標函數轉換成適應度函數
8.5.2標定適應度函數
8.6遺傳演算法與優化解
8.6.1適應度函數的確定
8.6.2線性分級策略
8.6.3演算法流程
8.7遺傳演算法與預測控制
8.8遺傳演算法與神經網路
8.9神經網路的遺傳進化訓練
8.9.1遺傳進化訓練的實現方法
8.9.2BP網路的遺傳進化訓練
8.10小結
習題與思考題
附錄常用神經控制術語漢英對照
參考文獻
……

② 迭代法的演算法

迭代是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現這一過程所使用的方法統稱為迭代法（Iterative Method）。
一般可以做如下定義：對於給定的線性方程組（這里的x、B、f同為矩陣，任意線性方程組都可以變換成此形式），用公式 （代表迭代k次得到的x，初始時k=0)逐步帶入求近似解的方法稱為迭代法（或稱一階定常迭代法）。如果存在，記為x*，稱此迭代法收斂。顯然x*就是此方程組的解，否則稱為迭代法發散。
跟迭代法相對應的是直接法（或者稱為一次解法），即一次性的快速解決問題，例如通過開方解決方程x +3= 4。一般如果可能，直接解法總是優先考慮的。但當遇到復雜問題時，特別是在未知量很多，方程為非線性時，我們無法找到直接解法（例如五次以及更高次的代數方程沒有解析解，參見阿貝耳定理），這時候或許可以通過迭代法尋求方程（組）的近似解。
最常見的迭代法是牛頓法。其他還包括最速下降法、共軛迭代法、變尺度迭代法、最小二乘法、線性規劃、非線性規劃、單純型法、懲罰函數法、斜率投影法、遺傳演算法、模擬退火等等。
利用迭代演算法解決問題，需要做好以下三個方面的工作： 例 1 ：一個飼養場引進一隻剛出生的新品種兔子，這種兔子從出生的下一個月開始，每月新生一隻兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，問到第 12 個月時，該飼養場共有兔子多少只？
分析：這是一個典型的遞推問題。我們不妨假設第 1 個月時兔子的只數為 u 1 ，第 2 個月時兔子的只數為 u 2 ，第 3 個月時兔子的只數為 u 3 ，……根據題意，「這種兔子從出生的下一個月開始，每月新生一隻兔子」，則有
u 1 = 1 ， u 2 = u 1 + u 1 × 1 = 2 ， u 3 = u 2 + u 2 × 1 = 4 ，……
根據這個規律，可以歸納出下面的遞推公式：
u n = u(n － 1）× 2 (n ≥ 2）
對應 u n 和 u(n － 1），定義兩個迭代變數 y 和 x ，可將上面的遞推公式轉換成如下迭代關系：
y=x*2
x=y
讓計算機對這個迭代關系重復執行 11 次，就可以算出第 12 個月時的兔子數。參考程序如下：
cls
x=1
for i=2 to 12
y=x*2
x=y
next i
print y
end
例 2 ：阿米巴用簡單分裂的方式繁殖，它每分裂一次要用 3 分鍾。將若干個阿米巴放在一個盛滿營養參液的容器內， 45 分鍾後容器內充滿了阿米巴。已知容器最多可以裝阿米巴 220,220個。試問，開始的時候往容器內放了多少個阿米巴？請編程序算出。
分析：根據題意，阿米巴每 3 分鍾分裂一次，那麼從開始的時候將阿米巴放入容器裡面，到 45 分鍾後充滿容器，需要分裂 45/3=15 次。而「容器最多可以裝阿米巴2^ 20 個」，即阿米巴分裂 15 次以後得到的個數是 2^20。題目要求我們計算分裂之前的阿米巴數，不妨使用倒推的方法，從第 15 次分裂之後的 2^20 個，倒推出第 15 次分裂之前（即第 14 次分裂之後）的個數，再進一步倒推出第 13 次分裂之後、第 12 次分裂之後、……第 1 次分裂之前的個數。
設第 1 次分裂之前的個數為 x 0 、第 1 次分裂之後的個數為 x 1 、第 2 次分裂之後的個數為 x 2 、……第 15 次分裂之後的個數為 x 15 ，則有
x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1）
因為第 15 次分裂之後的個數 x 15 是已知的，如果定義迭代變數為 x ，則可以將上面的倒推公式轉換成如下的迭代公式：
x=x/2 （x 的初值為第 15 次分裂之後的個數 2^20）
讓這個迭代公式重復執行 15 次，就可以倒推出第 1 次分裂之前的阿米巴個數。因為所需的迭代次數是個確定的值，我們可以使用一個固定次數的循環來實現對迭代過程的控制。參考程序如下：
cls
x=2^20
for i=1 to 15
x=x/2
next i
print x
end
ps:java中冪的演算法是Math.pow（2,20）；返回double，稍微注意一下
例 3 ：驗證谷角猜想。日本數學家谷角靜夫在研究自然數時發現了一個奇怪現象：對於任意一個自然數 n ，若 n 為偶數，則將其除以 2 ；若 n 為奇數，則將其乘以 3 ，然後再加 1。如此經過有限次運算後，總可以得到自然數 1。人們把谷角靜夫的這一發現叫做「谷角猜想」。
要求：編寫一個程序，由鍵盤輸入一個自然數 n ，把 n 經過有限次運算後，最終變成自然數 1 的全過程列印出來。
分析：定義迭代變數為 n ，按照谷角猜想的內容，可以得到兩種情況下的迭代關系式：當 n 為偶數時， n=n/2 ；當 n 為奇數時， n=n*3+1。用 QBASIC 語言把它描述出來就是：
if n 為偶數 then
n=n/2
else
n=n*3+1
end if
這就是需要計算機重復執行的迭代過程。這個迭代過程需要重復執行多少次，才能使迭代變數 n 最終變成自然數 1 ，這是我們無法計算出來的。因此，還需進一步確定用來結束迭代過程的條件。仔細分析題目要求，不難看出，對任意給定的一個自然數 n ，只要經過有限次運算後，能夠得到自然數 1 ，就已經完成了驗證工作。因此，用來結束迭代過程的條件可以定義為：n=1。參考程序如下：
cls
input Please input n=;n
do until n=1
if n mod 2=0 then
rem 如果 n 為偶數，則調用迭代公式 n=n/2
n=n/2
print —;n;
else
n=n*3+1
print —;n;
end if
loop
end
迭代法開平方：
#include<stdio.h>
#include<math.h>
void main()
{
double a,x0,x1;
printf(Input a: );
scanf(%lf,&a);//因為a是double型數據，所以要用%lf，而不是%f
if(a<0)
printf(Error! );
else
{
x0=a/2;
x1=(x0+a/x0)/2;
do
{
x0=x1;
x1=(x0+a/x0)/2;
}while(fabs(x0-x1）>=1e-6）；
}
printf(Result: );
printf(sqrt(%g)=%g ,a,x1）；
}
求平方根的迭代公式：x1=1/2*(x0+a/x0）。
演算法：1.先自定一個初值x0，作為a的平方根值，在我們的程序中取a/2作為a的初值；利用迭代公式求出一個x1。此值與真正的a的平方根值相比，誤差很大。
⒉把新求得的x1代入x0中，准備用此新的x0再去求出一個新的x1.
⒊利用迭代公式再求出一個新的x1的值，也就是用新的x0又求出一個新的平方根值x1，此值將更趨近於真正的平方根值。
⒋比較前後兩次求得的平方根值x0和x1，如果它們的差值小於我們指定的值，即達到我們要求的精度，則認為x1就是a的平方根值，去執行步驟5；否則執行步驟2，即循環進行迭代。
迭代法是用於求方程或方程組近似根的一種常用的演算法設計方法。設方程為f(x)=0，用某種數學方法導出等價的形式x=g(x），然後按以下步驟執行：
⑴ 選一個方程的近似根，賦給變數x0；
⑵ 將x0的值保存於變數x1，然後計算g(x1），並將結果存於變數x0；
⑶ 當x0與x1的差的絕對值還小於指定的精度要求時，重復步驟⑵的計算。
若方程有根，並且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。上述演算法用C程序的形式表示為：
【演算法】迭代法求方程的根
{ x0=初始近似根；
do {
x1=x0；
x0=g(x1）； /*按特定的方程計算新的近似根*/
} while (fabs(x0-x1）>Epsilon）；
printf（「方程的近似根是%f 」，x0）；
}
迭代演算法也常用於求方程組的根，令
X=（x0，x1，…，xn-1）
設方程組為：
xi=gi(X) (I=0，1，…，n-1）
則求方程組根的迭代演算法可描述如下：
【演算法】迭代法求方程組的根
{ for (i=0;i
x=初始近似根；
do {
for (i=0;i
y=x;
for (i=0;i
x=gi(X);
for (delta=0.0,i=0;i
if (fabs(y-x)>delta) delta=fabs(y-x）；
} while (delta>Epsilon）；
for (i=0;i
printf（「變數x[%d]的近似根是 %f」，I，x）；
printf（「 」）；
}
具體使用迭代法求根時應注意以下兩種可能發生的情況：
⑴ 如果方程無解，演算法求出的近似根序列就不會收斂，迭代過程會變成死循環，因此在使用迭代演算法前應先考察方程是否有解，並在程序中對迭代的次數給予限制；
⑵ 方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。
遞歸
遞歸是設計和描述演算法的一種有力的工具，由於它在復雜演算法的描述中被經常採用，為此在進一步介紹其他演算法設計方法之前先討論它。
能採用遞歸描述的演算法通常有這樣的特徵：為求解規模為N的問題，設法將它分解成規模較小的問題，然後從這些小問題的解方便地構造出大問題的解，並且這些規模較小的問題也能採用同樣的分解和綜合方法，分解成規模更小的問題，並從這些更小問題的解構造出規模較大問題的解。特別地，當規模N=1時，能直接得解。
【問題】 編寫計算斐波那契（Fibonacci）數列的第n項函數fib（n）。
斐波那契數列為：0、1、1、2、3、……，即：
fib(0)=0;
fib⑴=1;
fib(n)=fib(n-1）+fib(n-2） （當n>1時）。
寫成遞歸函數有：
int fib(int n)
{ if (n==0) return 0;
if (n==1） return 1;
if (n>1） return fib(n-1）+fib(n-2）；
}
遞歸演算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小於n）的求解。例如上例中，求解fib(n），把它推到求解fib(n-1）和fib(n-2）。也就是說，為計算fib(n），必須先計算fib(n-1）和fib(n- 2），而計算fib(n-1）和fib(n-2），又必須先計算fib(n-3）和fib(n-4）。依次類推，直至計算fib⑴和fib(0），分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。
在回歸階段，當獲得最簡單情況的解後，逐級返回，依次得到稍復雜問題的解，例如得到fib⑴和fib(0）後，返回得到fib⑵的結果，……，在得到了fib(n-1）和fib(n-2）的結果後，返回得到fib(n）的結果。
在編寫遞歸函數時要注意，函數中的局部變數和參數知識局限於當前調用層，當遞推進入「簡單問題」層時，原來層次上的參數和局部變數便被隱蔽起來。在一系列「簡單問題」層，它們各有自己的參數和局部變數。
由於遞歸引起一系列的函數調用，並且可能會有一系列的重復計算，遞歸演算法的執行效率相對較低。當某個遞歸演算法能較方便地轉換成遞推演算法時，通常按遞推演算法編寫程序。例如上例計算斐波那契數列的第n項的函數fib(n）應採用遞推演算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項。
【問題】 組合問題
問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。例如n=5，r=3的所有組合為：⑴5、4、3 ⑵5、4、2 ⑶5、4、1
⑷5、3、2 ⑸5、3、1 ⑹5、2、1
⑺4、3、2 ⑻4、3、1 ⑼4、2、1
⑽3、2、1
分析所列的10個組合，可以採用這樣的遞歸思想來考慮求組合函數的演算法。設函數為void comb(int m,int k）為找出從自然數1、2、……、m中任取k個數的所有組合。當組合的第一個數字選定時，其後的數字是從餘下的m-1個數中取k-1數的組合。這就將求m 個數中取k個數的組合問題轉化成求m-1個數中取k-1個數的組合問題。設函數引入工作數組a[ ]存放求出的組合的數字，約定函數將確定的k個數字組合的第一個數字放在a[k]中，當一個組合求出後，才將a[ ]中的一個組合輸出。第一個數可以是m、m-1、……、k，函數將確定組合的第一個數字放入數組後，有兩種可能的選擇，因還未去頂組合的其餘元素，繼續遞歸去確定；或因已確定了組合的全部元素，輸出這個組合。細節見以下程序中的函數comb。
【程序】
# include
# define MAXN 100
int a[MAXN];
void 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--)
printf（「%4d」，a[j]);
printf（「 」）；
}
}
}
void main()
{ a[0]=3;
comb（5,3）；
}
【問題】 背包問題
問題描述：有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。
設n 件物品的重量分別為w0、w1、…、wn-1，物品的價值分別為v0、v1、…、vn-1。採用遞歸尋找物品的選擇方案。設前面已有了多種選擇的方案，並保留了其中總價值最大的方案於數組option[ ]，該方案的總價值存於變數maxv。當前正在考察新方案，其物品選擇情況保存於數組cop[ ]。假定當前方案已考慮了前i-1件物品，現在要考慮第i件物品；當前方案已包含的物品的重量之和為tw；至此，若其餘物品都選擇是可能的話，本方案能達到的總價值的期望值為tv。演算法引入tv是當一旦當前方案的總價值的期望值也小於前面方案的總價值maxv時，繼續考察當前方案變成無意義的工作，應終止當前方案，立即去考察下一個方案。因為當方案的總價值不比maxv大時，該方案不會被再考察，這同時保證函數後找到的方案一定會比前面的方案更好。
對於第i件物品的選擇考慮有兩種可能：
⑴ 考慮物品i被選擇，這種可能性僅當包含它不會超過方案總重量限制時才是可行的。選中後，繼續遞歸去考慮其餘物品的選擇。
⑵ 考慮物品i不被選擇，這種可能性僅當不包含物品i也有可能會找到價值更大的方案的情況。
按以上思想寫出遞歸演算法如下：
try（物品i，當前選擇已達到的重量和，本方案可能達到的總價值tv)
{ /*考慮物品i包含在當前方案中的可能性*/
if（包含物品i是可以接受的）
{ 將物品i包含在當前方案中；
if (i
try(i+1,tw+物品i的重量，tv);
else
/*又一個完整方案，因為它比前面的方案好，以它作為最佳方案*/
以當前方案作為臨時最佳方案保存；
恢復物品i不包含狀態；
}
/*考慮物品i不包含在當前方案中的可能性*/
if （不包含物品i僅是可男考慮的）
if (i
try(i+1,tw,tv-物品i的價值）；
else
/*又一個完整方案，因它比前面的方案好，以它作為最佳方案*/
以當前方案作為臨時最佳方案保存；
}
為了理解上述演算法，特舉以下實例。設有4件物品，它們的重量和價值見表：
物品 0 1 2 3
重量 5 3 2 1
價值 4 4 3 1
並設限制重量為7。則按以上演算法，下圖表示找解過程。由圖知，一旦找到一個解，演算法就進一步找更好的佳。如能判定某個查找分支不會找到更好的解，演算法不會在該分支繼續查找，而是立即終止該分支，並去考察下一個分支。
按上述演算法編寫函數和程序如下：
【程序】
# include
# define N 100
double limitW,totV,maxV;
int option[N],cop[N];
struct { double weight;
double value;
}a[N];
int n;
void find(int i,double tw,double tv)
{ int k;
/*考慮物品i包含在當前方案中的可能性*/
if (tw+a.weight<=limitW)
{ cop=1;
if (i
else
{ for (k=0;k
option[k]=cop[k];
maxv=tv;
}
cop=0;
}
/*考慮物品i不包含在當前方案中的可能性*/
if (tv-a.value>maxV)
if (i
else
{ for (k=0;k
option[k]=cop[k];
maxv=tv-a.value;
}
}
void main()
{ int k;
double w,v;
printf（「輸入物品種數 」）；
scanf（（「%d」，&n);
printf（「輸入各物品的重量和價值 」）；
for (totv=0.0,k=0;k
{ scanf（「%1f%1f」，&w,&v);
a[k].weight=w;
a[k].value=v;
totV+=V;
}
printf（「輸入限制重量 」）；
scanf（「%1f」，&limitV);
maxv=0.0;
for (k=0;k find(0,0.0,totV);
for (k=0;k
if (option[k]) printf（「%4d」，k+1）；
printf（「 總價值為%.2f 」，maxv);
}
作為對比，下面以同樣的解題思想，考慮非遞歸的程序解。為了提高找解速度，程序不是簡單地逐一生成所有候選解，而是從每個物品對候選解的影響來形成值得進一步考慮的候選解，一個候選解是通過依次考察每個物品形成的。對物品i的考察有這樣幾種情況：當該物品被包含在候選解中依舊滿足解的總重量的限制，該物品被包含在候選解中是應該繼續考慮的；反之，該物品不應該包括在當前正在形成的候選解中。同樣地，僅當物品不被包括在候選解中，還是有可能找到比目前臨時最佳解更好的候選解時，才去考慮該物品不被包括在候選解中；反之，該物品不包括在當前候選解中的方案也不應繼續考慮。對於任一值得繼續考慮的方案，程序就去進一步考慮下一個物品。
【程序】
# include
# define N 100
double limitW;
int cop[N];
struct ele { double weight;
double value;
} a[N];
int k,n;
struct { int ;
double tw;
double tv;
}twv[N];
void next(int i,double tw,double tv)
{ twv.=1;
twv tw=tw;
twv tv=tv;
}
double find(struct ele *a,int n)
{ int i,k,f;
double maxv,tw,tv,totv;
maxv=0;
for (totv=0.0,k=0;k
totv+=a[k].value;
next(0,0.0,totv);
i=0;
While (i>=0)
{ f=twv.;
tw=twv tw;
tv=twv tv;
switch(f)
{ case 1: twv.++;
if (tw+a.weight<=limitW)
if (i
{ next(i+1,tw+a.weight,tv);
i++;
}
else
{ maxv=tv;
for (k=0;k
cop[k]=twv[k].!=0;
}
break;
case 0: i--;
break;
default: twv.=0;
if (tv-a.value>maxv)
if (i
{ next(i+1,tw,tv-a.value);
i++;
}
else
{ maxv=tv-a.value;
for (k=0;k
cop[k]=twv[k].!=0;
}
break;
}
}
return maxv;
}
void main()
{ double maxv;
printf（「輸入物品種數 」）；
scanf（（「%d」，&n);
printf（「輸入限制重量 」）；
scanf（「%1f」，&limitW);
printf（「輸入各物品的重量和價值 」）；
for (k=0;k
scanf（「%1f%1f」，&a[k].weight,&a[k].value);
maxv=find(a,n);
printf（「 選中的物品為 」）；
for (k=0;k
if (option[k]) printf（「%4d」，k+1）；
printf（「 總價值為%.2f 」，maxv);
}

③ 簡述演算法的定義和特徵以及它在c語言編程中如何使用的

一、什麼是演算法

演算法是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。演算法常常含有重復的步驟和一些比較或邏輯判斷。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

演算法的時間復雜度是指演算法需要消耗的時間資源。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time Complexity）。時間復雜度用「O（數量級）」來表示，稱為「階」。常見的時間復雜度有： O（1）常數階；O（log2n）對數階；O（n）線性階；O（n2）平方階。

演算法的空間復雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。

二、演算法設計的方法

1.遞推法

遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。設要求問題規模為N的解，當N=1時，解或為已知，或能非常方便地得到解。能採用遞推法構造演算法的問題有重要的遞推性質，即當得到問題規模為i-1的解後，由問題的遞推性質，能從已求得的規模為1，2，…，i-1的一系列解，構造出問題規模為I的解。這樣，程序可從i=0或i=1出發，重復地，由已知至i-1規模的解，通過遞推，獲得規模為i的解，直至得到規模為N的解。

④ 迭代學習控制的簡介

迭代學習控制（iterative learning control，簡稱ILC）由Uchiyama於1978年首先提出，不過因為論文由日文撰寫，影響不是很大。1984年，Arimoto等人用英文介紹了該方法。它是指不斷重復一個同樣軌跡的控制嘗試，並以此修正控制律，以得到非常好的控制效果的控制方法。
迭代學習控制是學習控制的一個重要分支，是一種新型學習控制策略。它通過反復應用先前試驗得到的信息來獲得能夠產生期望輸出軌跡的控制輸入，以改善控制質量。與傳統的控制方法不同的是，迭代學習控制能以非常簡單的方式處理不確定度相當高的動態系統，且僅需較少的先驗知識和計算量，同時適應性強，易於實現；更主要的是，它不依賴於動態系統的精確數學模型，是一種以迭代產生優化輸入信號，使系統輸出盡可能逼近理想值的演算法。它的研究對那些有著非線性、復雜性、難以建模以及高精度軌跡控制問題有著非常重要的意義。
.

⑤ 什麼叫演算法演算法有哪幾種表示方法

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。計算機科學家往往將「演算法」一詞的含義限定為此類「符號演算法」。「演算法」概念的初步定義：一個演算法是解決一個問題的進程。而並不需要每次都發明一個解決方案。

已知的演算法有很多，例如「分治法」、「枚舉測試法」、「貪心演算法」、「隨機演算法」等。

(5)迭代學習演算法的定義擴展閱讀

演算法中的「分治法」

「分治法」是把一個復雜的問題拆分成兩個較為簡單的子問題，進而兩個子問題又可以分別拆分成另外兩個更簡單的子問題，以此類推。問題不斷被層層拆解。然後，子問題的解被逐層整合，構成了原問題的解。

高德納曾用過一個郵局分發信件的例子對「分治法」進行了解釋：信件根據不同城市區域被分進不同的袋子里；每個郵遞員負責投遞一個區域的信件，對應每棟樓，將自己負責的信件分裝進更小的袋子；每個大樓管理員再將小袋子里的信件分發給對應的公寓。

⑥ 迭代學習控制的學習因子怎麼確定

迭代學習管控計算分析及在機械臂之應用
作者:lgg
本文是機械工程論文，目前，ILC的研究已經取得了很多成果，本文在此基礎上對ILC作了進一步的探討和研究，針對如何提高迭代學習的收斂速度設計了新的學習演算法，理論分析了演算法的

第 1 章 緒 論

1.1 引言
隨著科學技術的發展以及生產力水平的提高，人們對一些復雜的、不確定的系統的控制要求不斷提高。我們在生產實際中遇到的系統大多存在著非線性、強耦合以及不確定性等特點，從而導致系統的精確模型無從獲取。因此，採用傳統的基於模型的控制方法不能很好的對這些系統進行控制。智能控制應運而生，自 20 世紀 70年代形成至今不過 40 多年的時間，但其發展勢頭卻異常迅猛。學習控制是智能控制的一個高級分支，相對於傳統的智能控制方法而言，它具備了自己學習的能力。1978 年 Uchiyama[1]提出了一種控制高速運行的機械手的思想，此思想描述為：重復地對同一個運動軌跡進行跟蹤控制，與此同時不斷地調節控制律，依此便可以達到較好的控制效果。1984 年，Arimoto 等人在 Uchiyama 對機器人控制研究的基礎之上，提出了迭代學習控制(ILC)的概念。迭代學習控制方法是利用控制系統之前得到的控制經驗，並根據系統以往的控制輸入信號、實際輸出信號以及期望信號來尋找理想的控制輸入信號。這里我們把以往的信息看成一種經驗，迭代學習是利用經驗知識使得被控對象產生期望的運動，由此不僅削弱了對模型的依賴，還改進了跟蹤控制的性能。由於迭代學習控制自身的特點，比如要求系統較少的先驗知識以及較少的計算量，並且一般情況下無需辨識系統的參數，因此能處理未知參數以及不確定性等復雜問題，同時還具備了很好的魯棒性。這些特點使得迭代學習控制方法適用於一類機器人或其它機械裝置系統，為其基於自主學習來調整運動性能提供了一種較好的方法。因此，它的研究對像機器人那樣有著高度的非線性、難建模、強耦合等特點的系統實現高精度軌跡跟蹤控制有著非常重要的實際意義。
………………

1.2 課題的研究背景及意義
迭代學習控制理論的提出是以工業機器人的跟蹤控制為背景的，在實際的生產過程中，各種不確定因素的存在導致我們無法獲得系統的精確數學模型，因此傳統的以系統的數學模型為基礎的分析方法便無法較好的解決這些實際問題。隨著科技的發展和生產的需要，人們越來越關注如何採用合適的方法來處理實際中存在的不確定性問題，以期達到較好的跟蹤控制效果。在實際的生產過程中，普遍存在著不斷重復的控制過程，如包裝機的包裝過程，零部件批量生產的過程，機械手重復完成某種操作的過程等等。以包裝機的工作過程為例，其包裝過程就是一個典型的不斷重復操作的過程，如果被包裝物品的重量、尺寸以及其它相關參數都相同，就相當於假設了每次運行時的初始條件相同，那麼整個包裝機的運動軌跡就會基本上是完全一致。對於這樣一類具有重復運動性質的被控對象，運用迭代學習控制能起到很好的控制效果。迭代學習控制不要求已知系統的精確模型，而是利用已有的先驗知識不斷地進行學習，也就是說，它是利用在重復中學習的方法，最終實現在有限時間區間上對期望軌跡的完全跟蹤。它較為簡單的形式以及廣泛的實用價值引起了人們的大量關注。與此同時，怎樣解決迭代學習演算法的初始狀態問題以及如何加快迭代學習的收斂速度成為很多學者研究的熱點問題。如果系統能在較短的時間內實現對期望軌跡的跟蹤有著較高的實用價值。
……………

第 2 章 迭代學習控制的理論基礎

2.1 迭代學習控制的基本原理
機器人的誕生有著劃時代的意義，它的發展為人類文明的進步作出了卓越的貢獻，人們對機器人技術的研究也形成了一門新的學科——機器人學。它是一門綜合性學科，其發展離不開機械電子學、仿生學、控制理論、信息科學、人工智慧等學科。機器人的發展過程可以分為三個階段，1959 年世界上第一台工業機器人問世，它是美國人英格伯格和德沃爾共同研製的成果，它的誕生標志著機器人歷史的開始，同時它也是機器人成長的第一個階段。第一批工業機器人被稱為「尤尼梅特」，具有「萬能自動」的含義。1962 年生產出的工業機器人，命名為「沃爾薩特蘭」，有著「萬能搬動」的意思。「尤尼梅特」和「沃爾薩特蘭」也因此被認為是世界上最早的工業機器人，並且沿用至今。1970 年左右，第二代機器人產生，他們開始了外界環境的實用階段，同時得到了較好的普及。隨著智能控制等學科的發展，機器人不僅具備了「感知」能力，還具有獨立判斷和行動的能力，與此同時，它們還具備了記憶、推理和決策的能力，從而能夠完成一些復雜的動作。這些機器人被稱為第三代機器人，即智能機器人。如今，智能機器人被廣泛應用於各行各業，不僅節約了大量的人力物力，同時提高了作業效率。機器人的應用情況體現了一個國家的綜合國力。工業機器人在我國僅有 20 多年的發展歷史，我國曾研發並製造出一系列工業機器人，如噴塗機器人、氬弧焊機器人、裝卸載機器人等，並成功投入使用。雖然我國對機器人的研究起步晚，但現在也已走上了進步和發展的道路，與此同時我們也應該看到，與國外機器人的研究相比我們還有很長的路要走。今後我們要加深基礎學科的研究，開展跨國區域交流合作，理論聯系實際應用，爭取早日躋身於世界先進之列。
……………

2.2 迭代學習控制過程的表述
本章主要對迭代學習控製作了理論上的介紹，詳細介紹了迭代學習的基本原理，迭代學習控制過程的表述以及迭代學習演算法的流程。最後，為迭代學習收斂性分析所用理論及數學知識作了介紹，迭代學習演算法在收斂性證明時常用到 Banach 空間，向量和矩陣范數，λ 范數，Bellman-Gronwall 引理以及 Lipschitz 條件。這些理論知識都為後續學習律的設計，收斂性分析以及模擬研究等工作奠定了理論基礎。目前，智能控制在機器人控制中應用最多的是神經網路控制和模糊控制。神經網路具有容錯性、自學習和自適應等特點，因此在控制機器人時不要求機器人的精確數學模型，從而引起學者們的極大關注。模糊控制是以模糊數學、模糊語言形式以及模糊邏輯規則推理為基礎的控制科學，模糊控制系統是利用計算機控制技術構成閉環結構的一種智能控制系統。它亦不需要建立被控對象的精確數學模型，因此能對具有高度非線性，無精確數學模型的機器人系統進行有效控制。
……………

第 3 章 機器人指數變增益快速迭代學習控制........20
3.1 引言 ....... 20
3.2 系統描述 ..... 21
3.3 主要結果 ..... 22
3.3.1 新演算法的提出 ........ 22
3.3.2 考慮機械臂轉角限位時演算法的改進 ........ 22
3.4 收斂性分析 ....... 23
3.5 模擬研究 ..... 26
3.6 本章小結 ..... 29
第 4 章 帶擾動的非線性系統的快速迭代學習控制......31
4.1 引言 ....... 31
4.2 問題的描述 ....... 32
4.3 主要結果 ..... 33
4.4 收斂性證明 ....... 34
4.5 模擬研究 ..... 36
4.6 本章小結 ..... 38
第 5 章 具有可變遺忘因子的迭代學習演算法.....39
5.1 引言 ....... 39
5.2 新演算法的提出 ......... 39
5.3 主要結果 ..... 41
5.4 可變遺忘因子的設計 ......... 44
5.5 系統模型轉換 ......... 45
5.6 模擬研究 ..... 46
5.7 本章小結 ..... 48

第5章 具有可變遺忘因子的迭代學習演算法及在機械臂中的應用

5.1 引言
ILC 演算法自 1984 年由 Arimoto 等人提出以來就一直受到控制界的廣泛關注。它適用於一類具有重復運動特性的被控對象，其任務是尋找最優的控制輸入，使得被控系統的實際輸出軌跡在有限時間區間上實現與期望輸出軌跡的完全跟蹤[66]。文獻[67]對於重復運行的被控系統，設計了開環 P 型以及閉環 P 型迭代學習控制器，實現了在有限時間區間內對期望軌跡的跟蹤。文獻[68]中採用的開閉環 PD 型迭代學習律，與 P 型學習律相比增加了誤差信息量，提高了收斂速度，但因導數信號的引入增加了測量難度。文獻[67,68]的學習律都是因果型迭代學習律，即利用前一次迭代的t時刻的誤差信息來調節下一次t時刻的學習律。文獻[55]中綜述了因果型迭代學習律與非因果型迭代學習律的區別，即非因果型學習律是利用前一次迭代中未來時刻的誤差信息來調節學習律，非因果型學習律由於利用了前次迭代的未來時刻的誤差信息，使得控制器具有提前補償未來擾動的功能。文獻[69]提出了帶有遺忘因子的迭代學習律，削弱了系統模型不確定部分和非重復干擾對系統收斂性的影響，但文獻中引入的遺忘因子被設為固定常數，從而不能隨系統特性的變化而實時調整，使得迭代學習律無法得到令人滿意的收斂效果。針對以上問題，本文提出了具有可變遺忘因子的非因果型迭代學習演算法。該演算法不要求迭代初態與期望初態一致，並且能利用前一次迭代控制中未來時刻的誤差信息來調整下一次的控制律，既增加了信息量又避免了導數信號的使用；同時，引入的可變遺忘因子能根據系統特性的變化自行調節學習律，很好的處理了跟蹤速度和穩態誤差的矛盾。本文所提新演算法兼備了 D 型控制演算法的超前性和 P 型控制演算法易於執行的特性。
………………

結 論

ILC 不要求已知被控對象的精確數學模型，並且只需系統較少的先驗知識，從而引起學者們的廣泛關注和探討。本文對迭代學習控制的收斂速度問題進行了深入研究，主要開展了以下工作：
(1)對於含有初始誤差的機器人的軌跡跟蹤問題，首先將機器人系統的動力學方程轉化為狀態方程，然後採用指數變增益的非因果型迭代學習演算法對其進行控制。學習增益在迭代過程中有效的變化，從而加快了迭代學習的收斂速度。
(2)由於迭代學習演算法不需要精確的數學模型，且對未建模的系統有一定的魯棒性，由此本文針對具有狀態擾動和輸出干擾的一類非線性系統的軌跡跟蹤問題，採用了帶角度修正的 ILC 演算法。用輸出向量的角度關系作為反饋系數，用來判斷控制輸入好壞，依此對學習律的變化趨勢做出「獎懲」，因此收斂速度得到了有效提高。
(3)對於一般的非線性系統，採用了一種具有可變遺忘因子的非因果型迭代學習演算法。非因果型迭代學習律相比於因果型學習律在迭代過程中使用了未來時刻的誤差信息，不僅增加了信息量還使得控制器具有提前補償未來擾動的功能；引入可變的遺忘因子可以根據系統所處的狀態有效的調節控制輸入同時沿迭代方向進行濾波，從而加快了收斂速度，並削弱了系統的不確定部分對收斂性的影響。最後將此方法應用於機械臂的軌跡跟蹤控制，達到了較好的收斂效果。
……………
參考文獻（略）

⑦ 什麼是演算法，它的五大特性是什麼，演算法和程序的關系是什麼

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。
一個演算法應該具有以下五個重要的特徵：
有窮性（Finiteness）
演算法的有窮性是指演算法必須能在執行有限個步驟之後終止；
確切性(Definiteness)
演算法的每一步驟必須有確切的定義；
輸入項(Input)
一個演算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件；
輸出項(Output)
一個演算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的演算法是毫無意義的；
可行性(Effectiveness)
演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）。
演算法和程序的關系是：
演算法就是程序的靈魂，一個需要實現特定功能的程序，實現它的演算法可以有很多種，所以演算法的優劣決定著程序的好壞。
程序就是遵循一定規則的、為完成指定工作而編寫的代碼。有一個經典的等式闡明了什麼叫程序：程序
=
演算法
+
數據結構
+
程序設計方法
+
語言工具和環境
。

⑧ 迭代學習控制演算法和傳統PID相比哪個抗干擾性更好一些

迭代學習控制演算法只能應用在干擾小或者干擾重復出現的情況下，如果新來一個系統未知的新型干擾，系統要重新學習，在學習過程中系統剛度會受影響。而當系統學習完成後，如果此類干擾不再出現，系統白學啦。
傳統的PID控制方法是對寬域的干擾都有免疫力，並且不要時刻調整，缺點是當控制對象發生變化後，系統仍然使用老PID參數（這當然已經不是最優的參數了），導致對象可控性變壞。
問開環與閉環的問題，開來你控制還沒有入門，好好學吧。

⑨ 演算法的定義

演算法（algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

⑩ 迭代法是什麼

迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執行，在每次執行這組指令（或這些步驟）時，都從變數的原值推出它的一個新值。

利用迭代演算法解決問題，需要做好以下三個方面的工作：

一、確定迭代變數。在可以用迭代演算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變數，這個變數就是迭代變數。

二、建立迭代關系式。所謂迭代關系式，指如何從變數的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。

三、對迭代過程進行控制。在什麼時候結束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對於前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對於後一種情況，需要進一步分析出用來結束迭代過程的條件。

例 1 ： 一個飼養場引進一隻剛出生的新品種兔子，這種兔子從出生的下一個月開始，每月新生一隻兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，問到第 12 個月時，該飼養場共有兔子多少只？

分析： 這是一個典型的遞推問題。我們不妨假設第 1 個月時兔子的只數為 u 1 ，第 2 個月時兔子的只數為 u 2 ，第 3 個月時兔子的只數為 u 3 ，……根據題意，「這種兔子從出生的下一個月開始，每月新生一隻兔子」，則有

u 1 ＝ 1 ， u 2 ＝ u 1 ＋ u 1 × 1 ＝ 2 ， u 3 ＝ u 2 ＋ u 2 × 1 ＝ 4 ，……

根據這個規律，可以歸納出下面的遞推公式：

u n ＝ u n － 1 × 2 (n ≥ 2)

對應 u n 和 u n － 1 ，定義兩個迭代變數 y 和 x ，可將上面的遞推公式轉換成如下迭代關系：

y=x*2

x=y

讓計算機對這個迭代關系重復執行 11 次，就可以算出第 12 個月時的兔子數。參考程序如下：

cls

x=1

for i=2 to 12

y=x*2

x=y

next i

print y

end

例 2 ： 阿米巴用簡單分裂的方式繁殖，它每分裂一次要用 3 分鍾。將若干個阿米巴放在一個盛滿營養參液的容器內， 45 分鍾後容器內充滿了阿米巴。已知容器最多可以裝阿米巴 2 20 個。試問，開始的時候往容器內放了多少個阿米巴？請編程序算出。

分析： 根據題意，阿米巴每 3 分鍾分裂一次，那麼從開始的時候將阿米巴放入容器裡面，到 45 分鍾後充滿容器，需要分裂 45/3=15 次。而「容器最多可以裝阿米巴 2 20 個」，即阿米巴分裂 15 次以後得到的個數是 2 20 。題目要求我們計算分裂之前的阿米巴數，不妨使用倒推的方法，從第 15 次分裂之後的 2 20 個，倒推出第 15 次分裂之前（即第 14 次分裂之後）的個數，再進一步倒推出第 13 次分裂之後、第 12 次分裂之後、……第 1 次分裂之前的個數。

設第 1 次分裂之前的個數為 x 0 、第 1 次分裂之後的個數為 x 1 、第 2 次分裂之後的個數為 x 2 、……第 15 次分裂之後的個數為 x 15 ，則有

x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1)

因為第 15 次分裂之後的個數 x 15 是已知的，如果定義迭代變數為 x ，則可以將上面的倒推公式轉換成如下的迭代公式：

x=x/2 （ x 的初值為第 15 次分裂之後的個數 2 20 ）

讓這個迭代公式重復執行 15 次，就可以倒推出第 1 次分裂之前的阿米巴個數。因為所需的迭代次數是個確定的值，我們可以使用一個固定次數的循環來實現對迭代過程的控制。參考程序如下：

cls

x=2^20

for i=1 to 15

x=x/2

next i

print x

end

例 3 ： 驗證谷角猜想。日本數學家谷角靜夫在研究自然數時發現了一個奇怪現象：對於任意一個自然數 n ，若 n 為偶數，則將其除以 2 ；若 n 為奇數，則將其乘以 3 ，然後再加 1 。如此經過有限次運算後，總可以得到自然數 1 。人們把谷角靜夫的這一發現叫做「谷角猜想」。

要求：編寫一個程序，由鍵盤輸入一個自然數 n ，把 n 經過有限次運算後，最終變成自然數 1 的全過程列印出來。

分析： 定義迭代變數為 n ，按照谷角猜想的內容，可以得到兩種情況下的迭代關系式：當 n 為偶數時， n=n/2 ；當 n 為奇數時， n=n*3+1 。用 QBASIC 語言把它描述出來就是：

if n 為偶數 then

n=n/2

else

n=n*3+1

end if

這就是需要計算機重復執行的迭代過程。這個迭代過程需要重復執行多少次，才能使迭代變數 n 最終變成自然數 1 ，這是我們無法計算出來的。因此，還需進一步確定用來結束迭代過程的條件。仔細分析題目要求，不難看出，對任意給定的一個自然數 n ，只要經過有限次運算後，能夠得到自然數 1 ，就已經完成了驗證工作。因此，用來結束迭代過程的條件可以定義為： n=1 。參考程序如下：

cls

input "Please input n=";n

do until n=1

if n mod 2=0 then

rem 如果 n 為偶數，則調用迭代公式 n=n/2

n=n/2

print "—";n;

else

n=n*3+1

print "—";n;

end if

loop

end

迭代法

迭代法是用於求方程或方程組近似根的一種常用的演算法設計方法。設方程為f(x)=0，用某種數學方法導出等價的形式x=g(x)，然後按以下步驟執行：
（1） 選一個方程的近似根，賦給變數x0；
（2） 將x0的值保存於變數x1，然後計算g(x1)，並將結果存於變數x0；
（3） 當x0與x1的差的絕對值還小於指定的精度要求時，重復步驟（2）的計算。
若方程有根，並且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。上述演算法用C程序的形式表示為：
【演算法】迭代法求方程的根
{ x0=初始近似根；
do {
x1=x0；
x0=g(x1)； /*按特定的方程計算新的近似根*/
} while ( fabs(x0-x1)>Epsilon)；
printf(「方程的近似根是%f\n」，x0)；
}
迭代演算法也常用於求方程組的根，令
X=（x0，x1，…，xn-1）
設方程組為：
xi=gi(X) (I=0，1，…，n-1)
則求方程組根的迭代演算法可描述如下：
【演算法】迭代法求方程組的根
{ for (i=0;i
x=初始近似根;
do {
for (i=0;i
y=x;
for (i=0;i
x=gi(X);
for (delta=0.0,i=0;i
if (fabs(y-x)>delta) delta=fabs(y-x)；
} while (delta>Epsilon)；
for (i=0;i
printf(「變數x[%d]的近似根是 %f」，I，x)；
printf(「\n」)；
}
具體使用迭代法求根時應注意以下兩種可能發生的情況：
（1） 如果方程無解，演算法求出的近似根序列就不會收斂，迭代過程會變成死循環，因此在使用迭代演算法前應先考察方程是否有解，並在程序中對迭代的次數給予限制；
（2） 方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。
遞歸

遞歸是設計和描述演算法的一種有力的工具，由於它在復雜演算法的描述中被經常採用，為此在進一步介紹其他演算法設計方法之前先討論它。
能採用遞歸描述的演算法通常有這樣的特徵：為求解規模為N的問題，設法將它分解成規模較小的問題，然後從這些小問題的解方便地構造出大問題的解，並且這些規模較小的問題也能採用同樣的分解和綜合方法，分解成規模更小的問題，並從這些更小問題的解構造出規模較大問題的解。特別地，當規模N=1時，能直接得解。
【問題】 編寫計算斐波那契（Fibonacci）數列的第n項函數fib（n）。
斐波那契數列為：0、1、1、2、3、……，即：
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2) （當n>1時）。
寫成遞歸函數有：
int fib(int n)
{ if (n==0) return 0;
if (n==1) return 1;
if (n>1) return fib(n-1)+fib(n-2);
}
遞歸演算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小於n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n- 2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。
在回歸階段，當獲得最簡單情況的解後，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)後，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果後，返回得到fib(n)的結果。
在編寫遞歸函數時要注意，函數中的局部變數和參數知識局限於當前調用層，當遞推進入「簡單問題」層時，原來層次上的參數和局部變數便被隱蔽起來。在一系列「簡單問題」層，它們各有自己的參數和局部變數。
由於遞歸引起一系列的函數調用，並且可能會有一系列的重復計算，遞歸演算法的執行效率相對較低。當某個遞歸演算法能較方便地轉換成遞推演算法時，通常按遞推演算法編寫程序。例如上例計算斐波那契數列的第n項的函數fib(n)應採用遞推演算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項。
【問題】 組合問題
問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。例如n=5，r=3的所有組合為： （1）5、4、3 （2）5、4、2 （3）5、4、1
（4）5、3、2 （5）5、3、1 （6）5、2、1
（7）4、3、2 （8）4、3、1 （9）4、2、1
（10）3、2、1
分析所列的10個組合，可以採用這樣的遞歸思想來考慮求組合函數的演算法。設函數為void comb(int m,int k)為找出從自然數1、2、……、m中任取k個數的所有組合。當組合的第一個數字選定時，其後的數字是從餘下的m-1個數中取k-1數的組合。這就將求m 個數中取k個數的組合問題轉化成求m-1個數中取k-1個數的組合問題。設函數引入工作數組a[ ]存放求出的組合的數字，約定函數將確定的k個數字組合的第一個數字放在a[k]中，當一個組合求出後，才將a[ ]中的一個組合輸出。第一個數可以是m、m-1、……、k，函數將確定組合的第一個數字放入數組後，有兩種可能的選擇，因還未去頂組合的其餘元素，繼續遞歸去確定；或因已確定了組合的全部元素，輸出這個組合。細節見以下程序中的函數comb。
【程序】
# include
# define MAXN 100
int a[MAXN];
void 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--)
printf(「%4d」,a[j]);
printf(「\n」);
}
}
}

void main()
{ a[0]=3;
comb(5,3);
}
【問題】 背包問題
問題描述：有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。
設n 件物品的重量分別為w0、w1、…、wn-1，物品的價值分別為v0、v1、…、vn-1。採用遞歸尋找物品的選擇方案。設前面已有了多種選擇的方案，並保留了其中總價值最大的方案於數組option[ ]，該方案的總價值存於變數maxv。當前正在考察新方案，其物品選擇情況保存於數組cop[ ]。假定當前方案已考慮了前i-1件物品，現在要考慮第i件物品；當前方案已包含的物品的重量之和為tw；至此，若其餘物品都選擇是可能的話，本方案能達到的總價值的期望值為tv。演算法引入tv是當一旦當前方案的總價值的期望值也小於前面方案的總價值maxv時，繼續考察當前方案變成無意義的工作，應終止當前方案，立即去考察下一個方案。因為當方案的總價值不比maxv大時，該方案不會被再考察，這同時保證函數後找到的方案一定會比前面的方案更好。
對於第i件物品的選擇考慮有兩種可能：
（1） 考慮物品i被選擇，這種可能性僅當包含它不會超過方案總重量限制時才是可行的。選中後，繼續遞歸去考慮其餘物品的選擇。
（2） 考慮物品i不被選擇，這種可能性僅當不包含物品i也有可能會找到價值更大的方案的情況。
按以上思想寫出遞歸演算法如下：
try(物品i，當前選擇已達到的重量和，本方案可能達到的總價值tv)
{ /*考慮物品i包含在當前方案中的可能性*/
if(包含物品i是可以接受的)
{ 將物品i包含在當前方案中；
if (i
try(i+1,tw+物品i的重量,tv);
else
/*又一個完整方案，因為它比前面的方案好，以它作為最佳方案*/
以當前方案作為臨時最佳方案保存;
恢復物品i不包含狀態；
}
/*考慮物品i不包含在當前方案中的可能性*/
if (不包含物品i僅是可男考慮的)
if (i
try(i+1,tw,tv-物品i的價值)；
else
/*又一個完整方案，因它比前面的方案好，以它作為最佳方案*/
以當前方案作為臨時最佳方案保存;
}
為了理解上述演算法，特舉以下實例。設有4件物品，它們的重量和價值見表：
物品 0 1 2 3
重量 5 3 2 1
價值 4 4 3 1

並設限制重量為7。則按以上演算法，下圖表示找解過程。由圖知，一旦找到一個解，演算法就進一步找更好的佳。如能判定某個查找分支不會找到更好的解，演算法不會在該分支繼續查找，而是立即終止該分支，並去考察下一個分支。

按上述演算法編寫函數和程序如下：
【程序】
# include
# define N 100
double limitW,totV,maxV;
int option[N],cop[N];
struct { double weight;
double value;
}a[N];
int n;
void find(int i,double tw,double tv)
{ int k;
/*考慮物品i包含在當前方案中的可能性*/
if (tw+a.weight<=limitW)
{ cop=1;
if (i
else
{ for (k=0;k
option[k]=cop[k];
maxv=tv;
}
cop=0;
}
/*考慮物品i不包含在當前方案中的可能性*/
if (tv-a.value>maxV)
if (i
else
{ for (k=0;k
option[k]=cop[k];
maxv=tv-a.value;
}
}

void main()
{ int k;
double w,v;
printf(「輸入物品種數\n」);
scanf((「%d」,&n);
printf(「輸入各物品的重量和價值\n」);
for (totv=0.0,k=0;k
{ scanf(「%1f%1f」,&w,&v);
a[k].weight=w;
a[k].value=v;
totV+=V;
}
printf(「輸入限制重量\n」);
scanf(「%1f」,&limitV);
maxv=0.0;
for (k=0;k find(0,0.0,totV);
for (k=0;k
if (option[k]) printf(「%4d」,k+1);
printf(「\n總價值為%.2f\n」,maxv);
}
作為對比，下面以同樣的解題思想，考慮非遞歸的程序解。為了提高找解速度，程序不是簡單地逐一生成所有候選解，而是從每個物品對候選解的影響來形成值得進一步考慮的候選解，一個候選解是通過依次考察每個物品形成的。對物品i的考察有這樣幾種情況：當該物品被包含在候選解中依舊滿足解的總重量的限制，該物品被包含在候選解中是應該繼續考慮的；反之，該物品不應該包括在當前正在形成的候選解中。同樣地，僅當物品不被包括在候選解中，還是有可能找到比目前臨時最佳解更好的候選解時，才去考慮該物品不被包括在候選解中；反之，該物品不包括在當前候選解中的方案也不應繼續考慮。對於任一值得繼續考慮的方案，程序就去進一步考慮下一個物品。
【程序】
# include
# define N 100
double limitW;
int cop[N];
struct ele { double weight;
double value;
} a[N];
int k,n;
struct { int ;
double tw;
double tv;
}twv[N];
void next(int i,double tw,double tv)
{ twv.=1;
twv.tw=tw;
twv.tv=tv;
}
double find(struct ele *a,int n)
{ int i,k,f;
double maxv,tw,tv,totv;
maxv=0;
for (totv=0.0,k=0;k
totv+=a[k].value;
next(0,0.0,totv);
i=0;
While (i>=0)
{ f=twv.;
tw=twv.tw;
tv=twv.tv;
switch(f)
{ case 1: twv.++;
if (tw+a.weight<=limitW)
if (i
{ next(i+1,tw+a.weight,tv);
i++;
}
else
{ maxv=tv;
for (k=0;k
cop[k]=twv[k].!=0;
}
break;
case 0: i--;
break;
default: twv.=0;
if (tv-a.value>maxv)
if (i
{ next(i+1,tw,tv-a.value);
i++;
}
else
{ maxv=tv-a.value;
for (k=0;k
cop[k]=twv[k].!=0;
}
break;
}
}
return maxv;
}

void main()
{ double maxv;
printf(「輸入物品種數\n」);
scanf((「%d」,&n);
printf(「輸入限制重量\n」);
scanf(「%1f」,&limitW);
printf(「輸入各物品的重量和價值\n」);
for (k=0;k
scanf(「%1f%1f」,&a[k].weight,&a[k].value);
maxv=find(a,n);
printf(「\n選中的物品為\n」);
for (k=0;k
if (option[k]) printf(「%4d」,k+1);
printf(「\n總價值為%.2f\n」,maxv);
}

遞歸的基本概念和特點
程序調用自身的編程技巧稱為遞歸（ recursion）。
一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。
一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
注意：
(1) 遞歸就是在過程或函數里調用自身;
(2) 在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。