遞歸回溯演算法比較

⑴ Pascal演算法之回溯及遞推詳細介紹、

遞歸 遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫程序能是程序變得簡潔和清晰.2.1 遞歸的概念
1.概念一個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數).如:procere a; begin . . . a; . . .end;這種方式是直接調用.又如: procere b; procere c; begin begin . . . . . . c; b; . . . . . .end; end;這種方式是間接調用.例1計算n!可用遞歸公式如下: 1 當 n=0 時 fac(n)={n*fac(n-1) 當n>0時可編寫程序如下:program fac2;varn:integer;function fac(n:integer):real;beginif n=0 then fac:=1 else fac:=n*fac(n-1)end;beginwrite('n=');readln(n);writeln('fac(',n,')=',fac(n):6:0);end.例2 樓梯有n階台階,上樓可以一步上1階,也可以一步上2階,編一程序計算共有多少種不同的走法.設n階台階的走法數為f(n)顯然有 1 n=1 f(n)={2 n=2 f(n-1)+f(n-2) n>2可編程序如下：program louti;var n:integer;function f(x:integer):integer;beginif x=1 then f:=1 elseif x=2 then f:=2 else f:=f(x-1)+f(x-2);end;beginwrite('n=');read(n);writeln('f(',n,')=',f(n))end.2.2 如何設計遞歸演算法
1.確定遞歸公式2.確定邊界(終了)條件練習:用遞歸的方法完成下列問題1.求數組中的最大數2.1+2+3+...+n3.求n個整數的積4.求n個整數的平均值5.求n個自然數的最大公約數與最小公倍數6.有一對雌雄兔,每兩個月就繁殖雌雄各一對兔子.問n個月後共有多少對兔子?7.已知:數列1,1,2,4,7,13,24,44,...求數列的第 n項. 2.3典型例題例3 梵塔問題 如圖:已知有三根針分別用1,2,3表示,在一號針中從小放n個盤子,現要求把所有的盤子 從1針全部移到3針,移動規則是:使用2針作為過度針,每次只移動一塊盤子,且每根針上不能出現大盤壓小盤.找出移動次數最小的方案. 程序如下:program fanta;varn:integer;procere move(n,a,b,c:integer);beginif n=1 then writeln(a,'--->',c)else beginmove(n-1,a,c,b);writeln(a,'--->',c);move(n-1,b,a,c);end;end;beginwrite('Enter n=');read(n);move(n,1,2,3);end.例4 快速排序快速排序的思想是:先從數據序列中選一個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1, 處理結束.程序如下:program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.練習:1.計算ackerman函數值: n+1 m=0 ack(m,n)={ ack(m-1,1) m<>0 ,n=0 ack(m-1,ack(m,n-1)) m<>0,n<>0 求ack(5,4)
回溯 回溯是按照某種條件往前試探搜索,若前進中遭到失敗,則回過頭來另擇通路繼續搜索.3.1 回溯的設計 1.用棧保存好前進中的某些狀態.2.制定好約束條件例1由鍵盤上輸入任意n個符號;輸出它的全排列.program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.例2.n個皇後問題:program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;end.回溯演算法的公式如下:3.2 回溯演算法的遞歸實現由於回溯演算法用一棧數組實現的,用到棧一般可用遞歸實現。上述例1的遞歸方法實現如下：program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procere try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.例2：n皇後問題的遞歸演算法如下：程序1：program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.程序2：說明:當n=8 時有30條對角線分別用了l和r數組控制，用c數組控制列.當(i,j)點放好皇後後相應的對角線和列都為false.遞歸程序如下:program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.練習：1.找出所有從m個元素中選取n(n<=m)元素的組合。2.設有A,B,C,D,E 5人從事j1,j2,j3,j4,j5 5項工作每人只能從事一項,它們的效益表如下:求最佳安排,使效益最高.3.N個數中找出M個數(從鍵盤上輸入正整數N,M後再輸入N個正數),要求從N個數中找出若干個數,使它們的和為M,把滿足條件的數組找出來,並統計組數.4.地圖著色。如下圖12個區域用4種顏色著色要求相鄰的區域著不同的顏色5.將任意一正整數(1<n<100)分解成若干正整數的和. 如:4=1+1+1+1 =2+1+1 =2+2 =3+1.

⑵ Pasca演算法中的動態規劃、遞歸、回溯、枚舉、貪心有什麼區別最好舉個例子!!速度點！！急啊

我記得以前有一篇180頁的pascal演算法，我用delphi實現了其中一部分，這些演算法都相當有用，但是也是超難，我啃回溯啃了5天。動態規劃在分類步驟比較小的情況下用，遞歸太常用了，回溯就是循環的遞歸（解決迴路嵌套問題），枚舉只有情況有限的時候一個個列舉出來，貪心就是不求最佳，找一個滿足添加的結果就行

⑶ 遞推演算法和遞歸演算法有什麼區別

1、演算法的過程不同

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

遞歸演算法在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。

⑷ 如何理解遞歸，回溯，動態規劃等演算法

遞歸比較簡單的，就是遞推的逆向演算法。例如已知a(10)且a(n)=f(a(n+1))，讓你求a(1)。回溯是深度優先搜索必須要用到的方法，推薦你看下「八皇後問題」，看完就應該明白了。動態規劃是一種以空間換時間的演算法，也就是佔用內存較大，但是時間效率比較高的分階段演算法。推薦你看看「攔截導彈」問題，「0/1背包問題」。動態規劃先多看看題，然後再去理解概念比較好

⑸ 六、遞歸與回溯演算法

在計算機領域裡面，很多問題都可以要採用遞歸演算法來解決。遞歸中，最長用到的方法就是回溯法。我們具體分析問題的時候，可以發現這類問題本質是一個樹的形狀。

遞歸演算法的本質還是將原來的問題轉化為了更小的同一問題，進行解決。一般注意兩點：
1、遞歸終止的條件。對應到了遞歸演算法中最基本的問題，也是最最簡單的問題。
2、遞歸過程。遞歸過程需要將原問題一步一步的推到更小的 同一 問題，更小的意思就是子問題解決起來就更加的簡單。有寫情況是能夠找到一個遞推的公式的。這個過程中就需要透徹的去理解遞歸函數的意義。明確這個函數的輸入和輸出是什麼，這樣來寫的話，就清晰多了。

因為有了這樣的遞歸公式，那麼我們就很容易的能看出來遞歸的終止條件就是我們知道的f(0)和f(1)了。有了f(0)和f(1)之後，我們就能夠繼續的遞推出f(3)一直到f(n)了。

但是我們現在才用一個遞歸演算法的思想來解決這個問題:

像我們常見的數據結構如鏈表、樹、圖等都是有著天然的遞歸結構的，鏈表由於是一個線性的結構，那麼通常我們也是能夠直接循環遍歷就能解決問題的，但是這里我們用遞歸法來解決一下LeetCode上面的問題
LeetCode 203 移除鏈表元素
分析：鏈表的結構可以理解成一個節點連接這一個更短的鏈表，這樣依次一直看下去，直到最後一個節點None，那麼我們這個時候的遞歸終止條件就是head指向None了，返回的就是None

深入的理解遞歸演算法之後，我們就開始進行回溯法的學習。通過LeetCode上面的幾道題，我們來深入的探討一下遞歸與回溯法的應用。

持續更新中...
數據結構與演算法系列博客：
一、數據結構與演算法概述
二、數組及LeetCode典型題目分析
三、鏈表（Linked list）以及LeetCode題
四、棧與隊列（Stack and Queue
五、樹（Trees）
六、遞歸與回溯演算法
七、動態規劃
八、排序與搜索
九、哈希表

參考資料
1、
2、
3、

⑹ 回溯 遞歸的區別是什麼

區別就是回溯具有多向選擇，設有解決方案集合為{a1,a2,a3,...,an},當a1解決方案不能得到預期的結果時，則退回到a1後面的解決方案繼續執行。類似於迷宮求解，當右側不通時退回上格執行左側等，以及KMP演算法，當模式串失配時，nextValue數組將指示尾指針應退到哪個位置繼續匹配。

⑺ java回溯和遞歸的區別，主要什麼回溯怎麼用，有代碼最好

N皇後問題的非遞歸迭代回溯法java代碼實現
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class NQueen {

static int n; // 皇後個數
static int[] x; // 當前解如{0，2，4，1，3}分別代表第1、2、3、4列的行值
static int totle; // 可行方案個數
public static void main(String[] args) {
int input = 0; //輸入n值
int sum = 0; //可行方案個數
String temp; //臨時存儲輸入值
System.out.println("請輸入N後問題的N值：");

try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
temp = br.readLine();
input = Integer.parseInt(temp); //將輸入值轉換為int保存
if(input<=0){
throw new IOException("別輸負數好不？");
}
System.out.println("輸入的數是：" + input);

sum = nQueen(input); //調用nqueen方法

System.out.println("可行方案個數為：" + sum); //輸出sum

} catch (IOException e) {
System.out.println(e.getMessage());

}catch (NumberFormatException e){
System.out.println("請輸入數字。。。");
}
}
private static int nQueen(int input) {
n = input; //把輸入給全局變數n
totle = 0; //初始化totle
x = new int[n + 1];
for (int i = 0; i <= n; i++)
x[i] = 0; //初始化x
backtrack(); //調用回溯演算法
return totle;
}
private static void backtrack() {
int k = 1;
while (k > 0) {
x[k] += 1; //第k列皇後向下移一行
while ((x[k] <= n) && !(place(k))){ //如果當前第k列皇後未出界或者和其他皇後沖突
x[k] += 1; //第k列皇後向下移一行繼續尋找
System.out.println("在第"+k+"行 "+"第"+x[k]+"列放置皇後");
System.out.print("當前方案為 ");
for(int i=1;i<=k;i++) //列印尋找策略
System.out.print(x[i]+" ");
System.out.println();
}
if (x[k] <= n) //找到一個值並且未出界
if (k == n) { //已是最後一列說明已找到一個方案
totle++;
System.out.print("可行方案為： ");
for (int i = 1; i <= n; i++)
System.out.print(x[i] + " ");
System.out.println();
} else { //不是最後一列故尋找下一列
k++;
x[k] = 0;
}
else //找到的值已經出界，回退到上一列
k--;
}
}
//判斷皇後是否沖突
private static boolean place(int k) {
for (int j = 1; j < k; j++)
if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k]))
return false;
return true;
}
}

