算法设计与分析习题答案1-6章Word下载.doc
《算法设计与分析习题答案1-6章Word下载.doc》由会员分享，可在线阅读，更多相关《算法设计与分析习题答案1-6章Word下载.doc（26页珍藏版）》请在冰点文库上搜索。
high）
while（low<
high&
&
b[high]>
=prvotkey）
--high;
b[low]=b[high];
b[low]<
=prvotkey）
++low;
b[high]=b[low];
}
b[low]=b[0];
returnlow;
voidqsort（intl[],intlow,inthigh）
intprvotloc;
if（low<
prvotloc=partions（l,low,high）;
//将第一次排序的结果作为枢轴
qsort（l,low,prvotloc-1）;
//递归调用排序由low到prvotloc-1
qsort（l,prvotloc+1,high）;
//递归调用排序由prvotloc+1到high
voidquicksort（intl[],intn）
qsort（l,1,n）;
//第一个作为枢轴，从第一个排到第n个
intmain（）
inta[11]={0,2,32,43,23,45,36,57,14,27,39};
intvalue=0;
//将最小差的值赋值给value
for（intb=1;
b<
11;
b++）
cout<
<
a[b]<
'
'
;
endl;
quicksort（a,11）;
for（inti=0;
i!
=9;
++i）
if（（a[i+1]-a[i]）<
=（a[i+2]-a[i+1]））
value=a[i+1]-a[i];
else
value=a[i+2]-a[i+1];
value<
return0;
4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。
#include<
intmain（）
{
inta[]={1,2,3,6,4,9,0};
intmid_value=0;
//将“既不是最大也不是最小的元素”的值赋值给它
for（inti=0;
=4;
{
if（a[i+1]>
a[i]&
a[i+1]<
a[i+2]）
{
mid_value=a[i+1];
cout<
mid_value<
break;
}
elseif（a[i+1]<
a[i+1]>
{
cout<
}//for
5.编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。
doublevalue=0;
for（intn=1;
n<
=10000;
++n）
{
value=value*10+1;
if（value%2013==0）
"
n至少为:
break;
}
}//for
return0;
6.计算π值的问题能精确求解吗？
编写程序，求解满足给定精度要求的π值
intmain（）
doublea,b;
doublearctan（doublex）;
//声明
a=16.0*arctan（1/5.0）;
b=4.0*arctan（1/239）;
cout<
"
PI="
<
a-b<
endl;
return0；
doublearctan（doublex）
inti=0;
doubler=0,e,f,sqr;
//定义四个变量初
sqr=x*x;
e=x;
while（e/i>
1e-15）//定义精度范围
f=e/i;
//f是每次r需要叠加的方程
r=（i%4==1）?
r+f:
r-f;
e=e*sqr;
//e每次乘于x的平方
i+=2;
//i每次加2
}//while
returnr;
7.圣经上说：
神6天创造天地万有，第7日安歇。
为什么是6天呢？
任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。
例如，6=1+2+3，因此6是完美数。
神6天创造世界，暗示着该创造是完美的。
设计算法，判断给定的自然数是否是完美数
intvalue,k=1;
cin>
>
value;
for（inti=2;
=value;
{
while（value%i==0）
{
k+=i;
//k为该自然数所有因子之和
value=value/i;
}
if（k==value）
cout<
该自然数是完美数"
else
该自然数不是完美数"
return0;
8.有4个人打算过桥，这个桥每次最多只能有两个人同时通过。
他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。
这就意味着两个人过桥后必须有一个人将手电筒带回来。
每个人走路的速度是不同的：
甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？
由于甲过桥时间最短，那么每次传递手电的工作应有甲完成
甲每次分别带着乙丙丁过桥
例如：
第一趟：
甲，乙过桥且甲回来
第二趟：
甲，丙过桥且甲回来
甲，丁过桥
一共用时19小时
9．欧几里德游戏：
开始的时候，白板上有两个不相等的正整数，两个玩家交替行动，每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新数字时，他就输了。
请问，你是选择先行动还是后行动？
为什么？
设最初两个数较大的为a,较小的为b，两个数的最大公约数为factor。
则最终能出现的数包括:
factor,factor*2,factor*3,...,factor*（a/factor）=a.一共a/factor个。
如果a/factor是奇数，就选择先行动；
否则就后行动。
习题4
1.分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关，试说明这几个参数与分治法时间复杂性之间的关系。
2.证明：
如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问题的规模时，算法的时间复杂性可达到O（n）。
O（N）=2*O（N/2）+x
O（N）+x=2*O（N/2）+2*x
a*O（N）+x=a*（2*O（N/2）+x）+x=2*a*O（N/2）+（a+1）*x
由此可知，时间复杂度可达到O（n）;
3.分治策略一定导致递归吗？
如果是，请解释原因。
如果不是，给出一个不包含递归的分治例子，并阐述这种分治和包含递归的分治的主要不同。
不一定导致递归。
如非递归的二叉树中序遍历。
这种分治方法与递归的二叉树中序遍历主要区别是：
应用了栈这个数据结构。
4.对于待排序序列（5,3,1,9），分别画出归并排序和快速排序的递归运行轨迹。
归并排序：
（5,3）（1,9）；
（3,5,1,9）；
第三趟：
（1,3,5,9）；
快速排序：
第一趟：
5（,3,1,9）；
//5为哨兵，比较9和5
第二趟：
5（1,3,,9）；
//比较1和5，将1挪到相应位置；
第三趟：
5（1,3,,9）;
//比较3和5；
第四趟：
（1,3,5,9）;
5.设计分治算法求一个数组中的最大元素，并分析时间性能。
//简单的分治问题
//将数组均衡的分为“前”，“后”两部分
//分别求出这两部分最大值，然后再比较这两个最大值
externconstintn=6;
inta[n]={0,6,1,2,3,5};
//初始化
intmid=n/2;
intnum_max1=0,num_max2=0;
for（inti=0;
i<
=n/2;
++i）//前半部分
{
if（a[i]>
num_max1）
num_max1=a[i];
for（intj=n/2+1;
j<
n;
++j）//后半部分
if（a[j]>
num_max2）
num_max2=a[j];
if（num_max1>
=num_max2）
数组中的最大元素：
num_max1<
else
cout<
num_max2<
时间复杂度：
O（n）
6.设计分治算法，实现将数组A[n]中所有元素循环左移k个位置,要求时间复杂性为O（n），空间复杂性为O
（1）。
例如，对abcdefgh循环左移3位得到defghabc。
//采用分治法
//将数组分为0-k-1和k-n-1两块
//将这两块分别左移
//然后再合并左移
voidLeftReverse（char*a,intbegin,intend）
（end-begin+1）/2;
i++）//交换移动
inttemp=a[begin+i];
a[begin+i]=a[end-i];
a[end-i]=temp;
voidConverse（char*a,intn,intk）
LeftReverse（a,0,k-1）;
LeftReverse（a,k,n-1）;
LeftReverse（a,0,n-1）;
i++）
a[i]<
chara[7]={'
a'
'
b'
c'
d'
e'
f'
g'
};
Converse（a,7,3）;
7.设计递归算法生成n个元素的所有排列对象。
intdata[100];
//在m个数中输出n个排列数（n<
=m）
voidDPpl（intnum,intm,intn,intdepth）
{
if（depth==n）
{
i++）
data[i]<
}
for（intj=0;
m;
j++）
{
if（（num&
（1<
j））==0）
{data[depth]=j+1;
DPpl（num+（1<
j）,m,n,depth+1）;
DPpl（0,5,1,0）;
DPpl（0,5,2,0）;
DPpl（0,5,3,0）;
DPpl（0,5,4,0）;
DPpl（0,5,5,0）;
8.设计分治算法求解一维空间上n个点的最近对问题。
参见4.4.1最近对问题的算法分析及算法实现
9.在有序序列（r1,r2,…,rn）中，存在序号i（1≤i≤n），使得ri=i。
请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O（log2n）。
//在有序数组中
//采用二分法查找符合条件的元素
voidFindnum（int*a,intn）
intlow=0;
inthigh=n-1;
while（low<
=high）
intmid=（low+high）/2;
if（a[mid]==mid）
cout<
这个数是：
a[mid]<
break;
elseif（a[mid]>
mid）
high=mid-1;
low=mid+1;
inta[7]={1,0,2,5,6,7,9};
Findnum（a,7）;
时间复杂度为O（log2n）。
10.在一个序列中出现次数最多的元素称为众数。
请设计算法寻找众数并分析算法的时间复杂性。
//先对序列进行快速排序
//再进行一次遍历
//输出众数的重复次数
inta[10]={1,2,3,5,3,3,3,2,5,1};
inti=0;
intcount=0;
intmax=0;
//max表示出现的次数
qsort（a,0,10）;
while（i<
10）
intj;
j=i+1;
if（a[i]=a[j]&
{
count++;
i++;
}
if（count>
max）
{
max=count;
count=0;
}//while
cout<
重复次数：
max<
return0;
时间复杂度nlog（n）
11.设M是一个n×
n的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元素都按升序排列。
设计分治算法确定一个给定的整数x是否在M中，并分析算法的时间复杂性。
12.设S是n（n为偶数）个不等的正整数的集合，要求将集合S划分为子集S1和S2，使得|S1|=|S2|=n/2，且两个子集元素之和的差达到最大。
//先用快速排序进行一趟排序
//如果s1（大的数集）的的个数大于n/2
//将（i<
=n/2-low-1）个最小的数排到后面
//如果s1（大的数集）的的个数小于n/2
//将s2（小的数集）n/2-low-1排到前面
//将排好的数组的前n/2个数赋值给s1
//将排好的数组的后n/2个数赋值给s2
constintn=8;
voidpartions（inta[],intlow,inthigh）
//进行一趟快排
intprvotkey=a[low];
a[0]=a[low];
a[high]<
a[low]=a[high];
a[low]>
a[high]=a[low];
a[low]=prvotkey;
if（low>
=n/2）
for（inti=0;
=n/2-low-1;
for（intj=0;
n-i;
++j）
if（a[j]<
a[j+1]）
{
inttemp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}//for
}
}//if
else
for（intk=n-1;
k<
++k）
if（a[k]>
a[k-1]）
inttemp1=a[k];
a[k]=a[k-1];
a[k-1]=temp1;
inta[n]={1,3,5,9,6,0,-11,-8};
partions（a,0,n-1）;
if（i<
4）
cout<
属于子集s1的：
属于子集s2的：
return0;
13.设a1,a2,…,an是集合{1,2,…,n}的一个排列，如果i<
j且ai>
aj，则序偶（ai,aj）称为该排列的一个逆序。
例如，2,3,1有两个逆序：
（3,1）和（2,1）。
设计算法统计给定排列中含有逆序的个数。
//用归并进行排序
//当一个子集的一个数大于第二个子集的一个数，为逆序，即a[i]>
a[j]
//则逆序数为end-j+1;
intcount;
voidMerge（inta[],inta1[],intbegin,intmid,intend）//合并子序列
inti=begin,j=mid+1,k=end;
while（i<
=mid&
=end）
if（a[i]<
=a[j]）
a1[k++]=a[i++];
//取a[i]和a[j]中较小者放入r1[k]
else
{
a1[k++]=a[j++];
count+=（end-j+1）;
}
=mid）
a1[k++]=a[i++];
while（j<
a1[k++]=a[j++];
voidMergeSort（inta[]
升级会员 