C語言中“窮舉”和“遞推”算法的基本思想分析

王 斌

（商洛學院，陜西 商洛 726000）

C語言中“窮舉”和“遞推”算法的基本思想分析

王 斌

（商洛學院，陜西 商洛 726000）

結合實際案例分析C語言中“窮舉”和“遞推”算法的基本思想，并對這兩種算法的實現方法加以分析和研究，通過C語言將其轉換成可操作執行的程序編碼。文中對“窮舉”測試標準的轉換技巧和測試范圍的控制方式進行了詳細的分析；對“遞推”算法從初值、法則和遞推次數三方面展開論述，同時對遞推的順序進行闡述。

C語言；窮舉算法；遞推算法

1 引言

C語言是很多學習程序設計的入門課程，因為C語言具有語言簡潔、數據符號豐富、易于結構化等特點，便于在實際應用中實現。本文對“窮舉”和“遞推”算法進行分析，了解其基本思想，然后針對不同的算法，對相關的問題進行細致的論述。在對“窮舉”算法的研究中，先對這一算法在簡單問題中的應用進行分析，其次對其測試標準的轉化技巧進行了研究探析，最后對測試范圍進行了分析和論述。在對“遞推”算法的研究中，通過對基本思想的概念理解，結合順推和逆推的案例進行了詳細的論述。

2 “窮舉”算法分析

“窮舉”算法的基本思想：在既有的范圍內，根據相應的測試標準，對問題的答案進行逐一驗證，進而求得答案的算法過程，在這一過程中的循環遍歷直至得出答案后終止程序運行[1]。從“窮舉”算法的基本思想可以看出，測試范圍和測試標準是代碼編寫和程序運行的關鍵點所在。

2.1 “窮舉”算法在簡單實例中的應用

比如求解1-100內17倍數的個數，當然這是個比較簡單的數學題目，根據已有的數學知識不難得出這一題目答案：1-100內17的倍數有5個；但結合C語言程序，通過一定的程序語言和“窮舉”算法該怎樣實現并得出這一數字呢？根據“窮舉”算法的思想，在這一范圍內對所有數字進行逐一驗證，最終得出符合條件的數字，進而得出數量。

而在C語言中，這也是屬于較為簡單的題目，所以相對應的邏輯程序也較為簡單，首先需要設置1-100之間每兩個相鄰數字之間的差為1，其次判斷條件為17的倍數，然后設定計數器的初始值為0；經過這一簡單邏輯的梳理，在C語言的編寫過程中，每當程序查找到一個滿足條件的數字時，計數器的數字會自動加1。在以上分析的基礎上，可以得到以下C語言代碼程序：

#include＜stdio.h＞

Viod main()

{int i,count=0;//程序開始處定義兩個整形變量，i為循環變量，0為計數器初始值；

for(i=1;i＜100;i++)//設置for循環，設定i的初始值為1，循環的條件為100以內；

{if(i%17==0)Count++;}//設置判定條件，i=17的倍數；當i是17的倍數的時候，計數器則自動+1；

Printf(“1-100之間是17倍數的數字的個數為：%d ”, count);}//輸出總數，符合條件的17的倍數的個數為5。

2.2 分析測試標準轉換技巧

對測試標準的轉換分析，本文結合“四葉玫瑰數”進行分析，由于“四葉玫瑰數”的概念，可以更加直觀形象地體現出測試標準的轉換技巧，“四葉玫瑰數”就是四位數的自冪數的名稱；例：1634=1*1*1+6*6*6+3*3*3+4*4*4.可以很明顯地看出，“四葉玫瑰數”的定義為：數字各位的立方之和等于數字本身。

為了實現C語言程序中的轉換，就“四葉玫瑰數”的例子來說，將某一四位數的四個數字進行變量的設置，a,b,c,d分別為個十百千在代碼中的代表字符，即可得到一個測試標準的公式：d*1000+c*100+b*10+a*1==d4+c4+b4b+a4。

假如給定條件，設置測試的范圍為1000-9999，大致邏輯同1-100內17倍數，相鄰數字之間的差為1，結合得出的4層循環公式，根據設定的條件，編寫對應的C語言代碼，可得出最終有三個符合條件的數字即：1634,8208,9474。

2.3 對“窮舉”算法測試范圍的把握分析

對于前面兩個相對簡單的例子，主要是利用循環遍歷的思路進行程序的設定編寫，從而得到所求的答案；但在這一部分所要結合的案例為“雞兔同籠”，對測試范圍的把握，以及對循環次數的控制方法的分析。

案例給出條件為：籠子里有雞兔共48只，腳的數量為132，求雞和兔各自的數量？這樣的題目，若用常規的數學方程思路來考慮，設出兩個方程變量，列出等式則很容易可以得出答案：雞30和兔18。但現在利用C語言的模式來考慮的話，同樣可以設置兩個變量雞的數量為i，兔的數量為j，那么相對應的測試標準則為：（i==48-j）&&(2*i+4*j==132).

根據實際情況進行分析，假設132只腳都為雞，但總數量為48，所以得出i＜48，同樣的邏輯可以推理出j＜33；在這些數據和條件下可以實現代碼的編寫：

#include＜stdio.h＞

Viod main()

{int i,j;//設置雞和兔數量兩個變量；

for(i=1;i＜48;i++)//i的循環范圍需小于48；

for(j=1;j＜48;j++)//j的循環范圍需小于33；

{if((i==48-j)&&(2*i+4*j==132))//與數學方程思維類似，列出變量等式，滿足頭48個，腳132個；

Prntf(“there are%d chicken,there are%d rabbits ”,i, j);}}//最終會顯示出運行結果數量分別為30和18.

