順推法編程

A. 背包問題的演算法

3.2 背包問題
背包問題有三種

1.部分背包問題

一個旅行者有一個最多能用m公斤的背包，現在有n種物品，它們的總重量分別是W1，W2，...,Wn,它們的總價值分別為C1,C2,...,Cn.求旅行者能獲得最大總價值。

解決問題的方法是貪心演算法:將C1/W1,C2/W2,...Cn/Wn,從大到小排序,不停地選擇價值與重量比最大的放人背包直到放滿為止.

2.0/1背包

一個旅行者有一個最多能用m公斤的背包，現在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價值分別為C1,C2,...,Cn.若每種物品只有一件求旅行者能獲得最大總價值。

<1>分析說明:

顯然這個題可用深度優先方法對每件物品進行枚舉(選或不選用0,1控制).

程序簡單,但是當n的值很大的時候不能滿足時間要求，時間復雜度為O（2n）。按遞歸的思想我們可以把問題分解為子問題,使用遞歸函數

設 f(i，x)表示前i件物品，總重量不超過x的最優價值

則 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））

f（n，m）即為最優解，邊界條件為f（0，x）＝0 ，f(i,0)=0;

動態規劃方法(順推法)程序如下:

程序如下：

program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;

for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.

使用二維數組存儲各子問題時方便，但當maxm較大時如maxn=2000時不能定義二維數組f,怎麼辦,其實可以用一維數組,但是上述中j:=1 to m 要改為j:=m downto 1,為什麼?請大家自己解決。

3.完全背包問題

一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,

每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.

求旅行者能獲得的最大總價值。

本問題的數學模型如下：

設 f(x)表示重量不超過x公斤的最大價值，

則 f(x）=max{f(x-w[i])+c[i]} 當x>=w[i] 1<=i<=n

程序如下:（順推法）

program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
f(0):=0;
for i:=1 to m do
for j:=1 to n do
begin
if i>=w[j] then t:=f[i-w[j]]+c[j];
if t>f[i] then f[i]:=t
end;
writeln(f[m]);
end.

B. 在C語言中，什麼是迭代法

迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程，跟迭代法相對應的是直接法，即一次性解決問題。迭代法又分為精確迭代和近似迭代。「二分法」和「牛頓迭代法」屬於近似迭代法。迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執行，在每次執行這組指令（或這些步驟）時，都從變數的原值推出它的一個新值。

迭代是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現這一過程所使用的方法統稱為迭代法（Iterative Method）。

一般可以做如下定義：對於給定的線性方程組x=Bx+f（這里的x、B、f同為矩陣，任意線性方程組都可以變換成此形式），用公式x(k+1）=Bx(k)+f（括弧中為上標，代表迭代k次得到的x，初始時k=0)逐步帶入求近似解的方法稱為迭代法（或稱一階定常迭代法）。如果k趨向無窮大時limx（k）存在，記為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:\n");

scanf("%lf",&a);//為什麼在VC6.0中不能寫成「scanf("%f",&a）；」？

if(a<0)

printf("Error!\n");

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:\n");

printf("sqrt(%g)=%g\n",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\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」）；

}

具體使用迭代法求根時應注意以下兩種可能發生的情況：

⑴ 如果方程無解，演算法求出的近似根序列就不會收斂，迭代過程會變成死循環，因此在使用迭代演算法前應先考察方程是否有解，並在程序中對迭代的次數給予限制；

⑵ 方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。

遞歸

遞歸是設計和描述演算法的一種有力的工具，由於它在復雜演算法的描述中被經常採用，為此在進一步介紹其他演算法設計方法之前先討論它。

能採用遞歸描述的演算法通常有這樣的特徵：為求解規模為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（「\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件物品的選擇考慮有兩種可能：

⑴ 考慮物品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（「輸入物品種數\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);

}

C. 運籌學動態規劃關於最短路問題用逆推法和順推法差不多吧，用逆推法要寫很多…

差不多的，就好像是對換了起點和終點。最短路的問題用dijkstra演算法是最簡單的！動態規劃解決資源分配和背包問題用逆推法！

