分治策略1

习题2-1 求下列函数的渐进表达式：3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。

解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。

解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。

在某台计算机上实现并完成该算法的时间为t秒。

现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。

对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。

第2章分治法（Divide & Conquer）（算法常用技术之首）六大算法常用技术：分治法（e.g. 快速排序、归并排序等）贪心法（即局部最优法，e.g. Kruscal最小生成树算法）周游法（e.g. DFS, BFS等）回朔法（e.g. 8皇后问题，平面点集的凸包等）动态规划法分枝定界法（e.g. 整数规划问题等）快速排序的思想：用O(n)的时间把一个规模为n的表分割为两段，前段中的数据元素均小于后段中的数据元素，然后对分割后所得的两个小一点的表采用同样的方法分别进行排序；当两个小表排好之后，整个表的排序也就完成了。

（思考问题：如何证明快速排序的平均时间复杂度为 (n㏒n)?提示：考虑“逆序”的个数。

）分治法的要领分治法是把一个规模较大的问题分解为若干个规模较小的子问题，这些子问题相互独立且与原问题同类；首先求出这些子问题的解，然后把这些子问题的解组合起来得到原问题的解。

由于子问题与原问题是同类的，故使用分治法很自然地要用到递归。

因此分治法分三步：1 将原问题分解为子问题（Divide）2 求解子问题（Conquer）3 组合子问题的解得到原问题的解（Combine）分治法举例：给定n个数据元素，要找出其中的最大元和最小元。

简单直观的方法：一个一个地找，用n-1次比较来找出最大元，再用n-2次比较来找出最小元。

比较次数（基本运算）为2n-3次。

用分治法如何求解？当n=2时，一次比较就可以找出两个数据元素的最大元和最小元。

当n>2时，可以把n个数据元素分为大致相等的两半，一半有⎣n/2⎦个数据元素，而另一半有⎡n/2⎤个数据元素。

先分别找出各自组中的最大元和最小元，然后将两个最大元进行比较，就可得n个元素的最大元；将两个最小元进行比较，就可得n个元素的最小元。

