NOIP实用算法 7.分治
7.分治
a.子问题与母问题的相似性
b.二分查找
c.分析算式
d.最长非降子序列的二分法
a.子问题与母问题的相似性
在第三章“搜索”中我们讲过，要擅长利用相似性。现在我们介绍利用相似性的另一条思路：分治。
分治主要用来处理一维的数据结构。
分治，就是把母问题拆分为几个（一般是两个或三个）子问题，使每个子问题与母问题相似。这样就把大问题化成了相似的小问题，问题性质不变、规模成倍减小，最后很容易解决。
由于利用了子问题的相似性，分治采用递归实现。
实现时递归函数要完成两步——“分”、“合”。
“分”是指分拆成小问题、递归调用，这一步比较容易。
“合”是指对分拆得到的小问题的结论进行合并处理，有时这一步很困难。
若“分”出的子问题有两个，又可称该方法为“二分法”。类似地，也有“三分法”之说。
在第二章讨论过快速排序和归并排序，这都是对分治的经典应用。
还有一些经典算法也运用了分治思想，常常被用作解题工具。下面介绍一下。
b.二分查找
有时我们要判断一串数组成的序列中是否存在某数字N。
最普通的方法是，将N与该序列中每个数逐个比较。这种方法时间复杂度为O(n)。
如果我们预先得知该序列是有序（非增或非降）的，我们可以采用二分查找法（以序列非降为例）：
1.首先，将该序列作为保留的序列。
2.将N与保留的序列中最中间的数A比较。
2.若N
3.重复2、3，直到N=A或保留的序列为空。
4.若N=A，则在A前后找出与A相等的项的个数；若保留的序列为空，则序列中不存在N。
分析知，二分查找时间复杂度为O(lbn)。
注意：二分查找只适合非增或非降的序列；对于一般的序列，不要为应用二分查找而试图判断其是否有序或对其排序，那样会提高时间复杂度，反而不如逐个比较了。
c.分析算式
有时会碰到这种问题：输入一个表示算式的字符串（一般含四则运算、乘方等运算符），要求输出计算结果。
对于这样的问题，我们常采用这样的思路处理：找出式中最后运算的运算符A，先将其左右两边分别运算（递归地）、求值，再将得到的值进行A运算。
有一个类似的问题“删除多余括号”：输入一个表示算式的字符串（含四则运算、乘方、括号），要求尽可能多地删除其中多余的括号而不改变算式的运算过程和结果。
我们用可以类似的方法解决。下面给出源代码，以便读者更好地理解这个递归地分析算式的过程。
// Program "Delete()" 删除多余括号 // This is a C source file written by LastLeaf // 该程序已在gcc(DEV-C++)上编译通过 #include <stdio.h> #include <string.h> int a[1024]; char s[1024]; int cal(int st,int stp,int prev) { int t,i,min=4,mini; for(i=st;i<=stp;i++) { switch(s[i]) { case '^': if(min>3) { min=3; mini=i; } break; case '*': case '/': if(min>2) { min=2; mini=i; } break; case '+': case '-': if(min>1) { min=1; mini=i; } break; case '(': i++; for(t=1;t!=0;i++) { if(s[i]=='(')t++; if(s[i]==')')t--; } i--; break; } } if(s[st]=='(' && s[stp]==')' && min==4) { t=cal(st+1,stp-1,0); if(t>=prev) { a[st]=a[stp]=1; return t; } return 4; } if(min==4) return 4; cal(st,mini-1,min); if(s[mini]=='+' || s[mini]=='*') cal(mini+1,stp,min); else cal(mini+1,stp,min+1); return min; } int main() { FILE *fp; int i,sc; fp=fopen("delete.in","r"); fscanf(fp,"%s",s); fclose(fp); fp=fopen("delete.out","w"); sc=strlen(s); cal(0,sc-1,0); for(i=0;i<sc;i++) if(!a[i])fprintf(fp,"%c",s[i]); fprintf(fp,"\n"); fclose(fp); return 0; } |
NOIP2005中出现了“等价表达式”问题：明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？
这个选择题中的每个表达式都满足下面的性质：
1． 表达式只可能包含一个变量‘a’。
2． 表达式中出现的数都是正整数，而且都小于10000。
3． 表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符 ‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）
4． 幂指数只可能是1到10之间的正整数（包括1和10）。
5． 表达式内部，头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子：
((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9……
思路分析：对于这个问题，聪明的做法是，给未知数设一个值，然后计算每个代数式的结果（分治法），看看与原式是否匹配。不匹配即被排除。这里可以不使用高精度运算，这可以理解为：我们只计算高精度数的最后一位。若最后一位都不能匹配，就肯定要排除。我们多代几个比较随机的数之后，便基本上可以把干扰项排除完（除非一个极小概率事件发生了）。剩下的应该就是正确答案。
d.最长非降子序列的二分法
介绍“动态规划”时我们接触过最长非降子序列问题。这里有一个更好的解决方案，它基于贪心和分治：
1.另设置序列A[]，A[i]表示若非降子序列长度为i，其最后一项可能的最小数值。
2.一次考虑原序列中每一项。对于某项的数值n，若A[i]中存在数值大于n的项，则用二分查找的方法找出A[i]中数值大于n的项中最前的一项A[m]，令A[m]=n；否则在A[]末尾添加一项，值为n。
3.最后，最长非降子序列长度就是A[]的项数，A[]就是最长非降子序列之一。
有很多经典问题用分治解决。但是分治在NOIP提高组中出现不多。读者若想多了解一些，请参阅下方提供的资料链接。
本章无附件
本文由 最后的叶子 创作，转载或引用前请联系我们。
相关文章：
写的很好！
回复