D. pascal取數游戲（遞推） 遞推是什麼意思如何用遞推公式編程

別聽他的廢話，任何循環都可以是遞推，如輸入n，求1+2+3+4+5+……+n
var
i,n,sum:longint;
begin
sum:=0;
readln(n);
for i:=1 to n do
inc(sum,i);
write(sum);
readln
end;
這就是一個遞推，也就是說for i:=a to b都是遞推
至於你說的取數游戲，似乎是用遞推演算法來解這道題

E. 遞推演算法是怎麼回事

遞推定義
遞推演算法是一種簡單的演算法，即通過已知條件，利用特定關系得出中間推論，直至得到結果的演算法。

遞推演算法分為順推和逆推兩種。

順推法
所謂順推法是從已知條件出發，逐步推算出要解決的問題的方法叫順推。

如斐波拉契數列，設它的函數為f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。則我們通過順推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我們要求的解。

逆推法
所謂逆推法從已知問題的結果出發，用迭代表達式逐步推算出問題的開始的條件，即順推法的逆過程，稱為逆推。

遞推與遞歸的比較
相對於遞歸演算法,遞推演算法免除了數據進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.

比如階乘函數：f(n)=n*f(n-1)

在f(3)的運算過程中,遞歸的數據流動過程如下:

f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}

而遞推如下:

f(0)-->f(1)-->f(2)-->f(3)

由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意.

F. 我是PASCAL的菜鳥，動態規劃學的一塌糊塗，希望各位大俠指導一下動規要怎麼做

1.1 多階段決策過程的最優化問題
1、問題的提出

首先，例舉一個典型的且很直觀的多階段決策問題:
[例] 下圖表示城市之間的交通路網，線段上的數字表示費用，單向通行由A->E。求A->E的最省費用。

如圖從A到E共分為4個階段，即第一階段從A到B，第二階段從B到C，第三階段從C到D，第四階段從D到E。除起點A和終點E外，其它各點既是上一階段的終點又是下一階段的起點。例如從A到B的第一階段中，A為起點，終點有B1，B2，B3三個，因而這時走的路線有三個選擇，一是走到B1，一是走到B2，一是走到B3。若選擇B2的決策，B2就是第一階段在我們決策之下的結果，它既是第一階段路線的終點，又是第二階段路線的始點。在第二階段，再從B2點出發，對於B2點就有一個可供選擇的終點集合(C1，C2，C3)；若選擇由B2走至C2為第二階段的決策，則C2就是第二階段的終點，同時又是第三階段的始點。同理遞推下去，可看到各個階段的決策不同，線路就不同。很明顯，當某階段的起點給定時，它直接影響著後面各階段的行進路線和整個路線的長短，而後面各階段的路線的發展不受這點以前各階段的影響。故此問題的要求是：在各個階段選取一個恰當的決策，使由這些決策組成的一個決策序列所決定的一條路線，其總路程最短。具體情況如下：

（1）由目標狀態E向前推，可以分成四個階段，即四個子問題。如上圖所示。

（2）策略：每個階段到E的最省費用為本階段的決策路徑。

（3）D1，D2是第一次輸人的結點。他們到E都只有一種費用，在D1框上面標5，D2框上面標2。目前無法定下，那一個點將在全程最優策略的路徑上。第二階段計算中，5，2都應分別參加計算。
（4）C1，C2，C3是第二次輸入結點，他們到D1，D2各有兩種費用。此時應計算C1，C2，C3分別到E的最少費用。
C1的決策路徑是 min{（C1D1），（C1D2）}。計算結果是C1+D1+E，在C1框上面標為8。
同理C2的決策路徑計算結果是C2+D2+E，在C2框上面標為7。
同理C3的決策路徑計算結果是C3+D2+E，在C3框上面標為12。
此時也無法定下第一，二階段的城市那二個將在整體的最優決策路徑上。
（5）第三次輸入結點為B1，B2，B3，而決策輸出結點可能為C1，C2，C3。仿前計算可得Bl，B2，B3的決策路徑為如下情況。
Bl:B1C1費用 12+8=20， 路徑:B1+C1+D1+E
B2:B2C1費用 6+8=14， 路徑:B2+C1+D1+E
B3:B2C2費用 12+7=19， 路徑:B3+C2+D2+E
此時也無法定下第一，二，三階段的城市那三個將在整體的最優決策路徑上。
（6）第四次輸入結點為A，決策輸出結點可能為B1，B2，B3。同理可得決策路徑為
A：AB2，費用5+14=19，路徑 A+B2+C1+D1+E。
此時才正式確定每個子問題的結點中，那一個結點將在最優費用的路徑上。19將結果顯然這種計算方法，符合最優原理。子問題的決策中，只對同一城市（結點）比較優劣。而同一階段的城市（結點）的優劣要由下一個階段去決定。
1.2 動態規劃的概念
在上例的多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有「動態」的含義，稱這種解決多階段決策最優化問題的方法為動態規劃方法。

