参考b7分治算法

分治算法分治算法所谓分治算法就是将较大规模的问题分解成几个较小规模的问题,通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。1、解决算法实现的同时,需要估算算法实现所需时间。分治算法时间是这样确定的：解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量决定）合并所有子问题所需的工作量。2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法。3、分治的具体过程：//开始{if

①问题不可分 ②返回问题解else

{③从原问题中划出含一半运算对象的子问题1；④递归调用分治法过程，求出解1；⑤从原问题中划出含另一半运算对象的子问题2；⑥递归调用分治法过程，求出解2；⑦将解1、解2组合成整个问题的解；}}//结束分治算法——例1快速排序(递归算法)//将当前序列在中间位置的数定义为分隔数//在左半部分寻找比中间数大的数//在右半部分寻找比中间数小的数//若找到一组与排序目标不一致的数对则交换它们void

qsort(int

l,

int

r){int

i,

j,

mid,

p;i=l;j=r;mid=a[(l+r)/2];

do{while

(a[i]<mid)

i++;while

(a[j]>mid)

j--;if

(i<=j){p=a[i];

a[i]=a[j];

a[j]=p;i++;j--;

//继续找//注意这里要有等号//若未到两个数的边界,则递归搜索左右区间}}while(i<=j);if

(l<j)

qsort(l,

j);if

(i<r)

qsort(i,

r);}分治算法——例2用递归算法实现二分查找即：有n个已经从小到大排序好的数据,输入一个数m,用二分查找算法,判断它是否在这n个数中。#include<iostream>using

namespace

std;int

jc(int,

int);int

n,

a[1000],

m;int

main(){int

x,

y,

i;cin

>>

n;x=1;

y=n;for

(i=1;

i<=n;

i++)cin

>>

a[i];

//输入已排序的数cin

>>

m;

//输入要查找的数jc(x,

y);

//二分递归查找

cout<<endl;}//递归过程int

jc(int

x,

int

y){int

k;k=(x+y)/2;if

(a[k]==m)//取中间位置点//找到查找的数,输出cout<<"then

num

in"<<k<<endl;if

(x>y)

//找不到该数cout

<<

"no

find"

<<

endl;else{if

(a[k]<m)jc(k+1,y);

//在后半段查找

if

(a[k]>m)jc(x,

k-1);

//在前半段查找}}分治算法——例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【输出】三个实根（根与根之间留有空格）【输入样例】1

-5

-4

20【输出样例】-2.00

2.00

5.00分治算法——例3xx1=x-0.0005x2=x+0.0005xx1=x-0.0005【算法分析】为了便于求解,设方程f(x)=ax3+bx2+cx+d=0设根的值域（-100至100之间）中有x,其左右两边相距0.0005的地方有x1和x2两个数,即x1=x-0.0005,x2=x+0.0005。x1和x2间的距离（0.001）满足精度要求（精确到小数点后2位）。若出现如图所示的两种情况之一,则确定x为f(x)=0的根。1、f(x1)*f(x2)<0 2、f(x1)=0分治算法——例3【思路1-枚举法】根据题目的精度要求（小数点后2位）,我们可以在值域（-100至100之间）内间隔0.01依次枚举x的值,然后验证x是否为根这里,不妨把根和值域都扩大100倍（-10000至10000之间）,然后依次枚举该区间的每一个整数值x,

并在题目要求的精度内设定区间：x1=(x-0.05)/100,x2=(x+0.05)/100。若区间端点的函数值f(x1)和f(x2)异号或者区间端点x1的函数值f(x1)=0,

则确定x/100为f(x)=0的一个根。//枚举当前根*100的可能范围输入方程中各项的系数a,b,c,d

；for

(x=-10000;

x<=10000;

x++){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);}分治算法——例3【思路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]内的话,令x=(x1+x2)/2,

采用二分法,将区间[x1,x2]分成左右两个子区间：左子区间[x1,x]和右子区间[x,x2]如果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)的根。分治算法——例3{//枚举每一个可能的根for

(x=-100;x<=100;x++){x1=x;

x2=x+1;//确定根的可能区间if

(f(x1)==0)printf("%.2f

",x1);//若x1为根,则输出//若根在区间[x1,x2]中//若区间[x1,x2]不满足精度要求,则循环//计算区间[x1,x2]的中间位置//若根在左区间,则调整右指针//若根在右区间,则调整左指针else

if

(f(x1)*f(x2)<0){while

(x2-x1>=0.001{xx=(x2+x1)/2;if

((f(x1)*f(xx))<=0)x2=xx;else

x1=xx;}printf("%.2f

",x1);

//区间[x1,x2]满足精度要求,确定x1为根}}cout

<<

endl;}分治算法——例4设有N个选手进行循环比赛,其中N=2M,要求每名选手要与其他N-1名选手都赛一次,每名选手每天比赛一次,循环赛共进行N-1天,要求每天没有选手轮空。【输入】M【输出】表格形式的比赛安排表【样例输入】3【样例输出】1

23456782

14365873

41278564

32187655

67812346

58721437

85634128

7654321分治算法——例4【问题分析】以M=3(即N=23=8)为例,可以根据问题要求,制定出如下图所示的一种方案：以表格的中心为拆分点,将表格分成四个部分,就很容易看出有：①左上=右下,右上=左下；②左上所有单元格的数字加上4（n/2）后,就与右上相等。③将各个部分再进行分拆,同样符合以上规律所以：1×1

2×2

4×4

8×8Day1Day2Day3Day4Day5Day6Day7123456782

1

4 3

+4

6587341278564321876556781234658721437856341287654321分治算法——例4//变量half表示当前方阵的大小,也是要生成的下一个方阵的大小的一半//构造右上方方阵#include<cstdio>const

int

MAXN=33,

MAXM=5;intmatchlist[MAXN][MAXN];intm;intmain(){printf("Input

m:");scanf("%d",

&m);int

n=1<<

m,

k=1,half=1;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++)

//对称交换构造下半部分方阵

for(int

j=0;j<half;j++){

matchlist[i+half][j]=matchlist[i][j+half];

//左下方方阵等于右上方方阵matchlist[i+half][j+half]=matchlist[i][j];

//右下方方阵等于左上方方阵}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;}分治算法——例5取余运算（mod）输入b,p,k的值,求b^pmodk的值。其中b,p,k*k为长整形 数。【输入样例】2109【输出样例】2^10mod9=7分治算法——例5【算法分析】本题数据规模大（b,

p都是长整形）,如果直接求bp,时间复杂度过大可以将bp分解成较小的数,利用以下原理：A*B

%

K

=

(

(A

%

K)

*

(B

%

K)

)

%

K采用二分法,如：B19=

B9*B9

*

BB9

=B4*B4

*

BB4

=B2*B2B2

=B1*B1B1

=B0*B0

*

B是否要再乘以B11001分治算法——例5//利用分治求b^p%k//

b^0

%

k=1//分治,求tmp=b^(p/2)%k//b^p

%

k=(b^(p/2))^2

%

k//若p为奇数,则需再乘以b#include<iostream>#include<cstdio>using

namespace

std;int

b,

p,

k,

a;int

f(int

p){if

(p==0)

return

1;int

tmp=f(p/2)%k;tmp=(tmp*tmp)

%

k;if

(p%2==1)

tmp=(tmp*b)

%k;return

tmp;}int

main(){cin

>>

b

>>

p

>>

k;int

tmpb=b;b%=k;//读入3个数//将b的值备份//防止b太大printf("%d^%d

mod

%d=%d\n",

tmpb,

p,

k,

f(p));return

0;}分治算法——例6黑白棋子的移动（chessman）有2n个棋子（n≥4）排成一行,开始位置为白子全部在左边,黑子全部在右边,如下图为n=5的情形：○○○○○●●●●●移动棋子的规则是：每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可以右移到空位上去,但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移）,要求最后能移成黑白相间的一行棋子。如n=5时,成为：○●○●○●○●○●任务：编程打印出移动过程。【输入样例】7【输出样例】chessman.outstep

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*分治算法——例6【算法分析】我们先从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]中。分治算法——例6#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)

//初始化{int

i;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();}void

move(int

k)

//将c[k]、c[k+1]移动到空位{int

j;for

(j=0;j<=1;j++){c[sp+j]=c[k+j];c[k+j]='-';}sp=k;print();}//将2*n个棋子移动到合适位置//注意,这里的n是局部变量,与全局变量n不同void

mv(int

n){inti,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);}}intmain(){cin>>n;init(n);mv(n);}分治算法——例7月度开销农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来N

