传说中的算法宝典

1、一共考5道题，每道题2问1、 （重要）设L为n元数组，其中的数已按增序排列，另给定数值x，试采用二分搜索技术设计算法，查找数值是否在L中。要求若x在L中，则输出j，使L(j)=x；其x不在L中，则输出0。并证明，在最坏情况下，对所有n元数组L(n1)，二分搜索算法将数值x与L中元素比较次数为。解：比较次数：由于是2分搜索，每次比较或者成功，或者将搜索范围缩小一半。因此最多比较次数为2的对数，又当时，至少比较1次，所以比较次数不超过。二、满足三角不等式的TSP问题是否是NPC？为什么？解：证明思路，将哈密顿回路HC问题多项式变换到TSP问题:，且变换到TSP问题的实例是满足三角不等式的。因为，故

2、满足三角不等式的。多项式变换：设HC的实例为，据此构造TS实例，两个顶点之间的距离定义为，并设TSP旅游界值为。易知这个变换是多项式的。若HC存在一条哈密顿回路，则这条回路在上的长度必为B，而是最短旅游的界值，故这条回路是满足实例的一个TSP旅游。若存在一个满足B的TSP旅游，则该旅游必经过长度为1的边，而这些边均在G上，因此这个TSP旅游在G上是一条HC回路。这样就将，而。变换到的TSP实例的边长为1或2，可知该实例满足三角不等式，这就证明了满足三角不等式的TSP问题是NPC问题。三、给定城市集合，任两城市距离，求最小货郎旅游。试证明满足三角不等式的货郎优化问题为NP-hard。（重要）求满

3、足三角不等式的TSP的近似算法，并设计出能解答该问题的多项式时间近似算法A，其近似性能比为。证明：即满足三角不等式的TSP问题。证明思路，将哈密顿回路HC问题多项式变换到TSP问题:且变换到TSP问题的实例是满足三角不等式的（见第1题）。因为，故满足三角不等式的TSP问题是NPC问题。设存在TSP优化问题求解算法，设计TSP判定问题的算法如下：对于给定TSP判定问题的实例：，调用，求得城市排列：，若，则回答yes，否则回答no。若为多项式算法，则上述算法能够在多项式时间内解答，故TSP判定问题可以图灵归约到TSP优化问题，而已知TSP判定问题是NPC的，所以TSP优化问题是NPH的。算法：对调

4、用最小支撑树（有权图权值之和最小的连通子图）算法，得到树设的奇数顶点为，在中求点集的最小对集，将加入中，形成欧拉图在中求欧拉回路抄近路得到证明：因为TSP是回路，最小生成树是树，所以又对于所有最小对集的两条边，小于这四点相连的最小TSP旅游距离，所以，4、 对于背包问题 证明：(1) 、当时，该问题不存在多项式时间绝对近似算法(2) 、背包问题存在绝对近似性能比的多项式时间近似算法证明:(1)假设存在A,则存在常数（2）：实例为价值，为重量，为背包容量询问：求向量，使。算法：将物体按照排序，使从1到n将物体装包，直到不能装为止，记其总价值和为取复杂性：步骤，步骤，故总的时间复杂性为近似性能比：

5、设包含物体价值为，则 ， 而， 故， 即5、 n个整数，正整数m。求向量。证明是NPC的；若，求多项式时间算法，证明其正确性。六、给定WPAR问题实例：集合，对于每个有长度。询问：是否存在子集(1) 、试利用划分PAR是NPC问题，证明WPAR问题属于NPC类；(2) 、试设计拟多项式算法：(a) 判断是否存在，(b)若存在，应给出一个满足询问条件的。(3) 、针对如下实例，说明你设计算法的执行过程解：(1)、证明WPAR是NPC证明：(将)设PAR实例为，构造WPAR实例：，其中若PAR中存在一个划分，使得，则在WPAR中，而。因此，必存在使若WPAR中存在使，则。分析元素构成，中必含不含，

6、而中必含，不含。则有，即A中存在一个划分。又上述变换可在多项式时间内进行，因此，又，因此（2） 、设计WPAR拟多项式算法解：设，若B不能被3整除则无划分；若B能被3整除，则设计表t为n行，列。，若，则最终回答yes，否则no 若则若，则求解算法：记（3） 、用设计算法求解实例j：i0123456789101TT2TTTT3TTTTTT4TTTTTTT5TTTTTTTT七、（重要）给定2SAT问题实例，布尔变量集合，项集合，为U上布尔变量字母。试设计多项式时间算法：(1)、判定2SAT实例是否有可满足真值指派；(2)、若有可满足真值指派则算法给出使C满足U的真值指派。8、 证明团问题属于NPC

