常见的10种算法

admin 2024-12-13 12:03:56162 174

常见的10种算法

一般有以下几种常用运算：

检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。

插入：往数据结构中增加新的节点。

删除：把指定的结点从数据结构中去掉。

更新：改变指定节点的一个或多个字段的值。

排序：把节点按某种指定的顺序重新排列。例如递增或递减。

1、递归算法

递归过程一般通过函数或子过程来实现。

递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。

递归算法解决问题的特点：

递归就是在过程或函数里调用自身。

在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

下面来详细分析递归的工作原理。

先看看C语言中函数的执行方式，需要了解一些关于C程序在内存中的组织方式：

堆的增长方向为从低地址到高地址向上增长，而栈的增长方向刚好相反（实际情况与CPU的体系结构有关）。

当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息，每一个调用都被当作是活跃的。

栈上的那块存储空间称为活跃记录或者栈帧。

栈帧由5个区域组成：输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数，参见下图：

栈是用来存储函数调用信息的绝好方案，然而栈也有一些缺点：

栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用相当大的空间，尤其是在程序中使用了许多的递归调用的情况下。

除此之外，因为有大量的信息需要保存和恢复，因此生成和销毁活跃记录需要消耗一定的时间。

我们需要考虑采用迭代的方案。幸运的是我们可以采用一种称为尾递归的特殊递归方式来避免前面提到的这些缺点。

例题1：计算n！

计算n的阶乘，数学上的计算公式为：

使用递归的方式，可以定义为：

以递归方式实现阶乘函数的实现：

