『壹』 演算法的常用設計方法有哪些
演算法設計是一件非常困難的工作，經常採用的演算法設計技術主要有迭代法、窮舉搜索法、遞推法、貪婪法、回溯法、分治法、動態規劃法等等。
另外，為了更簡潔的形式設計和藐視演算法，在演算法設計時又常常採用遞歸技術，用遞歸描述演算法。
『貳』 四皇後問題求解
本章內容來自《妙趣橫生的演算法》一書中。
回溯法是一種非常有效，適用范圍相當廣泛的演算法設計思想。許多復雜的問題，規模較大的問題都可以使用回溯法求解。因此回溯法又有「通用解題方法」的美稱。
回溯法的基本思想是：在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度 探索 解空間樹。當 探索 到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續 探索 下去；如果該結點不包含問題的解，那就說明以該結點為根結點的子樹一定不包含「剪枝」操作。
如果應用回溯法求解問題的所有解，要回溯到解空間樹的樹根，這樣根結點的所有子樹都被 探索 到才結束。如果只要求解問題的一個解，問題的最終解，因此要跳過對以該結點為根的子樹的系統 探索 ，逐層向其祖先結點回溯。這個過程叫做解空間樹的那麼在 探索 解空間樹時，只要搜索到問題的一個解就可以結束了。
應用回溯法的思想求解四皇後問題
分析：
上面一節中已經詳細介紹了回溯法解決四皇後問題的基本過程。在這里將給出具體的演算法描述和程序清單。
其實在解決四皇後問題時，並不一定要真的構建出這樣一棵解空間樹，它完全可以通過一個遞歸回溯來模擬。所謂解空間樹只是一個邏輯上的抽象。當然也可以用樹結構來真實地創建出一棵解空間樹，不過那樣會比較浪費空間資源。
運行結果：
『叄』 Pascal演算法之回溯及遞推詳細介紹、
在程序編輯過程中，我們可能會遇到這樣一類問題，出題者告訴你數列的前幾個數，或通過計算機獲取了數列的前幾個數，要求編程者求出第N項數或所有的數列元素（如果可以枚舉的話），或求前N項元素之和。這種從已知數據入手，尋找規則，推導出後面的數的演算法，稱這遞推演算法。
在處理遞推問題時，我們有時遇到的遞推關系是十分明顯的，簡單地寫出遞推關系式，就可以逐項遞推，即由第i項推出第i+1項，我們稱其為顯示遞推關系。但有的遞推關系，要經過仔細觀察，甚至要藉助一些技巧，才能看出它們之間的關系，我們稱其為隱式的遞推關系。
遞推演算法的關鍵是認真分析題意，發現遞推關系，正確寫出遞推公式，求得邊界條件，然後用循環實現即可。總結
1.遞推演算法的基本形式，是指編程者讓計算機循環求得一序列數值，而後一項的計算結果是由上一項或多項推導出來的。有時，我們為求得一個數列的某一項，我們不得不從第一項開始，逐個計算前面每一項的值。雖然這樣做的效率不很高，但它能幫助我們解決許多實際問題。
2.無論是順著還是逆著遞推，其關鍵是遞推公式是否正確，邊界條件是否正確。二者有一個出錯。則所有遞推結果將都是錯誤的。
【】
例1：已知數列1，2，5，10，17，26，37...求數列的第n項。
通過分析，我們可以發現，數列後面的數在前一項的基礎上以1，3，5，7，9，11的規律增長，則可以得出增長規律的表達式為2*n-3,也就是a(1)=1,a(n)=a(n-1)+2*n-3;
還有一個規律，我們可以發現每一項依次為從0開始的自然數的平方再加1，即
(n-1)2+1,第一項（1-1）2+1，第二項（2-1）2+1，第三項（3-1）2+1... 例2:階梯問題：題目的意思是：有N級階梯，可以一步走上一級，也可以一步走兩級，求從階梯底走到頂端可以有多少種不同的走法。
這是一個隱式的遞推關系，如果編程者不能找出這個遞推關系，可能就無法做出這題來。我們來分析一下：走上第一級的方法只有一種，走上第二級的方法卻有兩種（兩次走一級或一次走兩級），走上第三級的走法，應該是走上第一級的方法和走上第二級的走法之和（因從第一級和第二級，都可以經一步走至第三級,也就是說增加的第三級有兩種處理方法，第一種就是直接作為一級走一步，那麼就和兩級的走法一致，另一種就是與第二級合並作一步走，那麼就和一級的走法一致，加起來就是一級的方法和二級的走法之和），推廣到走上第i級，是走上第i-1級的走法與走上第i-2級的走法之和。很明顯，這是一個菲波拉契數列。到這里，讀者應能很熟練地寫出這個程序。在以後的程序習題中，我們可能還會遇到菲波拉契數列變形以後的結果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。
例3：猴子吃桃問題：山中住有五隻猴。一天，老大看見一堆桃子，想把桃子據為已有，卻擔心讓老二老三知道了說自己太貪心。於是將桃分成相等的兩份，卻發現剩餘一個，於是，老大吃掉這一個以後，再帶走這堆桃的二分之一。第二天，老二也看到了這堆桃，其想法和做法與老大一樣，老三老四老五也和他們的兄長想到一塊去了。結果等老五吃完一個，帶走一半以後，這堆桃還剩餘11個。請編程計算當初這堆桃共有多少個。
這個下題目明眼人一看便知，我們如果按兄弟吃桃把桃的相反順序倒推過去，就能知道當初桃子的總數。其遞推的公式是a[n-1]=a[n]*2+1。遞推的初始值是a[5]=11（又稱邊界條件），待求a[0]的值。相信現在大家能很容易就能寫出正確的程序。在這里不過是想說明一下，遞推演算法不僅可以順著推、也可逆著推的道理。
【】
回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
用回溯演算法解決問題的一般步驟為：
一、定義一個解空間，它包含問題的解。
二、利用適於搜索的方法組織解空間。
三、利用深度優先法搜索解空間。
四、利用限界函數避免移動到不可能產生解的子空間。
問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。
回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題.
[遞推是學習材料，回溯是網路]
江靜
遊客 回答於：2010-8-29 15:05:18
遞歸
遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫
程序能是程序變得簡潔和清晰.
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;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)
end;
begin
write('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;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
2.2 如何設計遞歸演算法
1.確定遞歸公式
2.確定邊界(終了)條件
練習:
用遞歸的方法完成下列問題
1.求數組中的最大數
2.1+2+3+...+n
3.求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;
var
n:integer;
procere move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'--->',c)
else begin
move(n-1,a,c,b);
writeln(a,'--->',c);
move(n-1,b,a,c);
end;
end;
begin
write('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.
『肆』 演算法設計的過程一般是什麼樣子
您好，樓主
演算法設計就是把問題的解決步驟通過計算機編程語言來實現。
大概步驟如下：
1.分析問題：輸入什麼/輸出什麼/條件什麼/能用什麼方法
2.用流程圖畫出解決方案：決定程序的結構（有三大結構：順序結構、判斷結構、循環結構）
3.演算法設計：常見的演算法設計方法有：窮舉法/迭代法/遞推法/遞歸法/回溯法/貪婪法/分治法。
4.程序設計：這個就需要變成語言來實現的。
『伍』 簡述回溯法的2種演算法框架,並分別舉出適合用這兩種框架解決的一個問題實例
回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
基本思想
在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。（其實回溯法就是對隱式圖的深度優先搜索演算法）。 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束
一般表達
可用回溯法求解的問題P，通常要能表達為：對於已知的由n元組（x1，x2，…，xn）組成的一個狀態空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關於n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。
規律
我們發現，對於許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（j<=i）元組（x1，x2，…，xj）一定也滿足d中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反d中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反d中僅涉及到x1，x2，…，xi的一個約束，n≥i≥j。因此，對於約束集d具有完備性的問題p，一旦檢測斷定某個j元組（x1，x2，…，xj）違反d中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題p的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的演算法。
『陸』 五大基本演算法——回溯法
回溯法是一種選優搜索法（試探法）。
基本思想：將問題P的狀態空間E表示成一棵高為n的帶全有序樹T，把求解問題簡化為搜索樹T。搜索過程採用 深度優先搜索 。搜索到某一結點時判斷該結點是否包含原問題的解，如果包含則繼續往下搜索，如果不包含則向祖先回溯。
通俗來說，就是利用一個樹結構來表示解空間,然後從樹的根開始深度優先遍歷該樹，到不滿足要求的葉子結點時向上回溯繼續遍歷。
幾個結點：
擴展結點：一個正在產生子結點的結點稱為擴展結點
活結點：一個自身已生成但未全部生成子結點的結點
死結點：一個所有子結點已全部生成的結點
1、分析問題，定義問題解空間。
2、根據解空間，確定解空間結構，得 搜索樹 。
3、從根節點開始深度優先搜索解空間（利用 剪枝 避免無效搜索）。
4、遞歸搜索，直到找到所要求的的解。
1、子集樹
當問題是：從n個元素的集合S中找出滿足某種性質的子集時，用子集樹。
子集樹必然是一個二叉樹。常見問題：0/1背包問題、裝載問題。
遍歷子集樹時間復雜度：O（2^n）
2、排列樹
當問題是：確定n個元素滿足某種排列時，用排列數。常見問題：TSP旅行商問題，N皇後問題。
遍歷排列樹時間復雜度：O（n!）
通俗地講，結合Java集合的概念，選擇哪種樹其實就是看最後所得結果是放入一個List（有序）里，還是放入一個Set（無序）里。
剪枝函數能極大提高搜索效率，遍歷解空間樹時，對於不滿足條件的分支進行剪枝，因為這些分支一定不會在最後所求解中。
常見剪枝函數：
約束函數（對解加入約束條件）、限界函數（對解進行上界或下界的限定）
滿足約束函數的解才是可行解。
1、0/1背包問題
2、TSP旅行商問題
3、最優裝載問題
4、N-皇後問題
具體問題可網路詳細內容。
『柒』 演算法設計裡面分治法、貪心法、動態規劃法、回溯法、分枝限界法各是什麼意思
你這個問題問的內容太多了，還是看網路吧：
分治法：http://ke..com/view/1583824.htm?fr=aladdin
貪心演算法：http://ke..com/view/298415.htm
動態規劃：http://ke..com/view/28146.htm
回溯演算法：http://ke..com/view/6056523.htm
分支限界法：http://ke..com/view/4479359.htm
『捌』 演算法設計
這道題用遞歸效率較低.
由於確定了是分成三個數,可以用三個培梁for循環枚舉實現.
當然,在枚舉的時候可以對范岩亂圍進行一定限定,來提高效率.
int main()
{
int i, j, n;
cin >> n;
for ( i = n; i >= n/3; --i ) //最大的數肯定比n/3大;
for ( j = i; j >= 0; --j ) //第二個數小於等於i
if (( i + j <= n )&&( n - i - j <= j )) //第三個數只要n - i - j就可以了,這樣不用判斷和了
cout << n << " = " << i << " + " << j << " + " << n - i - j << endl;
return 0;
}
一般來說,當拆分的個數一定且不是很大時,用循環枚舉是最好的方法.
因為用遞歸同樣有很多冗餘,且傳遞參數需要耗費不少時間.而循環還可以做更多有效的剪枝.
分成四個數的配棗運時候完全可以用循環來做.當要求拆分的個數較多時,則可以把循環化為遞歸.
void search( int start, int end, int num )
{
if ( num==n ) {
判斷和;
返回上一層遞歸;
} else {
for ( i = start; i >= end; --i )
search( i, 0, num + 1 );
}
}
若要求輸出一個數的所有拆分方案,比如6=6,....6=1+1+1+1+1+1,那就可以用回溯法來做.