演算法順推法填表

⑴ 數列遞推演算法的原理

什麼是遞推
所謂遞推，是指從已知的初始條件出發，依據某種遞推關系，逐次推出所要求的各中間結果及最後結果。其中初始條件或是問題本身已經給定，或是通過對問題的分析與化簡後確定。
從已知條件出發逐步推到問題結果，此種方法叫順推。
從問題出發逐步推到已知條件，此種方法叫逆推。
無論順推還是逆推，其關鍵是要找到遞推式。這種處理問題的方法能使復雜運算化為若干步重復的簡單運算，充分發揮出計算機擅長於重復處理的特點。
遞推法是一種重要的數學方法，在數學的各個領域中都有廣泛的運用，也是計算機用於數值計算的一個重要演算法。
遞推演算法的首要問題是得到相鄰的數據項間的關系（即遞推關系）。遞推演算法避開了求通項公式的麻煩，把一個復雜的問題的求解，分解成了連續的若干步簡單運算。一般說來，可以將遞推演算法看成是一種特殊的迭代演算法。

遞推的特點
可用遞推演算法求解的題目一般有以下兩個特點：
1、問題可以劃分成多個狀態；
2、除初始狀態外，其它各個狀態都可以用固定的遞推關系式來表示。
在我們實際解題中，題目不會直接給出遞推關系式，而是需要通過分析各種狀態，找出遞推關系式。

【例1】數字三角形。
如下所示為一個數字三角形。請編一個程序計算從頂到底的某處的一條路徑，使該路徑所經過的數字總和最大。只要求輸出總和。

1、 一步可沿左斜線向下或右斜線向下走；
2、 三角形行數小於等於100；
3、 三角形中的數字為0，1，…，99；
測試數據通過鍵盤逐行輸入，如上例數據應以如下所示格式輸入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【演算法分析】
此題解法有多種，從遞推的思想出發，設想，當從頂層沿某條路徑走到第i層向第i+1層前進時，我們的選擇一定是沿其下兩條可行路徑中最大數字的方向前進，為此，我們可以採用倒推的手法，設a[i][j]存放從i,j 出發到達n層的最大值，則a[i][j]=max{a[i][j]+a[i+1][j]，a[i][j]+a[i+1][j+1]}，a[1][1] 即為所求的數字總和的最大值。

//【參考程序】
#include<iostream>
using namespace std;
int main(){
int n,i,j,a[101][101];
cin>>n;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
cin>>a[i][j]; //輸入數字三角形的值
for (i=n-1;i>=1;i--)
for (j=1;j<=i;j++)
{
if (a[i+1][j]>=a[i+1][j+1]) a[i][j]+=a[i+1][j]; //路徑選擇
else a[i][j]+=a[i+1][j+1];
}
cout<<a[1][1]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
思考
如果要輸出最大和的路徑該怎麼處理呢？

【例2】 骨牌問題
有2 × n的一個長方形方格，用一個1 × 2的骨牌鋪滿方格。
編寫一個程序，試對給出的任意一個n(n>0), 輸出鋪法總數。
【演算法分析】
（1）面對上述問題，如果思考方法不恰當，要想獲得問題的解答是相當困難的。可以用遞推方法歸納出問題解的一般規律。
（2）當n=1時，只能是一種鋪法，鋪法總數有示為x1=1。
（3）當n=2時：骨牌可以兩個並列豎排，也可以並列橫排，再無其他方法，如下左圖所示，因此，鋪法總數表示為x2=2；

（4）當n=3時：骨牌可以全部豎排，也可以認為在方格中已經有一個豎排骨牌，則需要在方格中排列兩個橫排骨牌（無重復方法），若已經在方格中排列兩個橫排骨牌，則必須在方格中排列一個豎排骨牌。如上右圖，再無其他排列方法，因此鋪法總數表示為x3=3。
由此可以看出，當n=3時的排列骨牌的方法數是n=1和n=2排列方法數的和

⑵ 遞推演算法是怎麼回事

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

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

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

如斐波拉契數列，設它的函數為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)

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

⑶ 請教元旦干支、年干支推演算法

1，年元旦干支的求法是：以本年元旦干支為基礎，求下一年的元旦干支，本年若為平年，則本年元旦干支加五，即得下一年的元旦干支；本年若為閏年，則本年元旦干支加六，即得下一年的年元旦干支。

⑷ 什麼是演算法，都什麼，舉個例子，謝謝

根據我個人的理解：
演算法就是解決問題的具體的方法和步驟，所以具有以下性質：

1、有窮性： 一個演算法必須保證執行有限步之後結束（如果步驟無限，問題就無法解決）
2、確切性：步驟必須明確，說清楚做什麼。
3、輸入：即解決問題前我們所掌握的條件。
4、輸出：輸出即我們需要得到的答案。
5、可行性：邏輯不能錯誤，步驟必須有限，必須得到結果。

