搜索
C语言经典算法集锦摘要C语言是在国内外得到广泛使用的结构化程序设计语言，许多大型开发工具都以C语言作为基础语言。C语言功能丰富、表达力强、使用方便灵活，尤其是它的算法多种多样，非常经典，有些问题必须使用这些算法才能解决。本文主要介绍了C语言中几种常用的经典的算法，即迭代法、递归法、穷举法，并举例用C语言进行实现。Summary:theC-languageisastructuredprogramminglanguageusedwidelyathomeandabroad,manylargedevelopmenttoolsarebasedontheclanguageasabaselanguage.C-languagefeature-rich,articulate,easytouseandflexible,especiallyalgorithmsforawidevarietyofit,veryclassic,someofthesealgorithmsmustbeusedtoresolvetheproblem.Thispaperfocusesonseveralclassicalgorithms,iterative,recursivemethod,methodofexhaustion,andimplementingitforexampleinC-language.关键词C语言，算法，程序KeyC-languagealgorithmsprogram一、C语言概述1.1C语言的起源C语言是1972年由美国人丹尼斯•里奇（DennisRitchie）设计发明的，并首次在UNIX操作系统的DECPDP―11计算机上使用。它是由早期的编程语言BCPL发展演变而来的。1983年美国国家标准学会为C语言制定了一套ANSI标准。C语言自投入使用以来，逐渐发展成为当今使用最为广泛的程序设计语言之一。1.2C语言的特点1.C语言是一种结构化语言。函数是C语言的基本结构模块，所有的程序活动内容都包含在其中，函数在程序中被定义完成独立的任务，独立的编译成目标代码，这样可以实现模块的程序化。2.C程序简洁、紧凑、灵活。TurboC共有43个关键字，9种控制语句，程序书写自由；C语言语法要求不太严格，程序设计自由度大。3.C语言算法丰富多样。计算机算法是对问题求解过程的精确描述，分为数值运算算法和非数值运算算法，常用的数值运算算法有迭代法、递推法、递归法等;非数值算法有穷举法、回溯法、贪心法、分治法等。4.C语言是一种中级语言。C语言把高级语言的基本结构与低级语言的实用性结合起来，可以实现汇编语言的绝大部分功能。5.C语言移植性好。用C语言编写的程序移植性好，生成的目标代码质量高，程序执行速度快。二、算法在拿到一个需要求解的问题之后，怎样才能编写出程序呢？除了选定合理的数据结构外，十分关键的一步就是设计算法，有了一个好的算法，就可以用任何一种计算机高级语言把算法转化为程序。算法是指为解决某个特定问题而采取的确定且有限的步骤，即算法是问题求解过程的运算描述,一个算法由有限条可完全机械执行的、有确定结果的指令组成。一个算法有以下五个特性：1.有穷性。在执行若干个操作步骤之后，算法将结束，而且每一步都在合理的时间内完成。2.确定性。算法中每一条指令必须有确切的含义，不能有二义性，对于相同的输入必能得出相同的执行结果。3.可行性。算法中指定的操作，都可以通过已经验证过可以实现的基本运算执行有限次后实现。4.有零个或多个输入。在计算机上实现的算法是用来处理数据对象的，在大多数情况下这些数据对象需要通过输入来得到。5.有一个或多个输出。算法的目的是为了求“解”，这些“解”只有通过输出才能得到。三、算法可分为两大类:数值运算算法和非数值运算算法。数值运算算法的目的是求数值解,如:求方程的根、函数的定积分等。非数值运算算法应用十分广泛,如:图书检索、人事管理、文字处理等。常用的数值运算算法有迭代法、递归法等;非数值运算算法有穷举法等。下面就来介绍这些常用的算法。1.迭代算法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。它是用计算机解决问题的一种基本方法，利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。例1计算三次方程x³+px+q=0的一个实根，按照Cardan公式，该三次方程一个实根的公式为：Xr=3)3/(*)3/(*)3/()2/(*)2/(2/pppqqq+3)3/(*)3/(*)3/()2/(*)2/()2/(pppqqq在计算实根xr的程序中，把计算一个浮点数的立方根的程序作为一个用户定义函数，而在主程序中两次调用这个函数。在计算3y过程中，使用迭代公式:rn+1=(2/3)*rn+y/(3r2n)程序如下：#includeiostream.h#includemath.hfloatcuberoot(float);voidmain(void){floatp,q,xr;printf(“Inputparametersp,q:”);scanf(“%e%e”,&p,&q);floata=sqrt(q/2*q/2+p/3*p/3*p/3);xr=cuberoot(-q/2+a)+cuberoot(-q/2-a);printf(“Therealrootoftheequationis:”);}floatcuberoot(floatx){floatroot,croot;constfloateps=1e-6;croot=x;do{root=croot;croot=(2*root+x/(root*root))/3;}while(abs(croot-root)eps);return(croot);}这个程序包含了一个用户定义函数cuberoot(x)，它负责计算浮点型自变量x的立方根的值。在主函数main()中，这个函数两次被调用。2.递归算法程序调用自身的编程技巧称为递归。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。递归算法简单而自然，源程序代码短小紧凑。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。在回归阶段，获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。例2Hanoi塔问题这是一个典型的只有递归方法才能解决的问题。问题是这样的：有3根针A、B、C；A针上有64个盘子，盘子大小不等，大盘子在下小盘子在上。要求把这64个盘子从A针移到C针上，在移动过程可以借助B针，但每次只允许移动一个盘子，且在移动过程中3根针上都保持大盘在下小盘在上。要求编程打印出移动的步骤。将n个盘子从A针移动到C针可以分解为一下三个步骤：（1）将A针n-1个盘子借助C针先移动到B针上；（2）把A针剩下的一个盘子移到C针上；（3）将n-1个盘从B针借助A针移到C针上。例如，要想将A针上3个盘子移到C针上，可以分解为以下三步：（1）将A针上2个盘子移到B针上（借助C针）（2）将A针上1个盘子移到C针上；（3）将B针上2个盘子移到C针上（借助A针）。其中第（2）步可以直接实现。第（1）步又可用递归方法分解为：①将A上1个盘子从A移到C；②将A上1个盘子从A移到B；③将C上1个盘子从C移到B。第（3）步又可分解为：①将B上1个盘子从B移到A；②将B上1个盘子从B移到C；③将A上1个盘子从A移到C。将以上综合起来，可得到移动的步骤为：A---C,A---B,C---B,A---C,B---A,B---C,A---C。上面第（1）步和第（3）步，都是把n-1个盘子从一个针移动到另一个针上，采取的办法是一样的，只是针的名字不同而已。为使之一般化，可以将第（1）步和第（3）步表示为：将“one”针上n-1个盘子移到到“two”针，借助“three”针。只是在第（1）步和第（3）步中，one、two、three和A、B、C的对应关系不同。对第（1）步，对应关系应该是one—A，two—B，three—C。对第（3）步，one—B，two—C，three—A。因此，可以把上面3个步骤分为两类操作：（1）将n-1个盘子从一个针上移到另一个针上（n1）；（2）将1个盘子从一个针上移到另一个针上。下面编写程序。分别用两个函数实现以上两类操作，用hanoi（）函数实现上面第1类操作，用move（）函数实现以上第2类操作，hanoi（n，one，two，three）表示将n个盘子从“one”针移到“three”针，借助“two”针。move（getone，putone）表示将1个盘子从“getone”针移到“putone”针。getone和putone也是代表A、B、C针之一，根据每次不同情况分别取A、B、C代入。程序如下：voidmove();voidhanoi();main(){intm;printf(“Inputthenumberofdiskes:”);scanf(“%d”,&m);printf(“Thesteptomoving%3ddiskes:\n”,m);hanoi(m,’A’,’B’,’C’);}voidmove(chargetone,charputone){printf(%c---%c\n,getone,putone);}voidhanoi(intn,charone,chartwo,charthree){if(n==1)move(one,three);else{hanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three);}}运行情况如下：Inputthenumberofdiskes:3Thesteptomoving3diskes:A---CA---BC---BA---CB---AB---CA---C3.穷举算法计算机的特点之一就是运算速度快，善于重复做同一件事情，“穷举法”正是基于这一特点的最古老的算法。当找不到解决问题规律时，可根据问题中的“约束条件”将解的所有可能情况一一列举出来，然后再逐一验证是否符合整个问题的求解要求，从而得到问题的所有解。用穷举法解决问题的一般模式：（1）列出问题的可能范围，一般用循环或者循环嵌套来实现；（2）探究、挖掘出问题解的约束条件；(3)根据约束条件优化算法，尽可能的缩小穷举范围，减少穷举次数，降低算法的时间和空间复杂度。例3“水仙花数”问题。水仙花数是指一个三位数，它的各位数的立方和正好等于该数本身，例如，153=1³+5³+3³。打印所有的“水仙花数”。分析：“水仙花数”的百位范围是1--9，十位范围是0--9，个位范围0--9；约束条件：“水仙花数”的各位立方和等于这个数本身；选择结构：三重循环程序如下：#includestdio.hmain(){intx,y,z;for(x=1;x=9;x++){for(y=0;y=9;y++){for(z=0;z=9;z++)if(100*x+10*y+z==x*x*x+y*y*y+z*z*z)printf(“水仙花数是：”，100*x+10*y+z);}}}四、结语C语言是目前人们最常用的编程语言，它不仅有丰富的数据结构，还有多样的算法，针对不同类型的问题有不同的算法。例如，求方程的根或方程组的根就要用到迭代法；Hanoi问题的解决需要用到递归法；打印“水仙花数”用的是枚举法；等等。要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。因此，一个好的算法对编写程序至关重要。本文详细介绍了三种常用的C语言经典算法，每个算法后都给出具体实例并用C程序实现，这样不但加深了我对C语言算法的理解，使我能够运用自如，而且让读者对这三种常用的算法及其能够解决的问题有一个