排列問題的遞歸算法

排列問題的遞歸算法第1頁(yè)，課件共11頁(yè)，創(chuàng)作于2023年2月4.1.4排列問題的遞歸算法

有n個(gè)元素，把它們編號(hào)為1，2…n，用一個(gè)數(shù)組A來存放所生成的排列，然后輸出它們。假定開始時(shí)n個(gè)元素以依次存放在數(shù)組A中，為了生成這n個(gè)元素的所有排列，可以采取下面的步驟：（1）第一個(gè)元素為1，即排列的第一個(gè)元素為1，生成后面n-1個(gè)元素的排列。

第2頁(yè)，課件共11頁(yè)，創(chuàng)作于2023年2月

（2）第一個(gè)元素和第二個(gè)元素互換，使排列的第一個(gè)元素為2，生成后面n-1個(gè)元素的排列。

（3）如此繼續(xù)，最后第一個(gè)元素和第n個(gè)元素互換，使排列的第一個(gè)元素為n，生成后面n-1個(gè)元素的排列。第3頁(yè)，課件共11頁(yè)，創(chuàng)作于2023年2月

在上面的第一步，為生成后面n-1個(gè)元素的排列，繼續(xù)采取下面的步驟：（1）第二個(gè)元素為2，即排列的第二個(gè)元素為2，生成后面n-2個(gè)元素的排列。（2）第二個(gè)元素和第三個(gè)元素互換，使排列的第二個(gè)元素為3，生成后面n-2個(gè)元素的排列。

第4頁(yè)，課件共11頁(yè)，創(chuàng)作于2023年2月

（3）如此繼續(xù)，最后第二個(gè)元素和第n個(gè)元素互換，使排列的第二個(gè)元素為n，生成后面n-2個(gè)元素的排列。

這種步驟一直繼續(xù)，當(dāng)排列的前n-2個(gè)元素已確定后，為生成后面2個(gè)元素的排列，可以：（1）第n-1個(gè)元素為n-1,即排列的第n-1個(gè)元素為n-1，生成后面1個(gè)元素的排列,此時(shí)n個(gè)元素已構(gòu)成一個(gè)排列。（2）第n-1個(gè)元素和第n個(gè)元素互換，使排列的第n-1個(gè)元素為n，生成后面1個(gè)元素的排列,此時(shí)n個(gè)元素已構(gòu)成一個(gè)排列。

第5頁(yè)，課件共11頁(yè)，創(chuàng)作于2023年2月

令排列算法perm(A,k,n)表示生成數(shù)組后面?zhèn)€元素的排列。通過上面的分析有：（1）基礎(chǔ)步：k=1,只有一個(gè)元素，已構(gòu)成一個(gè)排列。（2）歸納步：對(duì)任意的k,1<k<=n完成perm(A,k-1,n),逐一對(duì)第n-k元素與第n-k~n元素進(jìn)行互換，每互換一次，就執(zhí)行一次perm(A,k-1,n)操作，產(chǎn)生一個(gè)排列。

由此，排列生成的遞歸算法可描述如下：第6頁(yè)，課件共11頁(yè)，創(chuàng)作于2023年2月算法4.5排列的生成輸入：數(shù)組A[],數(shù)組的元素個(gè)數(shù)n輸出：數(shù)組A[]的所有排列1.template<classType>2.voidperm(TypeA[],intk,intn)3.{4. inti;5. if(k==1)6. for(i=0;i<n;i++) /*已構(gòu)成一個(gè)排列,輸出它*/7. cout<<A[i];8. else9. {10. for(i=n-k;i<n;i++)/*生成后續(xù)的一系列排列*/11. {12. swap(A[i],A[n-k]);13. perm(A,k-1,n);14. swap(A[i],A[n-k]);15. }16. }17.}第7頁(yè)，課件共11頁(yè)，創(chuàng)作于2023年2月第8頁(yè)，課件共11頁(yè)，創(chuàng)作于2023年2月第9頁(yè)，課件共11頁(yè)，創(chuàng)作于2023年2月4.1.5遞歸算法的討論

結(jié)構(gòu)清晰明了、容易閱讀、容易用數(shù)學(xué)歸納法證明它的正確性。程序調(diào)試很方便。遞歸深度加深，工作棧所需空間增大，遞歸調(diào)用時(shí)所花輔助操作增多。運(yùn)行效率