與窮舉法相比，動態規劃的方法有兩個明顯的優點:
(1)大大減少了計算量
(2)豐富了計算結果
從上例的求解結果中，我們不僅得到由A點出發到終點E的最短路線及最短距離，而且還得到了從所有各中間點到終點的最短路線及最短距離，這對許多實際問題來講是很有用的。

動態規劃的最優化概念是在一定條件下，我到一種途徑，在對各階段的效益經過按問題具體性質所確定的運算以後，使得全過程的總效益達到最優。
應用動態規劃要注意階段的劃分是關鍵，必須依據題意分析，尋求合理的劃分階段(子問題)方法。而每個子問題是一個比原問題簡單得多的優化問題。而且每個子問題的求解中，均利用它的一個後部子問題的最優化結果，直到最後一個子問題所得最優解，它就是原問題的最優解。
1.3 動態規劃適合解決什麼樣的問題
准確地說，動態規劃不是萬能的，它只適於解決一定條件的最優策略問題。
或許，大家聽到這個結論會很失望：其實，這個結論並沒有削減動態規劃的光輝，因為屬於上面范圍內的問題極多，還有許多看似不是這個范圍中的問題都可以轉化成這類問題。
上面所說的「滿足一定條件」主要指下面兩點：
(1)狀態必須滿足最優化原理；
(2)狀態必須滿足無後效性。
動態規劃的最優化原理是無論過去的狀態和決策如何，對前面的決策所形成的當前狀態而言，餘下的諸決策必須構成最優策略。 可以通俗地理解為子問題的局部最優將導致整個問題的全局最優在上例中例題1最短路徑問題中，A到E的最優路徑上的任一點到終點E的路徑也必然是該點到終點E的一條最優路徑，滿足最優化原理。

動態規劃的無後效性原則某階段的狀態一旦確定，則此後過程的演變不再受此前各狀態及決策的影響。也就是說，「未來與過去無關」，當前的狀態是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。具體地說，如果一個問題被劃分各個階段之後，階段 I 中的狀態只能由階段 I+1 中的狀態通過狀態轉移方程得來，與其他狀態沒有關系，特別是與未發生的狀態沒有關系，這就是無後效性。

1.1 多階段決策過程的最優化問題
1、問題的提出

首先，例舉一個典型的且很直觀的多階段決策問題:
[例] 下圖表示城市之間的交通路網，線段上的數字表示費用，單向通行由A->E。求A->E的最省費用。

2.1 為什麼要用動態規劃法解題
首先，看下面一個問題:

【例題1】數字三角形問題。

7

3 8

8 1 0

2 7 7 4

5 5 2 6 5

示出了一個數字三角形寶塔。數字三角形中的數字為不超過100的正整數。現規定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。假設三角形行數≤100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經過的數字的總和最大，輸出最大值。輸人數據：由文件輸入數據，文件第一行是三角形的行數N。以後的N行分別是從最頂層到最底層的每一層中的數字。
如輸入： 5
7
3 8
8 1 0
2 7 7 4
4 5 2 6 5
輸出：30
【分析】對於這一問題，很容易想到用枚舉的方法（深度搜索法）去解決，即列舉出所有路徑並記錄每一條路徑所經過的數字總和。然後尋找最大的數字總和，這一想法很直觀，很容易編程實現其程序如下：

