算法设计 第4章 分治法文档格式.docx
《算法设计 第4章 分治法文档格式.docx》由会员分享，可在线阅读，更多相关《算法设计 第4章 分治法文档格式.docx（19页珍藏版）》请在冰点文库上搜索。
j<
j++）
cout<
a[j]<
"
endl;
m=Max（a,0,n-1）;
a[m]<
return0;
}
intMax（inta[],intlow,inthigh）
intmid,max,max1,max2;
if（low==high）returnlow;
else
{
mid=（low+high）/2;
max1=Max（a,low,mid）;
max2=Max（a,mid+1,high）;
max=a[max1]>
a[max2]?
max1:
max2;
returnmax;
}
设计分治算法，实现将数组A[n]中所有的元素循环左移k个位置，要求时间
复杂度为，空间复杂度为，例如，对abcdefgh循环左移3位得到defghabc.
将数组元素左移n块，则将数组分成几块，然后将每一块进行编号，
然后进行移动，序号相同的，前一段序号的那个数移到后一段序号的那个数即可。
1.实现相邻两端相同编号的数进行移动
2.k个函数调用实现每个序号的书都进行移动
3.输出数组
*/
voidConverse（char*A,intn,intk）;
voidReverse（char*A,intfrom,intto）;
{
charA[100];
intk;
请输入数组：
A;
请输入左移的位数k：
k;
Converse（A,strlen（A）,k）;
voidReverse（char*A,intfrom,intto）
for（inti=0;
i<
（to-from+1）/2;
i++）
{
chartemp=A[from+i];
A[from+i]=A[to-i];
A[to-i]=temp;
voidConverse（char*A,intn,intk）
Reverse（A,0,k-1）;
Reverse（A,k,n-1）;
Reverse（A,0,n-1）;
移动后的数组为：
A[i];
在有序序列（r1,r2,r3·
·
rn）中，存在序号i（1<
=i<
=n）,
使得ri=i;
请设计一个分治算法找到这个元素，要求算法在最坏的情况下的
时间性能为O（log2n）;
这道题主要采用的是折半查找的思路，同时也体现出了分治法；
把一个大的问题折半折半再折半·
的处理，最终就可以找到目标。
1.输入数组
2.定义折半查找的函数；
2.1.折半找到中间的数比较r[i]和i的大小；
2.2.如果r[i]>
i则我们就直接在数组的左边找；
否则就在右边找。
2.3.找到目标输出；
#include<
voidf（inta[],intn）;
intmain（）
inta[1001];
inti,n;
请输入有序数组的个数：
for（i=0;
cin>
a[i];
f（a,n）;
voidf（inta[],intn）
intleft=0,right=n-1,mid;
while（left<
right）
mid=（left+right）/2;
if（a[mid]=mid）
{
cout<
这个元素是：
a[mid]<
break;
}
elseif（a[mid]>
mid）
right=mid;
else
left=mid;
在一个序列中出现次数最多的元素称为众数，
请设计算法寻找众数并分析算法的时间复杂性；
题目要求是要用分治法，那我们就只有在排序上用分治法，
将数组用快速排序，之后再遍历一次数组我们就可以找到众数。
此时算法的时间复杂性为nlog（n）;
1.输入数组；
2.对数组进行快速排序
3.for循环遍历数组，用if判断找出众数
4.输出众数。
intPartition（intr[],intfirst,intend）;
voidQuickSort（intr[],intfirst,intend）;
intr[10001];
intn,cont=0,max=0,temp;
请输入数组的元素：
j++）
r[j];
QuickSort（r,0,n-1）;
intk=i+1;
while（r[i]==r[k]&
&
i<
n）
cont++;
i++;
if（cont>
max）
{
temp=i-1;
max=cont;
cont=0;
i=i-1;
众数是：
r[temp]<
重复的次数是：
max<
//for（inti=0;
//cout<
r[i]<
//cout<
intPartition（intr[],intfirst,intend）//划分
inti=first,j=end;
//初始化待划分区间
while（i<
j）
j&
r[i]<
=r[j]）j--;
//右侧扫描
if（i<
j）{
inttemp=r[i];
r[i]=r[j];
r[j]=temp;
//将较小记录交换到前面
i++;
=r[j]）i++;
//左侧扫描
j）{
//将较大记录交换到后面
j--;
returni;
//返回轴值记录的位置
voidQuickSort（intr[],intfirst,intend）//快速排序
intpivot;
if（first<
end）{
pivot=Partition（r,first,end）;
//划分，pivot是轴值在序列中的位置
QuickSort（r,first,pivot-1）;
//求解子问题1，对左侧子序列进行快速排序
QuickSort（r,pivot+1,end）;
//求解子问题2，对右侧子序列进行快速排序
}
设M是一个n×
n的矩阵，其中每行的元素从左到右单增有序，
每列的元素从上到下单增有序。
给出一个分治算法计算出给定元素x
在M中的位置或者表明x不在M中。
分析算法的时间复杂性。
在n×
n的矩阵中其中每行的元素从左到右单增有序，每列的元素从上到下单增有序。
那么我们就可以找到矩阵的中心元素对其进行比较，比较后要找的元素可能有两块区域，
再对这两块区域再进行递归调用就可以找到我们想要的元素。
输出元素是否存在及其位置。
1，调用MatrixBinary函数
2.1每次都找到中心元素
2.2用要查找的元素与之进行比较
2.3如果比中心元素大就在其右侧或左下角反之在其左侧或者右上角
2.4继续递归调用MatrixBinary
2.5找到了返回1，否则返回0；
3.输出。
intM[5][5]=
{1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25}
};
intx=19;
intMatrixBinary（intM[5][5],intrb,intre,intcb,intce）
intrm=（rb+re）/2;
intcm=（cb+ce）/2;
if（rb>
re||cb>
ce）
if（x==M[rm][cm]）
x<
所在的位置：
M["
rm<
]["
cm<
]"
return1;
elseif（rb==re&
cb==ce）
if（x>
M[rm][cm]）
returnMatrixBinary（M,rb,re,cm+1,ce）||MatrixBinary（M,rm+1,re,cb,cm）;
else
returnMatrixBinary（M,rb,rm-1,cb,ce）||MatrixBinary（M,rm,re,cb,cm-1）;
}
intmain（）
inta=MatrixBinary（M,0,4,0,4）;
if（a==1）
要查找的"
存在"
不存在"
将数组用快速排序，之后再遍历一次数组我们就可以找到s1,s2。
3.for循环遍历数组，找到s1,s2
4.输出两个子集元素之和的最大差。
intn,s1=0,s2=0,c;
intk=n/2;
k;
s1=s1+r[i];
for（intq=k;
q<
q++）
s2=s2+r[q];
c=s2-s1;
两个子集元素之和的最大差是：
c<
循环赛日程安排问题：
设有n=2^k个运动员要进行网球循环赛。
现要设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能参赛一次；
先用2个选手模拟，再用4个选手模拟找到其中相似之处：
日程表划分为四小块，左下小块可以用左上小块的每个数相加同一个数；
右上角的数和左下角的数是一样的；
右下角的数和左上角的数是一样的。
我们找到它们的位置关系就可以把日程表表示出来；
注：
第一列表示选手的人数，第二列表示第一天，依次类推。
在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手
K=2时：
1234
2143
3412
4321
k=3时：
12345678
21436587
34127856
43218765
56781234
65872143
78563412
87654321
1.输入K;
2.创建动态二维数组
3.日程函数：
3.1填左下角
3.2填右上角
3.3填右下角
4.输出日程表；
voidTable（intk,int**a）;
intn=1;
for（intj=1;
=k;
j++）//参加比赛选手的人数
n=n*2;
int**a=newint*[n+1];
//根据n动态分配二维数组a
=n;
a[i]=newint[n+1];
Table（k,a）;
//分配日程函数
for（intq=1;
q<
=n;
q++）
for（intl=1;
l<
l++）
a[q][l]<
for（intr=0;
r<
r++）//释放空间
delete[]a[r];
delete[]a;
voidTable（intk,int**a）
inti,j,t,temp;
intn=2;
a[1][1]=1;
a[1][2]=2;
//最开始只有两个人比赛的安排
a[2][1]=2;
a[2][2]=1;
for（t=1;
t<
t++）
temp=n;
n=n*2;
for（i=temp+1;
i++）//填左下角的元素
for（j=1;
=temp;
a[i][j]=a[i-temp][j]+temp;
for（i=1;
i++）//填右上角的元素
for（j=temp+1;
a[i][j]=a[i+temp][（j+temp）%n];
for（i=temp+1;
i++）//填右下角的元素
for（j=temp+1;
a[i][j]=a[i-temp][j-temp];
升级会员 