? ????? 前置文章：遞歸算法：www.reibang.com/p/703069f3ba3f .
? ????? 遞歸問(wèn)題有兩個(gè)經(jīng)典的應(yīng)用：Fibonacci數(shù)列和漢諾塔問(wèn)題芦倒。我已經(jīng)在之前的文章里面講過(guò)坦敌，而除去這兩個(gè)問(wèn)題，還有一些問(wèn)題是能使用普通方式去求解正压，但是當(dāng)用遞歸的方式去解這道問(wèn)題的時(shí)候孩灯，會(huì)有種被醍醐灌頂?shù)母杏X：嗬，原來(lái)這道題還能這么做，真機(jī)智鳞骤。漢諾塔問(wèn)題也是這樣的一個(gè)問(wèn)題。
? ? ? ? 我要說(shuō)的就是這樣的一個(gè)問(wèn)題：全排列問(wèn)題黍判。全排列豫尽，非常簡(jiǎn)單的一種問(wèn)題，一個(gè)全排列的問(wèn)題你拿去到全國(guó)任一所高中顷帖，給一高三生拂募，讓他去解，基本都能給你做出來(lái)窟她，甚至不止一種方法：階乘陈症、全排列公式……當(dāng)然，這是全排列在數(shù)學(xué)上的造詣震糖，當(dāng)全排列來(lái)到算法录肯，來(lái)到程序界，就沒(méi)有這么優(yōu)美了吊说。
??????? 打個(gè)比方论咏，我現(xiàn)在手頭有四個(gè)水果：橙子优炬、蘋果、桃厅贪、梨蠢护。然后我要將這些水果給挨個(gè)排排隊(duì)，我要選出排起來(lái)之后樣子最好看的一種組合养涮。
??????? 那現(xiàn)在問(wèn)題就來(lái)了葵硕，這些水果一共能有多少種排隊(duì)的方式。你拿去問(wèn)高中生贯吓，他會(huì)告訴你：這不就是排列組合嘛懈凹，A44，也就是4×3×2×1=24種排列方式悄谐，然后讓寫下這些排列方式介评，挨個(gè)挨個(gè)寫，24種爬舰，也不多们陆。那我現(xiàn)在水果不是4種了，我有10種水果要排序情屹，然后寫下排列的方式坪仇，那你慢慢寫吧：10*9*8*7*6*5*4*3*2*1=3628800種。那我好的解決方法就是寫一個(gè)程序屁商，打印烟很，讓電腦去做颈墅，我別用人了蜡镶，不然得累死個(gè)人。那我就寫一個(gè)程序給排隊(duì)了：
??????????? 四個(gè)水果問(wèn)題我直接用一般的解決方法給做：我先把蘋果放這恤筛，然后我拿梨放蘋果左面官还、右面各放一次，在這里我用數(shù)組記錄這個(gè)順序毒坛，然后用一個(gè)統(tǒng)計(jì)數(shù)記錄種數(shù)望伦。我梨和蘋果放到一起，這就兩種方式煎殷，我接著拿我的桃屯伞，我挨個(gè)位置放，這不就插空嘛豪直，我這桃放一次有三個(gè)位置劣摇，然后我給用數(shù)組記錄，三個(gè)水果放一塊了弓乙，我這六種方式了末融，然后我就放橙子了钧惧，我這放進(jìn)去，24種方式勾习，然后我先存到數(shù)組浓瞪，再給輸出。這種解決思路就是用排列組合的方式解決這問(wèn)題巧婶。我寫一套通用的方法乾颁，那我就甭管有多少水果了，反正能把答案輸出粹舵。
??????????? 但是钮孵，這樣解決這個(gè)問(wèn)題有效率嗎？我每插入一個(gè)水果眼滤，我不停的寫入數(shù)組巴席、移動(dòng)數(shù)據(jù)，當(dāng)我水果太多的時(shí)候诅需，可能也就沒(méi)法解決了漾唉，為啥？數(shù)據(jù)操作太大堰塌，電腦宕機(jī)了赵刑。
??????????? 那這問(wèn)題咋整？考慮遞歸吧场刑。我要排這四個(gè)水果了般此，我現(xiàn)在感覺四個(gè)有點(diǎn)多，那我就排三個(gè)牵现，我先把蘋果放在第一個(gè)位置上铐懊，不管它了，然后我去排桃瞎疼、橙子科乎、梨去了。然后我就發(fā)現(xiàn)了贼急，我這三個(gè)水果也能精簡(jiǎn)茅茂，我把桃放第一個(gè)位置，我就排橙子和梨就行了太抓，等我排完這倆空闲，我再把橙子放到三個(gè)水果的第一個(gè)，我在排梨和桃走敌，排完我把梨放第一個(gè)碴倾，然后排桃和橙子。這我把蘋果放到第一個(gè)位置的剩下的排序就解決了，那我再把桃放四個(gè)水果的第一個(gè)位置……這不就是遞歸嘛影斑，我四個(gè)水果的問(wèn)題能成為四個(gè)里面的一個(gè)水果和其他三個(gè)水果的排列問(wèn)題给赞。這思路就有了，解決方案就出來(lái)了矫户。
void parm(int list[],int k,int m) {
//構(gòu)成一次全排列片迅，將結(jié)果輸出
??????? if(k == m){??????????
??????????????? for (int i=0; i<=m ;i++)
??????????????????????? cout<< list[i]<<" ";
??????????????? cout<<endl;
??????? }
??????? else
//在數(shù)組里面產(chǎn)生元素k～m的全排列,也就是相當(dāng)于我把四個(gè)水果簡(jiǎn)化到三個(gè)水果
??????????????? for(int j=k; j<=m; j++){??????????????????????????????????
??????????????????????? swap( list[k], list[j] );
??????????????????????? perm( list, k+1, m );
??????????????????????? swap( list[k], list[j] );
???????? }
}
??????? 通過(guò)遞歸的方式，我就把我手里四個(gè)水果的排列給找出來(lái)了皆辽，而且做了這么一個(gè)程序柑蛇，那我以后不管有多少水果我都不怕了。
??????? 我這就挑出最好看的一種排列方式驱闷，我就要用這種方式拿著我的水果出去了耻台，我干嘛去，我拿水果喂兔子去空另。