7、思路：已知顶点覆盖，而最大独立集问题，故最大独立集问题（若是上的点覆盖，则是上的最大独立集。若是上的最大独立集，则是上的点覆盖）。又最大独立集问题，故(若是上的最大独立集，则在的补图上所对应的子图是上的团)点覆盖：上的最小顶点集合，覆盖上所有的边；独立集：上的点集合，中任两点之间无边；补图：（？）团：上最大完全子图9、 TSP判定问题是数问题吗？是否存在拟多项式算法？为什么？答：TSP判定问题是数问题，因为任两城市间的距离及界值没有任何约束。因为可以将，从而证明，而有限制，事实上,故不受限制的原始TSP问题是强NPC。因此TSP问题不存在拟多项式时间算法。10、 集合覆盖问题T实例：为子集族询

8、问：求，使最小求证：时，上述问题无多项式时间绝对近似算法证明：若限制,则集合覆盖问题变为X3C问题。而，故集合覆盖问题是NPC问题。(反证法)设存在多项式时间绝对算法A，有现将复制份到，易知，在上应用算法A有，故：(之所以取整，是因为集合覆盖问题是求最小值问题）因此可以构造算法：（1）、；（2）、对调用A，得子集族的子集及；（3）、计算即为实例的最优解值因为是多项式的，所以也是多项式的，这就多项式时间回答了集合覆盖问题。而我们已知集合覆盖问题是NPC，这与矛盾，故假设不成立。即不存在多项式时间绝对近似算法。十一、假设一台处理机可连续加工任务。但在每个时刻，只允许加工一个任务，含有待加工任务集合

9、。其中所有任务都有相同的加工最早起始时间，但它们所需要的加工时间和加工最迟完成时间不同，即对于一个任务，其所需加工时间为，加工最迟完成时间为且，试设计一个多项式时间算法，给出任务集合的排工表，使能按要求完成的任务数达到最大。要求证明你所设计算法的正确性，并分析其时间复杂性，并通过下述实例说明算法的运行情况：（重要）算法，将所有任务按其结束时间由小到大排列，若满足时，有。令空，S为排工表。若，转设对个任务，已经安排了个任务加工。则对第个任务，只要有,则将其安排为第个任务：即，然后转若,则从已安排的个任务中，另择一个加工时间最长的任务，若，则将从中移出，将后的任务前移，再把并入，转否则（），k=k

10、+1, 转完成，S即排工表。正确性：由于的排序是一定的，只需证明每一步操作都使加工时间最短，则它的加工任务最多。归纳法证明：（1） 当时，显然成立；（2） 假设 时正确，即若个中拔下个，且加工时间最短，下面证明时也正确。当时，若，则安排第个任务，显然个任务最多能安排个，且时间最短；若，则由于算法中选择了中最长的任务，且当时用代替，使总加工时间，故仍满足加工时间最短，任务最多。综上所述，把个任务排完时，算法是正确的。复杂性：设有个任务，则最坏情况下对每个加工任务都有，从而从中查找最长加工时间任务，则一次查找为，每个任务都查找为，排序加工任务为，因此总的复杂度为。算法的实例运行情况：S=t1 k=

11、1 m=1 Ls=6S=t2 Ls+L2=10>d2 Ti=T1, Li>L2,Ti out, T2 in k=2, Ls=4S=t2t3ls+L3=6<10, k=3,m=2,Ls=6S=t2t3t4Ls+L4=11=d4,k=4,m=3,Ls=11 m=3S=t2t3t4Ls+L5=18>d5,Ti=T4,Li<L5,k=5,Ls=11S=t2t3t4t6Ls+L6=13<d6,k=6,Ls=13,m=4K=6,putout S=t2t3t4t6十二、排工问题（区间排工）实例：只有一台机器，n个任务，。对于每任务有加工起始时间，终止时间，加工长度询问：加

12、工表，表示的真正开始。使按时完成。时，在之前开始，或，在之前开始。（两个任务不同时开始进行）试证：(1)、问题（2） 、若限制，称为限制排工问题，试设计一多项式算法，限制排工任务数目最大，再证明算法的正确性，分析其复杂性。解：（1）见教材，试图将区间排工。设实例，对每一个有均为整数，。根据问题实例构造排工问题实例：， 我们不考虑B为奇数的情况，因为B为奇数时，PAR不存在一个划分。若存在一个划分，则可如此排工：将中所对应的任务安排在E之前完成，将所对应的任务安排在E之后完成。由此排工问题存在一个排工。若排工问题存在一个排工，则可如此进行划分：将位于E之前的任务对应的置入集合，E之后的任务所对应

13、的放在中。由于E之前的任务加工长度为（B为偶数），E之后的任务加工长度为，而，故，即存在一个划分。因此，我们得区间排工，由于，故区间排工。(2) 、算法，将所有任务按其结束时间由小到大排列，若满足时，有。令空，S为排工表。若，转设对个任务，已经安排了个任务加工。则对第个任务，只要有,则将其安排为第个任务：即，然后转若,则从已安排的个任务中，另择一个加工时间最长的任务，若，则将从中移出，将后的任务前移，再把并入，转否则，k=k+1, 转完成，S即排工表。正确性：由于的排序是一定的，只需证明每一步操作都使加工时间最短，则它的加工任务最多。归纳法证明：（3） 当时，显然成立；（4） 假设 时正确，即

14、若个中拔下个，且加工时间最短，下面证明时也正确。当时，若，则安排第个任务，显然个任务最多能安排个，且时间最短；若，则由于算法中选择了中最长的任务，且当时用代替，使总加工时间，故仍满足加工时间最短，任务最多。综上所述，把个任务排完时，算法是正确的。复杂性：设有个任务，则最坏情况下对每个加工任务都有，从而从中查找最长加工时间任务，则一次查找为，每个任务都查找为，排序加工任务为，因此总的复杂度为。13、 给定个整数，满足（超递增序列），有一正整数，试设计算法，找出一维0，1向量，使得或无解。解：算法证明：因为，所以若，必有，故应为1，否则使全为1也没有正确答案。复杂度：易知为。14、 （1）平面图的

15、最大团问题有多项式时间算法吗？Why?答：有，因为当在平面图上考虑团问题时，任何平面图都不会含有多于4个顶点的完全图，故只需检查所有的顶点个数，不超过4个子图就能找到极大团。因4是常数，故子图数目是多项式有界的。所以必有多项式算法。(2) 平面图的3着色问题有多项式算法吗？Why?答：没有，因为我们可以设计一个转线轨道图，用局部替换技术将一般图中的交点处理，将其转化为平面图。一般图的3着色问题，故平面图3着色也是NPC的，所以不存在多项式时间算法。15、 （重要）当时，TSP优化问题是否存在的多项式算法？答：不存在，用反证法证明。证明：设存在常数，使，即存在算法，对TSP的任意实例有。设是哈密

16、顿问题任意实例，由构造TSP问题实例如下。 若存在哈密顿回路，则若不存在哈密顿回路，则，因此可以设计哈密顿问题的TSP实例，调用算法由是否成立判定哈密顿是否存在解，又是多项式时间的，即哈密顿可以多项式时间求解，这与矛盾。故假设不成立，TSP不存在的多项式算法。16、 （重要）划分问题的拟多项式时间算法，并求划分的具体方案解：设，若B为奇数，显然不能划分。若B为偶数，设一个布尔变量：若,则回答yes，否则no计算的条件：若，则若，则框图如右：时间复杂度：外循环n，内循环，故。因为的输入长度为，并不是输入长度的多项式，故不是多项式算法，是拟多项式算法，。十七、已知MAXLA问题属于NPC类，MAX

17、LA问题描述为实例：简单图G=(V，E)及正整数K。询问：是否存在一一对应映射P：V1,2,.,|V|，使试证明MINLA问题也属于NPC类，MINLA问题为实例：与MAXLA相同。询问：是否存在一一对应映射P：V1,2,.,|V|，使证明：试图将 设图及正整数为的实例，定义的实例为图，其中，即为的补图。 对顶点集合中所有可能的映射，考虑：固定一点与其它所有点的值，即对固定顶点，为 所以又与互为补图所以所以当且仅当所以，18、 用图灵归约技术证明个最大子集个最大子集问题：实例：个元素，每个元素有一个长度。两个非负整数和询问：中是否有个不同的子集。满足且证明：假设是解个最大子集问题的子程序，其中

18、长度函数设集合和长度函数是划分问题的任意实例。设计划分问题的算法。从计算开始，若是奇数，则回答NO。否则，并调用子程序算法：若为奇数，则划分问题回答NO，结束。置，调用算法算法：求满足的最大数目。，（可能的界限）若，则并结束。；调用，检查是否有个子集满足若回答YES，则,转若回答NO，则,转 根据求出的满足的子集的最大数目，调用一次若回答YES，则表明所有满足的子集，也都满足，故相应划分问题回答No若回答NO，则满足的子集一定存在，所以划分回答Yes。十九、排工问题大全1、区间排工实例：有限任务集合,最早开始时间，最晚结束时间，加工长度。询问：是否存在排工表(1) 区间排工，用划分区间排工(2

19、) 区间排工证明：将3划分区间排工设三划分实例为由此构造区间排工实例：若三划分问题回答yes，变换后的区间排工也回答yes。若区间排工回答yes，则三划分问题也回答yes。且该变换是拟多项式变换。因为：三划分，所以：区间排工2、 最小迟序排工，有半序关系和最晚结束时间，不能按时完成的任务，证明，用证明。3、 先行约束排工：为1，处理机为，半序关系（1） 没有半序或半序为树时是P问题（2） 时是P问题（3） 半序和任意则是NPC4、 （重要）多任务排工实例：个处理机处理任务，加工时间，任务之间有半序关系。询问：最短时间内完成（1）（任意主次表，有空就加工），非空闲算法算法：开始所有处理都空闲，所

20、有任务都未加工对任务主次表从左向右扫描，判定每个任务是否处于加工状态。若可加工，则安排至下标最小的空闲处理机上加工。任务主次表是按半序关系的。（2） 证明将的时间区分成两部分：则在半序关系中存在一条通路，该通路覆盖子区间所以：即注：当最大加工时间，限制时，变成PAR问题5、 （重要）独立任务排工实例：任务，加工长度（1） LPT算法，先排时间长的:将任务排序，形成加工主次表对主次表从1到n扫描，若有空闲机器，则将任务安排空闲机器上加工，直至完成。复杂度：，多项式算法证：当时，显然成立。当时，假设最后完成的任务为。若最后完成的任务是，则只考虑前个任务，若前个满足，则个当然满足。在内所有任务都非常

21、空闲又若，则每个机器上最多安排2个任务，这样的排工是最优的，当然满足；若，则综上得证（再举例说明上界不能小于3）（2） F算法：多项式近似方案：将任务从大到小时间排序：确定正整数，对前个任务，求最优先排工，后个按先大后小顺序排工。证明：设T是前个任务的排工时间，若，则,设。在区间所有的处理器非空闲，开始做时，其它有任务可能未做完。又，至少有一台机器加工了和前个任务的平均个数，即个任务；又，是前个中最小的。算法复杂度：二十、装箱问题实例：个物体集合，每个物体，体积为，容量为C的箱子。询问：需要多少个箱子才能全部装完（1） 首次适合算法Fit-First:算法：按照一定顺序依次装入箱子。证明：任意

22、两个相邻箱子装入物体体积大于，若为偶数，则；又，若为奇数，则，又，为整数，（2） FD算法，先大后小将物体排序，体积从大到小依次装箱，二十一、背包问题实例：有限集合为重量，为价值判定问题：是否存在优化问题：，求向量。(1)、判定问题限制为偶数，则上述问题变为PAR问题。(2)、背包问题无多项式时间绝对近似算法，将价值扩大倍，变成另一个问题。反证法.(3)、的算法（见前文）(4)、（）多项式近似方案：，证明这个公式，给出时间复杂度算法描述：对任意一种个元素的组合都先放入包中尝试，最后选择一个最好的尝试。伪代码：下面算法先装个再继续装：证明：，为最优解，为算法的解(1)设是最优解的背包元素下标集合

23、，。若，则有最优解，假设。(2) 将中物体排序按照以下规则，.是前个最大价值。从开始到满足。设是第一个未装进去的价值，则，复杂度此处省略完全多项式近似方案及复杂度的分析二十二、TSP问题1、 满足三角不等式的TSP是NPC解：证明思路，将哈密顿回路HC问题多项式变换到TSP问题:，且变换到TSP问题的实例是满足三角不等式的。因为，故满足三角不等式的。多项式变换：设HC的实例为，据此构造TS实例，两个顶点之间的距离定义为，并设TSP旅游界值为。易知这个变换是多项式的。若HC存在一条哈密顿回路，则这条回路在上的长度必为B，而是最短旅游的界值，故这条回路是满足实例的一个TSP旅游。若存在一个满足B的

24、TSP旅游，则该旅游必经过长度为1的边，而这些边均在G上，因此这个TSP旅游在G上是一条HC回路。这样就将，而。变换到的TSP实例的边长为1或2，可知该实例满足三角不等式，这就证明了满足三角不等式的TSP问题是NPC问题。2、 TSP是强NPC：将其边长为1，2，是NPC，答：TSP判定问题是数问题，因为任两城市间的距离及界值没有任何约束。因为可以将，从而证明，而有限制，事实上,故不受限制的原始TSP问题是强NPC。因此TSP问题不存在拟多项式时间算法。3、 TSP优化将TSP判定TSP优化4、 TSP延伸已知部分旅游，能否延伸出一个长度不超过B的全程旅游回路证明：将TSP判定TSP延伸。假设

25、是求解TSP延伸问题的算法。设计TSP判定算法如下（折半法）：若调用子程序：，若回答yes,则令,转；否则，转。若，回答yes,否则no复杂度（重要）还有排工问题的考课件上的两个近似算法；和顶点覆盖问题满足三角不等式的TS问题。对实例对应的有权完全图G=<V,E>，求最小生成树记为T;T中度为奇数的顶点集为，必为偶数个;调用最小对集算法P在V中求出最小对集;将中加入T中，形成欧拉图D;在欧拉图中求出欧拉回路（P）;用抄近路方法将欧拉回路转换为TS旅游证明：1中d(T)<OPT(I);2中d(Ep)<=1/2OPT(I)故有d(T)<OPT(I),d(Ep)<

26、=1/2OPT(I).当PNP时，求证TS优化问题不存在的多项式时间近似算法。反证法。假设存在，则存在常数k使得;即存在多项式算法A，对最优解超过某常数的TSP实例G，有;设是HC实例，则构造TSP实例如F，其中V=V,;当中存在HC时，当中不存在时;因此可得当且仅当时，中存在HC回路;又因为A是多项式时间算法，故存在多项式时间算法解HC问题与PNP矛盾原题得证排工问题区间排工（有最早加工起始时间及加工最后期限）证明 区间问题是排工问题证明：设PAR实例，长度，构造排工实例当B为奇数时，不能划分，所以只考虑B为偶数的情况若存在PAR，则排工如下 ：将A中对应的任务安排在之前，A- A对应的安排

27、之后，即为一个区间排工。若存在一个排工，则将之前的所对应置入A，又由于，故，即PAR的一个划分。因此，所以区间排工NPC独立排工问题算法LPTStep1：将任务排序使：形成主次表：L=T1,T2,Tn，t1t2tn。Step2：对主次表从1到扫描，若有空闲机器，则将任务安排到空闲机器上加工。直到完成。独立任务排工问题的任意实例I，采用近似算法LPT求解，有：证明：当m=1时，定理结论为真，结论显然是对的，就1台机器。下面假设m>1。观察性质：首先可以假设最后完成的任务是tn，为什么，因为若最后一个任务为tk，则只考虑前k个任务即可。n-k个任务不管。若前k个任务满足结论，则前n个任务当然

28、也满足结论。取前k个任务形成实例I1，则OPT(I)OPT(I1)，LPT(I)=LPT(I1)所以在0,LPT(I)-tn内所有任务都非空闲。LPT(I)-tnLPT(I)+tnOPT(I)所以：因OPT(I)3tn，若不然则每个机器上最多可以安排2个任务，n2m。这样的排工是最优的。当然满足。所以.背包问题PNP时，背包问题不存在多项式时间绝对近似算法。证明：假设存在算法A，则存在常数k，使得将I复制k+1份得到I所以OPT(I)=(k+1)OPT(I)由此可得背包问题的多项式最优解算法，与PNP矛盾，故假设不成立。背包问题设计绝对性能比的多项式时间近似算法1)将所有元素按排序2)按上述顺

