分治演算法例題

Ⅰ 分治演算法問題

(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}的時候用歸納，需要一些詳盡的精準的陳述，不推薦。