program sjx;
const maxn=10;
var
a:array[1..maxn,1..maxn] of integer;
max:longint;
n,i,j:integer;
fname:string;

inputf:text;

procere try(x,y,dep:integer;sum:longint);
begin
if (dep=n) then
begin
if sum>max then max:=sum;
exit
end;
try(x+1,y,dep+1,sum+a[x+1,y]);
try(x+1,y+1,dep+1,sum+a[x+1,y+1]);
end;
begin
readln(fname);

assign(inputf,fname);

reset(inputf);

readln(inputf,n);
for i:=1 to n do
for j:= 1 to i do
read(inputf,a[i,j]);
max:=0;
try(1,1,1,a[1,1]);
writeln(max);
end.

但是當行數很大時，當三角形的行數等於100時，其枚舉量之大是可想而知的，用枚舉法肯定超時，甚至根本不能得到計算結果，必須用動態規劃法來解。
2.2 怎樣用動態規劃法解題
1.逆推法:

按三角形的行劃分階段，若行數為 n，則可把問題看做一個n-1個階段的決策問題。先求出第n-1階段(第n-1行上各點)到第n行的的最大和，再依次求出第n-2階段、第n-3階段……第1階段(起始點)各決策點至第n行的最佳路徑。
設：f[i,j]為從第i階段中的點j至第n行的最大的數字和；
則: f[n,j]=a[n,j] 1<=j<=n

f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]} 1<=j<=i.

f[1,1]即為所求。

程序如下：

program datasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn,1..maxn] of integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
for j:=1 to i do
read(inputf,a[i,j]);
for i:=1 to n do
f[n,i]:=a[n,i];
for i:=n-1 downto 1 do
for j:=1 to i do
if f[i+1,j]>f[i+1,j+1] then f[i,j]:=a[i,j]+f[i+1,j]
else f[i,j]:=a[i,j]+f[i+1,j+1];
writeln(f[1,1]);
end.

2. 順推法

按三角形的行劃分階段，若行數為 n，則可把問題看做一個n-1個階段的決策問題。先求第2行各元素到起點的最大和

,再依次求出第3,4，5,......,.n-1,n到起點的最大和,最後找第n行的最大值

設f[i,j]為 第i行第j列上點到起點的最大和

則 f[1，1]=a[1,1];

f[i，1]=a[i, 1]+f[i-1,1];

f[ i，j ]=max{ a[i,j]+f[i-1,j-1],a[i,j]+f[i-1,j]} 2<=j<=i

max(f[n,1],f[n,2],.......,f[n,n]}即為所求。

程序如下：

program datasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn,1..maxn] of integer;
maxsum:integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
for j:=1 to i do
read(inputf,a[i,j]);
fillchar(f,sizeof(f),0);

f[1,1]:=a[1,1];
for i:=2 to n do
begin
f[i,1]:=a[i,1]+f[i-1,1];
for j:=2 to i do
if f[i-1,j-1]>f[i-1,j] then f[i,j]:=a[i,j]+f[i-1,j-1]
else f[i,j]:=a[i,j]+f[i-1,j];
end;
maxsum:=0;
for i:=1 to n do
if f[n,i]>maxsum then maxsum:=f[n,i];
writeln(maxsum);
end.

說明一下：

1.用動態規劃解題主要思想是用空間換時間.

2.本題如果n較大，用2維數組空間可能不夠,可以使用1維數組.

程序如下:

program datasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn] of integer;
maxsum:integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
for j:=1 to i do
read(inputf,a[i,j]);
fillchar(f,sizeof(f),0);
f[1]:=a[1,1];
for i:=2 to n do
begin
for j:=i downto 2 do
if f[j-1]>f[j] then f[j]:=a[i,j]+f[j-1]
else f[j]:=a[i,j]+f[j];
f[1]:=a[i,1]+f[1];
end;
maxsum:=0;
for i:=1 to n do
if f[i]>maxsum then maxsum:=f[i];
writeln(maxsum);
end.

