[算法]列車算法

整理電腦的時候，發現很久之前的課程設計，雖然很簡單的課設，但還是想將它分享輸來，不然就永遠“爛”在我電腦里了，覺得有點可惜。

一、    問題陳述

假設停在鐵路調度站入口處的車廂序列的編號一次為1，2，3，4。設計一個程序，求出所有可能由此輸出的長度為4的車廂序列。

二、    問題分析與設計

車廂調度問題是實際生活中的一個抽象問題，實際上其本質就是一個N個數的全排列問題，所謂全排列算法就是對于給定的字符集，用有效的方法將所有可能的全排列無重復無遺漏地枚舉出來。

N個字符的全體排列之間存在一個確定的線性順序關系。所有的排列中除最后一個排列外，都有一個后繼；除第一個排列外都有一個前驅。每一個排列的后繼都可以從它的前驅經過最少的變化得到，全排列的生產算法就是從第一個排列開始逐個生產所有的排列的方法。

全排列的生產法通常有幾下幾種：

字典排序法：從右往左開始找出第一個比右邊數字小的數字的序號j，然后在以j為基準再從左往右，找出第一個比它大的最小的數，然后這兩個數位置對調。例如：1 5 4 7 6 32  的下一個排列是 1 56 74 3 2

鄰位交換法：鄰位對換法中下一個排列總是上一個排列某相鄰兩位對換得到的。例如：以4個元素的排列為例，將最后的元素4逐次與前面的元素交換，可以生成4個新排列：1 2 3 4、1 243、14 2 3、4 1 2 3。然后將最后一個排列的末尾的兩個元素交換，再逐次將排頭的4與其后的元素交換，又生成四個新排列：4 13 2、143 2、1 3 4 2、1 3 2 4。再將最后一個排列的排頭的兩個元素交換，再將4從后往前移：3 1 2 4、3 14 2、34 1 2、4 3 1 2。如此循環既可求出全部排列。

遞歸類算法：

我將選擇遞歸類算法作為實現該車廂調度的主要算法，通過設計perm遞歸函數，畫出遞歸流程圖如下圖所示：

三、    程序代碼

#include <stdio.h>

#include<stdlib.h>

int n = 0;

//交換兩個數

void swap(int *a, int *b)

{

int m;

m = *a;

*a = *b;

*b = m;

}

//遞歸

void perm(FILE* fw,int list[], int k, int m)

{

int i;

if(k > m)

{

for(i = 0; i <= m; i++)

{

fprintf(fw,"%d ", list[i]);

printf("%d ", list[i]);

}

printf("\n");

fprintf(fw,"\n");

n++;

}

else

{

for(i = k; i <= m; i++)

{

swap(&list[k], &list[i]);

perm(fw,list, k + 1, m);

swap(&list[k], &list[i]);

}

}

}

int main()

{

FILE* fw=fopen("pailie.txt","wt");

int i;

int j=0;

printf("請輸入列車長度N：");

scanf("%d",&i);

int list[i];

for(j;j<i;j++)

{

list[j]=j+1; //0-i

}

perm(fw,list,0,i-1);

printf("total:%d\n", n);

fprintf(fw,"total:%d\n",n);

fclose(fw);

return 0;

}

四、    運行結果

如果輸入列車長度為4，則運行結果如下：

將數據庫保存到txt：

五、    設計體會與總結

首先談談選題，本來可以做一個類似管理系統那一類的題目，但通過網上了解，無論是公司面試，還是各種競賽，遞歸算法都是考察的重中之重，也是解決問題的一種非常好的方法，于是我就決定放棄原來的題目，去選擇這個車廂調度算法，用遞歸來實現。通過這半個月的時間，我如期完成了此次的課程設計，車廂調度算法從本質上講就是N個數的全排列算法，雖然從代碼量上看是比較少，但是能夠徹底的從分析問題到理解問題再到解決問題，實際上還是沒那么容易。通過網上查閱資料發現一些牛人在面試華為公司曾遇到過這類的筆試題，讓應試者在二十分鐘內能用遞歸方法寫出這個算法那能進的機會就大大增加，從這點來看，就給我們一個啟示，我們大學生應該注重算法的分析以及打牢和鞏固基礎，這樣在實現一些比較稍微大型的一些項目來才會顯的得心應手。

該算法主要涉及到的一些知識點和難點主要有一下幾個方面，這也是我完成了該算法的一些收獲：

一、深刻的理解了形參和實參的傳遞問題，一些基本類型，例如×××，字符型以及字符串型都是以形參的形式傳遞的，而數組這些是以實參形式傳遞的。舉個例子：如果想要在主函數中通過傳參的方式來交換main函數中兩個×××變量a，b的值，那么外部函數中的兩個參數必須是以指針或者引用類型來作為參數類型，在主函數中這樣調用swap（&a，&b），即將兩個變量的地址作為參數，去調用外部的swap函數，這樣才能實現預期的效果。但是，如果主函數中是一個×××數組，例如intarray[]={a,b},那么在調用外部的swap函數，則不需要用用指針，可以將該array數組名直接作為swap的參數，進行調用，因為數組作為參數傳遞本身就是傳遞的地址，也就是實參形式傳遞。形參與實參的傳遞是本次實驗所獲得的最深刻的體會之一。

二、對遞歸的理解也更加深刻，如果一個方法用遞歸和非遞歸都能夠實現，那么遞歸能夠減少代碼量或許還能夠節省時間或空間復雜度，但不易于理解，非遞歸算法容易理解，但是代碼量會比較多，占用的空間會比較多，所謂任何事都用雙面性，有利有弊，遞歸就是一個很好的體現。

三、我將運行的結果保存到文本中，也鍛煉和鞏固C語言中文本操作的知識，例如：fopen("pailie.txt","wt")，第一個參數是文件名，如果該文件不存在則創建該文件，如果存在則可以通過fprintf()函數往文件中寫入，而fopen("pailie.txt","at")，則是對文件進行追加寫入。復習文件的寫入的時候還鞏固了文件的讀入，用過fgets()方法來實現對文本中數據的讀取。

以上三點就是我在課程設計的過程中覺得收獲最大的三點，在課程設計過程中，能夠鍛煉自己分析問題，解決問題的能力，通過認真仔細的畫第二節的那張遞歸程序的執行流程圖，就覺得畫圖法是理解遞歸程序的一個非常不錯的方法，不然的話就我個人而言覺得想要理解遞歸算法的話還是一件比較頭疼的事，所以覺得無論是學習還是做某個事，如果方法得當，那么能夠達到預期的效果就比較快，效率比較高。總的來講這兩周的時間，還是有不少的收獲，希望能夠將這些收獲的方法應用與以后的面試或者工作中！

==================== 迂者 丁小未 CSDN博客專欄=================

MyBlog：http://blog.csdn.net/dingxiaowei2013             MyQQ:1213250243

Unity QQ群：858550         cocos2dx QQ群：280818155

====================== 相互學習，共同進步 ===================

轉載請注明出處：http://blog.csdn.net/dingxiaowei2013/article/details/17558235