1. 9.2 回溯演算法的例子
在4 * 4的方格棋盤上放置4個皇後棋子，使得沒有兩個皇後在同一行、同一列，也不在同一條45度的斜線上， 問有多少種布局?
回溯演算法的解一般是向量，而這個題也不例外，設4維向量的<x1,x2,x3,x4>，Xi中i表示第幾個皇後，Xi表示在棋盤第i行的位置，比如其中一個解是<2,4,1,3>，如下圖
1.四皇後問題中，葉節點就是一個解。
2.四皇後每一個節點的子樹代表著下一個皇後可以放的列數，因為都是n，所以子樹都是n叉樹，故四皇後是一顆 n叉樹
3.四皇後的解至少有兩個，因為棋盤可以沿著中心線翻折
有n種物品，每種物品只有1個。第i種物品價值為vi，重量為wi，i=1，2，3...n. 問如何選擇放入背包的物品，使得總重量不超過B，而價值達到最大?
同樣，此問題的解可用一個向量來表示，該向量就代表了所有的物品，如果對應物品為1，則表示裝入背包，反之，沒有被裝入。
因此，回溯的每層可以表示為對應的物品，分支左右可以表示取或者不取（向量中表示為1或0）
總而言之，每一個節點也就是物品只有0和1兩種狀態，因此該樹一棵二叉樹，或者為 子集樹
1.選擇第一個物品，目前總重量為8，總價值為12。
2.再選擇第二個物品，總重量為14 > 13，觸發回溯。
3.不選擇第二個物品，選擇第三個商品，總重量是12，總價值為21。
4.再選擇第四個物品，總重量為15 > 13，觸發回溯。
5.不選擇第四個物品，總重量為12，總價值為21，與目前最優解價值進行比較，如果最優解價值大於21則替換目前的最優解向量和最優解價值。
1.背包問題只有在葉節點才能生成一個滿足條件的解，而之後將該解和最優解比較。
2.背包問題必須遍歷完所有的分支，才能夠獲得最終的解。
3.背包問題是一顆子集樹。
有n個城市，已知任兩個城市之間的距離， 求一條每個城市恰好經過一次的迴路，使得總長度最小 。
貨郎問題中主要的一點就是每一個點（除了第一個點）其他點必須經過且只能經過1次，這就很像數學中的排列。
因此，我們採用一個向量來表示貨郎問題的城市排列
1.貨郎問題是一顆分支不斷減少的排列數（和數學的排列類似）
2.貨郎問題也得遍歷完所有的情況，比較後得出最優解。
1.解都是用向量表示
2.搜索空間都是樹
3.搜索策略多種，有深度優先、寬度優先和跳躍式遍歷搜索樹。
2. 回溯法為什麼只對右孩子限制剪枝
你好，回溯法為什麼只對右孩子限制剪枝？回溯法採用試錯的思想，它嘗試分步的去解決一個問題。在分步解決問題的過程中，當它通過嘗試發現現有的分步答案不能得到有效的正確的解答的時候，它將取消上一步甚至是上幾步的計算，再通過其它的可能分步解答再次嘗試尋找問題的答案。
回溯法是暴力搜尋法中的一種。採用試探性的搜索原則，按優先條件向前進發，能進則進，無路則退，退而再另闢蹊徑，直至得到所有有效的結果集，也可能無解，回溯法通常使用遞歸方式實現，配合恰當的剪枝對復雜度優化有奇效。剪枝策略就是在搜索過程中利用過濾條件來剪去完全不用考慮的搜索路徑，從而避免了一些不必要的搜索，大大優化了演算法求解速度，還保證了結果的正確性。應用到回溯演算法中，我們就可以提前判斷當前路徑是否能產生結果集，如果否，就可以提前回溯。而這也叫做可行性剪枝另外還有一種叫做最優性剪枝，每次記錄當前得到的最優值，如果當前結點已經無法產生比當前最優解更優的解時，可以提前回溯，請參考！
3. 簡述回溯法的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的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的演算法。
4. 什麼是回溯演算法
回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。用回溯演算法解決問題的一般步驟為： 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;
5. 誰能解釋一下回溯演算法
分類: 電腦/網路 >> 程序設計 >> 其他編程語言
問題描述:
誰能解釋一下回溯演算法？
解析:
回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
初識回溯演算法是在解決8皇後問題時候，第一步按照順序放一個皇後，然後第二步符合要求放第2個皇後，如果沒有符合位置符合要求，那麼就要改變第一個皇後的位置，重新放第2個皇後的位置，直到找到符合條件的位置就可以了
回溯在迷宮搜索中使用很常見，就是這條路走不通，然後返回前一個路口，繼續下一條路。
6. 六、遞歸與回溯演算法
在計算機領域裡面，很多問題都可以要採用遞歸演算法來解決。遞歸中，最長用到的方法就是回溯法。我們具體分析問題的時候，可以發現這類問題本質是一個樹的形狀。
遞歸演算法的本質還是將原來的問題轉化為了更小的同一問題，進行解決。一般注意兩點：
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、
7. 回溯演算法的基本思想及其在軟體開發中的應用
回溯演算法其實就是簡單的枚舉，只不過是加了一點技巧。回溯演算法一般是已經完成的都是合法的，後續的操作不需要考慮先前已經完成的。短時間內通過文字也說不太明白，建議從一些題目去體會，八皇後、全排列。並綜合遞歸去理解這樣的話應該會有比較深刻的理解。
至於在軟體開發中的應用，演算法思想可以用在任何方面，最近甚至比較流行，將一些演算法用到硬體中，演算法提供的是一種思想，認真體會就會發現它會應用在任何方面。
希望能幫助到你。
8. (四) 回溯法(試探演算法)
約束函數和限界函數的目的是相同的，都為了剪去不必要搜索的子樹，減少問題求解所需實際生成的狀態結點數，它們統稱為剪枝函數（pruning function）。
使用剪枝函數的深度優先生成狀態空間樹中結點的求解方法稱為回溯法(backtracking)
使用剪枝函數的廣度優先生成狀態空間樹中結點的求解方法稱為分支/枝限界法(branch-and-bound)
回溯法/分支限界法 = 窮舉 + 剪枝。
回溯法是一個既帶有系統性又帶有跳躍性的搜索演算法；
這種以深度優先的方式系統地搜索問題的解得演算法稱為回溯法。其實回溯法就是對 隱式圖 的深度優先搜索演算法
回溯是窮舉方法的一個改進，它在所有可行的選擇中，系統地搜索問題的解。它假定解可以由向量形式 (x1,x2,...,xn) 來 表示，其中xi的值表示在第i次選擇所作的決策值，並以深度優先的方式遍歷向量空間,逐步確定xi 的值，直到解被找到。
若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束，來確保解的正確性。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。
有許多問題，當需要找出它的解集或者要求回答什麼解是滿足某些約束條件的最佳解時，往往要使用回溯法。( 找出解空間樹中滿足約束條件的所有解 )
回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。 這種方法適用於解一些組合數較大的問題 。
（1）問題框架
（2） 遞歸的演算法框架
回溯法是對解空間的深度優先搜索，在一般情況下使用遞歸函數來實現回溯法比較簡單，其中i為搜索的深度，框架如下：
（3）非遞歸回溯框架（遞歸轉非遞歸，這里可以參考樹的遍歷，或者看上篇博客——遞歸演算法介紹）
用回溯法解題的一個顯著特徵是在搜索過程中動態產生問題的解空間。在任何時刻，演算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為 ，則回溯法所需的計算空間通常為 。而顯式地存儲整個解空間則需要 或 內存空間。
回溯法解題的時候常遇到兩種類型的解空間樹：
用回溯法搜索子集樹的演算法框架可描述為：
用回溯法搜索排列樹的演算法框架可描述為：
9. 五大基本演算法——回溯法
回溯法是一種選優搜索法（試探法）。
基本思想：將問題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-皇後問題
具體問題可網路詳細內容。
10. 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.