回溯法與樹的遍歷
回溯法：其求解過程實質是一個先序遍歷一棵“狀態樹”的過程，只是這棵樹不是遍歷前預先建立的，而
是隱含在遍歷過程中。
題目描述：求含n個元素的集合的冪集。
例：A={1,2,3}，則A的冪集為{{1，2，3}，{1，2}，{1， 3}，{2，3}，{1}，{2}，{3}，{}}
解題思路：求冪集的過程可看成是依次對集合A中的元素進行取或捨的過程。
選擇合適的數據結構——假設以線性表表示集合。
樹根結點表示冪集元素的初始狀態（空集），葉子結點表示終結狀態（冪集的元素），第i層表
示已對前i-1個元素進行了取捨的當前狀態
編碼：
#include "stdafx.h"
#include< iostream.h>
#define N 10
typedef struct
{
int data[N];
int length;
}SqList;
//輸出線性表B
void Output(SqList& B)
{
int i;
if(B.length ==0)
cout<<"空集\n";
else
{
for(i=0;i<B.length ;i++)
cout<<B.data [i]<<"\t";
cout<<endl;
}
}
//求集合A的冪集，其中B為暫存冪集元素的線性表，i表示從第i個元素開始取捨，當
//i>n時則求得冪集的一個元素，並輸出
void GetPowerSet(int i,SqList A,SqList& B)
{
int x,k,j;
if(i>=A.length )
Output(B);
else
{
x=A.data [i];
k=B.length ;
B.data [k]=x;
B.length ++;
GetPowerSet(i+1,A,B);
B.length --;
GetPowerSet(i+1,A,B);
}
}
A={1,2,3}，則A的冪集為{{1，2，3}，{1，2}，{1， 3}，{2，3}，{1}，{2}，{3}，{}}
int main(int argc, char* argv[])
{
SqList A,B;
int i;
cout<<"輸入A集合的元素個數\n";
cin>>A.length ;
cout<<"輸入A集合的元素\n";
for(i=0;i
cin>>A.data [i];
B.length =0;
GetPowerSet(0,A,B);
return 0;
}
我不解的是第一次執行完output函數後該怎麼辦，如果繼續執行下面的語句，即b.length--和遞歸函數，那第二次輸出的集合顯然與答案不符，求大神指點，我記得老師說過還有什麼出棧的過程，求指導
算法理解：
理解1：
宏觀上我們可以這樣理解：要將A上的n個盤子按照要求移動到C上，我們可以想到：先將上邊的 n-1 個盤子移動到B上，再將A上剩余的最大的盤子移動到C上，然後將B上所有的盤子移動到C上，這是比較簡單的理解，但是對於算法實現的過程，還是沒有弄透徹。
理解2：
我們知道當盤子數為n時，移動的次數應該為 2^n-1；這個有公式 H(n) = 2H(n-1) +1 得來，理解為：上邊的n-1個盤子先翻轉到B上，將最大的盤子移動到C上，花費1步，然後將B上的盤子翻轉到C上，花費2H(n-1)步。
後來美國的一位學者發現一種出人意料的簡單的算法，只要輪流兩步操作既可以實現：首先，把三張桌子按順序首尾相接的排列，形成一個環，然後對A上的盤子開始移動，順時針擺放成 A B C的順序：
若n為奇數，圓盤的移動順序是 A->C->B->A->C->B->A......... 即 間隔兩個步長移動 。此處的n代表盤子位的層數，比如說 3 層漢諾塔就是從下往上數第1、3 個盤子移動的順序。
若n為偶數，圓盤移動的順序為A->B->C->A->B->C->A..........即 間隔一個步長移動。對n的解釋同上 第二個盤子移動 A->B->C。
現在開始算法：
首先先找到能夠移動的 即 A的最上邊的那個盤子 如代碼：
[cpp] view plaincopy
recursion_hano(n-1,A,C,B);
該調用從下往上數層數，第一次調用時是第二層的移動 應該為： A->B
第二次調用時為第三層的移動，經過兩次調用B、C翻轉，應該為 ：A->C
........................
如此到最高層來移動第一個盤子
接下來：
A上的盤子移動過之後，我們要移動B、C上的盤子，移動策略同上
第二段代碼的理解為：
[cpp] view plaincopy
moveAC(A,C);
對塔頂的兩個盤子，最上層的盤子假如移動到了C上，下一層的盤子就移動到B上，因為第一段代碼調用一次，B、C的順序翻轉一次。
最後一段代碼的理解：
[cpp] view plaincopy
recursion_hano(n-1,B,A,C);
交換B、A的順序是為了將 B上的盤子移動到C上，此處相當於為了實現步長為 1 的移動。
按照這樣的理解，可非常清楚的了解遞歸每一步實現的是什麼
如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C