29、序依次装入背包，直至放不下，得可行解GA(I)3)令A(I)=maxGA(I),背包问题有最优解为，是得到的解，求证证明：1）设R是最优解的背包元素下标集合，若|R|k，则可求到最优解，下面假设|R|>k2)将R中物体排成有序对，具体规则如下：a)前k个为R中受益最大的k个b)从i=k+1到|R|满足3)算法中必存在如下情况，即选定前k个作为包底，记;设s是在此情况下调用L(I,P,W,M,n)增加的收益设是在调用L(I,P,W,M,n)过程中第一个没有被装入包的元素4) 时间复杂度O(nk)=O(n)划分在已知划分问题实例存在划分的情况下T，求出具体划分：假定已有一张表t，n行，列，记

30、，由于存在划分，则tn,b=T,记n=a设一个集合A存放入选元素的下标If (a<0 或 b0) 则返回集合A，为所求；Else 判断 a-，go 1)将a加入集合A；b=b-S(a)；a-；go 1)WPAR问题设计WPAR的拟多项式算法，判定并求解。解：设，若B不能被3整除则无划分，若B能被3整除，则设计表t：n行，列若，则最终回来yes，存在划分，否则Not(i,0)=Tt(1,j)=T若ti-1,j=T，则ti,j=T若ti-1,j-S()=T，则ti,j= TTi,-1=FT0,j=F求解算法：记，记n=a （将入选元素的下标存入集合A）If (a<0 or b<=

31、0) 则返回A为所求Else 判断 a-; go 1)将a加入集合A；a-；go 1)集合覆盖问题实例，C为子集族，询问询问：求使且最小，求证时，无多项式时间近似算法。证明：1) 对任意实例，限制|S|=3q，则集合覆盖问题变为X3C2) 假设该问题存在多项式时间近似算法A，则有现将I复制k+1份，构造新实例I，则有OPT(I)=OPT(I)*(K+1)，在I上应用算法A，则有又且集合覆盖问题是求最小值问题，恒有，因此，可构造算法A，根据实例 I构造I，用A求解I得A(I)及子集族C的子集C计算，可得实例的最优解因为A是多项式的，则A亦是，即可在多项式时间内解答NPC问题，与PNP矛盾故原题得

