试题选讲课件

1、问题选讲北京大学 姚金宇第一部分 基础算法 车站 这是一个简陋的小火车站，整个车站只由一个进站口，一个出站口和一个栈道组成。如右图。火车在车站有三种调度情况：从进站口进入栈道从栈道进入出站口从进站口直接出站。车站其中栈道保证后进先出。现有n辆火车在进站口等待出站，排列为1，2，n。你的任务是计算一共有多少种不同出站序列。例如n=3时 进站序列为1，2，3。则一种可行的出站序列为3，1，2（调度方法为3进栈，2出站，1出站，3从栈道出站）简化操作我们将直接出站分成下列两个连续的操作：从进站口进栈道从栈道进出站口三种操作两种操作之后无论用何种算法，都会大大提高解决问题的效率。递推模型设f(i,j)

2、表示当进站口有i辆车，栈道中有j辆车，一共有多少种出站方式。f(i,j)=f(i-1, j+1) + f(i, j-1)边界 f(0,i)=1则f(n,0)即为所求。ANNIVERSARY CAKE给你一个S*S的方形蛋糕，要求你将其切成n块，每一块是ai*ai的方形。要求没有遗漏。输入S,n及a1,an，判断是否能够得到一种满足要求的切法。n=16，ai=10分析首先判断若S*S!=sigam(ai*ai)，则必然无解。否则深度优先搜索蛋糕的切法（实际上是枚举小蛋糕块的拼法）。每次找到最左上的一个空位置，易知这个位置一定是放置某一个小蛋糕块的最左上角。这样我们只需要再枚举还未填入的一个小蛋糕

3、块，若能够填入，则继续放入后继续递归；否则判断其他的小蛋糕块。最左上角未被填入的空位置（约定判断顺序为先上后左）判断该小蛋糕块能否填入优化判断小蛋糕块能否放入的时候，只需要检查最上边缘有没有被放置过蛋糕即可。这是因为每次都是贴着左上边沿放蛋糕，若当前蛋糕不能放置，则它的上边缘一定有某个方格以前被放置过蛋糕了。这样检查的时间复杂度从O(n2)降到了O(n)在搜索的时候对ai进行从大到小排序，先判断大蛋糕，后判断小蛋糕。在当前层的搜索中，对于当前的枚举的ai，若当前曾已经枚举过一个ak有ak=ai，则对于ai的枚举就是重复的，需要剪枝。问题：还有什么剪枝吗？求第K小数长度为n的序列a1,a2,an

4、，求其中的第k小数。分析可以先排序，然后直接确定第k小数。至少需要O(nlogn)的时间复杂度。其实我们没有必要知道所有的有序信息。设一个pivot，若n个数中:b1,b2,bm都比pivot小;c1,c2,cn-m都不比pivot小则若k=m则第k小的数在b中否则所求的数在c中如何分？xpivoti1,jnWhile (i=j)If (aix) j-;If (i=j)Swap ai, aj;i+; j-;a1aj都比pivot小，aj+1an都不比pivot小PIVOT的选择随机在pivot随机的情况下，该算法的期望是线性的。如何理解？有没有最坏情况下是线性的算法？第二部分 字符串算法 最长

5、重复子串对于串S，若它存在一个子串T，T在S中至少出现两次，则我们称T是S的一个重复子串。求长度为n的串S的最长重复子串例如S=abcdacdac，则最长重复子串为cdac预备知识后缀串最长公共前缀串的模式匹配算法模式匹配的KMP算法字母树第一种解法nexti的含义对每一个S的后缀S(pn)，求next数组，取出maxnexti-1就是该后缀的最长前缀重复串。算法的时间复杂度O(n2)第二种解法最长重复子串，必然是某两个后缀串的最长公共前缀。将所有的后缀串建成一棵字母树，即可求出任两个后缀的最长公共前缀 a b b a a S=aba 该算法的时间复杂度也是O(n2)更好的算法本题可以用更高级