練習:用一維數組和逆推法解本題.

2.3 用動態規劃法解題的一般模式

動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。如圖所示。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。
┌———┐┌———┐┌———┐
初始狀態→│決策1│→│決策2│→…→│決策n│→結束狀態
└———┘└———┘└———┘
(1)劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。在劃分階段時，注意劃分後的階段一定要是有序的或者是可排序的，否則問題就無法求解。
(2)確定狀態和狀態變數：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
(3)確定決策並寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩段各狀態之間的關系來確定決策。
(4)尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。
(5)程序設計實現：動態規劃的主要難點在於理論上的設計，一旦設計完成，實現部分就會非常簡單。
根據上述動態規劃設計的步驟，可得到大體解題框架如下:

1.初始化(邊界條件)

2.for i:=2 to n (順推法) 或 for i:=n-1 to 1(逆推法)

對i階段的每一個決策點求局部最優

3.確定和輸出結束狀態的值.

G. 1加2等於25,2加3等於36,3加4等於47,4加5等於多少

4加5等於58。

1+2＝25

2+3＝36

3+4＝47

每一項都是比前一項多11，也就是1+2＝3＝25，2+3＝5＝36，3+4=47，也就是說36比25多11，47比36多11，由此得出4+5=58。

順推法是從已知條件出發，逐步推算出要解決的問題的方法叫順推。

如斐波拉契數列，設它的函數為f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。則我們通過順推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我們要求的解。

逆推法從已知問題的結果出發，用迭代表達式逐步推算出問題的開始的條件，即順推法的逆過程，稱為逆推。

(7)順推法編程擴展閱讀

編程語言中，函數Func(Type a,……)直接或間接調用函數本身，則該函數稱為遞歸函數。遞歸函數不能定義為內聯函數。

在數學上，關於遞歸函數的定義如下：對於某一函數f(x)，其定義域是集合A，那麼若對於A集合中的某一個值X0，其函數值f(x0)由f(f(x0))決定，那麼就稱f(x)為遞歸函數。

一個含直接或間接調用本函數語句的函數被稱之為遞歸函數，在上面的例子中能夠看出，它必須滿足以下兩個條件：

1） 在每一次調用自己時，必須是（在某種意義上）更接近於解；

2） 必須有一個終止處理或計算的准則。

H. 定量背包PASCAL

如果K是未指定的，
f(m,volume) = 0 m=0時
f(m,volume) = f(m-1,volume) volume-vol[m]<0時
f(m,volume)
= max { value[m]+f(m-1,volume-vol[m]) , f(m-1,volume) }
f(m,volume)指從編號為1到m的物品中選取總體積不超過volume的物品所能達到的最大價值。
f(N,V)即為所求。

如果K是指定的，
f(m,L,volume)
= max { value[m]+f(m-1,L-1,volume-vol[m]) , f(m-1,L，volume)}
f(m,L,volume) = 0 l=0或m<l時
f(m,L,volume) = f(m-1,L，volume) volume-vol[m]<0時
f(m,L,volume)指從編號為1到m的物品中選取總體積不超過volume的L個物品所能達到的最大價值。
f(N,K,V)即為所求。
至於記錄選取物品情況，可以用字元串或數組記錄。如N=8，現在從1到6中選，如果選取6，從1到5中選取的結果是00001010，不選6，從1到5中選取的結果是00010011，那麼就看00101010（第6位置1）和00010011哪個的價值大，便把所求的f和相應的串作為返回值。
有很多地方重復計算了，可以優化剪枝，不過程序就會比較復雜了。

補充：

我說的K未指定時的方法實際上就是6樓所用到的方法，從編號為1到i的物品中取出總體積不超過t的物品使得總價值最大，無非分兩種情形，一種是不取物品n，從1到n-1中選取總體積不超過t的物品使價值最大；另一種是選取物品i，然後從1到i-1中選取總體積不超過t-tt[i]的物品使價值最大。這兩種情況中總價值更大的那個即為所求。

