第二章游戏中的数据结构与算法第三节基本

基本算法递归算法与二分搜索递归算法。二分搜索。了解递归算法的含义，掌握递归算法的基本运用。二分搜索算法，能使用二分搜索算法快速的在某队列中搜索数据。1递归函数是一个自己调用自己的函数。递归函数包括两种：直接递归（directrecursion）和间接递归。直接递归是指函数F的代码中直接包含了调用F的语句，而间接递归是指函数F调用了函数G，G又调用了H，如此进行下去，直到F又被调用。在深入探讨C++递归函数之前，来考察一下来自数学的两个相关概念——数学函数的递归定义以及归纳证明。在数学中经常用一个函数本身来定义该函数。例如阶乘函数f(n)=n！的定义。3.3基本算法3.3.7：递归算法2从该定义中可以看到，当n小于或等于1时，f(n)的值为1，如f(-3)=f(0)=f(1)=1。当n大于1时，f(n)由递归形式来定义，在定义的右侧也出现了f。在右侧使用f并不会导致循环定义，因为右侧f的参数小于左侧f的参数。从上阶乘定义可以得出：f(2)=2f(1)，由于已经知道f(1)=1，因此f(2)=2*1=2。以此类推，f(3)=3f(2)=3*2=6。3.3基本算法3.3.7：递归算法3对于函数f(n)的一个递归定义（假定是直接递归），要想使它成为一个完整的定义，必须满足如下条件：定义中必须包含一个基本部分，其中对于n的一个或多个值，f(n)必须是直接定义的（即非递归）。为简单起见，假定基本部分包含了n≤k的情况，其中k为常数。（在基本部分中指定n≥k的情形也是可能的，但较少见）。在递归部分中，右侧所出现的所有f的参数都必须有一个比n小，以便重复运用递归部分来改变右侧出现的f，直至出现f的基本部分。基本部分是：当n≤1时f(n)=1；递归部分是f(n)=nf(n-1)，其中右侧f的参数为n-1，比n要小。重复应用递归部分可把f(n-1)变换成对f(n-2)，f(n-3)，⋯，直到f(1)的调用。例如：f(5)=5f(4)=20f(3)=60f(2)=120f(1)3.3基本算法3.3.7：递归算法4作为递归定义的另外一个例子，来考察一下斐波那契数列的定义：例如：在这个定义中，=0和=1构成了定义的基本部分，

是定义的递归部分。右侧函数的参数都小于n。对于任何n>1的斐波那契数，对递归部分的重复应用应能把右侧出现的所有F变换成基本部分的形式。3.3基本算法3.3.7：递归算法5递归算法的特点：递归就是在过程或函数里调用自身。(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。(4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。3.3基本算法3.3.7：递归算法6递归算法的要求：递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)。二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)。三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。3.3基本算法3.3.7：递归算法7例如在象棋游戏中使用到了递归算法：3.3基本算法3.3.7：递归算法8intFactorial(intn){ if(n<=1) { return1; }else { returnn*Factorial(n-1); }}例如以下代码为最基础的求阶乘算法实现：3.3基本算法3.3.7：递归算法9例如把一个整数按n(2<=n<=20)进制表示出来，并保存在给定字符串中。比如121用二进制表示得到结果为：“1111001”。3.3基本算法3.3.7：递归算法10二分搜索又称折半搜索，它是一种效率较高的搜索方法。二分搜索要求：线性表是有序表，即表中节点按关键字已经进行排序，并且要用数组作为表的存储结构。不妨设有序表是递增有序的。二分搜索的基本思想二分搜索的基本思想是：设R[low..high]是当前的搜索区间。3.3基本算法3.3.8：二分搜索111）首先确定该区间的中点位置：2）然后将待查的K值与R[mid].key比较：若相等，则搜索成功并返回此位置，否则须确定新的搜索区间，继续二分搜索。具体方法如下：a）若R[mid].key>K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的搜索区间是左子表R[1..mid-1]。B）若R[mid].key<K，则要搜索的K必在mid的右子表R[mid+1..n]中，即新的搜索区间是右子表R[mid+1..n]。3.3基本算法3.3.8：二分搜索12二分搜索算法的执行过程已排序序列为：（2、3、5、8、9、11、12、16、18）若要搜索的值为11，则操作步骤如下：1）与第5个数值9比较2）因为11>9，所以和后半部分中间值12进行比较3.3基本算法3.3.8：二分搜索133）因为11<12，所以和前半部分的中间值11进行比较4）因为11=11，表示搜索已经完成，如不相等表示数据不在序列中。对二分搜索的分析如下：时间复杂度：因为每次搜索都会比上一次少一半的范围，所以最多只需要比较或

次，时间复杂度为

。运用二分搜索法搜索的数据必须是已排序的。此方法适合于不需要增删的静态序列。3.3基本算法3.3.8：二分搜索14二分搜索的性能分析：虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费O(nlgn)的时间。二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。3.3基本算法3.3.8：二分搜索15二分搜索的优点和缺点：优点:ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n次计较就可以完成查找过程。缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。因此可以通过一次比较抛弃更多的部分（即经过一次比较，使查找范围缩得更小），以达到提高效率的目的。把两种方法（顺序查找和折半查找）结合起来，即取顺序查找简单和折半查找高效之所长，来达到提高效率的目的。实际上这就是分块查找的算法思想。3.3基本算法3.3.8：二分搜索16以下代码为二分搜索的实现函数：intBinarySearch(intr[],constint&low,constint&high,constint&k){ intmid=(low+high)/2; if(low<high){ if(k<=r[mid]) BinarySearch(r,low,mid,k); else BinarySearch(r,mid+1,high,k); } elseif(low==high){ if(k==r[mid]) returnlow; else return-1; } else return-1;}3.3基本算法3.3.8：二分搜索17intmain(){ intnArray[9]={2,3,5,8,9,11,12,16,18}; intnKey=11; intindex=0; if(index=BinarySearch(nArray,0,8,nKey))

{ cout<<"数据"<<nKey<<"所在序列的位置为："<<index<<endl;

} else

{ cout<<"数据"<<nKey<<"不在此序列中"<<endl;

} system("pause"); return0;}3.3基本算法3.3.8：二分搜索18运行以上代码，执行效果如下：3.3基本算法3.3.8：二分搜索19本节介绍了递归算法。递归函数是一种自己调用自己的方法。通过本节的学习了解递归的概念和用法，二分搜索是一种效率较高的搜索方法。1.递归函数包括两种