【分治法】典型题目示例、含详细注释_分治法常见练习题

 一、众数问题：

1.

众数问题 问题描述： 　　给定含有n 个元素的多重集合S，每个元素在S 中出现的次数称为该元素的重数。多重集S 中重数最大的元素称为众数。 　　 例如，S={1，2，2，2，3，5}。 多重集S 的众数是2，其重数为3。 编程任务： 　　对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。 数据输入： 　　输入数据由文件名为input.txt 的文本文件提供。文件的第1 行多重集S 中元素个数n；接下来的n 行中，每行有一个自然数。 结果输出: 　　程序运行结束时，将计算结果输出到文件output.txt 中。输出文件有2 行，第1 行给出众数，第2 行是重数。 输入文件示例          输出文件示例 input.txt             output.txt 6                      2 1                      3 2 2 2 3 5

代码如下： 

#include <iostream>
#include <algorithm>//sort()函数头文件 
using namespace std;
#define N 10000
 
bool cmp(int a,int b){
    return a<b;
}
 
int MaxNum=0;  //存储众数大小 
int MaxNumCount=0;  //存储众数个数 
int num[10000];
 
void split(int left,int right){
    if (left >=right) return;//越界跳出 
    int FirstLeft=left;//记录初始最左侧 
    int FirstRight=right;//记录初始最右侧 
    int mid=(left+right)/2;
    for(;left<mid &&num[left]!=num[mid];left++);//找到中位数的左临界 
    for(;right>mid&&num[right]!=num[mid];right--);//找到中位数的右临界 
    if(MaxNumCount<right-left+1){MaxNum=num[mid];MaxNumCount=right-left+1;} 
	//若此中位数个数大于众数个数，则更新 
	
	//若中位数左临界左边数字个数小于众数个数，则不需要执行下述操作；中位数右临界数字亦然 
    if(left-FirstLeft>MaxNumCount )split(FirstLeft,left-1);  
    if(FirstRight-right>MaxNumCount)split(right+1,FirstRight);
}
 
int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    sort(num,num+n,cmp);//将数组从小到大排序
    int left0=0;int right0=n-1;
    split(left0,right0);
    cout<<MaxNum<<endl;
    cout<<MaxNumCount<<endl;
    return 0;
}

二、邮局选址问题

2.

邮局选址问题 问题描述： 　　在一个按照东西和南北方向划分成规整街区的城市里，n 个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y 坐标表示南北向。各居民点的位置可以由坐标(x,y) 表示。街区中任意2 点(x1,y1) 和(x2,y2) 之间的距离可以用数值|x1-x2|+|y1-y2| 度量。 居民们希望在城市中选择建立邮局的最佳位置，使n 个居民点到邮局的距离总和最小。 编程任务： 　　给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。 数据输入： 　　由文件input.txt 提供输入数据。文件的第1 行是居民点数n，1<=n<=10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000<=x，y<=10000。 结果输出: 　　程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是n 个居民点到邮局的距离总和的最小值。 输入文件示例               输出文件示例 input.txt                  output.txt 5                          10 1 2 2 2 1 3 3 -2 3 3

代码如下：

#include <iostream>
#include <algorithm>//sort()函数头文件 
using namespace std;
#define N 10000
 
bool cmp(int a,int b){
    return a<b;
}
 
int main()
{
    int n;cin>>n;
    int X=0, Y=0;//（X,Y）记录邮局位置
    int MinDis=0;
    int x[N],y[N];
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    
	//街区中任意2 点(x1,y1) 和(x2,y2) 之间的距离可以用数值|x1-x2|+|y1-y2| 度量。
	//所以可将x，y分开计算 
    sort(x,x+n,cmp);//排序 
    sort(y,y+n,cmp);//排序 
    X=x[n/2];Y=y[n/2];
    //下图有解释，为何取[n/2]，以及坐标数为奇/偶数此取值皆满足 
	//邮局位置找法思想，两边之和大于第三边，x取值必须在以两点为一组，在其连线上 
    for(int i=0;i<n;i++){
        int dis1=x[i]-X;int dis2=y[i]-Y;
        if(dis1<0) dis1=-1*dis1;//距离为正值，若作差为负数，则取相反数 
        if(dis2<0) dis2=-1*dis2;//距离为正值，若作差为负数，则取相反数 
        MinDis=MinDis+dis1+dis2;//求和 
    }
    cout<<MinDis<<endl;
    return 0;
}

 