(1≤N≤100,000)天里每天需要的开销。约翰打算为连续的M

(1≤M≤N)

个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。输入：第一行包含两个整数N、M，用单个空格隔开。接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。输出：一个整数，即最大月度开销的最小值。分治算法——例7【算法分析】直接求解答案较困难。转换思路，不难想到将问题转换为判定性问题求 解，从1到10000*N（最大可能答案为N个数的和）枚举答案i，找到第一 个满足存在一种方案，使得开销最多的fajo月开销小于等于i的i输出。设check(i)表示是否存在方案使得开销最多的fajo月的开销小于等于i。判断check(i)可以用贪心法，从左到右扫描每一天的开销，采用“物尽 其用”原则，在不超过i的前提下让每一个fajo月的天数越多越好。如果最终得到的预算案小于等于M，则check(i)=1，否则check(i)=0；每次判断时间复杂度O(N)，总的时间复杂度O(10000*N^2)，会超时。分治算法——例7如果check(i)=1,则答案必定小于等于i；如果check(i)=0，则答案必 定大于i。我们不必从小到大逐一枚举答案，而用“二分枚举答案”i值。用left表示二分区间左边界，right表示右边界，当right-left>1时：①mid=(left+right)/2②如果check(mid)=1则right=mid，否则left=mid重复执行直到right-left<=1，由于left的左边都是小于答案的，right的右边是大于等于答案的。所以最终答案就是right。时间复杂度O（n*log(n*10000)）,可以通过本题。这就是非常常见的