⑻ 結合騎士問題，說說遞歸演算法和回溯演算法的異同點

《我的老師》《我和老師》《我愛老師》
共同點：說的是我、老師
不同點：1.重點是講訴老師的事2.我和老師之間發生的事3.老師做了哪些事值得我敬愛
《這件事教育了我》《我總想著這件事》《我們班上新事多》
共同點：講訴一件事或多件事
不同點：1.這件事從哪方面教育了我2.這件事哪方面值得我思考3.我們班上發生的新事多.

⑼ 怎樣才能深刻理解遞歸和回溯

遞歸是一種演算法結構，回溯是一種演算法思想，一個遞歸就是在函數中調用函數本身來解決問題，回溯就是通過不同的嘗試來生成問題的解，有點類似於窮舉，但是和窮舉不同的是回溯會「剪枝」，意思就是對已經知道錯誤的結果沒必要再枚舉接下來的答案了，比如一個有序數列1,2,3,4,5，要找和為5的所有集合，從前往後搜索我選了1，然後2，然後選3 的時候發現和已經大於預期，那麼4,5肯定也不行，這就是一種對搜索過程的優化。
回溯分析是追蹤決策的特性之一。 是指對原始決策的產生機制、決策內容、主客觀環境等進行分析．從起點開始，按順序考察導致決策失誤的原因、問題的性質、失誤的程度等。
[演算法分析]
為了描述問題的某一狀態，必須用到它的上一狀態，而描述上一狀態，又必須用到它的上一狀態……這種用自已來定義自己的方法，稱為遞歸定義。例如：定義函數f(n)為：
f(n)=n*f(n－1) (n>0)
f(n)=1 (n=0)
則當0時，須用f(n-1)來定義f(n),用f(n-1-1)來定義f(n-1)……當n=0時，f(n)=1。
由上例我們可看出，遞歸定義有兩個要素：
（1）遞歸邊界條件。也就是所描述問題的最簡單情況，它本身不再使用遞歸的定義。
如上例，當n=0時，f(n)=1，不使用f(n-1)來定義。
（2）遞歸定義：使問題向邊界條件轉化的規則。遞歸定義必須能使問題越來越簡單。
如上例：f(n)由f(n-1)定義，越來越靠近f(0),也即邊界條件。最簡單的情況是f(0)=1。
遞歸演算法的效率往往很低, 費時和費內存空間. 但是遞歸也有其長處, 它能使一個蘊含遞歸關系且結構復雜的程序簡介精煉, 增加可讀性. 特別是在難於找到從邊界到解的全過程的情況下, 如果把問題推進一步,其結果仍維持原問題的關系, 則採用遞歸演算法編程比較合適.
遞歸按其調用方式分為: 1. 直接遞歸, 遞歸過程P直接自己調用自己; 2. 間接遞歸, 即P包含另一過程D, 而D又調用P.
遞歸演算法適用的一般場合為:
1. 數據的定義形式按遞歸定義.
如裴波那契數列的定義: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.
對應的遞歸程序為:
Function fib(n : integer) : integer;
Begin
if n = 0 then fib := 1 { 遞歸邊界 }
else if n = 1 then fib := 2
else fib := fib(n-2) + fib(n-1) { 遞歸 }
End;
這類遞歸問題可轉化為遞推演算法, 遞歸邊界作為遞推的邊界條件.
2. 數據之間的關系(即數據結構)按遞歸定義. 如樹的遍歷, 圖的搜索等.
3. 問題解法按遞歸演算法實現. 例如回溯法等.
從問題的某一種可能出發, 搜索從這種情況出發所能達到的所有可能, 當這一條路走到" 盡頭 "
的時候, 再倒回出發點, 從另一個可能出發, 繼續搜索. 這種不斷" 回溯 "尋找解的方法, 稱作
" 回溯法 ".