6、的数据结构解决后缀数组后缀树运用它们可以得到O(nlogn)甚至O(n)的算法第三部分 数学问题SPECIAL SUBSET给定集合M=1，2，n，取出M的所有不包含相邻自然数的子集合例如1,3就是一个符合要求的而1,3,4就不是对于每一个这样的子集合Si，求它的元素之积Ti。例如对于Si=1,3,Ti=1*3=3输出所有Ti的平方和例子n=4M=1,2,3,4S:1,2,3,4,1,3,2,4,1,4T:1,2,3,4,3,8,4T2:1,4,9,16,9,64,16输出1+4+9+16+9+64+16=119当问题的规模为N时第一种情况S集合只包含n，T=n*n第二种情况S集合包含n和其他

7、的数，则“其他的数”最大是n-2。第三种情况S集合不包含n，则“其他的数”最大是n-1n=4的情况4:4*41,4, 2, 4:(1*4)2 * (2*4)2=(1*1+2*2)*4*41231,3: (n=3的情况)抽象设Fi表示n=i时的平方和Fi=i*i +Fi-2*i*i +Fi-1O(n)的递推算法CALLING EXTRATERRESTRIAL INTELLIGENCE AGAIN 给定三个整数m,a,b，求两个正整数p, q满足：p和q都是素数p*q = ma/b = p/q = 1在满足1-3的前提下，p*q最大数据范围：4 m = 100000 ； 1 = a = b = 1

