第七章 分治算法.

Presentation on theme: "第七章 分治算法."— Presentation transcript:

1 第七章 分治算法

2 所谓分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。
你们玩过猜数字的游戏吗？你的朋友心里想一个1000以内的正整数，你可以给出一个数字x，你朋友只要回答“比x大”或者“比x小”或者“猜中”，你能保证在10次以内猜中吗？运气好只要一次就猜中。 开始猜测是1到1000之间，你可以先猜500，运气好可以一次猜中，如果答案比500大，显然答案不可能在1到500之间，下一次猜测的区间变为501到1000，如果答案比500小，那答案不可能在500到1000之间，下一次猜测的区间变为1到499。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。由于 ，因此不超过10次询问区间就可以缩小为1，答案就会猜中了，这就是二分的基本思想。 每一次使得可选的范围缩小一半，最终使得范围缩小为一个数，从而得出答案。假设问的范围是1到n，根据 ,所以我们只需要问O(logn)次就能知道答案了。 需要注意的是使用二分法有一个重要的前提，就是有序性，下面通过几个例子来体会二分法的应用。

3 例7.1 找数 描述： 给一个长度为n的单调递增的正整数序列，即序列中每一个数都比前一个数大。有m个询问，每次询问一个x，问序列中最后一个小于等于x的数是什么？ 输入： 第一行两个整数n,m。 接下来一行n个数，表示这个序列。 接下来m行每行一个数，表示一个询问。 输出： 输出共m行，表示序列中最后一个小于等于x的数是什么。假如没有输出-1。 样例输入： 5 3 5 1 3 样例输出： 4

4 分析： 我们用Left表示询问区间的左边界，用Right表示询问区间的右边界，[Left,Right]组成询问区间。一开始Left=1，Right=n，我们可以把原始序列的左边想象成若干个无穷小的数，把序列的右边想象成无穷大的数，这样比较好理解。序列已经按照升序排好，保证了二分的有序性。 每一次二分，我们这样来做： ①取区间中间值Mid=(Left+Right)/2； ②判断Mid与x的关系，如果a[Mid]>x，由于序列是升序排列，所以区间[Mid,Right]都可以被排除，修改右边界Right=Mid-1； ③如果a[Mid]<=x，修改左边界Left=Mid+1； 重复执行二分操作直到Left>Right。 下面我们来分析答案的情况。循环结束示意图如下：LeftRight大于x小于等于x 最终循环结束时一定是Left=Right+1，根据二分第②步的做法我们知道Right的右边一定都是大于x的，而根据第③步我们可以知道Left左边一定是小于等于x的。 所以，一目了然，最终答案是Right指向的数。Right=0就是题目中输出-1的情况。

5 程序如下： #include <iostream> using namespace std; int n,m,a[110000]; int main() { cin >> n >> m; for (int i=1; i<=n; i++) cin >> a[i]; a[0]=-1; for (int i=1; i<=m; i++) { int x; int left=1,right=n,mid; cin >> x; while (left <= right) { mid = (left + right) / 2; if (a[mid] <= x) left = mid + 1; else right = mid - 1; } cout << a[right] << endl; } return 0; }

6 例7. 2 快速排序(Quicksort) 快速排序由C. A. R
例7.2 快速排序(Quicksort) 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的中间数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是： ．设置两个变量i、j，排序开始的时候：i=0，j=N-1； ．以数组中任意元素作为关键数据(一般以数组中间元素作为关键数据)，赋值给key，可以是key=A[(i+j)/2]； 从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于等于key的值A[j]； ．从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于等于key的A[i]； 交换A[i]和A[j]的值，同时i++, j--； ．重复第3、4、5步，直到i>j； 例如有8个元素需要排序：

7 一趟快速排序后： 此时i>j,并且i左边的数字都小于等于key,j右边的数字都大于等于key，进而接下来可以分别对左边段[0, j]和右边段[i,N-1]利用同样的方法排序。

