分治算法例题

Ⅰ 分治算法问题

(1)设一函数int count(int b,int e,int x),可求出A[b,e]中x的出现频度,则:
int count(int b,int e,int x){
if(b==e){
return A[b]==x);
}
else{
return count(b,(b+e)/2,x)+count((b+e)/2+1,e,x);
}
}
复杂度O(n),具体地n次比较,n-1次加法运算.

(2)直接从第1个往后选,选到满为止.复杂度O(n)
证明:
假设此方法得出的解不是最优解,则:

设所选物品为1~k,必然存在一个n(n>k),用这个物品代替原所选物品物品时,能取得更优的解值.

但由条件可知,位置大于k的物品重量必然比小于k的物品大,所以至少要替换掉1个;而它的值却小于原物品中的任何一个.所以假设不成立.

按"直接从第1个往后选,选到满为止"的方法选取,得出的解就是最优解.

Ⅱ C++算法问题分治法 注意 要是c++！！！

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
int n;
int x[10000],y[10000];
int i=0,miny=0,minx=0;
int temp;
cin>>n;
temp=n;
while(temp--)
{
cin>>x[i]>>y[i];//存储各个士兵的坐标
i++;
}
for(int j=0;j<n;j++)//这主要是y轴方向的移动，找一个最小y坐标，使得
//y轴方向移动次数最小
{
int minyt=0;
for(int k=0;k<n;k++)
{
if(j==0)
{
miny+=abs(y[j]-y[k]);
}
else
{
minyt+=abs(y[j]-y[k]);//计算y=y[j],都移动到y=y[j],x不变，要移动的步数
}
}
if(j!=0)
{
if(minyt<miny)
miny=minyt;//记录y轴方向移动的最小步数。也就是确定最后就是移动了这个y轴上了。
}
}
sort(x,x+n);//对士兵x坐标排序，这里sort()是库函数在<algorithm>
int begin=(x[0]-n)>-10000?(x[0]-n):-10000;//这是x轴排列最小起始点。
int end=x[n-1];//这是x轴排列最大起始点。
for(int b=begin;b<=end;b++)//b依次以begin到end内的坐标作为起始点，
{
int minxt=0;
for(int p=0,q=b;p<n;p++,q++)
{
if(b==begin)
{
minx+=abs(x[p]-q);这是把x[]数组移动到x轴起始点为b的移动步数。
}
else
{
minxt+=abs(x[p]-q);
}
}
if(b!=begin)
{
if(minxt<minx)
minx=minxt;
}
}
cout<<minx+miny<<endl;
return 0;
}
程序如上，思想是先求y轴方向最小的移动步数。也就是找到，排列的y位置。
然后求x轴方向最小的移动步数。
对你给的数据是可以求出结果的。不知道其他大数数据是否可以，你可以试下。

Ⅲ 一道算法题目，急求答案

蛮力方法O(k) 就是要算k次那样的意思
分治法O(log(k)) 就是要算log(k)次那样的意思->就是k能除以几次2

下面几个没接粗过。

Ⅳ 分治算法的小问题

A是排好序的吗？？
应该是吧，不然还要分治算法干什么……
时间复杂度O（logn）
如n=16,朴素算法16次，分治算法4次

Ⅳ 分治策略的典型例题

