算法整理五——分治
目录
一、分治概述
二、二分搜索技术
二分搜索：
二分搜索技术-找数对
二分搜索技术-排序且不重复输出
三、循环赛日程表
四、棋盘覆盖
五、选择问题（掌握线性时间选择法解决此问题）
六、输油管问题
七、半数集问题
九、寻找中位数（快速排序版 openjudge题目）
一、分治概述
- 分治法的设计思想：将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破，分而治之
- 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同
- 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
- 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
3.子问题的解可以合并为该问题的解
4.快速排序（openjudge题目），并能灵活应用快速排序解决相关问题
5.用分治法解决：循环赛日程表、棋盘覆盖、找出这n个元素中第k小的元素（掌握线性时间选择法解决此问题）、输油管问题、半数集问题、整数因子分解问题、寻找中位数（快速排序版 openjudge题目）
二、二分搜索技术
二分搜索：
int binarySearch(int [] a, int x, int n){
// 在 a[0] <= a[1] <= ... <= a[n-1] 中搜索 x
// 找到x时返回其在数组中的位置，否则返回-1
int left = 0; int right = n - 1;
while (left <= right) {
int middle = (left + right)/2;
if (x == a[middle]) return middle;
if (x > a[middle]) left = middle + 1;
else right = middle - 1;
}
return -1; // 未找到x
}
二分搜索技术-找数对
给出若干个整数,询问其中是否有一对数的和等于给定的数。
说明: 如果有多对数符合要求,输出最小数最小的一对
输入样例:
4
2 5 1 4
6
输出
1 5
分析：
对输入数据从小到大排好序遇到第一个符合条件的输出，然后结束循环，这样就能保证输出最小数最小的一对，并且只输出一对
#include<iostream>
#include<algorithm>
using namespace std;
int f(int a[],int low,int high,int k)
//从下标i+1,到最后一个元素n,寻找sum-a[i]
{
int mid;
if(low>high)//终止条件
return 0;
mid=(low+high)/2;
if(a[mid]==k)
return mid;
else if(k>a[mid])
return f(a,mid+1,high,k);
else
return f(a,low,mid-1,k);
}
int main()
{
int i,n,a[101],sum;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
cin>>sum;
for(i=1;i<=n;i++)
{
if(f(a,i+1,n,sum-a[i]))
{
cout<<a[i]<<" "<<sum-a[i]<<endl;
break;
}
}
return 0;
}
二分搜索技术-排序且不重复输出
输入n个数，从小到大将他们输出，重复的数只输出一次
输入：
5
2 4 4 5 1
输出：
1 2 4 5
分析：
- 将数组排序
- 找到数组a(s,e),中位于中间的数x,利用该数将序列分割成两个子序列
- 查找x 的第一次出现（f）和最后出现(l),
- 利用这两个参数构造两个子序列(s,f-1), (l+1,e)
- 对左子序列进行处理
- 输出中间数
- 对右子序列进行处理
其实这题关键就是去掉中间重复的元素，利用二分搜索找出重复最左边的元素，然后找重复最右边的元素。输出最左边左边的元素，输出最右边右边的元素，中间的自然就去掉了。
#include<iostream>
#include<algorithm>
using namespace std;
void ff(int a[],int low,int high)
{
int mid,num,f,l,i;
if(low>high)//终止条件
return ;
mid=(low+high)/2;
num=a[mid];//中位数
i=mid-1;//i在左边
while(a[i]==num &&i>=low)//寻找左边与中位数相等的值
i--;
f=i;//f代表与中位数相等的最左边的值
i=mid+1;//找右边
while(a[i]==num&&i<=high)
i++;
l=i;//l代表与中位数相等的最右边的值
ff(a,low,f);//继续找左边
//输出左边的值
cout<<num<<" ";//输出中位数
ff(a,l,high);//输出右边的值
}
int main()
{
int i,n,a[101];
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
ff(a,0,n);
return 0;
}
三、循环赛日程表
循环赛日程表问题，设有n=2k个选手要进行循环赛，设计一个满足以下要求的比赛日程表：
每个选手必须与其他n-1个选手各赛一次；
每个选手一天只能赛一次；
循环赛一共进行n-1天。
分析：
用到矩阵拷贝
n*n的矩阵，分割k次，8*8的矩阵,k=3；4*4的矩阵,k=2
至于是怎么分的，看上图，对于8*8的矩阵相当于每两行切一刀
#include<iostream>#include<algorithm>using namespace std;int a[101][101];//Table(3)的执行void Copy(int tox,int toy,int fromx,int fromy,int r){for(int i=0;i<r;i++)for(int j=0;j<r;j++)a[tox+i][toy+j]=a[fromx+i][fromy+j];}void Table(int k)//k为分割次数{int i,r;//r代表行int n=1;//n为参赛人数for(i=1;i<=k;i++)//我理解的是通过分割次数，确定参赛人数n=n*2;for(i=0;i<n;i++)a[0][i]=i+1;//依次完成行列数是1,2,4….n/2 的矩阵的复制for(r=1;r<n;r=r*2)for(i=0;i<n;i+=2*r){//1次拷贝，通过多对矩阵的拷贝完成Copy(r,r+i,0,i,r);//左上角拷贝到右下角Copy(r,i,0,r+i,r); //右上角拷贝到左下角}}int main(){//8*8矩阵为例Table(3);for(int i=0;i<=7;i++){for(int j=0;j<=7;j++)cout<<a[i][j]<<" ";cout<<endl;}return 0;}结果输出如下：
四、棋盘覆盖
在一个2k×2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
问题：对于给定的特殊棋盘，设计棋盘覆盖方案
例如：
输入：
2 // k,棋盘的边长为2^k
0 1 //特殊方格的坐标（ 用2k ×2k 的矩阵表示一个棋盘）
输出：
2 0 3 3
2 2 1 3
4 1 1 5
4 4 5 5
分析：
- 分割：当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘，特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。
- 为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。如上图所示。
- 递归地使用这种分割，直至棋盘简化为棋盘1×1
void ff(int tr,int tc,int dr,int dc,int size)//tr:子棋盘左上角方格的行号；tc：棋盘左上角方格的列号；//dr：特殊方格所在的行号；dc：特殊方格所在的列号；//size=2^k{if(size==1)//结果return ;int t = tile++; // L型骨牌顺序号int s=size/2;//分割棋盘//处理左上角棋盘if(dr<tr+s && dc<tc+s)//特殊方格在此棋盘中ff(tr,tc,dr,dc,s);else// 如果不在，用 t 号L型骨牌覆盖右下角{board[tr+s-1][tc+s-1]=t;// 覆盖其余方格ff(tr,tc,tr+s-1,tc+s-1,s);}// 处理右上角子棋盘if (dr < tr + s && dc >= tc + s)// 特殊方格在此棋盘中ff(tr, tc+s, dr, dc, s);else {// 此棋盘中无特殊方格// 用 t 号L型骨牌覆盖左下角board[tr + s - 1][tc + s] = t;// 覆盖其余方格ff(tr,tc+s,tr+s-1,tc+s, s);}// 处理左下角子棋盘if (dr >= tr + s && dc < tc + s)// 特殊方格在此棋盘中ff(tr+s, tc, dr, dc, s);else {board[tr + s][tc + s - 1] = t;// 覆盖其余方格ff(tr+s, tc, tr+s, tc+s-1, s);}// 处理右下角子棋盘if (dr >= tr + s && dc >= tc + s)// 特殊方格在此棋盘中ff(tr+s, tc+s, dr, dc, s);else {board[tr + s][tc + s] = t;// 覆盖其余方格ff(tr+s, tc+s, tr+s, tc+s, s);}}}五、选择问题（掌握线性时间选择法解决此问题）
元素选择问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。
输入：对每一个测试例有2行，第一行是整数n和k（1≤k＜n≤1000），第二行是n个整数。
输出：第k小的元素。
输入样例：
5 2
3 9 4 1 6
输出样例：
3
分析：线性时间选择算法，平均时间复杂度为 O(n )。
- 模仿快速排序算法，首先对输入数组进行划分，然后对划分出的子数组之一进行递归处理。
- 快速排序的基本思想：
- 首先选第一个数作为分界数据，
- 将比它小的数据存储在它的左边，比它大的数据存储在它的右边，它存储在左、右两个子集之间。
- 这样左、右子集就是原问题分解后的独立子问题。
- 再用同样的方法，继续解决这些子问题，直到每个子集只有一个数据，就完成了全部数据的排序工作。
- （1）如果nleft ＝k﹣1，则分界数据就是选择问题的答案
- nleft ＞k﹣1，则选择问题的答案继续在左子集中找。问题规模变小。
- nleft ＜k﹣1，则选择问题的答案继续在右子集中找第k-nleft-1个数。问题规模变小。
#include<iostream>#include<algorithm>using namespace std;int a[101];int select(int left,int right,int k){if(left>=right)//递归出口return a[left];int i=left;int j=right+1;int p=a[left];//根据快速排序，最左边元素作为分界while(true){do{i=i+1;}while(a[i]<p);//从左到右do{j=j-1;}while(a[j]>p);//从右到左if(i>=j)break;//一趟排序结束swap(a[i],a[j]);}if(j-left+1==k)//j-left+1 :左区元素的个数return p;a[left]=a[j];a[j]=p;if(j-left+1<k)//在右区域找return select(j+1,right,k-j+left-1);elsereturn select(left,j-1,k);}int main(){int n,k;//n个元素，找第k小的元素cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];//sort(a+1,a+n+1);cout<<select(1,n,k)<<endl;return 0;}六、输油管问题
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经（或南或北）与主管道相连。
如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位置？
给定n口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和
分析：
通过下面坐标图很好理解，就是找一条平行x轴的直线，使几个点到这条线的总距离之和最小。所以只需要确定油道的y坐标即可，由中位数定理可知，y是中位数，应满足
所以，这题就变成了求中位数，中位数即是要求的y值，但是要求输出的是总和最小值，用上面公式即可
方法一：对数组a排序（一般是升序），取中间的元素。
sort(a,a+n); //按升序排序
int min=0;
for(int i=0;i<n;i++)
min += (int)fabs(a[i]-a[n/2]);
cout<<min<<endl;
方法二：采用分治策略求中位数，快速排序中的分割算法
int select(int left,int right,int k)
{
这个方法与上面代码完全一样，可以不用更改
}
int main()
{
int n,x;//n个元素，找第k小的元素
cin>>n;
for(int i=0;i<n;i++)
cin>>x>>a[i];//x坐标用不到，不存储，a[i]用来存储y坐标
int y=select(0,n-1,n/2+1);
int min=0;
for(int i=0;i<n;i++)
min += (int)fabs(a[i]-y);
cout<<min<<endl;
return 0;
}
七、半数集问题
要求找出具有下列性质的数的个数(包含输入的自然数n)：
先输入一个自然数n(n<=500),然后对此自然数按照如下方法进行处理:
1.不作任何处理;
2.在它的左边加上一个自然数,但该自然数不能超过最近添加数字的一半;
3.加上数后,继续按此规则进行处理,直到不能再加自然数为止。
如输入6，则有16,26,126,36,136
对于每一个新数a，依次可以构造出首位是1~a/2的新数字；对每一个新数字，继续按照相同的方法进行处理
递归结束的条件是：添加的新数字为1
设自然数n的半数集中的元素个数为f(n)，
方法一：存在重复计算
#include <iostream>using namespace std;int comp(int n) {int ans=1; //n的半数集合的大小，n属于这个集合，因此初值为1for(int i=1;i<=n/2;i++) { //i为新数的前面的部分数字ans=ans+ comp(i);}return ans;}int main() {int x,num;cin>>x;num=comp(x);cout<<num<<endl;return 0;}方法二：记忆式搜索(备忘录)
#include <iostream>#include<cstring>using namespace std;int a[101];//相当于一个标记，算过标记1int comp(int n) {int ans=1; //n的半数集合的大小，n属于这个集合，因此初值为1if(a[n]>0)return a[n];for(int i=1;i<=n/2;i++) { //i为新数的前面的部分数字ans=ans+ comp(i);}a[n]=ans;return ans;}int main() {int x,num;memset(a,0,sizeof(a));/*memset(参数1，参数2，参数3)作用将某一块内存中的全部内容置为指定的值参数1：起始位置；参数2：指定的值；参数3：字节大小*/cin>>x;num=comp(x);cout<<num<<endl;return 0;}八、整数因子分解问题
大于1的正整数n可以分解为： 
对于给定的正整数n，编程计算n共有多少种不同的分解式。
例如：当n=12时，共有8种不同的分解式：
#include <iostream>using namespace std;int total;//全局变量int ff(int n) {if (n==1)//因子为1时total++; //获得一个分解elsefor (int i=2; i<=n; i++)if (n%i==0)ff(n/i);}int main() {int n;cin>>n;total = 0;ff(n);cout<<total<<endl;return 0;}九、寻找中位数（快速排序版 openjudge题目）
在N（1 <= N <= 100001 且N为奇数）个数中，找到中位数。
样例输入
5
2 4 1 3 5
样例输出
3
这个题与前面输油管问题类似【采用分治策略求中位数，快速排序中的分割算法】
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[101];
int select(int left,int right,int k)
{
}
int main()
{
int n;//n个元素
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<select(0,n-1,n/2+1);
return 0;
}