“二分答案+贪心判断”分治算法——例7#include

<iostream>

using

namespace

std;const

int

MAXN

=

100005;int

A[MAXN],N,M;//判断limit对应的fajo月数是否不超过Mbool

ok(int

limit){int

c

=

1;for(int

i=1,sum=0;

i<=N;

i++)if

(sum+A[i]<=limit)sum+=A[i];else{++c;

//找到一个fajo月sum=A[i];//若有一个数比limit大，则一定不符合要求

if

(sum>limit)return

0;}return

c<=M;}int

main(){cin

>>

N

>>

M;for(int

i=1;

i<=N;

i++)

cin

>>

A[i];int

l=1,

r=10000*N;while

(r-l>1){int

mid=l+r>>1;

//比(l+r)/2快if

(ok(mid))

r=mid;else

l

=

mid;}cout

<<

r

<<

endl;return

0;}分治算法——例8路由器安置一条街道安装无线网络，需要放置M个路由器。整条街道上一共有N户居 民，分布在一条直线上，每一户居民必须被至少一台路由器覆盖到。现 在的问题是所有路由器的覆盖半径是一样的，我们希望用覆盖半径尽可 能小的路由器来完成任务，因为这样可以节省成本。输入格式：输入第一行包含两个整数M和N，以下N行每行一个整数Hi表 示该户居民在街道上相对于某个点的坐标。（不保证Hi有序）输出格式：输出仅包含一个数，表示最小的覆盖半径，保留一位小数。1

≤N,

M

≤100000，-10000000≤Hi≤10000000分治算法——例8【算法分析】跟上题类似，二分答案：设check(i)=0表示半径为i不符合题目要 求，反之check(i)=1表示半径为i符合题目要求。用贪心思想计算check(i)：对于最左边的一户居民，一定在第一 个圆的左边缘。接着找到最左边一个未被圆覆盖到的居民，再画一 个圆...如下图共需要3个路由器。分治算法——例8答案要求精确到小数点后一位怎么办？求出精确到小数点后两位的答案，保留一位小数输出。二分答案不仅适用于整数答案，也适用于求小数答案。答案集合想象成后一个数比前一个数大0.01递增，将二分查找的指 向条件改为right-left>0.01即可。分治算法——例8#include

<iostream>using

namespace

std;constint

MAXN=100005