例1：二分查找
在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。比较自然的想法是一个一个地扫描L的所有元素，直到找到x为止。这种方法对于有n个元素的线性表在最坏情况下需要n次比较。一般来说，如果没有其他的附加信息，在有n个元素的线性表中查找一个元素在最坏情况下都需要n次比较。下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？
如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：比较x和L中任意一个元素L[i]，若x=L[i]，则x在L中的位置就是i；如果x<L[i]，由于L是递增排序的，因此假如x在L中的话，x必然排在L[i]的前面，所以我们只要在L[i]的前面查找x即可；如果x>L[i]，同理我们只要在L[i]的后面查找x即可。无论是在L[i]的前面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。很显然此问题分解出的子问题相互独立，即在L[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。
于是我们得到利用分治法在有序表中查找元素的算法。
function Binary_Search(L,a,b,x);
begin
if a>b then return(-1)
else begin
m:=(a+b) div 2;
if x=L[m] then return(m)
else if x>L[m]
then return(Binary_Search(L,m+1,b,x));
else return(Binary_Search(L,a,m-1,x));
end;
end;
在以上算法中，L为排好序的线性表，x为需要查找的元素，b,a分别为x的位置的上下界，即如果x在L中，则x在L[a..b]中。每次我们用L中间的元素L[m]与x比较，从而确定x的位置范围。然后递归地缩小x的范围，直到找到x。
例2：快速排序
快速排序的基本思想是基于分治法的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：
分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。
程序代码如下：
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin b[i]:=b[j];i:=i+1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin b[j]:=b[i];j:=j-1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
例3：归并排序
归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。
程序代码如下：
program gbpx;
const maxn=7;
type arr=array[1..maxn] of integer;
var a,b,c:arr;
i:integer;
procere merge(r:arr;l,m,n:integer;var r2:arr);
var i,j,k,p:integer;
begin
i:=l;j:=m+1;k:=l-1;
while (i<=m)and (j<=n) do
begin
k:=k+1;
if r[i]<=r[j] then begin r2[k]:=r[i];i:=i+1 end
else begin r2[k]:=r[j];j:=j+1 end
end;
if i<=m then
for p:=i to m do begin k:=k+1;r2[k]:=r[p] end;
if j<=n then
for p:=j to n do begin k:=k+1;r2[k]:=r[p] end;
end;
procere mergesort( var r,r1:arr;s,t:integer);
var k:integer; c:arr;
begin
if s=t then r1[s]:=r[s] else
begin
k:=(s+t) div 2;
mergesort(r,c,s,k);
mergesort(r,c,k+1,t);
merge(c,s,k,t,r1)
end;
end;
begin
write('Enter data:');
for i:= 1 to maxn do
read(a[i]);
mergesort(a,b,1,maxn);
for i:=1 to maxn do
write(b[i]:9);
writeln;
end.

Ⅵ 阐述一个生活中您所了解的用分治法解决问题的案例。

生活中用分治法解决问题的案例如下：

找出伪币

给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。

比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。

假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。

另外一种方法就是利用分而治之方法。假如把16个硬币的例子看成一个大的问题。

第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把16个硬币的问题分成两个8硬币的问题来解决。

第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。

最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。

假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。

这样16硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。

称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。

由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。

(6)分治算法例题扩展阅读：

解题步骤

分治法解题的一般步骤：

（1）分解，将要解决的问题划分成若干规模较小的同类问题；

（2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

Ⅶ 分治法 练习题 divide and conquer

可以用经典的二分法：每次找中间位置。具体地说，
初始有端点1和n，故取中点p=[(n+1)/2]，这里中括号表示取整。考察连续的三个点p-1,p,p+1处的数的大小关系。由于已知序列是单峰的（为容易说明算法思想，假设没有相等的数），故A_{p-1}, A_{p}, A_{p+1}只有三种可能：要么递增，要么递减，要么先增后减。
如果先增后减，则此p即为所求。
如果递增，则说明欲求的峰值点比这个p点大，那么考虑端点p和n，重复上面的算法。
如果递减，则说明欲求的峰值点比这个p点小，那么考虑端点1和p，重复上面的算法。
这就建立了递归算法。

复杂度是O(log_2{n}). 因为每次考虑都把欲求的峰值点的可能位置从全部可能中缩小一半（加减1，在大O符号中可忽略不及）。具体地说，当序列长度是2^m的时候，第一次取中点，排除掉一半可能，剩下2^{m-1}个可能的峰值点；第二次取中点，排除掉一半可能，剩下2^{m-2}个可能的峰值点；一次类推。最终经过至多多m+1次就能找到峰值点。反过来看，设n=2^m，那么m=log_2{n}。用大O符号，数值+1可以忽略。当序列长度不是2^m的时候，一定有一个m使得序列长度介于2^{m}和2^{m+1}，按照上述证明，复杂度介于O(log_2{n})和O(log_2{n}-1)，这俩O符号的意思的一样的，所以复杂度是O(log_2{n})。

用归纳法证明的思想本质是一样的，不过严格的陈述需要自己设定很多额外的约定才能说清楚，比如n的值从介于2^{m-1}和2^m变化到介于2^m和2^{m+1}的时候用归纳，需要一些详尽的精准的陈述，不推荐。