C語言中常見的幾種算法淺析

孟小丁 白春霞

摘要：C語言是一門結(jié)構(gòu)化的程序設(shè)計(jì)語言，在解決實(shí)際問題時(shí)，除了掌握扎實(shí)的基本語法知識，更重要的是要學(xué)習(xí)如何編寫程序。本文針對C語言程序設(shè)計(jì)課程實(shí)踐教學(xué)中存在的問題，從算法設(shè)計(jì)的角度，對常用的遞歸算法，排序算法，迭代法，“打擂臺”法，輾轉(zhuǎn)相除法等進(jìn)行描述和分析。設(shè)計(jì)程序不僅保證算法的正確性，還要考慮算法的質(zhì)量。所以如何編寫高效且正確的程序是至關(guān)重要的。

關(guān)鍵詞：C語言;算法;程序設(shè)計(jì)

中圖分類號：G642? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? ? 文章編號：1009-3044（2018）34-0215-02

著名計(jì)算機(jī)科學(xué)家Wirth提出“算法+數(shù)據(jù)結(jié)構(gòu)=程序”。這一公式對于結(jié)構(gòu)化設(shè)計(jì)語言是適用的[1]。算法是解決“做什么”和“怎么做”的問題，數(shù)據(jù)結(jié)構(gòu)是加工對象。所以不了解算法就談不上程序設(shè)計(jì)。隨著教學(xué)內(nèi)容的增加，程序設(shè)計(jì)的難度隨之增大，對特定問題設(shè)計(jì)相應(yīng)的算法尤為重要。利用C語言的知識在解決實(shí)際問題時(shí)，除了考慮算法和數(shù)據(jù)結(jié)構(gòu)外，還應(yīng)采用結(jié)構(gòu)化程序設(shè)計(jì)的方法進(jìn)行程序設(shè)計(jì)。

C語言程序設(shè)計(jì)作為大學(xué)生的一門基礎(chǔ)必修課程，對提升大學(xué)生計(jì)算機(jī)編程能力至關(guān)重要，也是后續(xù)專業(yè)課程學(xué)習(xí)的先修課程。在C語言教學(xué)過程中，學(xué)生對程序設(shè)計(jì)往往顯得力不從心，特別是在程序設(shè)計(jì)實(shí)驗(yàn)課上，對于一道程序難度不大的編程題，部分學(xué)生卻不知道如何下手去做。在教學(xué)過程中，于清[2]建議以算法優(yōu)先并結(jié)合案例教學(xué)的模式開展C語言的教學(xué)。屈婉玲[3]對算法課程的教學(xué)改革進(jìn)行的總結(jié)。其他學(xué)者對C語言設(shè)計(jì)的遞歸算法[4，5]、排序算法[6]等分別進(jìn)行了研究。

結(jié)合個(gè)人的實(shí)際教學(xué)情況，本文對常見的幾種算法進(jìn)行分析。

1 算法與分析

該課程教學(xué)中，涉及的典型算法有遞歸算法，排序算法，迭代法，“打擂臺算法”，輾轉(zhuǎn)相除法等。

1.1 遞歸算法

遞歸的概念是，在調(diào)用一個(gè)函數(shù)的過程中，直接或間接調(diào)用該函數(shù)本身。遞歸算法的執(zhí)行過程分為回溯和遞推兩個(gè)階段[1]。在第一個(gè)回溯階段，把較復(fù)雜的問題求解到比原問題簡單的一些問題。這個(gè)階段，必須要有結(jié)束遞歸的條件。在第二個(gè)遞推的階段，當(dāng)獲得最簡單情況的解后，逐級返回，依次得到稍復(fù)雜的解。

遞歸調(diào)用方式有直接遞歸調(diào)用和間接遞歸調(diào)用。常見應(yīng)用于求解斐波那契數(shù)列[7]、漢諾塔問題[8，9]、樹的遍歷[10，11]、求階乘（見示例1）等。

遞歸一般可以代替循環(huán)語句使用，雖然程序結(jié)構(gòu)優(yōu)美，但執(zhí)行效率較低，耗費(fèi)計(jì)算機(jī)內(nèi)存資源，難以閱讀和維護(hù)[12]。當(dāng)效率處在第一位的時(shí)候，還須謹(jǐn)慎使用遞歸。

1.2 排序算法

