□屠新兵

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

中職C語言中窮舉法的編程方法探索

□屠新兵

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

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

C語言；窮舉法

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

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

1 百錢百雞問題

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

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

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

2 整錢化零問題

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

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

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

3 邏輯推理問題

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

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