演算法通俗的講：就是解決問題的方法和步驟。在計算機發明之前便已經存在。只不過在計算機發明後，其應用變得更為廣泛。通過簡單的演算法，利用電腦的計算速度，可以讓問題變得簡單。

譬如：計算 1×2×3×4。。。。×999999999×1000000000
如果人為計算，可想而知，即使你用N卡車的紙張都很難計算出來，即使算出來了，也很難保證其准確性。
如果用VB演算法：
dim a as integer
a=1
For i =1 to 1000000000
a=a*i
next i
input a
就這樣，簡單的演算法，通過計算機強大的計算能力，問題就解決了。
關於這段演算法的解釋：i每乘一次，其數值都會增大1，一直乘到1000000000，這樣，就將從1到1000000000的每個數都乘了。而且每乘一次，就將結束賦給a,這樣，a就代表了前面的相乘的所有結果，一直乘到1000000000。最後得到的a，就是我們想要的。

〓以下是網路復制過來的，如果你有足夠耐心，可以參考一下。

演算法（Algorithm）是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
演算法可以理解為有基本運算及規定的運算順序所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列，並且這樣的步驟和序列可以解決一類問題。
一個演算法應該具有以下五個重要的特徵：
1、有窮性： 一個演算法必須保證執行有限步之後結束；
2、確切性： 演算法的每一步驟必須有確切的定義；
3、輸入：一個演算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定除了初始條件；
4、輸出：一個演算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的演算法是毫無意義的；
5、可行性： 演算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算後即可完成。
計算機科學家尼克勞斯-沃思曾著過一本著名的書《數據結構十演算法= 程序》，可見演算法在計算機科學界與計算機應用界的地位。
[編輯本段]演算法的復雜度
同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。
時間復雜度
演算法的時間復雜度是指演算法需要消耗的時間資源。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法的時間復雜度也因此記做
T(n)=Ο(f(n))
因此，問題的規模n 越大，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time Complexity）。
空間復雜度
演算法的空間復雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。
詳見網路詞條"演算法復雜度"
[編輯本段]演算法設計與分析的基本方法
1.遞推法
遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關系，從而達到目的，此方法稱為遞推法。
2.遞歸
遞歸指的是一個過程：函數不斷引用自身，直到引用的對象已知
3.窮舉搜索法
窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，並從眾找出那些符合要求的候選解作為問題的解。
4.貪婪法
貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。
5.分治法
把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。
6.動態規劃法
動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。
7.迭代法
迭代是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現這一過程所使用的方法統稱為迭代法。
[編輯本段]演算法分類
演算法可大致分為基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、並行演算法。
[編輯本段]舉例
經典的演算法有很多，如："歐幾里德演算法"。
[編輯本段]演算法經典專著
目前市面上有許多論述演算法的書籍，其中最著名的便是《計算機程序設計藝術》（The Art Of Computer Programming) 以及《演算法導論》（Introction To Algorithms）。
[編輯本段]演算法的歷史
「演算法」即演演算法的大陸中文名稱出自《周髀算經》；而英文名稱Algorithm 來自於9世紀波斯數學家al-Khwarizmi，因為al-Khwarizmi在數學上提出了演算法這個概念。「演算法」原為"algorism"，意思是阿拉伯數字的運演算法則，在18世紀演變為"algorithm"。歐幾里得演算法被人們認為是史上第一個演算法。 第一次編寫程序是Ada Byron於1842年為巴貝奇分析機編寫求解解伯努利方程的程序，因此Ada Byron被大多數人認為是世界上第一位程序員。因為查爾斯·巴貝奇(Charles Babbage)未能完成他的巴貝奇分析機，這個演算法未能在巴貝奇分析機上執行。 因為"well-defined procere"缺少數學上精確的定義，19世紀和20世紀早期的數學家、邏輯學家在定義演算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題，並提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了演算法定義的難題，圖靈的思想對演算法的發展起到了重要作用的。

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

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

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

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

(5)演算法順推法填表擴展閱讀

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

比如階乘函數：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)   由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推。

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

⑹ 遞推法比較大小

默認第一個數是最大（小）值，然後讓第一個與其餘的比較，將大的值賦值給第一個數，繼續進行比較。當一個數比其他數都大時結束遞歸。返回的第一個數，就是最大(小)值。
遞推演算法是一種簡單的演算法，即通過已知條件，利用特定關系得出中間推論，直至得到結果的演算法。遞推演算法分為順推和逆推兩種。

⑺ 背包問題的演算法

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.

⑻ 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……直至我們要求的解。

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

(8)演算法順推法填表擴展閱讀

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

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

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

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

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

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

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

⑽ 逆推啥意思

1遞推演算法分為順推和逆推兩種。所謂逆推法從已知問題的結果出發，用迭代表達式逐步推算出問題的開始的條件，即順推法的逆過程，稱為逆推。
2男孩推到女孩，被女孩推到那就叫逆推，，。解釋很淺顯，不想多做深入。。一般人都明白，不明白的不是一般人
望採納！