[參考程序]
下面給出用回溯法求所有路徑的演算法框架. 注釋已經寫得非常清楚, 請讀者仔細理解.
Const maxdepth = ????;
Type statetype = ??????; { 狀態類型定義 }
operatertype = ??????; { 算符類型定義 }
node = Record { 結點類型 }
state : statetype; { 狀態域 }
operater :operatertype { 算符域 }
End;
{ 注: 結點的數據類型可以根據試題需要簡化 }
Var
stack : Array [1..maxdepth] of node; { 存當前路徑 }
total : integer; { 路徑數 }
Procere make(l : integer);
Var i : integer;
Begin
if stack[L-1]是目標結點 then
Begin
total := total+1; { 路徑數+1 }
列印當前路徑[1..L-1];
Exit
End;
for i := 1 to 解答樹次數 do
Begin
生成 stack[l].operater;
stack[l].operater 作用於 stack[l-1].state, 產生新狀態 stack[l].state;
if stack[l].state 滿足約束條件 then make(k+1);
{ 若不滿足約束條件, 則通過for循環換一個算符擴展 }
{ 遞歸返回該處時, 系統自動恢復調用前的棧指針和算符, 再通過for循環換一個算符擴展 }
{ 注: 若在擴展stack[l].state時曾使用過全局變數, 則應插入若干語句, 恢復全局變數在
stack[l-1].state時的值. }
End;
{ 再無算符可用, 回溯 }
End;
Begin
total := 0; { 路徑數初始化為0 }
初始化處理;
make(l);
列印路徑數total
End.

