[算法]列車算法

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

一、    問題陳述

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

二、    問題分析與設(shè)計

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

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

全排列的生產(chǎn)法通常有幾下幾種：

字典排序法：從右往左開始找出第一個比右邊數(shù)字小的數(shù)字的序號j，然后在以j為基準(zhǔn)再從左往右，找出第一個比它大的最小的數(shù)，然后這兩個數(shù)位置對調(diào)。例如：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。如此循環(huán)既可求出全部排列。

遞歸類算法：

我將選擇遞歸類算法作為實現(xiàn)該車廂調(diào)度的主要算法，通過設(shè)計perm遞歸函數(shù)，畫出遞歸流程圖如下圖所示：

三、    程序代碼

#include <stdio.h>

#include<stdlib.h>

int n = 0;

//交換兩個數(shù)

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;

}

四、    運行結(jié)果

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

將數(shù)據(jù)庫保存到txt：

五、    設(shè)計體會與總結(jié)

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

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

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

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

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

以上三點就是我在課程設(shè)計的過程中覺得收獲最大的三點，在課程設(shè)計過程中，能夠鍛煉自己分析問題，解決問題的能力，通過認(rèn)真仔細(xì)的畫第二節(jié)的那張遞歸程序的執(zhí)行流程圖，就覺得畫圖法是理解遞歸程序的一個非常不錯的方法，不然的話就我個人而言覺得想要理解遞歸算法的話還是一件比較頭疼的事，所以覺得無論是學(xué)習(xí)還是做某個事，如果方法得當(dāng)，那么能夠達(dá)到預(yù)期的效果就比較快，效率比較高?？偟膩碇v這兩周的時間，還是有不少的收獲，希望能夠?qū)⑦@些收獲的方法應(yīng)用與以后的面試或者工作中！

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

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

Unity QQ群：858550         cocos2dx QQ群：280818155

====================== 相互學(xué)習(xí)，共同進(jìn)步 ===================

轉(zhuǎn)載請注明出處：http://blog.csdn.net/dingxiaowei2013/article/details/17558235