(void){intsumInt=fact(3);printf("3的阶乘为：%d\n",sumInt);system("PAUSE");//结束不退出}//递归求阶乘intfact(intn){if(n0)return0;elseif(n==0||n==1)return1;elsereturnn*fact(n-1);}

例题2：斐波那契数列

(void){printf("%d\n",fibonacci(10));system("PAUSE");//结束不退出}//斐波那契数列，第一二项为1；后面的每一项为前两项之和intfibonacci(inta){if(a==1||a==2){return1;}else{returnfibonacci(a-1)+fibonacci(a-2);}}

例题3：递归将整形数字转换为字符串

(void){charstr[100];inti;printf("enterainteger:\n");scanf("%d",i);toString(i,str);puts(str);system("PAUSE");//结束不退出}//递归将整形数字转换为字符串inttoString(inti,charstr[]){intj=0;charc=i%10+'0';if(i/=10){j=toString(i,str)+1;}str[j]=c;str[j+1]='\0';returnj;}

例题4：汉诺塔

//递归汉诺塔voidhanoi(inti,charx,chary,charz){if(i==1){printf("%c-%c\n",x,z);}else{hanoi(i-1,x,z,y);printf("%c-%c\n",x,z);hanoi(i-1,y,x,z);}}voidmain(void){hanoi(10,'A','B','C');system("PAUSE");//结束不退出}

例题5：猴子吃桃

//猴子吃桃，每天吃一半再多吃一个，第十天想吃时候只剩一个intchitao(inti){if(i==10){return1;}else{return(chitao(i+1)+1)*2;}}voidmain(void){printf("%d",chitao(5));system("PAUSE");//结束不退出}

例题6：N皇后问题

/*======================N皇后问题========================*/define_CRT_SECURE_NO_WARNINGS//避免scanf报错define_CRT_SECURE_NO_WARNINGS//避免scanf报错_CRT_SECURE_NO_WARNINGS//避免scanf报错define_CRT_SECURE_NO_WARNINGS//避免scanf报错/**定义最大数组大小**///（感觉没啥用但是最好尽可能开大点，但是不要太大，不要超出系统可建造范围）typedefstructNode*Hash;/**新的路程又开始了这次准备用数组来做哈希还有双向平方处理冲突**/structNode{charphone[15];intnum;};intmaxInt(intx,inty){if(xy)returnx;elsereturny;}char*minstr(char*x,char*y){if(strcmp(x,y)0)returny;elsereturnx;}intnextprime(constintn){intp=(n%2==1)?n+2:n+1;/**先找一个大于N的奇数**/inti;while(pMAX){for(i=(int)sqrt(p);i=2;i--)/**然后再判断是不是素数**/if(p%i==0)break;if(i2)returnp;/**是那就返回这个数**/elsep+=2;/**不是那就下一个奇数**/}}intdeal(char*s,intp)/**然后把字符串映射成下标(映射的方式很多很多，随便猜一个靠谱的就行了)**/{intindex=(atoi(s+2))%p;returnindex;}intinsert(Hashh,intpos,char*s,intp,intMax)/**哈希查找的插入实现,分别是哈希数组，数组位置，身份证号，数组最大大小,MAX看到代码最后就明白了**/{inti,posb=pos;/**备份pos值方便双向平方查找**/for(i=1;;i++){if(strcmp(h[pos].phone,"")==0)/**如果为pos的值空直接插入**/{strcpy(h[pos].phone,s);h[pos].num++;Max=max(Max,h[pos].num);break;}else{if(strcmp(h[pos].phone,s)==0)/**不为空的话，就看看身份证号是不是想等**/{h[pos].num++;Max=maxInt(Max,h[pos].num);break;}else{//原p%2==1if(i%2==1)pos=(posb+(i*i))%p;/**不相等就找下一个位置，分别向后找一次和往前找一次，如此循环**/else{//原i*ipos=posb-((i-1)*(i-1));while(pos0)pos+=p;}}}}returnMax;}voidinitial(Hashh,intp)/**把哈希数组初始化（初始化的动词英文忘记咋写了。。。。）**/{inti;for(i=0;ip;i++){h[i].phone[0]='\0';h[i].num=0;}}intmain(){intMax=0;intn;/**总数N然后就开始找大于N的最小素数了**/scanf("%d",n);/**输出中把\n也输入进去避免下面输入会出现奇葩的事情**/intp=nextprime(2*n);/**突然想起来每次输入的都是俩电话号码，所以电话号码最大数是2*n**/Hashh=(Hash)malloc(p*sizeof(structNode));/**建立哈希数组**/initial(h,p);charphone[15];charphone1[15];while(n--){scanf("%s%s",phone,phone1);Max=insert(h,deal(phone,p),phone,p,Max);Max=insert(h,deal(phone1,p),phone1,p,Max);}inti,num=0;char*Minstr=NULL;for(i=0;ip;i++){if(h[i].num==Max){if(Minstr==NULL)Minstr=h[i].phone;elseMinstr=minstr(Minstr,h[i].phone);num++;}}printf("%s%d",Minstr,Max);if(num1)printf("%d",num);system("PAUSE");//结束不退出}

6、贪心算法

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件，直到把所有数据枚举完。

贪心算法的思想如下：

建立数学模型来描述问题；

把求解的问题分成若干个子问题；

对每一子问题求解，得到子问题的局部最优解；

把子问题的解局部最优解合成原来解问题的一个解。

与动态规划不同的是，贪心算法得到的是一个局部最优解（即有可能不是最理想的），而动态规划算法得到的是一个全局最优解（即必须是整体而言最理想的），

一个有趣的事情是，动态规划中的01背包问题就是一个典型的贪心算法问题。

如下例子：贪心算法货币统计问题

_CRT_SECURE_NO_WARNINGS//避免scanf报错include""intpower(intx,intn){intresult;if(n==1)returnx;if(n%2==0)result=power(x,n/2)*power(x,n/2);elseresult=power(x,(n+1)/2)*power(x,(n-1)/2);returnresult;}voidmain(){intx=5;intn=3;printf("power(%d,%d)=%d\n",x,n,power(x,n));system("PAUSE");//结束不退出}

归并排序

时间复杂度是O(NlogN)O(Nlog⁡N)，空间复制度为O(N)O(N)（归并排序的最大缺陷）
归并排序（MergeSort）完全遵循上述分治法三个步骤：

分解：将要排序的n个元素的序列分解成两个具有n/2个元素的子序列；

解决：使用归并排序分别递归地排序两个子序列；

合并：合并两个已排序的子序列，产生原问题的解。

include""include""define_CRT_SECURE_NO_WARNINGS//避免scanf报错#//设置一个数组，数组的下标表示集合中的元素，所以数组只用下标为1，2，3的空间intset[5];//i代表数组下标，n表示集合中最大的元素值voidPowerSet(inti,intn){//当in时，说明集合中所有的元素都做了选择，开始判断if(in){for(intj=1;j=n;j++){//如果树组中存放的是1，说明在当初尝试时，选择取该元素，即对应的数组下标，所以，可以输出if(set[j]==1){printf("%d",j);}}printf("\n");}else{//如果选择要该元素，对应的数组单元中赋值为1；反之，赋值为0。然后继续向下探索set[i]=1;PowerSet(i+1,n);set[i]=0;PowerSet(i+1,n);}}voidmain(){intn=3;for(inti=0;i5;i++){set[i]=0;}PowerSet(1,n);system("PAUSE");//结束不退出}

很多人认为回溯和递归是一样的，其实不然。在回溯法中可以看到有递归的身影，但是两者是有区别的。
回溯法从问题本身出发，寻找可能实现的所有情况。和穷举法的思想相近，不同在于穷举法是将所有的情况都列举出来以后再一一筛选，而回溯法在列举过程如果发现当前情况根本不可能存在，就停止后续的所有工作，返回上一步进行新的尝试。
递归是从问题的结果出发，例如求n！，要想知道n！的结果，就需要知道n*(n-1)!的结果，而要想知道(n-1)!结果，就需要提前知道(n-1)*(n-2)!。这样不断地向自己提问，不断地调用自己的思想就是递归。

使用回溯法解决问题的过程，实际上是建立一棵“状态树”的过程。

例如，在解决列举集合{1,2,3}所有子集的问题中，对于每个元素，都有两种状态，取还是舍，所以构建的状态树为：

回溯算法的求解过程实质上是先序遍历“状态树”的过程。树中每一个叶子结点，都有可能是问题的答案。图1中的状态树是满二叉树，得到的叶子结点全部都是问题的解。

在某些情况下，回溯算法解决问题的过程中创建的状态树并不都是满二叉树，因为在试探的过程中，有时会发现此种情况下，

再往下进行没有意义，所以会放弃这条死路，回溯到上一步。在树中的体现，就是在树的最后一层不是满的，即不是满二叉树，需要自己判断哪些叶子结点代表的是正确的结果。

9、动态规划(DP)算法

基本思想原理

与分而治之原理类似，将待求解的问题划分成若干个子问题（阶段）求解，顺序求解各个子问题（阶段），前一子问题（阶段）为后一子问题（阶段）的求解提供有用的信息。

通过各个子问题（阶段）的求解，依次递进，最终得到初始问题的解。一般情况下，能够通过动态规划求解的问题也可通过递归求解。

动态规划求解的问题多数有重叠子问题的特点，为了减少重复计算，对每个子问题只求解一次，将不同子问题（阶段）的解保存在数组中。

与分而治之的区别：

与递归区别：

适用解决问题

采用动态规划求解的问题一般具有如下性质：

最优化原理：求解问题包含最优子结构，即，可由前一子问题（阶段）最优推导得出后一子问题（阶段）最优解，递进得到初始问题的最优解。

无后效性：某状态以后的过程不会影响以前的状态，只与当前状态有关。

有重叠子问题：子问题（阶段）之间不是独立的，一个子问题（阶段）的解在下一子问题（阶段）中被用到。（不是必需的条件，但是动态规划优于其他方法的基础）

比如斐波那契数列，就是一个简单的例子。

定义：

Fab(n)=Fab(n-1)+Fab(n-2)Fab(1)=Fab(2)=1;

实现1：

staticintGetFab(intn){if(n==1)return1;if(n==2)return1;returnGetFab(n-1)+GetFab(n-2);}

假如我们求Fab(5)。那我们需要求Fab（4）+Fab（3）。

Fab(4)=Fab(3)+Fab(2)..显然。Fab（3）被计算机不加区别的计算了两次。而且随着数字的增大，计算量是指数增长的。

如果我们使用一个数组，记录下Fab的值。当Fab(n)!=null时。

直接读取。那么，我们就能把时间复杂度控制在n以内。

实现2：

staticint[]fab=newint[6];staticintGetFabDynamic(intn){if(n==1)returnfab[1]=1;if(n==2)returnfab[2]=1;if(fab[n]!=0)//如果存在，就直接返回。{returnfab[n];}else//如果不存在，就进入递归，并且记录下求得的值。{returnfab[n]=GetFabDynamic(n-1)+GetFabDynamic(n-2);}}

这就是，动态规划算法的备忘录模式。只需要把原来的递归稍微修改就行了。

下面是0-1背包问题的解法。

可以对比一下。（一个限重w的背包，有许多件物品。sizes[n]保存他们的重量。values[n]保存它们的价值。求不超重的情况下背包能装的最大价值）

staticint[]size=newint[]{3,4,7,8,9};//5件物品每件大小分别为3,4,7,8,9且是不可分割的0-1背包问题staticint[]values=newint[]{4,5,10,11,13};////5件物品每件的价值分别为4,5,10,11,13staticintcapacity=16;staticint[,]dp=newint[6,capacity+1];staticintknapsack(intn,intw){if(w0)return-10000;if(n==0)return0;if(dp[n,w]!=0){returndp[n,w];}else{returndp[n,w]=(knapsack(n-1,w),knapsack(n-1,w-size[n-1])+values[n-1]);/**knapsack(n,w)指在前N件物品在W剩余容量下的最大价值。*这个公式的意思是，对于某一件物品，*1、如果选择装进去，那么，当前价值=前面的n-1件物品在空位w-size(n)下的最大价值（因为空位需要留出，空位也隐含了价值）。*再加上这件物品的价值。等于knapsack(n-1,w-size[n-1])+values[n-1]*2、如果我们选择不装进去，那么，在n-1物品的情况下空位仍然在，当前价值=前面n-1件物品在空位w下的最大价值。*等于knapsack(n-1,w)*注意：随着演算，某一情况下的价值不会一成不变。*此时我们做出决策：到底是在装入时的价值大，还是不装入时的价值大呢？我们选择上面两种情况中值较大的。并记录在案。*最后dp[N,M]就是我们要求的值。*/}}

10、字符串匹配算法

字符串匹配问题的形式定义：

文本（Text）是一个长度为n的数组T[1..n]；

模式（Pattern）是一个长度为m且m≤n的数组P[1..m]；

T和P中的元素都属于有限的字母表Σ表；

如果0≤s≤n-m，并且T[s+1..s+m]=P[1..m]，即对1≤j≤m，有T[s+j]=P[j]，则说模式P在文本T中出现且位移为s，且称s是一个有效位移（ValidShift）。

比如上图中，目标是找出所有在文本T=abcabaabcabac中模式P=abaa的所有出现。

该模式在此文本中仅出现一次，即在位移s=3处，位移s=3是有效位移。

解决字符串匹配的算法包括：

朴素算法（NaiveAlgorithm）、

Rabin-Karp算法、

有限自动机算法（FiniteAutomation）、