Ox引言简谈常见的算法分析设计策略项波波，09713043（安徽中医学院信息工程学院，安徽合肥230031）摘要：对于计算机科学来说，算法分析与设计是至关重要的。怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中,这耍我们了解掌握各种算法分析设计策略。本文阐述冇哪些算法分析设计策略，说明各个策略的特点、方法。总结算法设计分析的各种分析设计策略，加深对各种算法分析设计的应用，学会运用各种算法设计分析问题。关键字：算法分析与设计、实质、特点、要求。JanetalkaboutcommonalgorithmanalysisdesignstrategyXIANGbobo,09713043(SchoolofMedicalandInformationEngineering,TraditionalChineseMedicineOfAnhuiUniversity,Hefei,anhui230031China)Abstract:forcomputersciencefor,thealgorithmanalysisanddesignisveryimportant.Howtoanalysisalgorithmof"good"intheHbadH,howtodesignalgorithm,andwidelyusedincomputerscience,thistoourunderstandingofallkindsofthealgorithmanalysisdesignstrategy.Thispaperanalyzeswhatalgorithmdesignstrategy,explainthecharacteristicsofvariousstrategiesandmethods.Summaryanalysisalgorithmdesignkindsofanalysisdesignstrategy,deepenourunderstandingofthevariousalgorithmanalysisanddesignoftheapplication,andlearntouseallkindsofalgorithmdesignanalysisproblem.Keyword:algorithmanalysisanddesign,theessence,thecharacteristic,therequirements・：TU4U.01文献标识码：A我们一般常见的几种算法分析设计策略主耍有：递归算法、动态规划、贪心算法、冋溯法、分支限界法。接下來我主要介绍一下这几种算法。1.1递归算法：直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。递归算法的实质：递归算法的实质：是把问题转化为规模缩小了的同类问题的了问题。然后递归调用函数(或过程)來表示问题的解。递归算法的特点：递归算法解决问题的特点：(1)递归就是在过程或函数里调用自身。(2)在使用递归策略时，必须冇一个明确的递归结朿条件，称为递归出口。(3)递归算法解题通常显得很简洁，但递归算法解题的运行效率鮫低。所以一般不提倡用递归算法设计程序。(4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈來存储。递归次数过多容易造成栈溢出等。所以一般不提们用递归算法设计程序。递归算法举例：描述：把一个整数按n(2<=n<=20)进制表示出來，并保存在给定字符串中。比如121用二进制表示得到结果为：“X11001\参数说明：s:保存转换后得到的结果。n:待转换的整数。b:n进制(2<二nv=20)voidnumbconv(char*s,intn,intb){intlen;if(n==0){strcpy(s,return;}/*figureoutfirstn-1digits*/numbconv(s,n/b,b);/*addlastdigit*/len=strlen(s);s[len]=n0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZn[n%b];s[len+1]='\0：}voidmain(void){chars[20];inti,base;FILE*fin,*fout;fin=fopen(npalsquareJn”，fout=fopenCpalsquare.out,f,,fw”)；assert(fin!=NULLfout!=NULL);fscanf(fin,"%d",base);/*PLSsetSTARTandEND*/for(i=START;i<=END;i++){numbconv(s,i*i,base);fprintf(fout,M%s\nM,s);}exit(0);}1.2分治法在计算机科学中，分治法是一种很垂耍的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序,归并排序)，傅立叶变换(快速傅立叶变换)分治策略：对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。分治法所能解决的问题一般具有以下几个特征：1)该问题的规模缩小到一定的程度就可以容易地解决2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。3)利用该问题分解出的子问题的解...