8 【程序实现】 void qsort(int le,int ri) { int i=le, j=ri, mid=a[(le+ri)/2]; while(i<=j) //注意这里要有等号 { while(a[i]<mid) i++; //在左边找大于等于mid的数 while(a[j]>mid) j--; //在右边找小于等于mid的数 if(i<=j) { swap(a[i],a[j]); //交换 i++, j--; //继续找 } } if(le<j) qsort(le,j); //分别递归继续排序 if(i<ri) qsort(i,ri); } 快速排序(Quicksort)是对冒泡排序的一种改进，快速排序的时间复杂度是O(nlogn)，速度快，但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序的方法。但快速排序需要一个栈空间来实现递归，若每一趟排序都将记录序列均匀地分割成长度相近的两个子序列，则栈的最大深度为log(n+1)。

9 【例3】一元三次方程求解 有形如：ax3+bx2+cx+d＝0这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,d均为实数），并约定该方程存在三个不同实根（根的范围在-100至100之间），且根与根之差的绝对值≥1。 要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后2位。 提示：记方程f（x）=0，若存在2个数x1和x2，且x1<x2，f（x1）*f（x2）＜0，则在（x1，x2）之间一定有一个根。 输入：a，b，c，d 输出：三个实根（根与根之间留有空格） 【输入输出样例】 输入： 输出： 【算法分析】 这是一道有趣的解方程题。为了便于求解，设方程f(x)=ax3+bx2+cx+d＝0，设根的值域（-100至100之间）中有x， 其左右两边相距0.0005的地方有x1和x2两个数，即 x1=x ，x2=x 。x1和x2间的距离（0.001）满足精度要求（精确到小数点后2位）。若出现如图1所示的两种情况之一，则确定x为f(x)=0的根。

10 有两种方法计算f(x)=0的根x: 1．枚举法 根据根的值域和根与根之间的间距要求(≥1)，我们不妨将根的值域扩大100倍(-10000≤x≤10000)，依次枚举该区间的每一个整数值x，并在题目要求的精度内设定区间：x1=，x2=。若区间端点的函数值f(x1)和f(x2)异号或者在区间端点x1的函数值f(x1)=0，则确定为f(x)=0的一个根。 由此得出算法： 输入方程中各项的系数a，b，c，d ； for (x=-10000;x<=10000;x++) //枚举当前根*100的可能范围 { x1=(x-0.05)/100；x2=(x+0.05)/100；//在题目要求的精度内设定区间 if (f(x1)*f(x2)<0||f(x1)==0) //若在区间两端的函数值异号或在x1处 的函数值为0，则确定x/100为根 printf(“%.2f”,x/100)； } 其中函数f(x)计算x3+b*x2+c*x+d： double f(double x) //计算x3+b*x2+c*x+d f=x*x*x+b*x*x+c*x+d； } //f函数

11 2.分治法 枚举根的值域中的每一个整数x(-100≤x≤100)。由于根与根之差的绝对值≥1，因此设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若 ⑴f(x1)=0，则确定x1为f(x)的根； ⑵f(x1)*f(x2)>0，则确定根x不在区间[x1，x2]内，设定[x2，x2+1]为下一个搜索区间 ⑶f(x1)*f(x2)<0，则确定根x在区间[x1，x2]内。 如果确定根x在区间[x1，x2]内的话（f(x1)*f(x2)<0），如何在该区间找到根的确切位置。采用二分法，将区间[x1，x2]分成左右两个子区间：左子区间[x1，x]和右子区间[x，x2]（其中x=）： 如果f(x1)*f(x)≤0，则确定根在左区间[x1，x]内，将x设为该区间的右指针（x2=x），继续对左区间进行对分；如果f(x1)*f(x)>0，则确定根在右区间[x，x2]内，将x设为该区间的左指针（x1=x），继续对右区间进行对分； 上述对分过程一直进行到区间的间距满足精度要求为止（x2-x1<0.001）。此时确定x1为f(x)的根。

12 由此得出算法： 输入方程中各项的系数a，b，c，d ； { for (x=-100;x<=100;x++) //枚举每一个可能的根 x1=x;x2=x+1; //确定根的可能区间 if (f(x1)==0) printf("%.2f ",x1); //若x1为根，则输出 else if (f(x1)*f(x2)<0) //若根在区间[x1，x2]中 while (x2-x1>=0.001) //若区间[x1，x2]不满足精度要求，则循环 xx=(x2+x1)/2; //计算区间[x1，x2]的中间位置 if ((f(x1)*f(xx))<=0) //若根在左区间，则调整右指针 x2=xx; else x1=xx; //若根在右区间，则调整左指针 } printf("%.2f ",x1); //区间[x1，x2]满足精度要求，确定x1为根 cout<<endl; double f(double x) //将x代入函数 return (x*x*x*a+b*x*x+x*c+d); 其中f(x)的函数说明如枚举法所示。

13 【例4】、循环比赛日程表（match） 【问题描述】 设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。 输入：M 输出：表格形式的比赛安排表 【样例输入】match.in 3 【样例输出】match.out

14 【问题分析】 以M=3(即N=23=8)为例，可以根据问题要求，制定出如下图所示的一种方案：
以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出有A=D，B=C，并且，这一规律同样适用于各个更小的部分。 设有n个选手的循环比赛，其中n=2m，要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行n-1天。要求每天没有选手轮空.以下是八名选手时的循环比赛表，表中第一行为八位选手的编号，下面七行依次是每位选手每天的对手。

15 【算法分析】 从八位选手的循环比赛表中可以看出,这是一个具有对称性的方阵,可以把方阵一分为四来看,那么左上角的4*4的方阵就是前四位选手的循环比赛表,而右上角的4*4的方阵就是后四位选手的循环比赛表,它们在本质上是一样的,都是4个选手的循环比赛表,所不同的只是选手编号不同而已,将左上角中方阵的所有元素加上4就能得到右上角的方阵.下方的两个方阵表示前四位选手和后四位选手进行交叉循环比赛的情况,同样具有对称性,将右上角方阵复制到左下角即得到1,2,3,4四位选手和5,6,7,8四位选手的循环比赛表,根据对称性, 右下角的方阵应与左上角的方阵相同.这样,八名选手的循环比赛表可以由四名选手的循环比赛表根据对称性生成出来.同样地, 四名选手的循环比赛表可以由二名选手的循环比赛表根据对称性生成出来,而两名选手的循环比赛表可以说是已知的,这种程序设计方法叫做分治法,其基本思想是把一个规模为n的问题分成若干个规模较小的问题,使得从这些较小问题的解易于构造出整个问题的解。 程序中用数组matchlist记录n名选手的循环比赛表, 整个循环比赛表从最初的1*1的方阵按上述规则生成出2*2 的方阵, 再生成出4*4 的方阵,……，直到生成出整个循环比赛表为止.变量half表示当前方阵的大小,也是要生成的下一个方阵的大小的一半 。

16 【参考程序】 #include<cstdio> const int MAXN=33,MAXM=5; int matchlist[MAXN][MAXN]; int m; int main() { printf("Input m:"); scanf("%d",&m); int n=1<<m,k=1,half=1; // 1<<m 相当于 2^m matchlist[0][0]=1; while (k<=m) for (int i=0;i<half;i++) //构造右上方方阵 for (int j=0;j<half;j++) matchlist[i][j+half]=matchlist[i][j]+half; for (int i=0;i<half;i++) //对称交换构造下半部分方阵 matchlist[i+half][j]=matchlist[i][j+half]; //左下方方阵等于右上方方阵 matchlist[i+half][j+half]=matchlist[i][j]; //右下方方阵等于左上方方阵 }

17 half*=2; k++; } for (int i=0;i<n;i++) { for (int j=0;j<n;j++) printf("%4d",matchlist[i][j]); putchar('\n'); return 0;

18 输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整形数。 【输入样例】mod.in 2 10 9
【问题描述】 输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整形数。 【输入样例】mod.in 2 10 9 【输出样例】mod.out 2^10 mod 9=7 【算法分析】 本题主要的难点在于数据规模很大（b，p都是长整型数），对于b^p显然不能死算，那样的话时间复杂度和编程复杂度都很大。 下面先介绍一个原理：A*B%K = (A%K )*(B% K )%K。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢？

19 显然对于任何一个自然数P，有P=2. P/2 + P%2，如19=2. 19/2 + 19%2=2
显然对于任何一个自然数P，有P=2 * P/2 + P%2，如19=2 * 19/2 + 19%2=2*9+1，利用上述原理就可以把B的19次方除以K的余数转换为求B的9次方除以K的余数，即B19=B2*9+1=B*B9*B9，再进一步分解下去就不难求得整个问题的解。

20 【参考程序】 #include<iostream> #include<cstdio> using namespace std; int b,p,k,a; int f(int p) //利用分治求b^p % k { if (p==0) return 1; // b^0 %k=1 int tmp=f(p/2)%k; tmp=(tmp*tmp) % k; // b^p %k=(b^(p/2))^2 % k if (p%2==1) tmp=(tmp * b) %k; //如果p为奇数，则 b^p % return tmp; //k=((b^(p/2))^2)* b%k } int main() cin>>b>>p>>k; //读入3个数 int tmpb=b; //将b的值备份 b%=k; //防止b太大 printf("%d^%d mod %d=%d\n",tmpb,p,k,f(p)); //输出 return 0;

21 【例8】、黑白棋子的移动（chessman）
【问题描述】 有2n个棋子（n≥4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形： ○○○○○●●●●● 移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为： ○●○●○●○●○● 任务：编程打印出移动过程。 【输入样例】chessman.in 7 【输出样例】chessman.out step 0:ooooooo*******-- step 1:oooooo--******o* step 2:oooooo******--o* step 3:ooooo--*****o*o* step 4:ooooo*****--o*o* step 5:oooo--****o*o*o* step 6:oooo****--o*o*o* step 7:ooo--***o*o*o*o* step 8:ooo*o**--*o*o*o* step 9:o--*o**oo*o*o*o* step10:o*o*o*--o*o*o*o* step11:--o*o*o*o*o*o*o*

22 【算法分析】 我们先从n=4开始试试看，初始时： ○○○○●●●● 第1步：○○○——●●●○● {—表示空位} 第2步：○○○●○●●——● 第3步：○——●○●●○○● 第4步：○●○●○●——○● 第5步：——○●○●○●○● 如果n=5呢？我们继续尝试，希望看出一些规律，初始时： ○○○○○●●●●● 第1步：○○○○——●●●●○● 第2步：○○○○●●●●——○● 这样，n=5的问题又分解成了n=4的情况，下面只要再做一下n=4的5个步骤就行了。同理，n=6的情况又可以分解成n=5的情况，……，所以，对于一个规模为n的问题，我们很容易地就把他分治成了规模为n-1的相同类型子问题。 数据结构如下：数组c[1..max]用来作为棋子移动的场所，初始时，c[1]~c[n]存放白子（用字符o表示），c[n+1]~c[2n]存放黑子（用字符*表示），c[2n+1]，c[2n+2]为空位置（用字符—表示）。最后结果在c[3]~c[2n+2]中。

23 【参考程序】 #include<iostream> using namespace std; int n,st,sp; char c[101]; void print() //打印 { int i; cout<<"step "<<st<<':'; for (i=1;i<=2*n+2;i++) cout<<c[i]; cout<<endl; st++; } void init(int n) //初始化 st=0; sp=2*n+1; for (i=1;i<=n;i++) c[i]='o'; for (i=n+1;i<=2*n;i++) c[i]='*'; c[2*n+1]='-';c[2*n+2]='-'; print();

24 void move(int k) //移动一步
{ int j; for (j=0;j<=1;j++) c[sp+j]=c[k+j]; c[k+j]='-'; } sp=k; print(); void mv(int n) //主要过程 int i,k; if (n==4) //n等于4的情况要特殊处理 move(4); move(8); move(2); move(7); move(1); else move(n); move(2*n-1); mv(n-1); int main() cin>>n; init(n); mv(n);

25 【问题描述】 求方程f(x)=2^x+3^x-4^x=0在[1，2]内的根。 提示：2x可以表示成exp(x*log(2))的形式。
【上机练习】 1、方程f(x)的根 【问题描述】 求方程f(x)=2^x+3^x-4^x=0在[1，2]内的根。 提示：2x可以表示成exp(x*log(2))的形式。 【输入格式】 输入：[1，2]的区间值。 【输出格式】 输出：方程f(x)=0的根，x的值精确小数点10位。 【输入样例】 1 2 【输出样例】 2、求一元三次方程的解 【问题描述】 有形如： ax3+bx2+cx+d=0一元三次方程。给出该方程中各项的系数 (a， b， c， d  均为实数 )，并约定该方程存在三个不同实根 (根的范围在 -100至 100之间 )，且根与根之差的绝对值 >=1。要求由小到大依次在同一行上输出这三个实根。 【输入格式】 输入：a，b，c，d 【输出格式】 输出： 三个实根（根与根之间留有空格） 【输入样例】Equ.in 1 –5 –4 20 【输出样例】Equ.out

26 3、求逆序对 给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。 【输入格式】 第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。 【输出格式】 所有逆序对总数。 【输入样例】deseq. in 4 3 2 【输出样例】deseq.out 【数据范围】 N<=105，Ai<=105。

27 4、麦森数（mason） 【问题描述】 形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P= ，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 任务：从文件中输入P（1000<P< ），计算2P-1的位数和最后500位数字（用十进制高精度数表示）。 【输入格式】 文件中只包含一个整数P（1000<P< ）。 【输出格式】 第一行：十进制高精度数2P-1的位数； 第2-11行：十进制高精度数2P-1的最后500位数字（每行输出50位，共输出10行，不足500位时高位补0）； 不必验证2P-1与P是否为素数。 【输入样例】mason.in 1279 【输出样例】mason.out 386