這一例子只是眾多問題中的一個，是一個有解的問題，但在實際情況中，也會有很多問題，在詳細的分析、代碼的設計、程序的編寫等運行之后并沒有結果；針對無解的情況，在編寫代碼之初可以將這一問題考慮進去，在其中設置相應的變量加以標識，在程序運行過程中，當遇到這樣的情況時，系統會自動輸出相應的提示[2]。

3 “遞推”算法的研究

3.1 “遞推”算法的基本思想分析

“遞推”算法的基本思想為按照固有的法則，讀一個或多個元素進行推算，在規定的步驟內，最終得出所需的元素。基于這一思想，其中的固有法則通常理解為各元素之間的關系，從它們的關系中可以體現出數值變化的規律；一個或多個元素則是指遞推一開始的取值數字；規定的步驟是指遞推的次數；從中可以看出，“遞推”算法有三個關鍵的條件：遞推初始值，遞推法則和遞推次數。

以“10的階乘”為例來分析這三個關鍵條件的重要性，結合數學知識可得：n!=(n-1)!*n其中(n＞=1),通過分析可得遞推的初始值為1，遞推法則即為n!=(n-1)!*n，遞推次數則是由n的取值來決定的。以此為基礎條件，將其轉換為相應的語言代碼，設置出一個變量來反映1-10之間的變化，設定f來表示階乘結果，f的初始值為1。

3.2 順推和逆推的應用分析

遞推算法有兩種算法，分別為順推和逆推；前者為從既定的條件出發，根據相應的法則運算出最終的結果，后者則是從結果出發，通過一定的法則推算出起始條件。

首先來說順推法，結合斐波那契數列可以更加直觀形象地對這一方法進行描述；在數學家斐波那契的《算盤書中》有一個與兔子相關的問題：給出的條件為每對兔子每個月可以繁殖出一對小兔子，新生的每對兔子從第三個月也可以開始繁殖小兔子；假設最初只有一對兔子，并且兔子不死亡；在這樣的一個規律下生成的一個數列公式為：f(1)=1,f(2)=1,f(n)=f (n-1)+f(n-2)(n＞=3)；提出問題在第20個月的時候，兔子的總對數為多少？

根據給定的條件和需要求得的答案，代碼編寫如下：

#include＜stdio.h＞

Viod main()

{long int f1=1,f2=1;//設定初始值為1；

Int n;

For(n=1;n＜=9;n++)//n為遞推的循環次數；

{f1=f1=f2;//f1表示20個月內單月的兔子對數；

f2=f2=f1;}//f2表示20個月內雙月的兔子對數；

Printf(“%d”,f2);}//通過程序運行最終可得出結果為6765對。

接下來是逆推法的分析，經典的逆推法應用問題為“猴子吃桃”，這一問題的內容為：猴子第一天吃掉當前桃子數量的一半，然后多吃了一個；第二天吃了剩下桃子的一半，然后再多吃一個，以此類推；然而在第十天的時候剩下了一個桃子，問一開始有多少桃子？

這是一個很經典的知道結果數字，但沒有初始數字的題目，從而也就是最經典的逆推題型；根據各處的條件內容可以進行以下的假設和類推：最后一天為f(n)=1，然后倒數第二天的為f(n)=f(n-1)/2-16，整理可得f(n-1)=(f(n)+1)*2，從這一等式中可以理解為：前一天桃子的數量為當前加一之后的2倍；在現有的條件下可以對其進行C語言程序編寫，運行后可以得出結果為1534個。

4 結語

經過分析可以更加明確地了解兩種算法的特點；其中“窮舉”算法要具備一定的測試范圍和測試標準，然后進行循環遍歷測試出結果；“遞推”算法不管是順推法還是逆推法，都是要結合實際情況進行分析后，找出三個關鍵條件遞推初值、法則和遞推次數，然后再按照推算法則，求得結果[3]。這兩種算法在實際的應用中受控于循環，“窮舉”算法的循環遍歷和“遞推”算法的遞推算法被反復執行；在語言程序的編寫設計過程中，注意對結構的循環設置和對執行次數的循環控制，優化程序運行過程，提升運算效率。

[1]胡楓．《C語言程序設計》的案例式教學的設計[J]．青海師范大學學報：自然學科版，2010，26(4)：48-51．

[2]彭旭東．C語言小程序算法的表示[J]．天津理工大學學報，2011，27(3)：35-38．

[3]張新華．基于C語言的“窮舉”與“遞推”算法的研究[J]．齊齊哈爾大學學報(自然科學版)，2014(06)：29-32．

Analysis on the Basic Ideas of"Exhaustion"and"Recursion"Algorithms of C Language

Wang Bin
(Shangluo University,Shangluo 726000,Shaanxi)

This paper analyzes the basic ideas of"exhaustion"and"recursion"algorithms of C language with actual cases,and analyzes the implementation methods of these two algorithms,converting it into executable code with C language.The conversion skills of"exhaustion"testing standards and controlling ways of test range are analyzed.The"recursion"algorithm is analyzed from the initial value,rule,and recursion times,and the recursion sequence is expounded at the same time.

C language;exhaustion algorithm;recursion algorithm

TP312.1

A

1008-6609(2016)05-0049-02

王斌，男，陜西商州人，本科，工程師，研究方向：軟件工程。