因此算法的时间复杂度为：T(n)=⎩⎨⎧>+=22)2/(221n n T n 此方程可用主定理求解：a=2, b=2, f(n)=2, a Log b n =n 1, f(n)比a Log b n 的量级低（第一种情况）；所以可得T(n)= Θ(a Log b n)= Θ(n)。

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。

问题的规模越小，越容易直接求解，解题所需的计算时间也越少。

例如，对于n个元素的排序问题，当n=1时，不需任何计算。

n=2时，只要作一次比较即可排好序。

n=3时只要作3次比较即可，…。

而当n较大时，问题就不那么容易处理了。

要想直接解决一个规模较大的问题，有时是相当困难的。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略的定义分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

这自然导致递归过程的产生。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法所能解决的问题一般具有以下几个特征：一、该问题的规模缩小到一定的程度就可以容易地解决；二、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

三、利用该问题分解出的子问题的解可以合并为该问题的解；四、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。

1、求n个元素的全排。

（30分）2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。

（30分）3、设有n=2k个运动员要进行网球循环赛。

设计一个满足要求的比赛日程表。

（40分）提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include "iostream"using namespace std;#define N 100void Perm(int* list, int k, int m){if (k == m){for (int i=0; i<m; i++)cout << list[i] << " ";cout << endl;return;}else{for (int i=m; i<k; i++){swap(list[m], list[i]);Perm(list, k, m+1);swap(list[m], list[i]);}}}void swap(int a,int b){int temp;temp=a;a=b;b=temp;}int main(){int i,n;int a[N];cout<<"请输入排列数据总个数：";cin>>n;cout<<"请输入数据：";for(i=0;i<n;i++){cin>>a[i];}cout<<"该数据的全排列："<<endl;Perm(a,n,0);return 0;}《算法设计与分析》实验报告实验二递归与分治策略应用提高学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期一、实验目的1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。

算法总结---最常⽤的五⼤算法（算法题思路）算法总结---最常⽤的五⼤算法（算法题思路）⼀、总结⼀句话总结：> 【明确所求：dijkstra是求点到点的距离，辅助数组就是源点到⽬标点的数组】> 【最简实例分析：⽐如思考dijkstra：假设先只有三个点】1、贪⼼算法是什么？> 当前看来最好的选择> 局部最优解> 可能得到整体最优解或是最优解的近似解贪⼼算法（⼜称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪⼼算法不是对所有问题都能得到整体最优解，但对范围相当⼴泛的许多问题他能产⽣整体最优解或者是整体最优解的近似解。

2、贪⼼算法实例？> 求最⼩⽣成树的Prim算法：【边集中依次选取那些权值最⼩的边】> 求最⼩⽣成树的Kruskal算法：【和求最短路径有点相似：不过这⾥是求两个集合之间的距离】：【⼀维中间数组记录到当前已经选择顶点的最短距离】：【⼆维表记录每个点到每个点的最短距离】> 计算强连通⼦图的Dijkstra算法：【和最⼩⽣成树Kruskal类似】【⼆维表记录每个点到每个点的最短距离】【明确所求：dijkstra是求点到点的距离，辅助数组就是源点到⽬标点的数组】【每次从辅助数组中选择最⼩的，⽤选出的点来更新辅助数组】【最简实例分析：⽐如思考dijkstra：假设先只有三个点】> 构造huffman树的算法：【每次都选取权值⼩的两个点合成⼆叉树】Kruskal算法简述在带权连通图中，不断地在边集合中找到最⼩的边，如果该边满⾜得到最⼩⽣成树的条件，就将其构造，直到最后得到⼀颗最⼩⽣成树。

假设 WN=(V,{E}) 是⼀个含有 n 个顶点的连通⽹，则按照克鲁斯卡尔算法构造的过程为：先构造⼀个只含 n 个顶点，⽽边集为空的⼦图，若将该⼦图中各个顶点看成是各棵树上的根结点，则它是⼀个含有 n 棵树的⼀个森林。

奥地利分治计划1945年，纳粹德国战败，第二次世界大战进入尾声。

作为德国人最亲密的“盟友”、同根同源的兄弟，奥地利遭遇了和大哥德国人同样的命运。

根据苏、美、英、法为首的同盟国达成的协议，奥地利由苏、美、英、法四国分区占领，奥地利从此进入和德国一样的“四国分治”。

但有意思的是，仅仅十年时间，美苏等国就撤离了奥地利，结束了四国分治的状态。

奥地利从此变成了一个独立国家，并和美苏没有了什么买卖。

很多人不禁感到疑惑，从四国分治到永久中立，奥地利为何能摆脱美苏的“魔掌”？这就要从二战结束时说起。

1943年，二战形势不断向同盟国一方逆转，轴心国集团的失败已经成为时间问题。

美苏等国开始讨论战后的形势和利益瓜分问题，对奥地利的处置也是其中之一。

1943年，美苏英等国家外长在莫斯科举行会议。

会上，苏联认为奥地利虽被德国占领，但奥地利依然要为二战负责。

苏联是想以此为借口，在奥地利瓜分利益，包括占领地盘和获得赔款。

但苏联的这个提议遭到了西方国家的强烈反对。

美英认为，奥地利被德国吞并了，要负责也应该德国负责。

如果按苏联的逻辑，那么被德国占领的丹麦、挪威是不是也要为二战负责？毫无疑问，苏联人是在为吞并和掠夺奥地利找借口。

由于双方存在严重分歧，因此双方始终无法达成一致。

美国人深知苏联人的想法，为此抛出了把奥地利作为德国一部分进行处置的提议。

由于奥地利和德国南部相连，如果作为德国的一部分，奥地利毫无疑问会划入美国人的势力范围。

苏联人自然不同意，因此坚决反对这个提议。

美国人见苏联人不同意，又抛出由英国人占领的提议。

但苏联人同样不接受，苏联人认为，美英是一伙的，两国穿一条裤子，英国人占领和美国人占领没区别。

最终，在激烈的争吵中，双方不欢而散，对奥地利的处置问题被暂时搁置。

不过虽然问题被搁置，但苏联人并没有就此罢手，也没有放弃吞并奥地利的野心。

习题11.图论诞生于七桥问题。

出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。

七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图1.7是这条河以及河上的两个岛和七座桥的草图。

请将该问题的数据模型抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。

输入：一个起点 输出：相同的点 1， 一次步行2， 经过七座桥，且每次只经历过一次 3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。

另一类是只有二个奇点的图形。

2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。

请用伪代码描述这个版本的欧几里德算法 1.r=m-n2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。

要求分别给出伪代码和C ++描述。

//采用分治法//对数组先进行快速排序 //在依次比较相邻的差 #include <iostream> using namespace std;int partions(int b[],int low,int high) {图1.7 七桥问题int prvotkey=b[low];b[0]=b[low];while (low<high){while (low<high&&b[high]>=prvotkey)--high;b[low]=b[high];while (low<high&&b[low]<=prvotkey)++low;b[high]=b[low];}b[low]=b[0];return low;}void qsort(int l[],int low,int high){int prvotloc;if(low<high){prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1qsort(l,prvotloc+1,high); //递归调用排序由 prvotloc+1到 high}}void quicksort(int l[],int n){qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个}int main(){int a[11]={0,2,32,43,23,45,36,57,14,27,39};int value=0;//将最小差的值赋值给valuefor (int b=1;b<11;b++)cout<<a[b]<<' ';cout<<endl;quicksort(a,11);for(int i=0;i!=9;++i){if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) )value=a[i+1]-a[i];elsevalue=a[i+2]-a[i+1];}cout<<value<<endl;return 0;}4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。

习题11. 图论诞生于七桥问题。

出生于瑞士的伟大数学家欧拉（LeonhardEuler ，1707—1783）提出并解决了该问题。

七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。

请将该问题的数据模型抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。

输入：一个起点输出：相同的点1， 一次步行2， 经过七座桥，且每次只经历过一次3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。

另一类是只有二个奇点的图形。

图 七桥问题南2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。

请用伪代码描述这个版本的欧几里德算法=m-n2.循环直到r=0m=nn=rr=m-n3 输出m3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。

要求分别给出伪代码和C++描述。

编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。

#include<iostream>using namespace std;int main(){double value=0;for(int n=1;n<=10000 ;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<<n<<endl;break;}}计算π值的问题能精确求解吗编写程序，求解满足给定精度要求的π值#include <iostream>using namespace std;int main (){double a,b;double arctan(double x);圣经上说：神6天创造天地万有，第7日安歇。

为什么是6天呢任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。

算法设计与分析习题答案1算法设计与分析习题答案1习题1 1. 图论诞生于七桥问题。

出生于瑞士的伟大数学家欧拉提出并解决了该问题。

七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区图是这条河以及河上的两个岛和七座桥的图七桥问题草图。

请将该问题的数据模型抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。

输入：一个起点输出：相同的点1，一次步行2，经过七座桥，且每次只经历过一次3，回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。

另一类是只有二个奇点的图形。

2．在欧几里德提出的欧几里德算法中用的不是除法而是减法。

请用伪代码描述这个版本的欧几里德算法=m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素的差。

要求分别给出伪代码和C++描述。

//采用分治法//对数组先进行快速排序//在依次比较相邻的差#include using namespace std; int partions(int b,int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low while (low=prvotkey)--high; b[low]=b[high]; while (low b[high]=b[low]; } b[low]=b[0]; return low; } void qsort(int l,int low,int high) { int prvotloc; if(low prvotloc=partions(l,low,high);//将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1); //递归调用排序low 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序prvotloc+1到high } } void quicksort(int l,int n) { qsort(l,1,n); // 第一个作为枢轴，从第一个排到第n个} int main() { int a[11]={0,2,32,43,23,45,36,57,14,27,39};int value=0;//将最小差的值赋值给value for (int b=1;b quicksort(a,11); for(int i=0;i!=9;++i) { if( (a[i+1]-a[i]) value=a[i+2]-a[i+1]; } cout return 0; } 4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。

plan23工作原理(一)plan23工作原理1. 前言在程序开发过程中，我们经常使用各种算法和数据结构来解决问题。

其中一个十分重要的算法就是plan23算法。

本文将从浅入深，详细解释plan23工作原理及其相关原理。

2. 什么是plan23算法plan23算法是一种高效的排序算法，它能够在O(n log n)的时间复杂度下将一个无序的数组进行排序，并且具有稳定性和泛化性。

它的名字来源于其基本原理中的两个关键概念：“plan”和”23”。

3. plan“plan”是指plan23算法在排序过程中的规划和分割。

它将原始数组按照一定规则进行递归地分割，直到最终得到若干个长度更小的子数组。

这种分割方式使得算法能够对子数组进行并行处理，提高了排序的效率。

4. 23“23”是指plan23算法使用了两个关键的操作步骤：“取2”和”取3”。

在plan23算法的每一次迭代中，它会选择2个子数组进行合并，然后再选择3个子数组进行合并。

这样的分组策略既考虑了排序效率，又兼顾了算法的稳定性和泛化性。

5. 具体实现plan23算法的具体实现包括以下几个步骤：•步骤1：将原始数组递归地分割成若干个子数组，直到每个子数组的长度为1或0。

•步骤2：对每一对相邻的子数组进行合并，得到新的有序子数组。

•步骤3：对每一组3个相邻的子数组进行合并，得到新的有序子数组。

•步骤4：重复步骤2和步骤3，直到得到完全有序的数组。

通过以上步骤，plan23算法能够高效地将一个无序的数组进行排序。

在实际应用中，我们可以根据具体的需求对算法进行优化，包括使用并行计算、分治策略等方法。

6. 总结在本文中，我们介绍了plan23算法的工作原理及其相关原理。

它是一种高效的排序算法，能够以O(n log n)的时间复杂度对一个无序的数组进行排序。

通过了解plan和23的概念，我们能够更好地理解这个算法的设计思想和实现方式。

希望本文对你理解plan23算法有所帮助！参考资料•[Plan23 Sorting Algorithm]( •[Sorting algorithm](。