本來這是要用遞歸來完成的，非遞歸方法則要用到棧，但是若每個物品的體積都是正整數的話，則可以用遞推方法來完成。6樓正是用的此種方法。

二重循環中，外層循環是物品編號1到N，內層循環是體積V到0，其中i=k一個循環下來，數組b[]的每個元素b[j]中存儲了從物品1到k中選取物品使得體積之和剛好為j，所能達到的最大價值，若a[j]=false，則表示無法選取物品組合使得體積之和恰好為j，此時相對應的b[j]=0。

例如物品5的體積為tt[5]=8，價值為w[5]=13，i=4循環結束時，b[8]=0，b[28]=46，b[29]=0，b[36]=55，那麼i=5循環結束後，由於a[0]=true，於是a[0+tt[5]]即a[8]=true，b[8]顯然由原來的0變為15，b[28]+w[5]=59>b[28+tt[5]]=55，於是b[36]變為59，而a[29]=false，b[29]=0，因而a[37]和b[37]保持不變。最後i=N循環結束後，b[1]到b[V]z中的最大者，即為所求。

若是體積不是整數，使精確到小數點後兩位的數，可以將物品體積和指定的V全部擴大100倍，化為整數問題來解決。

6樓程序里的判斷語句中的(j+tt[i]<=t) 一項可以去掉，但是數組a[]、b[]的范圍要重新設，因為最後j+tt[i]會達到所有N個物品的總體積。最後仍在b[1]到b[V]中去最大值，超過V的那些b[]不理。

7樓的方法則是要求價值p為正整數，外層循環仍然是物品編號，內層循環則是價值p從P到0，P為所有物品的總價值。

思路如下，從編號為1到k的物品中取出總價值不低於p的物品使得總體積最小，同樣分取和不取物品k兩種情形，取兩種情形中體積小者。

程序實現和6樓類似，只不過b[]換成f[p]，表示從1到k中選取物品使價值之和恰好為p，所能達到的最小體積。外層最後一輪循環k=N結束後，從f[1]到f[P]中尋找小於V的那些f[p]，其中最大的那個p極為所求。

取法記錄：C中可以用數組、結構、枚舉來記錄。比如對於6樓的方法，增設一個M[V][N]記錄取法。M[35][]={1，0，1，0，0，...0，1，0}表示取第1、3、N-1個物品，這三個物品的體積之和為35，上面舉例中b[8]和b[36]發生改變，於是M[8][]和M[36][]要相應改變，即M[8][5]和M[36][5]由0遍1，這里5代表第五個元素，不是按C的習慣代表第六個元素。

K指定的話方法其實是一樣的，分兩種情況討論。我最早學的BASIC，後來就是C，pascal泛泛瀏覽過，沒寫過pascal程序，現在是能讀不能寫。只好說明大致的思路如下：

value[1]到value[N]，vol[1]到vol[N]為物品價值，體積，V為背包體積，K為要取的物品個數。

if L=0 or m<L then return 0 and return pickup=none //要取0個物品或是要取物品數大於剩餘物品數當然是只有什麼都不取了

if volume-vol[m]<0 then f(m,L,volume) = f(m-1,L，volume) return f and pickup //物品m體積大於剩餘空間，只有考慮不取物品m，從1到m-1中取L件的情況了，pickup不變

f(m,L,volume) = max { value[m]+f(m-1,L-1,volume-vol[m]) , f(m-1,L，volume)} //以上兩種情況都不成立的話，那麼就分兩種情況了，一是去m，從1到m-1中取L-1件，一是不取m,從1到m-1中取L件

return f and pickup //f(m-1,L，volume)大的話則pickup即為f(m-1,L，volume)返回的pickup,否則pickup為f(m-1,L-1,volume-vol[m])返回的pickup進行修改，把物品m標記為選取。

f(N.K,V)即為所求最大價值，返回的pickup為取法。

