“百錢買百雞”問題的C語言算法分析

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

關鍵詞：C語言；循環語句；百錢買百雞

中圖分類號：TP311.1 文獻標識碼：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）

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

2 C語言循環語句（C language loop statement）

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

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

of "spending 100 dollars on 100 chickens"）

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

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

4 算法設計與分析（Algorithm design and analysis）

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

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

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

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

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

根據對算法五的三種情況進行對比可以發現，情況一的執行次數為126，情況二的執行次數為25*9=225，情況三的執行次數為14*25=350，顯然選擇取值范圍小的兩個變量作為循環變量來構造二重循環是比較合理的，當然這三種情況的算法執行效率都要優于前面的算法。

5 結論（Conclusion）

以上五個算法是應用多重循環語句對“百錢買百雞”問題的算法分析，由差到優循序漸進地對算法進行了改進，通過每一次的改進降低了算法的執行時間，從最初的106次的循環執行次數降到了最后的126次，最終得到了最為理想的算法。所以，我們在進行算法設計時，不應該只是得出了正確的算法就可以了，而是要盡量去尋找最優的算法，要具有不斷地對已有算法設計進行改進和優化的精神。當然，該問題的解決方法不止于此，必定還會有一些更優的算法值得我們去探索。

參考文獻（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] 黃隆華，陳志輝.算法設計與分析課程的“百錢買百雞問題”趣用[J].計算機教育，2016（3）：143-145.

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

[6] 許桂平.淺析C語言三種循環結構語句[J].考試周刊，2014 （21）：117-118.

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

[8] 馬學敏.計算機C語言循環語句的應用研究[J].中國新通信， 2016（17）：87-88.

作者簡介：

龍敏敏（1979-），女，本科，講師.研究領域：計算機應用技術，計算機教育教學.