回溯演算法偽代碼

❶ 回溯演算法，用c語言實現

這個演算法應該不難，基本和全排列的演算法類似，只不過判斷條件不是n=1， 而是在判斷已經取得的數的和>=M為終止條件。

具體的演算法，我給個大概流程吧

int lst[N]; //保存選取的數
int index = 0; //lst中最後的一個數的位置

func(W, N)
{
if(N == 0) //遍歷完畢 返回
return;
for(i=0 to N)
{
if( W[i][1] != -1 ) //判斷是否已經讀取當前值
{
lst[index++] = W[i][0] //當前值加入到保存數組
W[i][1] = -1; //設置當前值已經讀取，不可再讀
if(check() == 0)
{
func(W, N-1); //大小不夠M，繼續往下讀
}
else if(check() == 1)
{
print(lst); //和為M，輸出
}
lst[--index] = 0; //回溯，尋找下一組解
W[i][1] = 0;
}
}
}

check()
{
if(sum(lst) > W)
return -1;

if(sum(lst) < W)
return 0;
return 1;
}

❷ 在C# 使用回溯演算法，得到一個值後 ，直接結束演算法，開始其他程序

回溯演算法一般要記錄所有值的結果到一個類似於數組的數據結構裡面，如果想要提前結束回溯演算法，就判斷一下數組裡面是不是已經有結果了。如果有了，直接就可以返回了。

❸ c語言回溯演算法

if(n==7||a[n+1][i]!=1&&a[n+1][i+1]!=1&&a[n+1][i-1]!=1)
這行的代碼是判斷是否可以放皇後的句子。如果可以就將所在位置置 1 。後面也就是這樣做判斷的。這個程序應當有問題，其中try應當是C語言中一個關鍵字啊，不可以這么用。
就我的看法：八皇後的問題應當用遞歸加回溯會都到更好的代碼，我寫過，不過也快忘了。

❹ 用偽碼描述回溯法搜索排列樹的演算法模式。

希望能幫到你！！！

❺ 什麼是回溯演算法

回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。用回溯演算法解決問題的一般步驟為： 1、定義一個解空間，它包含問題的解。 2、利用適於搜索的方法組織解空間。 3、利用深度優先法搜索解空間。 4、利用限界函數避免移動到不可能產生解的子空間。 問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。 1.跳棋問題： 33個方格頂點擺放著32枚棋子，僅中央的頂點空著未擺放棋子。下棋的規則是任一棋子可以沿水平或成垂直方向跳過與其相鄰的棋子，進入空著的頂點並吃掉被跳過的棋子。試設計一個演算法找出一種下棋方法，使得最終棋盤上只剩下一個棋子在棋盤中央。 演算法實現提示 利用回溯演算法，每次找到一個可以走的棋子走動，並吃掉。若走到無子可走還是剩餘多顆，則回溯，走下一顆可以走動的棋子。當吃掉31顆時說明只剩一顆，程序結束。 2.中國象棋馬行線問題： 中國象棋半張棋盤如圖1(a)所示。馬自左下角往右上角跳。今規定只許往右跳，不許往左跳。比如 圖4（a）中所示為一種跳行路線，並將所經路線列印出來。列印格式為： 0，0->2,1->3,3->1,4->3,5->2,7->4,8… 演算法分析： 如圖1(b),馬最多有四個方向，若原來的橫坐標為j、縱坐標為i,則四個方向的移動可表示為： 1: （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7) 3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8) 搜索策略： S1:Ａ[１]:=(0,0); S2:從Ａ[1]出發，按移動規則依次選定某個方向，如果達到的是（4,8）則轉向S3,否則繼續搜索下 一個到達的頂點； S3:列印路徑。 演算法設計： procere try(i:integer); {搜索} var j:integer; begin for j:=1 to 4 do {試遍4個方向} if 新坐標滿足條件 then begin 記錄新坐標; if 到達目的地 then print {統計方案，輸出結果} else try(i+1); {試探下一步} 退回到上一個坐標，即回溯; end; end;

❻ 應用問題求解，加油站有效加油位問題！

