3+三+分治算法+习题参考答案
第三章 分治算法习题
1、编写程序实现归并算法和快速排序算法
参见后附程序
2、用长为100、200、300、400、500、600、700、800、900、1000的10个数组的排列来统计这两种算法的时间复杂性。
有些同学用的微秒us
用s 可能需要把上面的长度改为10000，……，100000，都可以
大部分的结果是快速排序算法要比归并算法快一些。
3、讨论归并排序算法的空间复杂性。
解析：归并排序由分解与合并两部分组成，如果用()S n 表示归并排序所用的空间。 则由
MergeSort(low, mid) //将第一子数组排序 )2/(n S
MergeSort(mid+1, high) //将第二子数组排序 )2/(n S
Merge(low, mid, high) //归并两个已经排序的子数组 n n O 2)(≈
则
)()2/()(n O n S n S +≤
递归推导得
)
()
2()1()()2
()2()2()1()()2
()4()()2()(1n O n O S n O n O n O n O S n O n O n S n O n S n S k k =+≤+++++≤++≤+≤- 又由存储数组长度为n ，则有 )()(n O n S ≥
因此，空间复杂度为)(n O 。
4、说明算法PartSelect 的时间复杂性为()O n
证明：提示：假定数组中的元素各不相同，且第一次划分时划分元素v 是第i 小元素的概率为n /1。因为Partition 中的case 语句所要求的时间都是)(n O ，所以，存在常数c ，使得算法PartSelect 的平均时间复杂度)(n C k A 可以表示为
))1()((1)(1∑∑<≤≤<--+-+≤k i n
i k k A i k A k A i C i n C n cn n C
令)),((max )(n C n R k
A k =取),1(R C ≥试证明cn n R 4)(≤。 证明：令)(n C k
A 表示n 个元素的数组A 中寻找第k 小元素的平均时间复杂度，因1)-n 0,Partition(的时间复杂度是)(n O ，故存在常数c ，使得算法PartSelect 的平均时间复杂度)(n C k A 可以表示为))1()((1)(1∑∑<≤≤<--+-+
≤k i n i k k A i k A k A i C i n C n cn n C 令)),((max )(n C n R k A k
=且不妨设等式在n k k =时成立，则)(n R 满足 ))1()((1)(1∑∑<≤≤<--+-+≤k i n
i k k A i k A i C i n C n cn n R 以下用第二数学归纳法证明cn n R 4)(≤。取),1(R C ≥
当1=n 时，取c ≥C/4,则c R 4)1(≤
当2=n 时，c c c R c R 442
12)1(212)2(=+≤+≤成立。 对于一般的n ，设对所有小于n 的自然数cn n R 4)(≤成立，则
cn
n c cn n
n n c cn n n n n c cn n n k n k n c cn n k k n k n k n c cn n k k n n n
c cn n R k R k R k n R n R n
cn n R n n n n n n n n n n n 4)
33(143)2
3)21((4)2
3)1((4)2
)1)((2)2)(1((4))1(())1()1((4))1()1()(())1()1((1)(22222≤-+≤+-+≤--+--≤--+--≤-+-+--+≤-++++-++-+≤-++++++-++-+≤ 得证。
证明：（1）当7r =时，假设数组A 中元素互不相同。由于每个具有7个元素的数组的中间值u 是该数组中的第4小元素，因此数组中至少有4个元素不大于u ，/7n ????个中间值中至少有/7/2n ????????个不大于这些中间值的中间值v 。因此，在数组A 中至少有
4/7/22/7n n *??≥???
???????
个元素不大于v 。换句话说，A 中至多有
5122/72(/7/7),(06)77
n n n n e n e -=--≤+≤≤???? 个元素大于v 。同理，至多有51277
n +个元素小于v 。这样，以v 为划分元素，产生的新数组至多有51277n +个元素。当24n ≥时，512117714
n n +≤。 另一方面，在整个执行过程中，递归调用Select 函数一次，涉及规模为/7n ，而下一次循
环Loop 涉及的数组规模为1114
n 。程序中其他执行步的时间复杂度至多是n 的倍数cn ，用()T n 表示算法在数组长度为n 的时间复杂度，则当24n ≥时，有递归关系
111()()()714
T n T n T n cn ≤++ 用数学归纳法可以证明，()14T n cn ≤。所以时间复杂度是()O n 。
（2）当3r =时，使用上述方法进行分析，可知在进行划分后数组A 中有至多n n 653232≤+个元素。而递归关系为cn n T n T n T ++≤)6
5()31()(。若通过归纳法证明出有()T n kcn ≤的形式，用数学归纳法可以证明，cn n T 28)(≤。所以时间复杂度是()O n 。
归并排序的 C++语言描述
#include
template
template
template
void main()
{
int const n(5);
int a[n];
cout<<"Input "< for(int i=0;i cin>>a[i]; //for(int j=0;j //b[j]=a[j]; MergeSort(a,0,n-1); cout<<"The sorted array is"< for(i=0;i cout< cout< } template void MergeSort(T a[],int left,int right) // { if(left { int i=(left+right)/2; T *b=new T[]; MergeSort(a,left,i); MergeSort(a,i+1,right); Merge(a,b,left,i,right); Copy(a,b,left,right); } template void Merge(T c[],T d[],int l,int m,int r) { int i=l; int j=m+1; int k=l; while((i<=m)&&(j<=r)) { if(c[i]<=c[j])d[k++]=c[i++]; else d[k++]=c[j++]; } if(i>m) { for(int q=j;q<=r;q++) d[k++]=c[q]; } else for(int q=i;q<=m;q++) d[k++]=c[q]; } template void Copy(T a[],T b[], int l,int r) { for(int i=l;i<=r;i++) a[i]=b[i]; } 快速排序的C++语言描述 #include template void main() { int const n(5); int a[n]; cout<<"Input "< for(int i=0;i cin>>a[i]; QuickSort(a,0,n-1); cout<<"The sorted array is"< for(i=0;i cout< cout< } template void QuickSort(T a[],int p,int r) { if(p { int q=Partition(a,p,r); QuickSort(a,p,q-1); QuickSort(a,q+1,r); } } template int Partition(T a[],int p,int r) { int i=p,j=r+1; T x=a[p]; while(true) { while(a[++i] while(a[--j]>x); if(i>=j)break; Swap(a[i],a[j]); } a[p]=a[j]; a[j]=x; return j; } template inline void Swap(T &s,T &t) { T temp=s; s=t; t=temp; } 问题场景：在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。 问题描述：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。 1、一维最接近点对问题 算法思路： 这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n^2)的计算时间。在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法。采用分治法思想，考虑将所给的n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S 的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n^2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n^2)。整个算法所需计算时间T(n)应满足:T(n)=2T(n/2)+O(n^2)。它的解为T(n)=O(n^2)，即与合并步骤的耗时同阶，这不比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。 设S中的n个点为x轴上的n个实数x1,x2,..,xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1,x2,..,xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，在排序算法已经证明，时间复杂度为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S|x≤m}；S2={x∈S|x>m}。这样一来，对于所有p∈S1和q∈S2有p 算法练习题-分章节-带答案 算法练习题---算法概述 一、选择题 1、下面关于算法的描述，正确的是（） A、一个算法只能有一个输入 B、算法只能用框图来表示 C、一个算法的执行步骤可以是无限的 D、一个完整的算法，不管用什么方法来表示，都至少有一个输出结果 2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（） A、设计算法，编写程序，提出问题，运行程序，得到答案 B、分析问题，编写程序，设计算法，运行程序，得到答案 C、分析问题，设计算法，编写程序，运行程序，得到答案 D、设计算法，提出问题，编写程序，运行程序，得到答案 3、下面说法正确的是（） A、算法+数据结构=程序 B、算法就是程序 C、数据结构就是程序 D、算法包括数据结构 4、衡量一个算法好坏的标准是（）。 A、运行速度快 B、占用空间少 C、时间复杂度低 D、代码短 5、解决一个问题通常有多种方法。若说一个算法“有效”是指( )。 A、这个算法能在一定的时间和空间资源限制内将问题解决 B、这个算法能在人的反应时间内将问题解决 C、这个算法比其他已知算法都更快地将问题解决 D、A和C 6、算法分析中，记号O表示（），记号Ω表示（）。 A.渐进下界 B.渐进上界 C.非紧上界 D.非紧下界 7、以下关于渐进记号的性质是正确的有：（） A.f(n)(g(n)),g(n)(h(n))f(n)(h(n)) =Θ=Θ?=Θ B.f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n)) ==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D.f(n)O(g(n))g(n)O(f(n)) =?= 目录 1031 输油管道问题 (2) 解题思路 (2) 程序代码 (2) 1032 邮局选址 (5) 解题思路 (5) 程序源代码 (5) 1034 集合划分2 (7) 解题思路： (7) 程序源代码： (7) 1033 集合划分 (9) 解题思路 (9) 程序源代码 (9) 1031 输油管道问题 解题思路 本题目可以分为两个步骤： 1、找出主管道的位置； 2、根据主管道的位置，计算各个油井到主管道的长度之和。 根据题意，设主管道贯穿东西，与y 轴平行。而各个子油井则分布在主输油管道的上下两侧。如下图： 由上图，其实只需要确定主管道的y 坐标，而与各个子油井的x 坐标无关！根据猜测，易知：主管道的y 坐标就是所有子油井y 坐标的中位数。（可以用平面几何知识证明，略） 求中位数的方法可以用排序后取a[(left+right)/2]，当然更推荐用书上的线性时间选择算法解决。记求得的主管道为m y ，最后要输出的结果只需要计算：1||n i m i y y =-∑，输出即可。 另外要提醒的是本题多Case 。 程序代码 #include //本函数求arr[p:q]的一个划分i，使arr[p:i-1]都小于arr[i]，arr[i+1,q]都大于arr[i] int partition(int *arr,int p,int q) { int index = p-1,start = p,base = arr[q]; for(;start 《算法设计与分析》实验报告 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 分治法 【摘要】：分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。本文主要叙述了分治法的设计思想及与之有关的递归思想，了解使用分治法解决问题的过程。 【关键词】：分治法分解算法递归二分搜索 Partition Method （Junna Wei） 【abstract 】: the partition method can explain to popular: decomposition, put a slice of territory is decomposed into several pieces of small, then pieces of land occupation of conquest, the decomposition can be different political factions or something, then let them each other alienation. This paper mainly describes the design idea of the partition method and recursive thinking, related to understand the process of solving the problem using the partition method. 【key words 】: partition method decomposition algorithm recursive Binary search 1.引论 目录 1031 输油管道问题 (1) 解题思路 (1) 程序代码 (1) 1032 邮局选址 (4) 解题思路 (4) 程序源代码 (4) 1034 集合划分2 (6) 解题思路: (6) 程序源代码: (6) 1033 集合划分 (8) 解题思路 (8) 程序源代码 (8) 1031 输油管道问题 解题思路 本题目可以分为两个步骤: 1、找出主管道得位置; 2、根据主管道得位置,计算各个油井到主管道得长度之与。 根据题意,设主管道贯穿东西,与y 轴平行。而各个子油井则分布在主输油管道得上下两侧。如下图: 由上图,其实只需要确定主管道得y 坐标,而与各个子油井得x 坐标无关！根据猜测,易知:主管道得y 坐标就就是所有子油井y 坐标得中位数。(可以用平面几何知识证明,略) 求中位数得方法可以用排序后取a[(left+right)/2],当然更推荐用书上得线性时间选择算法解决。记求得得主管道为,最后要输出得结果只需要计算:,输出即可。 另外要提醒得就是本题多Case。 程序代码 #include #include 算法分析与设计实验报告第四次附加实验 while (a[--j]>x); if (i>=j) { break; } Swap(a[i],a[j]); } a[p] = a[j]; //将基准元素放在合适的位置 a[j] = x; return j; } //通过RandomizedPartition函数来产生随机的划分 template vclass Type> int RandomizedPartition(Type a[], int p, int r) { int i = Random(p,r); Swap(a[i],a[p]); return Partition(a,p,r); } 较小个数排序序列的结果: 测试结果 较大个数排序序列的结果: 实验心得 快速排序在之前的数据结构中也是学过的，在几大排序算法中，快速排序和归并排序尤其是 重中之重，之前的快速排序都是给定确定的轴值，所以存在一些极端的情况使得时间复杂度 很高，排序的效果并不是很好，现在学习的一种利用随机化的快速排序算法，通过随机的确 定轴值，从而可以期望划分是较对称 的，减少了出现极端情况的次数，使得排序的效率挺高了很多， 化算法想呼应，而且关键的是对于随机生成函数，通过这一次的 学习终于弄明白是怎么回事了，不错。 与后面的随机实 验和自己的 实验得分助教签名 附录： 完整代码(分治法) //随机后标记元素后的快速排序 #i nclude 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 华南农业大学期末考试试卷（A卷） 2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log2n C．2n2D．3nlog3n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨 牌的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法 对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6. 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A ．（4.5，0） B ．（4.5，4.5） C ．（5，5） D ．（5，0） 7. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下 说法不正确？ A ．让水桶大的人先打水，可以使得每个人排队时间之和最小 B ．让水桶小的人先打水，可以使得每个人排队时间之和最小 C ．让水桶小的人先打水，在某个确定的时间t 内，可以让尽可能多的人打上水 D ．若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分 别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A ．问题规模相同，问题性质相同 B ．问题规模相同，问题性质不同 C ．问题规模不同，问题性质相同 D ．问题规模不同，问题性质不同 9. 对布线问题，以下 是不正确描述。 A ．布线问题的解空间是一个图 B ．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定 C ．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的 D ．采用先入先出的队列作为活结点表，以终点b 为扩展结点或活结点队列为空作为算法结束条件 10. 对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。 A ．n! B ．2n C ．2 n+1 -1 D ． ∑=n i i n 1 !/! 答案：DACAD CACCB 分治算法——排列问题 2011-08-05 15:10:52| 分类：分治算法|字jm号大中小订阅 设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。 分析：设R={r 1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。,集合X中元素的全排列记为perm(X)。其中(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn )perm(Rn)构成。 思路是递归产生前缀是list[0:k-1]，且后缀是list[k:m]的全排列的所有排列。……算法将list[k:m]中每一个元素分别与list[k]中元素交换。然后递归地计算list[k+1:m]的全排列，并将计算结果作为list[0:k]的后缀。 1）切记Perm(list,k,m)是产生从k开始到m结束的所有全排列，这个很重要。要产生所有全排列，只要调用这个函数就行了，至于这个函数怎么实现，先不要去管。（一开始理解递归函数的时候，由于过多的在意函数的流程，而忘了函数本身的功能。） 2）将有限个元素的全排列分成前缀和后缀两部分。用一个元素作前缀，剩下元素作后缀。显然作前缀的一个元素可以是所有元素的任意一个，对前缀位置的元素作一轮交换即可。先确定了一个前缀，然后对后缀元素们求全排列（不要关心怎么求全排列。对后缀元素求全排列，就是原问题的一个子问题，分治法的一个特征。）这样就得到了一个确定前缀的所有全排列。 贴上自己写的代码： #include 安徽文达信息工程学院学生实验报告（计算机语言编程类适用） 一、【实验目的】 1.熟悉分治算法思想。 2.验证具体问题算法的设计及程序实现。 二、【实验内容】 1、有N枚硬币，其中一枚是假币，假币和真币重量不同，可以用一个没有刻度的天平测，求出假币是哪一枚，现要求采用分治法解决，请写出算法设计思路。(不需要编程) 答：（1）N为偶数时，将N枚硬币分成N/2，N/2的两份将第一份分成N/4，N/4的两份，分别置于天平两端，如果天平倾斜，则假币在第一份N/2中，反之水平，则假币在第二份N/2中; （2）N为奇数时，将N枚硬币分成（N+1）/2，（N-1）/2的两份,将第一份分成（N+1）/4，(N+1)/4的两份，分别置于天平两端，如果天平倾斜，则假币在第一份(N+1)/2中，反之水平，则假币在第二份(N-1)/2中， （3）将含假币的的币数赋值给N，N为偶数执行步骤（1），N为奇数执行步骤（2），如此执行直至找出含假币的2或3枚硬币，如果是2枚硬币则找1枚硬币构成3枚，3枚则直接两两置于天平两端，找到使天平水平的两枚硬币，则假币是剩下的硬币。 2、格雷码问题： 对于给定的正整数n，格雷码为满足如下条件的一个编码序列： (1) 序列由2n个编码组成，每个编码都是长度为n的二进制位串。 (2) 序列中无相同的编码。 (3) 序列中位置相邻的两个编码恰有一位不同。 例如：n=1时的格雷码为：{0, 1}。 n=2时的格雷码为：{00, 01, 11, 10}。 n=3时的格雷码为：{000, 001, 011, 010,110,111,101,100}。 gray码问题求解思想： 将一个规模n位gray码序列表示为G(n), G(n)以相反顺序排列的序列表示为G’(n)。则gray 码的构造规则即子问题的划分规则为：G(n+1)= 0G(n) 1G’(n) 或G(n+1)= G(n) 0G’(n)1。 请尝试编写程序，完成格雷码问题的处理。 二、简答题： 1.备忘录方法和动态规划算法相比有何异同简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。 7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面 8.贪心算法求解的问题主要具有哪些性质简述之。 9.分治法的基本思想是什么合并排序的基本思想是什么请分别简述之。 10.简述分析贪心算法与动态规划算法的异同。 三、算法编写及算法应用分析题： 1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。 ①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。 ②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。 ③给出上述算法的递归算法。 ④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。 3.已知1()*() i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序（要求给出计算步骤）。 4.根据分枝限界算法基本过程,求解0-1背包问题。 已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。 6.试用动态规划算法实现下列问题：设A 和B 是两个字符串。我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括： ①删除一个字符。 ②插入一个字符。 ③将一个字符改为另一个字符。 请写出该算法。 7.对于下图使用Dijkstra 算法求由顶点a 到顶点h 的最短路径。 8.试写出用分治法对数组A[n]实现快速排序的算法。 9.有n 个活动争用一个活动室。已知活动i 占用的时间区域为[s i ，f i ]，活动i,j 相容的条件是：sj ≥f i ，问题的解表示为(x i | x i =1，2…，n,)，x i 表示顺序为i 的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。 10.设x 1、x 2、x 3是一个三角形的三条边，而且x 1+x 2+x 3=14。请问有多少种不同的三角形给出解答过程。 11.设数组A 有n 个元素，需要找出其中的最大最小值。 ①请给出一个解决方法，并分析其复杂性。 ②把n 个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和 分治算法举例 文稿归稿存档编号：[KKUY-KKIO69-OTM243-OLUI129-G00I-FDQS58- 1设X[0：n-1]和Y[0：n-1]为两个数组，每个数组中含有n个已排序好的数。试设计一个O(logn)时间的分治算法，找出X和Y的2n个数的中位数，并证明算法的时间复杂性为O(l o g n)。注：个数为奇数，则处于最中间位置的数； 个数为偶数，则中间两个数据的平均数。 解： 利用二分查找思想： 对于两个等长的数组， 如果数组长度为奇数，令mid为数组的最中间元素的位置，则有 X[mid]，Y[mid]分别为两个数组的中位数，则存在以下情况： （1）如果X[mid] 为y=(Y[mid]+Y[mid+1])/2.0(这里考虑到中位数不一定为整数)。则存在以下情况： （1）如果x 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。 A、最小堆 B、最大堆 C、栈 D、数组 1．最大子段和问题：给定整数序列 n a a a ,,,21 ，求该序列形如 j i k k a 的子段和 的最大值： j i k k n j i a 1max ,0max 1) 已知一个简单算法如下： int Maxsum(int n,int a,int& best i,int& bestj){ int sum = 0; for (int i=1;i<=n;i++){ int suma = 0; for (int j=i;j<=n;j++){ suma + = a[j]; if (suma > sum){ sum = suma; besti = i; bestj = j; } } } return sum; }试分析该算法的时间复杂性。 2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。 3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。 （提示：令1()max ,1,2,,j k i j n k i b j a j n L ） 解：1）分析按照第一章，列出步数统计表，计算可得)(2 n O 2）分治算法：将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种可能： ①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； ②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同； ③a[1:n]的最大子段和为两部分的字段和组成，即 j n j i l n i j a a a a a 122； intMaxSubSum ( int *a, int left , int right){ int sum =0; if( left==right) sum = a[left] > 0? a[ left]:0 ; else {int center = ( left + right) /2; int leftsum =MaxSubSum ( a, left , center) ; int rightsum =MaxSubSum ( a, center +1, right) ; int s_1 =0; int left_sum =0; for ( int i = center ; i >= left; i--){ left_sum + = a [ i ]; if( left_sum > s1) s1 = left_sum; } int s2 =0; int right_sum =0; for ( int i = center +1; i <= right ; i++){ right_sum + = a[ i]; if( right_sum > s2) s2 = right_sum; } sum = s1 + s2; if ( sum < leftsum) sum = leftsum; if ( sum < rightsum) sum = rightsum; } return sum; } int MaxSum2 (int n){ int a； returnMaxSubSum ( a, 1, n) ; } 该算法所需的计算时间T(n)满足典型的分治算法递归分式T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn) 一、选择题 1、衡量一个算法好坏的标准是（ C ）。 （A）运行速度快（B）占用空间少（C）时间复杂度低（D）代码短 2、记号O的定义正确的是（A）。 （A）O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }；（B）O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤ f(n) }；（C）O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0 有：0 ≤f(n) 华南农业大学期末考试试卷（A卷）2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120 分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log 2n C．2n2 D．3nlog 3 n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog 2 n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨 牌的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算 法对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。 A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6.有9个村庄，其坐标位置如下表所示： 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在才能使到邮局到这9个村庄的总距离和最短。 A．（4.5，0）B．（4.5，4.5）C．（5，5）D．（5，0） 7.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下说法不正确？ A．让水桶大的人先打水，可以使得每个人排队时间之和最小 B．让水桶小的人先打水，可以使得每个人排队时间之和最小 C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样 8.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题， 分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。0007算法笔记——【分治法】最接近点对问题
算法练习题-分章节-带答案
分治算法例题
算法分析实验报告--分治策略
分治法
分治算法例题
分治算法实验(用分治法实现快速排序算法)
算法分析实验报告--分治策略
2009.1算法设计与分析课程期末试卷-A卷(自测 )
分治算法—排列问题
分治算法设计
算法分析与设计部分含计算的复习题及参考答案
分治算法举例
计算机算法设计与分析期末考试复习题
算法分析习题详细答案五
算法分析复习题(含答案)
29.1算法设计与分析课程期末试卷-a卷(自测 ) (2)(1)
- 计算机算法设计和分析》习题及答案解析
- 算法合集之《分治算法在树的路径问题中的应用》
- 算法设计和分析复习试题目及答案解析
- 0007算法笔记——【分治法】最接近点对问题
- 《算法设计与分析》考试题目与答案
- 算法分析习题详细答案五
- 分治法及其应用示例
- 分治算法讲解
- 算法设计与分析习题答案1-6章
- 分治算法在树的路径问题中的应用
- 分治算法试题
- 算法分析与设计部分含计算的复习题及参考答案
- 算法设计与分析习题解答1-6章
- 算法练习题-分章节-带答案
- 国家集训队2009论文集分治算法在树的路径问
- 算法分析与设计部分含计算的复习题及参考答案
- 用分治法解决问题
- 漆子超《分治算法在树的路径问题中的应用》
- 分治习题汇总
- 分治算法例题