王 斌

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

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

王 斌

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

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

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

1 引言

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

2 “窮舉”算法分析

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

2.1 “窮舉”算法在簡單實例中的應(yīng)用

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

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

#include＜stdio.h＞

Viod main()

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

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

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

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

2.2 分析測試標準轉(zhuǎn)換技巧

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

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

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

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

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

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

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

#include＜stdio.h＞

Viod main()

{int i,j;//設(shè)置雞和兔數(shù)量兩個變量；

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

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

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

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

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

3 “遞推”算法的研究

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

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

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

3.2 順推和逆推的應(yīng)用分析

遞推算法有兩種算法，分別為順推和逆推；前者為從既定的條件出發(fā)，根據(jù)相應(yīng)的法則運算出最終的結(jié)果，后者則是從結(jié)果出發(fā)，通過一定的法則推算出起始條件。

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

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

#include＜stdio.h＞

Viod main()

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

Int n;

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

{f1=f1=f2;//f1表示20個月內(nèi)單月的兔子對數(shù)；

f2=f2=f1;}//f2表示20個月內(nèi)雙月的兔子對數(shù)；

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

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

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

4 結(jié)語

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

[1]胡楓．《C語言程序設(shè)計》的案例式教學的設(shè)計[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

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