8、000.输入文件包含有不超过2000组数据。基本思路枚举较小的素数p，这样q是满足下面两个情况下的最大的素数：q=m/pq=p*b/a我们需要解决两个子问题：找出素数找出素数序列中满足要求的最大数素数(PRIME)大于1的正整数p被称作素数，如果p仅有的正因子是1和p素数判定理论：如果n是合数，则他必有一个小于或等于sqrt(n)的约数。操作：枚举2至sqrt(n)的所有整数，判断其中有无p的约数。时间复杂度：O(sqrt(n)ERAOSTHENES筛法（筛选法）问题：如何求2-n中所有的素数？筛选法：建立一个表，给每个值标记true从2到n枚举每一个整数p，如果当前p的标记为true，则p为

9、素数若当前p为素数，则将n以内的p*p , p*(p+1),都标记为false（被筛去）伪素数测试费马小定理 如果p是一个素数，则对于任意的a,若(a,p)=1，则 ap-1=1(mod p)n是一个正整数，若an-1=1(mod n)，我们说n是基于a的一个伪素数。伪素数测试若一个数是伪素数，则它几乎肯定是素数；若一个数不是伪素数，则它一定不是素数。我们可以通过多次选取基数a（通常选取2,3,5,7进行测试)，如果n都是伪素数，则它几乎可以肯定是素数了。回到原问题筛选法求1-MAXM的素数表的时间复杂度为O(n*ln(n)对于每一个询问，枚举p，在素数表里面二分查找最大的满足两个条件的素数即

10、可。枚举p的时间复杂度为O(sqrt(n)二分查找q的时间复杂度为O(log2m)，其中m为素数表的规模。关于二分在问题不好直接得到答案的时候，枚举答案再进行判断往往是一个有效的办法。这时候往往就要用到二分法典型例子：解奇数次的一元方程MATRIX MULTIPLICATION给定三个n*n的矩阵A，B，C判断A*B是否等于C？关于矩阵矩阵的概念由英国数学家Sylvester于1850年首先提出1858年 英国数学家Cayley建立了矩阵运算规则矩阵是一个强有力的工具，它能够把一组相互独立的数用一张数表的形式联系起来，看成一个整体，并用它来参与运算。用矩阵描述一个复杂物体是非常紧凑的矩阵在自然

11、科学、工程技术、社会科学等领域中有着广泛的应用矩阵定义由mn个数排成m行、n列的矩阵阵列：称为 m 行 n 列矩阵，简记为mn矩阵，A=称 为 A 的第 i 行第 j 列元素。矩阵乘法_定义设A为ms矩阵，B为sn矩阵A与B的乘积为一mn矩阵C，定义如下：N阶方阵的幂定义A1 = A, A2 = AA, A3 = A2A, , Ak = Ak-1AAk即为k个A相乘只有方阵的幂才有意义AkAl = Ak+l, (Ak)l = Akl矩阵的幂跟数的幂性质很相似联想：如何求(A)k回到原问题直接计算A*B，然后再与C进行逐一元素的比对，这样的时间复杂度是O(n3)联想到素数判定的伪素数测试（必要条

12、件测试！）假设有一个随机的n*1的矩阵X，若A*B=C则必然有X*(A*B)=X*CX*(A*B)=(X*A)*B=Y*B，Y=X*A也是一个n*1的矩阵！计算X*A,Y*B,X*C的时间复杂度都是O(n2)问题的解决我们可以随机产生k个X矩阵，进行上述的测试。若全部满足，则我们可以“几乎”肯定A*B=C了。算法的时间复杂度O(n2)扩展问题给定三个n*n的矩阵A,B,CA*B要么等于C，要么与C矩阵有一个元素不相同。判断A*B是否等于C，若不相等，找出那个不相同元素的位置FLAVIUS JOSEPHUS RELOADED对于如下递推方程：F1=C (CN)Fi=(aFi-1+b) mod N

13、求F的循环节长度a, b, N=109，保证循环节长度不超过106在跑圈的时候如果和同时起跑A的速度为1，B的速度为2则会在时间之后再次追上我们把这个原理运用到求循环节的问题中来追赶法Function：f(x)return (a*x+b)%Nx=y=Crepeatx=f(f(x)y=f(y)Until (x=y)循环出来之后所找到的点一定是圈上的点（为什么？）追赶法的时间复杂度是O(L)第四部分 图论问题AIRLINE COMPANY有一个n个节点的连通无向图，有m条边。现在需要你给这m条边编号1-m。满足对于同一个点，它的所有连边的标号的最大公约数为1。请你找出这样任意一组满足要求的解。问题

14、：一定有解吗？如果不连通，一定有解码？欧拉路问题欧拉路：遍历每一条边一次且仅一次的路欧拉回路问题：如何判断一个图存在欧拉路？欧拉回路？如何求一个图的欧拉路？哈密顿路问题哈密顿路：经过每个节点一次且仅一次的路径。带权哈密顿路：两个节点之间的边有权值。路径上各条边的权值和为该路径的总权值。最优哈密顿路：总权值最小的哈密顿路。哈密顿路问题(2)求最优哈密顿路目前还未找到多项式复杂度的算法。如果采用盲目搜索，枚举所有的路径，理论时间复杂度是O(n!)对于n比较小的情况，我们可以尝试动态规划。哈密顿路问题(3)用一个集合z表示当前路径访问过的点集合。设f(Z,i)表示经过点集Z，最后一个到达节点i的最优

15、哈密顿路的总权值（i属于Z)。f(Z,i)=minf(Z,j)+w(j,i)其中Z=Z-j我们可以用二进制数实现Z集合。算法的时间复杂度为O(2nn2)第五部分 其他JOSEPHUS问题编号为1到N的N个人围成一圈，从第一个人开始，1、2报数，报2的人出圈，直至圈中只剩下一个人。求最后剩下的人的编号。例如N=5时，出圈的顺序是2，4，1，5，最后剩下的人是3。一般约瑟夫问题的解法：线性表模拟。时间复杂度O(nm)本题的特殊性：m=2第一圈报完数后，编号为偶数的人就全部出圈了。此时圈中剩下n/2个人。若n是偶数，此时又从编号为1的人开始报1；若n是奇数，编号为1的人出圈，从编号为3的人开始报1。第二圈与第一圈有类似性！如何利用？分析1232k+12k452k-1 2k-2当n=2k+1时：在编号为1的人出圈之后，如果把剩下k个人的编号整除2，就转换成了编号为1到k的k个人出圈报数。1232k2k-1452k-2 2k-3当n=2k时：如果把剩下k个人的编号加1再整除2，就转换成了编号为1到k的k个人出圈报数。分析分析设f(i)表示编号为1到i的i个人围成一圈报数，最后剩下的人的编号。f(1)=1f(2k)=2*f(k)-1f(2k+1)=2*f(k)+1所求答案：f(n)扩展寻找最小的K