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

王 斌

（商洛學(xué)院，陜西 商洛 726000）

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

王 斌

（商洛學(xué)院，陜西 商洛 726000）

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

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

1 引言

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

2 “窮舉”算法分析

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

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

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

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

#include＜stdio.h＞

Viod main()

{int i,count=0;//程序開始處定義兩個(gè)整形變量，i為循環(huán)變量，0為計(jì)數(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ù)；當(dāng)i是17的倍數(shù)的時(shí)候，計(jì)數(shù)器則自動(dòng)+1；

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

2.2 分析測(cè)試標(biāo)準(zhǔn)轉(zhuǎn)換技巧

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

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

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

2.3 對(duì)“窮舉”算法測(cè)試范圍的把握分析

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

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

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

#include＜stdio.h＞

Viod main()

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

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ù)學(xué)方程思維類似，列出變量等式，滿足頭48個(gè)，腳132個(gè)；

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

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

3 “遞推”算法的研究

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

[3]張新華．基于C語言的“窮舉”與“遞推”算法的研究[J]．齊齊哈爾大學(xué)學(xué)報(bào)(自然科學(xué)版)，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

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