1.已知有
3
個物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容積
M=20，根據
0-1
背
包動態規劃的遞推式求出最優解。
2.按要求完成以下關於排序和查找的問題。
①對數組
A={15，29，135，18，32，1，27，25，5}，用快速排序方法將其排成遞減序。
②請描述遞減數組進行二分搜索的基本思想，並給出非遞歸演算法。
③給出上述演算法的遞歸演算法。
④使用上述演算法對①所得到的結果搜索如下元素，並給出搜索過程：18，31，135。
3.已知
1
(
)
*
(
)
i
i
k
k
ij
r
r
A
a
+
=
，
k
=1，2，3，4，5，6，
r
1
=5，
r
2
=10，
r
3
=3，
r
4
=12，
r
5
=5，
r
6
=50，
r
7
=6，
求矩陣鏈積
A
1
×A
2
×A
3
×A
4
×A
5
×A
6
的最佳求積順序（要求給出計算步驟）
。
4.
根
據
分
枝
限
界
算
法
基
本
過
程
,
求
解
0-1
背
包
問
題
。
已
知
n=3,M=20
，
(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。
5.試用貪心演算法求解汽車加油問題：
已知一輛汽車加滿油後可行駛
n
公里，
而旅途中有若干個加油站。
試設計一個有效演算法，指出應在哪些加油站停靠加油，使加油次數最少，請寫出該演算法。
6.試用動態規劃演算法實現下列問題：設
A
和
B
是兩個字元串。我們要用最少的字元操作，將字元串
A
轉換為字元串
B，這里所說的字元操作包括：
①刪除一個字元。
②插入一個字元。
③將一個字元改為另一個字元。
請寫出該演算法。
7.對於下圖使用
Dijkstra
演算法求由頂點
a
到頂點
h
的最短路徑。
8.試寫出用分治法對數組
A[n]實現快速排序的演算法。
9.有
n
個活動爭用一個活動室。
已知活動
i
佔用的時間區域為[s
i
，
f
i
]，
活動
i,j
相容的條件是：
sj≥f
i
，問題的解表示為(x
i
|
x
i
=1，2…，n,)，x
i
表示順序為
i
的活動編號活動，求一個相容的活動子
集，且安排的活動數目最多。
10.設
x
1
、
x
2
、
x
3
是一個三角形的三條邊，而且
x
1
+x
2
+x
3
=14。請問有多少種不同的三角形？給出解答過
程。
11.設數組
A
有
n
個元素，需要找出其中的最大最小值。
①請給出一個解決方法，並分析其復雜性。
②把
n
個元素等分為兩組
A1
和
A2，分別求這兩組的最大值和最小值，然後分別將這兩組的最大值
和最小值相比較，求出全部元素的最大值和最小值。如果
A1
和
A2
中的元素多於兩個，則再用上述
方法各分為兩個子集。直至子集中元素至多兩個元素為止。這是什麼方法的思想？請給出該方法的
演算法描述，並分析其復雜性。
12.有
n
個程序和長度為
L
的磁帶，
程序
i
的長度為
a
i
，
已知
L
a
n
i
i
≻
∑
=
1
，
求最優解(x
i
，
x
2
，
...，
x
i
，
…，
x
n
)，x
i
=0，1,
x
i
=1，表示程序
i
存入磁帶，x
i
=0，表示程序
i
不存入磁帶，滿足
L
a
x
n
i
i
i
≤
∑
=
1
，
且存放的程序數目最多。
13.試用分治法實現有重復元素的排列問題：設
)
,...,
,
{
2
1
n
r
r
r
R
=
是要進行排列的
n
個元素，其中元素
n
r
r
r
,...,
,
2
1
可能相同，試設計計算
R
的所有不同排列的演算法。
14.試用動態規劃演算法實現
0-1
閉包問題，請寫出該演算法。
15.試用貪心演算法求解下列問題：將正整數
n
分解為若干個互不相同的自然數之和，使這些自然數的乘
積最大，請寫出該演算法。
16.試寫出用分治法對一個有序表實現二分搜索的演算法。
17.試用動態規劃演算法實現最長公共子序列問題，請寫出該演算法。
18.假設有
7
個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量
M＝150，
使用回溯方法求解此背包問題，請寫出狀態空間搜索樹。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
價值
10
40
30
50
35
40
30
19.求解子集和問題：對於集合
S={1，2
，6，8}，求子集，要求該子集的元素之和
d=9。
①畫出子集和問題的解空間樹；
②該樹運用回溯演算法，寫出依回溯演算法遍歷節點的順序；
③如果
S
中有
n
個元素，指定
d，用偽代碼描述求解子集和問題的回溯演算法。
20.求解填字游戲問題：在
3×3
個方格的方陣中要填入數字
1
到
N（N≥10）內的某
9
個數字，每個方
格填一個整數，似的所有相鄰兩個方格內的兩個整數之和為質數。試採用回溯法寫出滿足這個要求
的一種數字填法的演算法和滿足這個要求的全部數字填法的演算法。
21.試用動態規劃演算法實現最大子矩陣和問題：
求
n
m
×
矩陣
A
的一個子矩陣，
使其各元素之和為最大。
22.試用回溯法解決下列整數變換問題：關於整數
i
的變換
f
和
g
定義如下：
⎣
⎦
2
/
)
(
;
3
)
(
i
i
g
i
i
f
=
=
。
對於給定的兩個整數
n
和
m
，要求用最少的變換
f
和
g
變換次數將
n
變為
m
。
23.關於
15
謎問題。在一個
4×4
的方格的棋盤上，將數字
1
到
15
代表的
15
個棋子以任意的順序置入
各方格中，空出一格。要求通過有限次的移動，把一個給定的初始狀態變成目標狀態。移動的規則
是：每次只能把空格周圍的四格數字（棋子）中的任意一個移入空格，從而形成一個新的狀態。為
了有效的移動，設計了估值函數
C
1
(x)，表示在結點
x
的狀態下，沒有到達目標狀態下的正確位置
的棋子的個數。

❼ 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.

❽ c語言高手幫個忙（圓排列回溯演算法）

數組下標要從0開始使用啊
a=(float *)malloc(C.n*sizeof(float));
b=(float *)malloc((C.n+1)*sizeof(float));//記錄每次的排列
rf=(int *)malloc((C.n+1)*sizeof(int));//標記已經使用的圓
這時的C.n還沒有值，就malloc是沒有意義的！！

❾ 硬幣兌換問題回溯法偽代碼

A數組用來存放硬幣,數值1代表正面，0代表反面；
static int s;s是存放每列狀態的數初始為0代表一列都沒翻，第幾位為1就代表第幾列被翻轉
int turncoin(A,S,N，n) //A(N*9數組） ，N是行數 n代表當次翻哪一列 初次調用n=0，代表第一列
{ int i=1;//因為每列只有兩種狀態，所以每列只翻一次
static int max=0;//用來存放翻轉後正面朝上的最大硬幣數；
static int S;//大S用來存儲當前硬幣堆的翻轉狀態
do {turncoin(A,S,N，n+1);if （n==8）{ int tem=sum //sum為遍歷A數組,所有元素之和（即為當前正面朝上的硬幣數)
if（sum>max）{S=s; //把當前翻轉狀態存儲到S,S內總是存儲著擁有正面朝上硬幣數量最高的一種翻轉狀態；}}}while(i--&&transform(N，n));
//transform()函數翻轉第N列的硬幣 並且對s的第n位置一 成功返回ture 並且對是 實現就是for(i=0；
ireturn S; //好了 這里S根據S每一位就得道最終所要求的結果}
拓展資料：
一、題目描述：
一個翻硬幣的游戲，有N(N <=10000）行硬幣，每行有九個硬幣，排成一個N*9的方陣，有的硬幣正面朝上，有的反面朝上。我們每次可把一整行或者一整列的所有硬幣翻過來，請問怎麼翻，使得正面朝上的硬幣盡量多（翻硬幣無次數限制）。
二、思路分析：
枚舉2^9種列的翻法。
遍歷N行，如果某行正面朝上的少，翻之；如果正面朝上的多，不翻
記下使得正面最多的方法即可
耗時O(2^9 * N)
這個得到的是最優解.用位運算效率還是很高的.
對每一列,都用一個9位的數表示,一共有N個
然後便利所有的9位狀態,(000000000)-(111111111) (二進制)
對於每個狀態,都與這N個數異或,每次異或後累加所有的1的值假設為k,如果k小於5則k=9-k.
對N個數累加所有的k,得到最終累加和.
求出所有狀態下累加和最大的,就是正面朝上的硬幣盡量多的個數.
翻面的方法橫列分別是最優解的8位狀態和與之對應的每個數異或後累加和k是否小於5.

❿ 用遞歸函數設計八皇後問題的回溯演算法C++代碼

解析：遞歸實現n皇後問題。
演算法分析：
數組a、b、c分別用來標記沖突，a數組代表列沖突，從a[0]~a[7]代表第0列到第7列。如果某列上已經有皇後，則為1，否則為0。
數組b代表主對角線沖突，為b[i-j+7]，即從b[0]~b[14]。如果某條主對角線上已經有皇後，則為1，否則為0。
數組c代表從對角線沖突，為c[i+j]，即從c[0]~c[14]。如果某條從對角線上已經有皇後，則為1，否則為0。
代碼如下：
#include <stdio.h>
static char Queen[8][8];
static int a[8];
static int b[15];
static int c[15];
static int iQueenNum=0; //記錄總的棋盤狀態數
void qu(int i); //參數i代錶行
int main()
{
int iLine,iColumn;
//棋盤初始化，空格為*，放置皇後的地方為@
for(iLine=0;iLine<8;iLine++)
{
a[iLine]=0; //列標記初始化，表示無列沖突
for(iColumn=0;iColumn<8;iColumn++)
Queen[iLine][iColumn]='*';
}
//主、從對角線標記初始化，表示沒有沖突
for(iLine=0;iLine<15;iLine++)
b[iLine]=c[iLine]=0;
qu(0);
return 0;
}
void qu(int i)
{
int iColumn;
for(iColumn=0;iColumn<8;iColumn++)
{
if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)
//如果無沖突
{
Queen[i][iColumn]='@'; //放皇後
a[iColumn]=1; //標記，下一次該列上不能放皇後
b[i-iColumn+7]=1; //標記，下一次該主對角線上不能放皇後
c[i+iColumn]=1; //標記，下一次該從對角線上不能放皇後
if(i<7) qu(i+1); //如果行還沒有遍歷完，進入下一行
else //否則輸出
{
//輸出棋盤狀態
int iLine,iColumn;
printf("第%d種狀態為：\n",++iQueenNum);
for(iLine=0;iLine<8;iLine++)
{
for(iColumn=0;iColumn<8;iColumn++)
printf("%c ",Queen[iLine][iColumn]);
printf("\n");
}
printf("\n\n");
}
//如果前次的皇後放置導致後面的放置無論如何都不能滿足要求，則回溯，重置
Queen[i][iColumn]='*';
a[iColumn]=0;
b[i-iColumn+7]=0;
c[i+iColumn]=0;
}
}
}