□屠新兵

(揚(yáng)州市邗江中等專業(yè)學(xué)校江蘇揚(yáng)州225009)

中職C語(yǔ)言中窮舉法的編程方法探索

□屠新兵

(揚(yáng)州市邗江中等專業(yè)學(xué)校江蘇揚(yáng)州225009)

在計(jì)算機(jī)編程語(yǔ)言的學(xué)習(xí)過(guò)程中，我們會(huì)遇到窮舉法的編程處理方法，包括百錢百雞問(wèn)題、整錢化零問(wèn)題、邏輯推理等等。本文主要以C語(yǔ)言編程為例，對(duì)窮舉法的編程方法進(jìn)行探索，讓大家對(duì)循環(huán)語(yǔ)句和分支語(yǔ)句有進(jìn)一步的了解。

C語(yǔ)言；窮舉法

在計(jì)算機(jī)編程語(yǔ)言的學(xué)習(xí)過(guò)程中，我們會(huì)遇到一些窮舉法的編程處理方法，包括百錢百雞問(wèn)題、整錢化零問(wèn)題、邏輯推理等等。當(dāng)我們對(duì)這些問(wèn)題進(jìn)行分析時(shí)會(huì)發(fā)現(xiàn)，它們中很多都可以用一種最原始的方法——窮舉法來(lái)解決。而窮舉法是最常用的一種方法，是C語(yǔ)言中的一個(gè)重要知識(shí)點(diǎn)。本文主要以C語(yǔ)言編程為例，對(duì)這些窮舉法的編程方法進(jìn)行探索，希望給大家?guī)?lái)一定的幫助。

我們先來(lái)了解一下，什么是窮舉法。窮舉法的基本思想是根據(jù)題目的部分條件確定答案的大致范圍，并在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到全部情況驗(yàn)證完畢。下面通過(guò)幾個(gè)實(shí)例，來(lái)對(duì)窮舉法編程處理方法進(jìn)行探索。

1 百錢百雞問(wèn)題

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

分析：本題用數(shù)學(xué)列方程解應(yīng)用題的方法，3個(gè)未知數(shù)，兩個(gè)方程，解決起來(lái)比較麻煩。在C語(yǔ)言中，就是典型的窮舉法的例子，用100元來(lái)買雞，公雞的數(shù)量(用變量i表示)的變化范圍是0-20只，母雞的數(shù)量(用變量j表示)的變化范圍是0-33只，總共100只，那么小雞的數(shù)量(用變量k表示)k=100-i-j，知道了數(shù)量，如果價(jià)錢正好是100元，就是本題的答案。程序如下：

拓展：本題是3個(gè)未知數(shù)，兩個(gè)方程，前兩個(gè)未知數(shù)可以通過(guò)窮舉的方法得到，第三個(gè)未知數(shù)可以通過(guò)其中的一個(gè)方程解得，另一個(gè)方程可以用來(lái)驗(yàn)證正確性。當(dāng)然，在本題中，小雞的數(shù)量也可窮舉，雙100可以用來(lái)驗(yàn)證，但這種算法讓計(jì)算機(jī)循環(huán)的次數(shù)太多，不夠優(yōu)化，所以不提倡。類似的題目有很多，如雞兔同籠問(wèn)題，已知頭的數(shù)目和腳的數(shù)目，求雞兔各有多少，兩個(gè)方程，兩個(gè)未知數(shù)，答案唯一，那么一個(gè)未知數(shù)用來(lái)窮舉，另一個(gè)未知數(shù)可以通過(guò)一個(gè)方程解得，剩下的一個(gè)方程用來(lái)驗(yàn)證。

2 整錢化零問(wèn)題

例2：將1元錢換成1角、2角、5角的零錢，輸出所有的換法。

分析：本題與上題的不同之處是，本題只有一個(gè)限制條件就是10元，對(duì)個(gè)數(shù)沒(méi)有限制，那么這個(gè)限制條件是用來(lái)驗(yàn)證的，1角、2角、5角的數(shù)量必須通過(guò)窮舉得到。程序如下：

拓展：如果需要兌換的整錢數(shù)額再大一些，允許零錢的品種再多一點(diǎn)，那就多加循環(huán)。類似的問(wèn)題很多，比如：?2*7?=3848，等式中缺一個(gè)十位數(shù)和一個(gè)個(gè)位數(shù)，編程求出這兩個(gè)數(shù)。前一個(gè)數(shù)的十位數(shù)和后一個(gè)數(shù)的個(gè)位數(shù)都需要窮舉，等式滿足即為找到。

3 邏輯推理問(wèn)題

例3：甲、乙、丙、丁四人同時(shí)參加全國(guó)數(shù)學(xué)競(jìng)賽，賽前甲乙丙分別做了預(yù)測(cè)：甲說(shuō)：丙第一名，我第三名。乙說(shuō)：我第一名，丁第四名。丙說(shuō)：丁第二名，我第三名。成績(jī)揭曉后，發(fā)現(xiàn)他們每人只對(duì)了一半，輸出他們的名次。

分析：這是小學(xué)邏輯推理問(wèn)題，人腦做起來(lái)相對(duì)簡(jiǎn)單。編程來(lái)講，可以用窮舉法來(lái)解決，也就是甲、乙、丙、丁四人都有可能1原4名（名次不相同）。具體是：甲(用變量i表示)名次范圍1原4，循環(huán)沒(méi)問(wèn)題；乙(用變量j表示)名次范圍1原4，與甲名次相同就跳過(guò)；丙(用變量k表示)的名次范圍1原4，與甲或乙相同就跳過(guò)；那么丁(用變量m表示)名次就是m= 10-i-j-k（1、2、3、4名次各一，總和是10），然后，驗(yàn)證三人的答案，答對(duì)一半可以用異或運(yùn)算符（^）來(lái)計(jì)算。程序如下：

1004-7026（2016）15-0125-02

F274

A

10.16675/j.cnki.cn14-1065/f.2016.15.094

屠新兵（1975.2-），男，江蘇邗江，揚(yáng)州市邗江中等專業(yè)學(xué)校綜合高中部主任,一級(jí)教師,研究方向：計(jì)算機(jī)教學(xué)。