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

王斌，男，陕西商州人，本科，工程师，研究方向：软件工程。