排序方法按照排序的規(guī)律可分為“升序”和“降序”。排序的方法[13-15]有很多，如希爾排序、堆排序、快速排序、冒泡排序、選擇法排序等。在C語言課程教學(xué)中，主要介紹的是冒泡法排序和簡單選擇法排序兩種。

2 趣味性案例及求解算法

在學(xué)習(xí)過程中，常介紹一些趣味性的程序設(shè)計(jì)題目，例如猴子吃桃子、求解楊輝三角、n階魔方陣的問題等。這些題目對提高學(xué)生的學(xué)習(xí)興趣也起到了至關(guān)重要的作用。

還有一些實(shí)際應(yīng)用題目也包含了相應(yīng)的算法思想，比如：窮舉法求解“百錢買百雞”問題，回溯法求解“n皇后”問題等，KMP算法求解“字符串”匹配問題等。

3 結(jié)論與展望

上述主要介紹和分析了學(xué)生學(xué)習(xí)C語言過程中幾種常用的算法，并給出了具體實(shí)例。另外簡單介紹了C語言中的一些趣味性實(shí)例對應(yīng)的求解算法。為了有效地解決實(shí)際問題，不僅需要保證算法的正確性，還要考慮算法的質(zhì)量等要素，所以在編寫程序的過程中，逐步教會或引導(dǎo)學(xué)生設(shè)計(jì)一個(gè)正確且有效的算法是至關(guān)重要的。

參考文獻(xiàn)：

[1]譚浩強(qiáng).C程序設(shè)計(jì)（第四版）[M].清華大學(xué)出版社.2010.

[2]于清，吐爾根·依布拉音，等.算法為先的C語言教學(xué)模式探討[J].計(jì)算機(jī)教育，2009（20）：106-108+96.

[3]屈婉玲，王捍貧，段莉華.面向軟件工程學(xué)科的算法課程建設(shè)[J].中國大學(xué)教學(xué)，2012（12）：55-57.

[4]任偉，任正云.C語言中遞歸調(diào)用的算法研究[J].襄陽職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2014（1303）：27-30+34.

[5]李偉.淺析C語言遞歸算法[J].電腦知識與技術(shù)，2012（830）：7229-7235.

[6]閆鑫，王琴竹.循序漸進(jìn)學(xué)習(xí)C語言選擇排序算法[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2018（14）：53-56.

[7]孫義欣，宋大偉.斐波那契數(shù)列問題的C語言教學(xué)實(shí)施探討[J].電腦編程技巧與維護(hù)，2012（16）：151-152+154.

[8]白會波，高瑞平.漢諾塔問題的算法分析及C語言演示程序的實(shí)現(xiàn)[J].電腦知識與技術(shù)，2010（609）：2130-2131.

[9]肖桂云，袁亞麗.用C語言解決漢諾塔問題的方法及過程分析[J].河北北方學(xué)院學(xué)報(bào)（自然科學(xué)版），2006（03）：71-73.

[10]王敏，趙曉雷.基于遍歷搜索二叉樹中最長路徑的算法研究[J].現(xiàn)代電子技術(shù)，2010（3308）：54-55+58.

[11]龔佳，袁赟，劉遠(yuǎn)軍.一種二叉樹非遞歸遍歷算法的C語言實(shí)現(xiàn)[J].電腦知識與技術(shù)，2014（1001）：223-225.

[12]Stenphen Prata.C Primer Plus（第五版）中文版[M].人民郵電出版社.2005.

[13]宋美英.基于C語言的冒泡排序算法探討[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2011（29）：48-49+55.

[14]王敏.改進(jìn)的雙向選擇排序算法[J].信息技術(shù)，2010（3409）：21-24+79.

[15]毛廣敏.常用C語言排序算法解析[J].軟件導(dǎo)刊，2012（1111）：51-54.

[16]李向軍，楊花娥.求解一元三次方程近似根的幾種算法的C語言實(shí)現(xiàn)[J].西安聯(lián)合大學(xué)學(xué)報(bào)，1999（02）：65-69.

[17]馬麗娟.常用計(jì)算機(jī)算法簡介及C語言舉例[J].電腦知識與技術(shù)，2010（611）：2655-2659+2662.

[18]柳小強(qiáng).基于C語言最大公約數(shù)算法的設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2011（11）：53-56.

【通聯(lián)編輯：王力】