⑽ 用遞歸回溯法設計旅行售貨員問題的演算法

一、回溯法：
回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。

二、演算法框架：
1、問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。

2、回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
運用回溯法解題通常包含以下三個步驟：
（1）針對所給問題，定義問題的解空間；
（2）確定易於搜索的解空間結構；
（3）以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索；

3、遞歸回溯：由於回溯法是對解空間的深度優先搜索，因此在一般情況下可用遞歸函數來實現回溯法如下：
procere try(i:integer);
var
begin
if i>n then 輸出結果
else for j:=下界 to 上界 do
begin
x[i]:=h[j];
if 可行{滿足限界函數和約束條件} then begin 置值；try(i+1); end;
end;
end;

說明：
i是遞歸深度；
n是深度控制，即解空間樹的的高度；
可行性判斷有兩方面的內容：不滿約束條件則剪去相應子樹；若限界函數越界，也剪去相應子樹；兩者均滿足則進入下一層；

搜索：全面訪問所有可能的情況，分為兩種：不考慮給定問題的特有性質，按事先頂好的順序，依次運用規則，即盲目搜索的方法；另一種則考慮問題給定的特有性質，選用合適的規則，提高搜索的效率，即啟發式的搜索。
回溯即是較簡單、較常用的搜索策略。
基本思路：若已有滿足約束條件的部分解，不妨設為（x1,x2,x3,……xi），I<n,則添加x(i+1)屬於s(i+2)，檢查(x1,x2,……,xi,x(i+1))是否滿足條件，滿足了就繼續添加x(i+2)、s(i+2)，若所有的x(i+1)屬於s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察過的x1屬於s1，看其是否滿足約束條件，為此反復進行，直至得到解或證明無解。