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

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

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

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

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

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

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

of "spending 100 dollars on 100 chickens"）

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

這是一個(gè)古典數(shù)學(xué)問題，買一只公雞值5錢，一只母雞值3錢，三只小雞值1錢，問如果用100錢買100只雞，那么公雞、母雞和小雞分別多少只？我們假設(shè)公雞、母雞和小雞的個(gè)數(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è)計(jì)與分析（Algorithm design and analysis）

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

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

對于這個(gè)算法我們可以計(jì)算一下它的循環(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這個(gè)約束條件，得到算法三如下：

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

以上算法的循環(huán)次數(shù)只有19*33=627次，相對上個(gè)算法又大幅度提高了算法的執(zhí)行效率。我們嘗試再進(jìn)行進(jìn)一步的分析： 我們可以進(jìn)一步分析出公雞、母雞和小雞的更小范圍，根據(jù)一只公雞5錢，一只母雞3錢，三只小雞1錢，得知，若a的值為15時(shí)，公雞的總錢為75錢，剩下的25錢最多可買75只小雞，達(dá)不到百雞數(shù)量的要求，所以公雞a的值必定小于15，a的大致范圍是1—14；若b的值為25時(shí)，母雞的總錢為75錢，剩下的25錢最多可買75只小雞，剛好達(dá)到百雞的數(shù)量，所以b的值不會(huì)超過25，b的大致取值范圍為1—25；由于a、b的最大值分別為14和25，那么要滿足百雞數(shù)量的話，c的最小值至少應(yīng)是61，又當(dāng)c的值為90只時(shí)，小雞的總錢才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，顯然選擇取值范圍小的兩個(gè)變量作為循環(huán)變量來構(gòu)造二重循環(huán)是比較合理的，當(dāng)然這三種情況的算法執(zhí)行效率都要優(yōu)于前面的算法。

5 結(jié)論（Conclusion）

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

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

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

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

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

作者簡介：

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