pascal程序應該是個function f()函數吧，主程序直接對value、vol、V等初始化，然後調用f(N,K,V)。由於函數進行了遞歸，在N增大時所要求的空間和時間會很大。如果用非遞歸的方法會稍好，可以用分支定界法剪枝，比如不取5，從1到4中選取的結果已經求出，而選取了5，不選4，現在從1到3中取，v不超過6.4，而前面算1到4時已經有了1到3，v不超過7.1的結果，這個結果加上5的價值都不如前面算的1到4的結果，更不用說v不超過6.4了，因此就不用繼續計算1到3，v不超過6.4的結果了。不過這樣將需要更多的變數保存中間結果，即搜索樹上的中間結點，程序也將復雜化。

上面所有的討論都沒有考慮有多解的情形，如果取1、2、6和取2、4都是總體積58，總價值97，且為最優解，則上面的所有方法都只能得到其中一組解，如果要得到所有解，需要對保存取法的變數進行改動，通常建立一個索引即可。M[1]到M[V]可以作為V個指向鏈表的指針，如果v=28有三組解，可以用num[28]=3保存或是保存在M[28]指向的鏈表的頭結點。上面所謂的a[m]為true或false也不用了，num[m]=0(此時M[m]指向null)或者M[m]指向的頭結點是個單結點。其實無需記錄解的數目，v=36的解變更時，自然會讀取v=28的解的鏈表，從頭讀到尾。

I. 做數學題的方法

1、學數學最重要的就是解題能力

要想會做數學題目，就要有大量的練習積累，知道各類型題目的解題步驟與方法，題目做多了就有手感了，再拿出類似的題目才會有解題思路。

2、其次是學會預習

解題思路不是直接就有的，也並非通過做幾道簡單的題目就能輕易獲得，而是在預習過程中不斷積累出來的。因此，預習在數學學習過程中起到了非常重要的作用。預習一方面能夠讓大家提前對數學知識有所了解，另一方面能夠培養數學獨立學習能力。

3、學數學必須多做題

理解了數學基本定義和知識點以後，就需要通過做對應習題去鞏固知識，多做多練才能更好地掌握所學知識，學數學也是看花容易綉花難的，只有真正動手去做題、經歷了實操過程能學會。

4、做完題要學會總結

對於做過的題型及做錯的題目要善於進行分類總結，再遇到類似的題目要會分析，知道哪裡容易出現問題，然後盡量去避免。同時在做題和總結過程中，要學會舉一反三，抓住考點去復習。

5、學數學要會看書和查缺補漏

數學基礎考點都來源於課本，大家之所以覺得書沒什麼可看，是因為對教材掌握程度不夠。書上的每個定義都要理解後倒背如流，深究每個詞語的含義，做懂每個例題，會推導數學公式及變形公式。

做數學題目方法不唯一，只要是邏輯合理、能一步步推導出結論的方法都可以，不必拘泥於老師講授的方法。做數學小題也可以採用畫圖、試值法、代入法等去做，只要沉下心去研究，功夫不負有心人，數學總能夠學好。

J. 什麼是遞推法和遞歸法兩者在思想上有何聯系

1、遞推法：遞推演算法是一種根據遞推關系進行問題求解的方法。通過已知條件，利用特定的遞推關系可以得出中間推論，直至得到問題的最終結果。遞推演算法分為順推法和逆推法兩種。 

2、遞歸法：在計算機編程中，一個函數在定義或說明中直接或間接調用自身的編程技巧稱為遞歸。通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸做為一種演算法在程序設計語言中廣泛應用。 

3、兩者的聯系：在問題求解思想上，遞推是從已知條件出發，一步步的遞推出未知項，直到問題的解。從思想上講，遞歸也是遞推的一種，只不過它是對待解問題的遞推，直到把一個復雜的問題遞推為簡單的易解問題。然後再一步步的返回去，從而得到原問題的解。 

(10)順推法編程擴展閱讀

相對於遞歸演算法,遞推演算法免除了數據進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值。

比如階乘函數：f(n)=n*f(n-1)  

在f(3)的運算過程中,遞歸的數據流動過程如下:   f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}  

而遞推如下:   f(0)-->f(1)-->f(2)-->f(3)   由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推。

但是遞歸作為比較基礎的演算法,它的作用不能忽視。所以,在把握這兩種演算法的時候應該特別注意。