摘 要：C語言是使用時間最久和最普及的計算機(jī)高級程序設(shè)計語言之一，屬于面向過程的程序設(shè)計語言，兼有匯編語言和高級語言的雙重特點，是人們學(xué)習(xí)計算機(jī)程序設(shè)計的首選語言，也是學(xué)習(xí)其他計算機(jī)課程和進(jìn)行軟件開發(fā)的基礎(chǔ)。C語言程序設(shè)計中的循環(huán)語句是C語言的一個難點，可以用來解決許多具有規(guī)律性重復(fù)操作的實際問題，文章通過對“百錢買百雞”這個問題的算法進(jìn)行設(shè)計、分析和優(yōu)化，以尋求解決問題的最優(yōu)算法。

關(guān)鍵詞：C語言；循環(huán)語句；百錢買百雞

中圖分類號：TP311.1 文獻(xiàn)標(biāo)識碼：A

Abstract：As a process-oriented programming language，C programming language is one of the most classic and popular computer programming languages with the characteristics of the assembly language and the high-level language.It is not only the first choice for the people who begin to learn computer programming，but also the basis for other computer courses and software development.As a difficult point in C Programming Language learning，the loop statement can be used to solve many practical problems of regularly repetitive operation.Taking the case of "spending 100 dollars on 100 chickens"，the paper implements design，analysis and optimization，and finally proposes the optimal algorithm.

Keywords：C programming language；loop statement；spending 100 dollars on 100 chickens

1 引言（Introduction）

計算機(jī)算法設(shè)計是計算機(jī)專業(yè)學(xué)習(xí)的核心專業(yè)內(nèi)容，算法設(shè)計對于培養(yǎng)一個人的邏輯思維能力具有重要的作用，能進(jìn)行有效的算法設(shè)計是對一個計算機(jī)學(xué)者的基本要求。求解同一個問題的算法可能有多種，進(jìn)行算法設(shè)計的優(yōu)劣往往在一定程度上體現(xiàn)出設(shè)計者的計算機(jī)應(yīng)用能力，所以，我們要學(xué)會如何對一個算法進(jìn)行分析并進(jìn)行優(yōu)化[1，2]。一個算法不一定能說它是最優(yōu)的，我們所說的最優(yōu)算法是指在某一種衡量標(biāo)準(zhǔn)下，優(yōu)于解決該問題的所有可能的算法。一般地，解決某個問題的最優(yōu)算法是指在時間復(fù)雜度的基礎(chǔ)上的最優(yōu)性，時間復(fù)雜度是指算法執(zhí)行的時間長短，通過把算法的核心操作執(zhí)行的次數(shù)作為算法的時間度量[3]，這里，我們使用C語言的循環(huán)語句解決“百錢買百雞問題”，基于算法中的循環(huán)次數(shù)來判斷算法的優(yōu)劣[4，5]。

2 C語言循環(huán)語句（C language loop statement）

C語言是一種廣泛使用的程序設(shè)計語言，它具有功能豐富、使用靈活、目標(biāo)程序效率高等特點[6]。C語言是用流程控制語句來控制程序的執(zhí)行流程，流程控制語句包括順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)三類，C語言中的循環(huán)語句又包括for循環(huán)語句、while循環(huán)語句和do…while循環(huán)語句三種，用它們可以解決實際應(yīng)用中需要重復(fù)處理和計算的問題[7，8]。例如，計算1到100之間的整數(shù)的和，就需要重復(fù)地做加法；求數(shù)組中的最大值，需要重復(fù)地進(jìn)行兩個數(shù)據(jù)的比較；求素數(shù)問題，需要依次對每個整數(shù)進(jìn)行判斷；求百錢買百雞問題，需要依次窮舉每個可能的值通過計算來進(jìn)行判斷；求水仙花問題，需要對范圍內(nèi)的整數(shù)依次進(jìn)行計算判斷等等。對于這些復(fù)雜的問題，使用循環(huán)語句來解決效率很高，下面我們通過“百錢買百雞”這個經(jīng)典問題來進(jìn)行分析。

3 “百錢買百雞”問題描述（The problem description

of "spending 100 dollars on 100 chickens"）

中國古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提出了著名的“百錢買百雞問題”：雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，問翁、母、雛各幾何？

這是一個古典數(shù)學(xué)問題，買一只公雞值5錢，一只母雞值3錢，三只小雞值1錢，問如果用100錢買100只雞，那么公雞、母雞和小雞分別多少只？我們假設(shè)公雞、母雞和小雞的個數(shù)分別為a、b、c，那么買公雞的錢數(shù)為5*a，買母雞的錢數(shù)為3*b，買小雞的錢數(shù)為c/3；并且a、b、c之和為100，a，b，c都是正整數(shù)且c是3的倍數(shù)，該問題用數(shù)學(xué)中的三元一次方程組表達(dá)如下：

4 算法設(shè)計與分析（Algorithm design and analysis）

對于上述列出的三元一次方程，最直觀的方法就是采用三重循環(huán)來解決，我們對a、b、c的范圍進(jìn)行限定，用for循環(huán)語句進(jìn)行算法設(shè)計，得出算法一如下：

該算法直接將三元一次方程轉(zhuǎn)化為C語言三重循環(huán)程序，沒有進(jìn)一步考慮a、b、c更小的取值范圍，所以導(dǎo)致循環(huán)次數(shù)為100*100*100=106，算法的復(fù)雜度太高，所以我們可以根據(jù)每種雞的價錢先確定a、b、c的取值范圍：公雞為5錢，所以a的取值范圍為1—20，當(dāng)然a的取值的不可能是20，否則100錢剛好買20只公雞與百雞的題意不符；b的取值范圍為1—33，c的取值范圍為3—99；得到算法二如下：

