“百錢買百雞”問(wèn)題的C語(yǔ)言算法分析

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

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

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

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

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

3 “百錢買百雞”問(wèn)題描述（The problem description

of "spending 100 dollars on 100 chickens"）

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

這是一個(gè)古典數(shù)學(xué)問(wèn)題，買一只公雞值5錢，一只母雞值3錢，三只小雞值1錢，問(wèn)如果用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ù)，該問(wèn)題用數(shù)學(xué)中的三元一次方程組表達(dá)如下：

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

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

該算法直接將三元一次方程轉(zhuǎn)化為C語(yǔ)言三重循環(huán)程序，沒(méi)有進(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；得到算法二如下：

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

此時(shí)我們?cè)賮?lái)計(jì)算一下以上算法需要執(zhí)行的循環(huán)次數(shù)為19*33*33=20691次，很明顯，此時(shí)算法的執(zhí)行效率有了一定的提高，縮小小雞c的取值范圍使得算法的循環(huán)次數(shù)變?yōu)樯蟼€(gè)算法的三分之一。那么這一次改進(jìn)后的算法就是最理想的算法嗎？還有沒(méi)有進(jìn)一步改進(jìn)的空間呢？答案是肯定的。其實(shí)只要我們?cè)僮屑?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次，相對(duì)上個(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ì)超過(guò)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ù)對(duì)算法五的三種情況進(jìn)行對(duì)比可以發(fā)現(xiàn)，情況一的執(zhí)行次數(shù)為126，情況二的執(zhí)行次數(shù)為25*9=225，情況三的執(zhí)行次數(shù)為14*25=350，顯然選擇取值范圍小的兩個(gè)變量作為循環(huán)變量來(lái)構(gòu)造二重循環(huán)是比較合理的，當(dāng)然這三種情況的算法執(zhí)行效率都要優(yōu)于前面的算法。

5 結(jié)論（Conclusion）

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

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

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

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

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

作者簡(jiǎn)介：

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