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

□屠新兵

(揚州市邗江中等專業學校江蘇揚州225009)

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

□屠新兵

(揚州市邗江中等專業學校江蘇揚州225009)

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

C語言；窮舉法

在計算機編程語言的學習過程中，我們會遇到一些窮舉法的編程處理方法，包括百錢百雞問題、整錢化零問題、邏輯推理等等。當我們對這些問題進行分析時會發現，它們中很多都可以用一種最原始的方法——窮舉法來解決。而窮舉法是最常用的一種方法，是C語言中的一個重要知識點。本文主要以C語言編程為例，對這些窮舉法的編程方法進行探索，希望給大家帶來一定的幫助。

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

1 百錢百雞問題

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

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

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

2 整錢化零問題

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

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

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

3 邏輯推理問題

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

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

1004-7026（2016）15-0125-02

F274

A

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

屠新兵（1975.2-），男，江蘇邗江，揚州市邗江中等專業學校綜合高中部主任,一級教師,研究方向：計算機教學。