對于這個算法我們可以計算一下它的循環(huán)次數(shù)為19*33*97=60819次，可見算法的效率還是不高。那么我們還能不能再進(jìn)行一定的改進(jìn)呢？通過分析，買小雞的錢數(shù)為c/3，那么小雞的數(shù)量c是3的倍數(shù)，所以為了提高執(zhí)行效率，我們可以把對小雞的for循環(huán)語句中c的步長值設(shè)為3，這樣可以減少一定的循環(huán)次數(shù)，也可以去掉c%3==0這個約束條件，得到算法三如下：

此時我們再來計算一下以上算法需要執(zhí)行的循環(huán)次數(shù)為19*33*33=20691次，很明顯，此時算法的執(zhí)行效率有了一定的提高，縮小小雞c的取值范圍使得算法的循環(huán)次數(shù)變?yōu)樯蟼€算法的三分之一。那么這一次改進(jìn)后的算法就是最理想的算法嗎？還有沒有進(jìn)一步改進(jìn)的空間呢？答案是肯定的。其實只要我們再仔細(xì)觀察可以發(fā)現(xiàn)，這個算法實際上可以不用三重循環(huán)，而只用二重循環(huán)就可以達(dá)到目的，因為二重循環(huán)比三重循環(huán)會大大降低循環(huán)次數(shù)，因而提高執(zhí)行速度。由于公雞a和母雞b的數(shù)量確定后，其實小雞c的數(shù)量也就等于確定了，即c=100-a-b，從而就不需要再進(jìn)行加一重循環(huán)了，此時又可以去掉a+b+c=100這個約束條件，得到算法四如下：

以上算法的循環(huán)次數(shù)只有19*33=627次，相對上個算法又大幅度提高了算法的執(zhí)行效率。我們嘗試再進(jìn)行進(jìn)一步的分析： 我們可以進(jìn)一步分析出公雞、母雞和小雞的更小范圍，根據(jù)一只公雞5錢，一只母雞3錢，三只小雞1錢，得知，若a的值為15時，公雞的總錢為75錢，剩下的25錢最多可買75只小雞，達(dá)不到百雞數(shù)量的要求，所以公雞a的值必定小于15，a的大致范圍是1—14；若b的值為25時，母雞的總錢為75錢，剩下的25錢最多可買75只小雞，剛好達(dá)到百雞的數(shù)量，所以b的值不會超過25，b的大致取值范圍為1—25；由于a、b的最大值分別為14和25，那么要滿足百雞數(shù)量的話，c的最小值至少應(yīng)是61，又當(dāng)c的值為90只時，小雞的總錢才30錢，剩下10只即使都買公雞也只50錢，總錢達(dá)不到百錢的要求，所以c的值肯定是小于90，又c是3的倍數(shù)，所以大致估算c的取值范圍為63—87。既然a、b、c的大致范圍都確定了，我們可以得到下列算法五：

根據(jù)對算法五的三種情況進(jìn)行對比可以發(fā)現(xiàn)，情況一的執(zhí)行次數(shù)為126，情況二的執(zhí)行次數(shù)為25*9=225，情況三的執(zhí)行次數(shù)為14*25=350，顯然選擇取值范圍小的兩個變量作為循環(huán)變量來構(gòu)造二重循環(huán)是比較合理的，當(dāng)然這三種情況的算法執(zhí)行效率都要優(yōu)于前面的算法。

5 結(jié)論（Conclusion）

以上五個算法是應(yīng)用多重循環(huán)語句對“百錢買百雞”問題的算法分析，由差到優(yōu)循序漸進(jìn)地對算法進(jìn)行了改進(jìn)，通過每一次的改進(jìn)降低了算法的執(zhí)行時間，從最初的106次的循環(huán)執(zhí)行次數(shù)降到了最后的126次，最終得到了最為理想的算法。所以，我們在進(jìn)行算法設(shè)計時，不應(yīng)該只是得出了正確的算法就可以了，而是要盡量去尋找最優(yōu)的算法，要具有不斷地對已有算法設(shè)計進(jìn)行改進(jìn)和優(yōu)化的精神。當(dāng)然，該問題的解決方法不止于此，必定還會有一些更優(yōu)的算法值得我們?nèi)ヌ剿鳌?/p>

參考文獻(xiàn)（References）

[1] Fathima H.，Musthafa A.Syed.Optimization Based Routing Algorithms[J].International Journal of Applied Research on Information Technology and Computing，2014，5（1）：55-70.

[2] Guang-Yu Zhu，Wei-BoZhang.Optimal Foraging Algorithm for Global Optimization[J].Applied Soft Computing，2017，51：294-313.

[3] R.VenkataRao，G.G.Waghmare.A New Optimization Algorithm for Solving Complex Constrained Design Optimization Problems[J].Engineering Optimization，2017，49（1）：60-83.

[4] 黃隆華，陳志輝.算法設(shè)計與分析課程的“百錢買百雞問題”趣用[J].計算機(jī)教育，2016（3）：143-145.

[5] 耿國華.算法設(shè)計與分析[M].北京：高等教育出版社，2012（1）： 20-22.

[6] 許桂平.淺析C語言三種循環(huán)結(jié)構(gòu)語句[J].考試周刊，2014 （21）：117-118.

[7] 任愛華.C語言程序設(shè)計[M].北京：中央廣播電視大學(xué)出版社，2015：66-95.

[8] 馬學(xué)敏.計算機(jī)C語言循環(huán)語句的應(yīng)用研究[J].中國新通信， 2016（17）：87-88.

作者簡介：

龍敏敏（1979-），女，本科，講師.研究領(lǐng)域：計算機(jī)應(yīng)用技術(shù)，計算機(jī)教育教學(xué).