三、集合划分问题

	3.	集合划分问题 问题描述： 　　n 个元素的集合{1,2,., n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2， 3，4}可以划分为15 个不同的非空子集如下： {{1}，{2}，{3}，{4}}， {{1，2}，{3}，{4}}， {{1，3}，{2}，{4}}， {{1，4}，{2}，{3}}， {{2，3}，{1}，{4}}， {{2，4}，{1}，{3}}， {{3，4}，{1}，{2}}， {{1，2}，{3，4}}， {{1，3}，{2，4}}， {{1，4}，{2，3}}， {{1，2，3}，{4}}， {{1，2，4}，{3}}， {{1，3，4}，{2}}， {{2，3，4}，{1}}， {{1，2，3，4}} 其中，集合{{1，2，3，4}} 由1 个子集组成；集合{{1，2}，{3，4}}，{{1，3}，{2， 4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2， 3，4}，{1}} 由2 个子集组成；集合{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}， {2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}} 由3 个子集组成；集合{{1}，{2}，{3}，{4}} 由4 个子集组成。 编程任务： 　　给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。 数据输入： 　　由文件input.txt 提供输入数据。文件的第1 行是元素个数n 和非空子集数m。 结果输出: 　　程序运行结束时，将计算出的不同的由m个非空子集组成的集合数输出到文件output.txt 中。 输入文件示例            输出文件示例 input.txt               output.txt 4    3                      6

 代码如下：

#include <iostream>
 
using namespace std;
 
int num(int n, int m){
    if(n==m||m==1) return 1;
    else{return num(n-1,m-1)+num(n-1,m)*m;}
}
 
int main()
{
    int n,m;cin>>n>>m;
    cout<<num(n,m)<<endl;
    return 0;
}

 对{1,2,3}进行划分：

（1）、1个子集：{1,2,3}        即num(3,1)=1

（2）、2个子集：{1,2},{3}    {1,3},{2}     {2,3},{1}        即num(3,2)=3

（3）、3个子集：{1},{2},{3}        即num(3,3)=1

对{1,2,3,4}进行划分为3个子集：

（1），在对{1,2,3}划分为两个子集的结果中加入{4}: {1,2},{3},{4}    {1,3},{2},{4}     {2,3},{1},{4}        此个数为num(3,2)

（2）,在对{1,2,3}划分为三个子集的结果中加入元素4:{1,4},{2},{3}        {1},{2,4},{3}        {1},{2},{3,4}        此个数为num(3,3)*3

综上所述：

num(4,3)=num(3,2)+num(3,3)*3

推广至num(n,m)为：        num(n,m)=num(n-1,m-1)+num(n-1,m)*m  

且当 n==m或者m==1时，num(n,m)=1

四、输油管道问题

	4.	输油管道问题 问题描述： 　　某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。 编程任务： 　　给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。 数据输入： 　　由文件input.txt 提供输入数据。文件的第1 行是油井数n，1<=n10000。接下来n 行是油井的位置，每行2 个整数x 和y，-10000<=x，y<=10000 。 结果输出: 　　程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是油井到主管道之间的输油管道最小长度总和。 输入文件示例       输出文件示例 input.txt           output.txt 5                       6 1 2 2 2 1 3 3 -2 3 3

代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
#define N 10000
 
bool cmp(int a,int b){
    return a<b;
}
 
int main()
{
    int n;cin>>n;
    int X=0, Y=0;//（X,Y）记录邮局位置
    int MinDis=0;
    int x[N],y[N];
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    sort(x,x+n,cmp);
    sort(y,y+n,cmp);
    X=x[n/2];Y=y[n/2];//邮局位置找法思想，两边之和大于第三边
    //将坐标两两分组，距离两点最近距离肯定在其两点间连线上，取交集即可；
    for(int i=0;i<n;i++){
        int dis1=x[i]-X;int dis2=y[i]-Y;
        if(dis1<0) dis1=-1*dis1;
        if(dis2<0) dis2=-1*dis2;
        MinDis=MinDis+dis2;
		//只需要y坐标距离差的绝对值（与第二题不同，此题为东西走向管道，不需考虑X坐标） 
    }
    cout<<MinDis<<endl;
    return 0;
}

五、 整数因子分解问题

代码如下：

#include <iostream>
 
using namespace std;
 
int factor(int n){
    int sum=0;
    for(int i=n;i>1;i--){
        if(n%i==0){//i是n的因子 
            int j=n/i;
            if(factor(j)==0) sum++;
            else{
                sum=sum+factor(j);
            }
        }
    }
    return sum;
}
 
int main()
{
    int n;cin>>n;
    cout<<factor(n)<<endl;
    return 0;
}