32、证给定几个整数满足(超递增)，有一正整数S，设计多项式算法A，找出一个n维向量使或确定无解，证明并分析复杂性。算法：S=SFor (i=n to 1)if () =1;Else =0 ;If (S=0) x为所求Else 无解复杂性：O(n)L为N元数组，其中元素递增，给定数值x，设采用二分搜索，查找x是否在数组中，要求，若x在L中，输出下标，否则输出0，并求出最大比较次数。a)算法：l=1,r=nif (l>r) 则j=0; 转6)j=;if (x=L(j);转6)if (x>L(j) l=j+1;else r=j-1; 转2)输出jb) 比较次数：对二维搜索，每次搜索成功将范围

33、减半，故最多比较次数为2的对数，又因为当n=1时至少比较1次，故比较次数不超过 2SAT实例，,判断是否有真值指派，若有求出。算法：根据U,C构造有向图G，2n个顶点，分别是若，则添加和两条边，对，若有，则；若，则判定：若图G中对，有和同时存在，则无真值指派。反之，亦是（G上没有回路真值指派，因为G中无回路不同时存在）求解：a)如2)所述赋值b)扩展赋值（若有，则在的同时，对所有指向的节点赋0，所有指向的节点赋1）c) 对a、b之后，仍未赋值的变量，可同时赋0或同时赋1已知MAXLA问题是NPC，求证MINLA亦是NPCMAXLA：简单图，询问是否一一映射，使证明：根据MAXLA实例构造MINLA实例如下：及k，其中V=V，则G为G的补图：又从MAXLA到MINLA的变换是多项式的求证：第k个最大子集是NP-hard实例：有限集集合A每个，有，两个非负整数，询问：A中是否存在k个不同的子集，满足证明：设SA,S,B,k是个解第k个最大子集问题的子程序.构造划分问题实例A，设计划分问题算法如下：S(A)为奇，则返回No再调用一次SA,S,B-1,若回答yes，则所有满足的A也满足，故无划分若回答No，则使，则划分综上所述，若S是多项式算法，则可以多