下载文档原格式
第5章算法与复杂性习题一、选择题1. B2. D3. C4. A5. B6. B7. D8.B9.C 10.A11.A 12.C 13.A 14.A二、简答题1．什么是算法，算法的特性有哪些？答：“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。
算法的特性有：(1) 有穷性(可终止性)：一个算法必须在有限个操作步骤内以及合理的有限时间内执行完成。
(2) 确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。
(3) 有效性(可执行性)：算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。
(4) 输入及输出：一个算法应该有零个或多个输入数据、有1个或多个输出数据。
2．什么是算法的时间复杂度和空间复杂度，如何表示？答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。
记为，T(n)，其中，n代表求解问题的规模。
算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算机中运行所占用空间的大小。
简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。
记为，S(n)，其中，n代表求解问题的规模。
时间复杂度和空间复杂度同样，引入符号“O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。
3．用图示法表示语言处理的过程。
答：语言处理的过程如图所示：4．简述算法设计的策略。
答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法，而不是计算机程序的本身。
一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。
要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。
通常可以利用实验对比分析、数学方法来分析算法。
实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。
算法（第四版）C#习题题解——1.3.49⽤6个栈实现⼀个O（1）队列因为这个解法有点复杂，因此单独开⼀贴介绍。
那么这⾥就使⽤六个栈来解决这个问题。
这个算法来⾃于。
原⽂⾥⽤的是 Pure Lisp，不过语法很简单，还是很容易看懂的。
先导知识——⽤两个栈模拟⼀个队列如何使⽤两个栈来模拟⼀个队列操作？这是⼀道很经典的题⽬，答案也有很多种，这⾥只介绍之后会⽤到的⼀种⽅法。
⾸先我们有两个栈，H 和 T，分别⽤作出队和⼊队⽤。
这样，⼊队操作等同于向 T 添加元素，T 的⼊栈操作只需要 O(1) 时间。
如果 H 不为空，出队操作等同于 H 弹栈，H 的弹栈操作也只需要 O(1) 时间。
但如果 H 为空，则需要将 T 中的元素依次弹出并压⼊到 H 中，这是⼀个 O(n) 的操作。
显然，这种⽅式中，出队操作的最坏时间复杂度是 O(n)，并不满⾜题⽬要求。
分摊 O(n)那么，怎么解决这个问题呢？⼀个很⾃然的想法是，如果在栈 H 变为空之前，我们就能逐步将栈 T 的内容弹出并压⼊到另⼀个栈 H' 中，等到栈 H 为空时，直接交换 H 和 H' 即可。
假设⽬前的队列状态是这样，有三个元素等待出队，还有三个元素等待⼊队。
现在依次让三个元素出队，与此同时我们让栈 T 中的元素依次进⼊ H' 中。
每⼀次出队都执⾏两个操作，元素出队和元素复制（Pop & Push），时间复杂度 O(1) + O(1) + O(1) = O(1)。
第⼀次操作（出队）第⼆次操作（出队）第三次操作（出队）现在栈 H 和栈 T 都为空，下⼀次出队操作时，我们直接交换栈 H 和栈 H'（由于是交换引⽤，因此时间复杂度仍为 O(1)）。
之后再进⾏出队操作。
这就是这个算法基本想法，在栈 H 变为空之前，分步将栈 T 中的内容分步复制到另⼀个栈中。
当栈 H 为空时直接⽤准备好的栈 H' 替代 H，保证时间复杂度为常数。
·54· 第3章 离散傅里叶变换（DFT ）及其快速算法（FFT ）3.1 引 言本章是全书的重点，更是学习数字信号处理技术的重点内容。
因为DFT （FFT ）在数字信号处理这门学科中起着不一般的作用，它使数字信号处理不仅可以在时域也可以在频域进行处理，使处理方法更加灵活，能完成模拟信号处理完不成的许多处理功能，并且增加了若干新颖的处理内容。
离散傅里叶变换（DFT ）也是一种时域到频域的变换，能够表征信号的频域特性，和已学过的FT 和ZT 有着密切的联系，但是它有着不同于FT 和ZT 的物理概念和重要性质。
只有很好地掌握了这些概念和性质，才能正确地应用DFT （FFT ），在各种不同的信号处理中充分灵活地发挥其作用。
学习这一章重要的是会应用，尤其会使用DFT 的快速算法FFT 。
如果不会应用FFT ，那么由于DFT 的计算量太大，会使应用受到限制。
但是FFT 仅是DFT 的一种快速算法，重要的物理概念都在DFT 中，因此重要的还是要掌握DFT 的基本理论。
对于FFT 只要掌握其基本快速原理和使用方法即可。
3.2 习题与上机题解答说明：下面各题中的DFT 和IDFT 计算均可以调用MA TLAB 函数fft 和ifft 计算。
3.1 在变换区间0≤n ≤N -1内，计算以下序列的N 点DFT 。
(1) ()1x n =(2) ()()x n n δ=(3) ()(), 0＜＜x n n m m N δ=- (4) ()(), 0＜＜m x n R n m N = (5) 2j()e, 0＜＜m n N x n m N π=(6) 0j ()e n x n ω=(7) 2()cos , 0＜＜x n mn m N N π⎛⎫= ⎪⎝⎭(8)2()sin , 0＜＜x n mn m N N π⎛⎫= ⎪⎝⎭(9) 0()cos()x n n ω=(10) ()()N x n nR n =(11) 1,()0n x n n ⎧=⎨⎩，解：(1) X (k ) =1N kn N n W -=∑=21j0eN kn nn π--=∑=2jj1e1ekN n k nπ---- = ,00,1,2,,1N k k N =⎧⎨=-⎩(2) X (k ) =1()N knNM n W δ-=∑=10()N n n δ-=∑=1，k = 0, 1, …, N -1(3) X (k ) =100()N knNn n n W δ-=-∑=0kn NW 1()N n n n δ-=-∑=0kn NW，k = 0, 1, …, N -1为偶数为奇数·55·(4) X (k ) =1m knN n W -=∑=11kmN N W W --=j (1)sin esin k m N mk N k N π--π⎛⎫⎪⎝⎭π⎛⎫ ⎪⎝⎭，k = 0, 1, …, N -1 (5) X (k ) =21j 0e N mn kn N N n W π-=∑=21j ()0e N m k nNn π--=∑=2j()2j()1e1em k N N m k Nπ--π----= ,0,,0≤≤1N k mk m k N =⎧⎨≠-⎩(6) X (k ) =01j 0eN nknN n W ω-=∑=021j 0e N k nN n ωπ⎛⎫-- ⎪⎝⎭=∑=002j 2j 1e1ek NN k N ωωπ⎛⎫- ⎪⎝⎭π⎛⎫- ⎪⎝⎭--= 0210j 202sin 2e2sin /2N k N N k N k N ωωωπ-⎛⎫⎛⎫- ⎪⎪⎝⎭⎝⎭⎡⎤π⎛⎫- ⎪⎢⎥⎝⎭⎣⎦⎡⎤π⎛⎫- ⎪⎢⎥⎝⎭⎣⎦，k = 0, 1, …, N -1或 X (k ) =00j 2j 1e 1e Nk N ωωπ⎛⎫- ⎪⎝⎭--，k = 0, 1, …, N -1(7) X (k ) =102cos N kn N n mn W N -=π⎛⎫ ⎪⎝⎭∑=2221j j j 01e e e 2N mn mn kn N N N n πππ---=⎛⎫ ⎪+ ⎪⎝⎭∑=21j ()01e 2N m k n N n π--=∑+21j ()01e 2N m k n N n π--+=∑=22j ()j ()22j ()j ()11e 1e 21e 1e m k N m k N N N m k m k N N ππ--+ππ--+⎡⎤--⎢⎥+⎢⎥⎢⎥--⎣⎦=,,20,,N k m k N mk m k N M ⎧==-⎪⎨⎪≠≠-⎩，0≤≤1k N - (8) ()22j j 21()sin ee 2j mn mnN N x n mn N ππ-π⎛⎫== ⎪-⎝⎭ ()()112222j j j ()j ()0011()=e e ee 2j 2j j ,2=j ,20,(0≤≤1)N N kn mn mn m k n m k n N N N N N n n X k W Nk m N k N mk k N --ππππ---+===--⎧-=⎪⎪⎨=-⎪⎪-⎪⎩∑∑其他(9) 解法① 直接计算χ(n ) =cos(0n ω)R N (n ) =00j j 1[e e ]2n n ωω-+R N (n )X (k ) =1()N knNn n W χ-=∑=0021j j j 01[e e ]e 2N kn n n N n ωωπ---=+∑=0000j j 22j j 11e 1e 21e 1e N N k k N N ωωωω-ππ⎛⎫⎛⎫--+ ⎪ ⎪⎝⎭⎝⎭⎡⎤--⎢⎥+⎢⎥⎢⎥--⎣⎦，k = 0, 1, … , N -1 解法② 由DFT 共轭对称性可得同样的结果。
1.1.1 给出以下表达式的值：a. ( 0 + 15 ) / 2b. 2.0e-6 * 100000000.1c. true && false || true && true答案：a.7,b.200.0000002 c.ture1.1.2 给出以下表达式的类型和值：a. (1 + 2.236)/2b. 1 + 2 + 3 + 4.0c. 4.1 >= 4d. 1 + 2 + "3"答案：a.1.618 b. 10.0 c.true d.331.1.3 编写一个程序，从命令行得到三个整数参数。
如果它们都相等则打印equal，否则打印not equal。
public class TestUqual{public static void main(String[] args){int a,b,c;a=b=c=0;StdOut.println("Please enter three numbers");a =StdIn.readInt();b=StdIn.readInt();c=StdIn.readInt();if(equals(a,b,c)==1){StdOut.print("equal");}else{StdOut.print("not equal");}}public static int equals(int a ,int b , int c){if(a==b&&b==c){return 1;}else{return 0;}}}1.1.4 下列语句各有什么问题（如果有的话）？a. if (a > b) then c = 0;b. if a > b { c = 0; }c. if (a > b) c = 0;d. if (a > b) c = 0 else b = 0;答案：a. if (a > b) c = 0; b. if (a > b) { c = 0; }1.1.5 编写一段程序，如果double 类型的变量x 和y 都严格位于0 和1 之间则打印true，否则打印false。
算法第四版习题答案1.2/** 1.2.1 编写一个Point2D的用例，从命令行接受一个整数N。
在单位正方形内生成N个随机点，然后计算两点之间的最近距离*/public class testPoint2D {public testPoint2D() {// TODO Auto-generated constructor stub}public static void drawbox(double bw, double bh){StdDraw.setPenRadius(0.005);StdDraw.setPenColor(StdDraw.RED);Interval1D xinterval = new Interval1D(0, bw);Interval1D yinterval = new Interval1D(0, bh);Interval2D box = new Interval2D(xinterval, yinterval);box.draw();}public static Point2D[] drawpoint(int N){Point2D[] p=new Point2D[N];for(int i=0;i<N;i++){double x=Math.random();double y=Math.random();p[i]=new Point2D(x, y) ;p[i].draw();}return p;}public static double findmindist(Point2D[] p){Point2D p1=p[0];Point2D p2=p[1];double mindist =p[0].distanceTo(p[1]);StdDraw.setPenRadius(0.002);StdDraw.setPenColor(StdDraw.RED);int n=p.length ;for(int i=1;i<n-1;i++)for(int j=i+1;j<n;j++){double temp=p[i].distanceTo(p[j]);if(temp<mindist){ mindist=temp;p1=p[i];p2=p[j];}}p1.drawTo(p2);StdOut.print("min dist="+mindist +p1.toString()+p2.toString());return mindist;}public static void main(String[] args) {int N=StdIn.readInt();//读取画点的数量//StdDraw.setXscale(0,1 );//StdDraw.setYscale(0,1);drawbox(1,1);//画出一个单位大小的正方形StdDraw.setPenRadius(0.01);StdDraw.setPenColor(StdDraw.BLACK);//drawpoint(N);//画出N个点double min=findmindist(drawpoint(N));}}/** 编写一个Interval1D的用例，从命令行接受一个整数N。
第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。
若f=Ο(g)，则必然存在常数c1>0和n0，使得∀n≥n0，有f≤c1*g(n)。
由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。
必要性。
同理，若g=Ω(f)，则必然存在c2>0和n0，使得∀n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。
2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得∀n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。
由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。
3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。
证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得∀n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。
4）log(n!)= Θ(nlogn)证明：∙由于log(n!)=∑=n i i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。
∙由于对所有的偶数n 有，log(n!)= ∑=n i i 1log ≥∑=n n i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。
当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得∀n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。
算法第四版习题答案1.2/** 1.2.1 编写一个Point2D的用例，从命令行接受一个整数N。
在单位正方形内生成N个随机点，然后计算两点之间的最近距离*/public class testPoint2D {public testPoint2D() {// TODO Auto-generated constructor stub}public static void drawbox(double bw, double bh){StdDraw.setPenRadius(0.005);StdDraw.setPenColor(StdDraw.RED);Interval1D xinterval = new Interval1D(0, bw);Interval1D yinterval = new Interval1D(0, bh);Interval2D box = new Interval2D(xinterval, yinterval);box.draw();}public static Point2D[] drawpoint(int N){Point2D[] p=new Point2D[N];for(int i=0;i<N;i++){double x=Math.random();double y=Math.random();p[i]=new Point2D(x, y) ;p[i].draw();}return p;}public static double findmindist(Point2D[] p){Point2D p1=p[0];Point2D p2=p[1];double mindist =p[0].distanceTo(p[1]);StdDraw.setPenRadius(0.002);StdDraw.setPenColor(StdDraw.RED);int n=p.length ;for(int i=1;i<n-1;i++)for(int j=i+1;j<n;j++){double temp=p[i].distanceTo(p[j]);if(temp<mindist){ mindist=temp;p1=p[i];p2=p[j];}}p1.drawTo(p2);StdOut.print("min dist="+mindist +p1.toString()+p2.toString());return mindist;}public static void main(String[] args) {int N=StdIn.readInt();//读取画点的数量//StdDraw.setXscale(0,1 );//StdDraw.setYscale(0,1);drawbox(1,1);//画出一个单位大小的正方形StdDraw.setPenRadius(0.01);StdDraw.setPenColor(StdDraw.BLACK);//drawpoint(N);//画出N个点double min=findmindist(drawpoint(N));}}/** 编写一个Interval1D的用例，从命令行接受一个整数N。
C程序设计(第四版)(谭浩强)第一章课后习题答案P006 1.1 向屏幕输出文字.#include<stdio.h>//预编译. 代码均调试成功,若有失误大多不是代码问题.自已找找.int main(){printf("Welcome to \n");return 0; //与int main对应,为了程序可移植性,建议全用int main + return 0;.}P008 1.2 求两个数的和.#include<stdio.h>int main(){int a,b,sum;a=5;b=4;sum=a+b;printf("The sum is %d .\n",sum);return 0;}P008 1.3 调用函数比较两个数的大小.#include<stdio.h>int main(){int max(int x,int y); //被调用函数在主函数后面,用前先声明.int a,b,c;scanf("%d,%d",&a,&b); //输入时要按格式来,此处的逗号,用空格会发生错误.c=max(a,b); //a,b作为实参传入被调用函数中.printf("The max is %d .\n",c);return 0;}int max(int x,int y) //定义了两个形参.{int z; //z属于局部变量,可与主函数中相同名字.if (x>y)z=x;elsez=y;return(z); //z作为整个程序的出口值,赋给主函数中的c.}P015 0.6 三个数的大小.(数字0表示课后练习题)#include<stdio.h>int main(){int a,b,c,d; //d是用于存储最大值的.int max(int x , int y , int z); //测试可知,在VS2008中,可以不预先声明.printf("Please input 3 numbers :\n");scanf("%d %d %d",&a,&b,&c);d=max(a,b,c); //调用函数中有三个形参,这里需要传入三个实参,才可运算.printf("The max is :%d .\n",d); // d可以换成max(a,b,c).}int max(int x , int y , int z){int m;if (x>y && x>z) //求三者之大的一种方法.m=x;if (y>x && y>z)m=y;if (z>y && z>x)m=z;return (m); //返回值m给主函数中的d.}C程序设计(第四版)(谭浩强)第2章课后习题答案算法——程序的灵魂P017 2.1 计算机1-5相乘的积.#include<stdio.h>int main(){int i,s=1; //在执行数值操作前一定要先有个初值.for(i=1;i<6;i++) //这里是到6.{s=s*i; //相乘}printf("The sum is %d .\n",s);return 0;}#include<stdio.h> //作出要求:换成1到11间奇数相乘.int main(){int i,s=1; //在执行数值操作前一定要先有个初值.for(i=1;i<12;i++) //这里是到,但题目要求的是取单数.也可以是i=i+2{if(i%2!=0) //i对取模,值为非为奇数;为则为偶数.s=s*i;elsecontinue; //跳过这个for循环的这一次,执行下一次.}printf("The sum is %d .\n",s);return 0;}P019 2.2 按要求输出80分以上的学生信息.暂时没法做.年的概念是地球围绕太阳一周的时间（所谓公转周期）称为一年，这个周期是相当稳定的，很长时间也不会变动1秒，但是真正的一年是365.2423天（目前）。
计算机算法设计与分析第四版课后答案【篇一：计算机算法分析与设计(第四版)习题算法分析部分详解(实验六)】//6-1、6-6项目vc++6.0测试通过//6-15项目vc2005测试通过//6-1 最小长度电路板排列问题//头文件stdafx.h// stdafx.h : include file for standard system include files,// or project specific include files that are used frequently, but // are changed infrequently//#pragma once#define win32_lean_and_mean // exclude rarely-used stuff from windows headers #include stdio.h#include tchar.h// todo: reference additional headers your program requires here// sy61.cpp : defines the entry point for the console application.////description://分支限界法 6_1 最小长度电路板排列问题//#include my.h#include stdafx.h#include iostream#include queueusing namespace std;int n,m;//#include outofbounds.h//定义节点类class boardnode{friend int fifoboards(int **,int ,int,int *);//非类成员，可以访问私有成员的函数，最优序列查找public:operator int() const{return cd;}//返回常数 cdint len();public:int *x,s,cd,*low,*high;//x表示当前节点的电路板排列，s表示当前节点排列好的电路板的数//表示当前节点的最大长度，low，high分别表当前节点表示每一个连接块的第一个，和最后一个电路板//的位置};//编写类的len()函数,求出当前节点的连接块长度的最大值int boardnode::len(){int tmp=0;for(int k=1;k=m;k++)if(low[k]=n high[k]0 tmphigh[k]-low[k])tmp=high[k]-low[k];return tmp;}int fifioboards(int **b,int n,int m,int *bestx)//n为电路板的数量，m为连接块的数量 {// int bestd;queueboardnode q;//声明boardnode类的节点队列qboardnode e;e.x=new int[n+1];//为数组指针x分配n+1个动态空间，存储当前的排列e.s=0;//最初时，排列好的电路板的数目为0e.cd=0;e.low=new int[m+1];//存储每个连接块的第一个电路板的位置e.high=new int[m+1];//存储每个连接块的最后一个电路板的位置 for(int i=1;i=m;i++){e.high[i]=0;//初始化开始时的每个连接块的最后一个电路板的位置为0，表示连接块i还没有电路板放入e.x的排列中e.low[i]=n+1;//初始化开始时的每个连接块的第一个电路板的位置为n+1，表示连接块i还没有电路板放入e.x的排列中}for(i=1;i=n;i++)e.x[i]=i;//初始化e.x的排列为1，2,3.....nint bestd=n+1;//最优距离bestx=0;//记录当前最优排列do{if(e.s==n-1)//当已排列了n-1个时{//判断是否改变每个连接块的最后一个电路板的位置for(int j=1;j=m;j++)if(b[e.x[n]][j] ne.high[j])e.high[j]=n;int ld=e.len();//存储当前节点的各连接块长度中的最大长度//如果当前的最大长度小于了n+1if(ldbestd){delete[] bestx;bestx=e.x;bestd=ld;//最优距离}else delete[] e.x;//删除分配给e.x的数组空间delete[] e.low;//删除分配给e.low的数组空间delete[] e.high;//删除分配给e.high的数组空间}else{int curr=e.s+1;//rr记录现在应该排列第几个电路板for(int i=e.s+1;i=n;i++)//处理扩展节点下一层所有子节点{boardnode n;n.low=new int[m+1];//与if中的意思相同n.high=new int[m+1];for(int j=1;j=m;j++){n.low[j]=e.low[j];//将e.low[]中的值赋给n.low[]n.high[j]=e.high[j];if(b[e.x[i]][j]){if(currn.low[j])n.low[j]=curr;//若当前节点连接块j的第一个电路板的位置比现在正在排列的电路板的位置还小if(currn.high[j])n.high[j]=curr;}}n.cd=n.len();//如果，当前节点的最大长度小于了最优长度则：if(n.cdbestd){n.x=new int[n+1];n.s=e.s+1;for(int j=1;j=n;j++)n.x[j]=e.x[j];n.x[n.s]=e.x[i];//交换位置n.x[i]=e.x[n.s];//交换位置q.push(n);//将节点n加入队列中}else{delete[] n.low;delete[] n.high;}//printf(%d,bestd);}delete[] e.x;//当前扩展节点所有子节点均考虑，变成死结点} //try{if(!q.empty()){e=q.front(); //取队列首节点作为扩展节点q.pop();}else return bestd;//}//catch(outofbounds)//{//return bestd;//}//printf(finish);}while(!q.empty());return bestd;return 1;}//测试void main(){//scanf(%d%d,n,m);cinnm;int **b=new int*[n+1];for (int t=0; t=n; t++)b[t] = new int[m+1];for(int i=1;i=n;i++)for(int j=1;j=m;j++)cinb[i][j];//scanf(%d,b[i][j]);int *bestx=new int[n+1];int bestd=0;bestd=fifioboards(b,n,m,bestx);printf(%d\n,bestd);for(i=1;i=n;i++){coutbestx[i] ;}coutendl;}//6-6 经典n皇后问题//description:经典n皇后问题广度优先建议n=14解空间为子集树 //参考答案说排列树是不正确的，本例打印n*n棋盘的所有解，即放置方法 #include iostream#include fstream#include algorithm#include functional#include queueusing namespace std;//本例子直接输入棋盘大小，不用文件//ifstream in(input.txt); //请在项目文件夹下新建一个input.txt//ofstream out(output.txt);class node{public:node(int n){t = 0;this-n = n;loc = new int[n + 1];for (int i = 0; i= n; ++i){loc[i] = 0;}}node(const node other){this-t = other.t;this-n = other.n;this-loc = new int [n + 1];for (int i = 0; i = n; ++i){this-loc[i] = other.loc[i];}}int t;//已放置t个皇后【篇二：计算机算法分析与设计(第四版)习题算法分析部分详解(实验二)】>实验内容：算法实现问题2-1、2-5、2-7//2-1 众数问题思路1：先排序，然后再统计，时间复杂度较高。
第8章扩展应用举例练习题一、简答题1．请举出在数据结构课程中讲过的算法里用到穷举思想的算法。
【参考答案】穷举思想是将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有的对象，问题将最终得以解决。
例如在数据结构课程中讲到的朴素的字符串匹配算法。
2．请举出在数据结构课程中讲过的算法里用到分治思想的算法。
【参考答案】分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
可以采用递归的方式求解这些子问题，然后将各子问题的解合并得到原问题的解。
在数据结构课程中使用了分治算法的例子有快速排序和归并排序等。
3．请举出在数据结构课程中讲过的算法里用到贪心思想的算法。
【参考答案】贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。
因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。
在数据结构课程中使用贪心算法的例子有：哈夫曼编码；单源最短路径；最小生成树的Prim算法和Kruskal 算法等。
4．请举出在数据结构课程中讲过的算法里用到搜索思想的算法。
【参考答案】搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法，即深度优先搜索(DFS--Depth First search)和广度优先搜索(BFS--Breadth First Search)。
深度优先搜索：深度优先搜索所遵循的搜索策略是尽可能"深"地搜索树。
它的基本思想是:为了求得问题的解，先选择某一种可能情况向前(子结点)探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。
深度优先搜索的实现方式可以采用递归或者栈来实现。
运筹学部分课后习题解答P47 用图解法求解线性规划问题a）12121212min z=23466 ..424,0x xx xs t x xx x++≥⎧⎪+≥⎨⎪≥⎩解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为最优解，即该问题有无穷多最优解，这时的最优值为min3z=23032⨯+⨯= P47 用图解法和单纯形法求解线性规划问题a）12121212max z=10x5x349 ..528,0x xs t x xx x++≤⎧⎪+≤⎨⎪≥⎩<解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，即112122134935282xx xx x x=⎧+=⎧⎪⇒⎨⎨+==⎩⎪⎩，即最优解为*31,2Tx⎛⎫= ⎪⎝⎭这时的最优值为max335z=101522⨯+⨯=单纯形法： 原问题化成标准型为121231241234max z=10x 5x 349..528,,,0x x x s t x x x x x x x +++=⎧⎪++=⎨⎪≥⎩ j c →105、B CB X b 1x 2x3x4x0 3x \9 3 4 1 0 04x8[5] 2 .0 1 j j C Z -105 00 0 3x 21/5 .0 [14/5] 1 -3/5 101x8/512/5 0 （1/5 j j C Z -1 0 -25 2x 3/2 0 ；1 5/14 -3/14 101x11 0-1/7 2/7 （j j C Z --5/14-25/14所以有*max 33351,,1015222Tx z ⎛⎫==⨯+⨯= ⎪⎝⎭P78 已知线性规划问题：1234124122341231234max24382669,,,0z x x x x x x x x x x x x x x x x x x x =+++++≤⎧⎪+≤⎪⎪++≤⎨⎪++≤⎪≥⎪⎩求: (1) 写出其对偶问题；（2）已知原问题最优解为)0,4,2,2(*=X ，试根据对偶理论，直接求出对偶问题的最优解。
算法（第四版）C#习题题解——2.3写在前⾯习题&题解2.3.1解答2.3.2解答2.3.3解答N / 2在快速排序中，⼀个元素要被交换，有以下两种情况1.该元素是枢轴，在切分的最后⼀步被交换2.该元素位于枢轴错误的⼀侧，需要被交换到另⼀侧去注意，以上两种情况在⼀次切分中只会出现⼀次⾸先来看第⼀种情况，如果⼀个元素变成了枢轴那么在之后的切分中该元素会被排除，不存在后续的交换。
因此我们的⽬标应该是：最⼤的元素总是出现在错误的⼀侧，同时切分的次数尽可能多。
接下来我们来思考如何构造这样的数组由于我们针对的是最⼤的元素，因此「错误的⼀侧」就是枢轴的左侧。
为了使切分的次数尽可能多，我们需要保持最⼤值移动的距离尽量短。
但如果每次只移动⼀位的话，下⼀次切分时最⼤值就会变成枢轴例如 4 10 3 5 6，枢轴为 4，交换后数组变为：4 3 105 6随后 4 和 3 交换3 4 10 5 6下⼀次切分时 10 会变成枢轴，不再参与后续的切分。
因此我们需要让最⼤值每次移动两个元素。
考虑下⾯的数组：2 10 4 1 63 8 5 7 9第⼀次切分的时候，枢轴为 2，10 和 1 进⾏交换数组变为：2 1 4 10 63 8 5 7 9随后枢轴交换，数组变为：1 2 4 10 6 3 8 5 7 9第⼆次切分，枢轴为 4，10 和 3 进⾏交换。
1 2 4 3 6 10 8 5 7 9随后枢轴交换数组变为：1 2 3 4 6 10 8 5 7 9第三次切分，枢轴为 6，10 和 5 交换1 2 3 4 6 5 8 10 7 9随后枢轴交换，数组变为：1 2 3 4 5 6 8 10 7 9第四次切分，枢轴为 8，10 和 7 交换1 2 3 4 5 6 8 7 10 9枢轴交换，数组变为1 2 3 4 5 6 7 8 10 9最后⼀次切分，枢轴为 10，直接交换1 2 3 4 5 6 7 8 9 10我们可以总结出要构造这样的数组的模板a2 max a3 a1其中 a1 < a2 < a3 < maxmax 每轮切分移动两格，总共切分 N/ 2 次。
《算法（第四版）》读书笔记（完结）⼤⼀下的时候学过数据结构,但是⾯试的时候发现⼀些基础知识都忘的差不多了,所以打算借这本书重新学习⼀下算法与数据结构.使⽤的语⾔是JAVA.IDE是Eclipse,相关设置请看以下两篇⽂章:注意数据⽂件如果直接⽤记事本看是不会显⽰换⾏的,可以⽤notepad++等软件查看.1.1 基础编程模型JAVA基础语句数组创建1.3 背包、队列和栈队列:先进先出(FIFO)下压栈:后进先出(LIFO)求值算法:1. 将操作数压⼊操作数栈2. 将运算符压⼊运算符栈3. 忽略左括号4. 遇到右括号时,弹出⼀个运算符,弹出所需数量的操作数,并将运算结果压⼊操作数栈1.4 算法分析2-sum问题:先归并排序,然后对于a[i],在j>i的范围内⽤⼆分查找寻找a[j]=-a[i],时间复杂度为O(NlogN)3-sum问题:先归并排序,然后对于a[i]和a[j](j从i+1开始遍历),在k>j的的范围内⽤⼆分查找寻找a[k]=-a[i]-a[j],时间复杂度为O(N^2logN)1.5 union-find算法union-find算法也就是经典的并查集算法,⽤于解决动态连通性问题.通过对这个算法的⼀步步更新可以体会到算法优化的思想和好处.基本思想:对于给定的两个触点,判断它们所在的连通分量是否相同,将查找连通分量称为find.如果未连通,则将这两个触点以及分别与它们连通的触点连通,将连通称为union.基础实现:使⽤⼀个id数组,保证在同⼀连通分量中的所有触点在id数组中的值是全部相同的.1. find:返回触点在id数组中对应的值.2. union:分别对p和q进⾏find操作,如果对应值相等不做操作,不相等则遍历id数组,将所有与p的对应值相等的id值改为q的id值.quick-union:改变id数组的定义,每个触点所对应的id元素都是同⼀个分量中另⼀个触点的名称,这种联系称为链接.由⼀个触点的链接⼀直跟随下去⼀定会到达根触点,即链接指向⼦集的触点.当且仅当两个触点的根触点相同时它们存在于同⼀个连通分量中.1. find:返回⼀个触点链接的根触点.2. union:分别对p和q进⾏find操作,如果对应值相等不做操作,不相等则将p的根触点链接到q的根触点上.加权quick-union:为了防⽌树极度不均衡,记录每⼀棵树的⼤⼩并总是将较⼩的树连接到较⼤的树上.在程序中引⼊size数组记录各个触点的根节点所对应的分量的⼤⼩.1. find:返回⼀个触点链接的根触点.2. union:分别对p和q进⾏find操作,如果对应值相等不做操作,不相等则判断对应值的根节点分量的⼤⼩,将⼩树的根触点链接到⼤树的根触点上.路径压缩:为find函数添加⼀个循环,将在路径上遇到的所有节点都直接链接到根节点.关于并查集,可以参考.2.1 初级排序算法选择排序:时间复杂度为O(N^2).找到数组中最⼩的元素,将它和数组的第⼀个元素交换位置.然后在剩下的元素中重复这⼀步骤.特点是运⾏时间和输⼊⽆关以及数据移动是最少的.插⼊排序:时间复杂度为O(N^2).遍历数组中的每⼀个元素,将它与左边的元素⽐较并插⼊到合适的位置中,这会使该元素左边的所有元素都是有序的.因为插⼊排序总需要找到某元素在其左边序列的位置,所以可以⽤⼆分查找进⾏这⼀过程,称为⼆分插⼊排序.插⼊排序对部分有序的数组很有效,例如:1. 数组中每个元素距离它的最终位置都不远2. ⼀个有序的⼤数组接⼀个⼩数组3. 数组中只有⼏个元素的位置不正确希尔排序:时间复杂度⼩于O(N^2).插⼊排序的缺点在于只能交换相邻的元素.希尔排序的思想是使数组中任意间隔为h的元素都是有序的,即h有序数组.希尔排序需要⼀个递增序列来决定h的值,最后⼀个h必须为1.具体步骤是对于每⼀个h,遍历数组中i=h~N的所有a[i],将a[i]与a[i-h],a[i-2h]......进⾏插⼊排序,然后按递增序列减⼩h,直到h=1为⽌.2.2 归并排序归并排序:时间复杂度为O(NlogN),所需额外空间和N成正⽐.先递归地将⼀个数组分成两个⼦数组分别排序,然后将结果归并起来.在归并前可以添加判断条件,如果a[mid]<=a[mid+1]则跳过归并.原地归并:将数组复制到⼀个辅助数组中,然后把归并的结果放回原数组.1. 如果其中半边的元素都⽤完了则放⼊另外半边的所有元素2. 如果其中半边的元素⼤于另外半边的元素则放⼊另外半边的元素,并令另外半边的下标加1.⾃顶向下的归并排序:创建辅助数组,递归地对原数组的左半边和右半边排序后进⾏归并操作,终⽌条件为high<=low.改进:递归会使⼩规模问题中⽅法的调⽤过于频繁,所以⽤不同的⽅法处理⼩规模问题能改进⼤多数递归算法的性能.使⽤插⼊排序处理⼩规模(⽐如长度⼩于15)的⼦数组⼀般可以将归并排序的运⾏时间缩短10%~15%.⾃底向上的归并排序:创建辅助数组,从两两归并开始,每⼀轮归并中⼦数组的⼤⼩都会翻倍,直到可以将原数组分为两个⼦数组归并为⽌.这种⽅法很适合⽤链表组织的数据.可以证明没有任何排序算法能⽤少于NlgN次⽐较将数组排序,这意味着归并排序是⼀种渐进最优的基于⽐较排序的算法.2.3 快速排序快速排序:时间复杂度为O(NlogN).将⼀个数组随机打乱(防⽌出现最坏情况),然后通过切分变为两个⼦数组,将两部分独⽴地排序,使得切分点左边的所有元素都不⼤于它,右边的所有元素都不⼩于它.递归地进⾏这⼀过程.切分:⼀般策略是随意取a[low]作为切分元素,然后从数组的左端向右扫描,找到⼀个⼤于等于它的元素,再从数组的右端向左扫描,找到⼀个⼩于等于它的元素,交换它们的位置.如此继续,直到两个指针相遇时,将切分元素和左⼦数组最右侧的元素a[j]交换然后返回j改进:1. 当⼦数组较⼩时(⽐如长度⼩于15)使⽤插⼊排序2. 取⼦数组的⼀⼩部分元素(⽐如3个)的中位数来切分数组,还可以将切分元素放在数组末尾作为哨兵来去掉数组边界测试.3. 如果数组含有⼤量重复元素,可以采⽤三向切分的办法,将数组分为⼩于切分元素,等于切分元素和⼤于切分元素三部分,它将排序时间降到了线性级别.2.4 优先队列优先队列是⼀种抽象数据类型,它应该⽀持删除最⼤元素和插⼊元素两种操作.⼆叉树是⼀个空链接,或者是⼀个有左右两个链接的结点,每个链接都指向⼀棵⼦⼆叉树.⼆叉堆:当⼀棵⼆叉树的每个结点都⼤于等于它的两个⼦结点时,它被称为堆有序.⼆叉堆是⼀组能够⽤堆有序的完全⼆叉树排序的元素,并在数组中按照层级储存(不使⽤数组的第⼀个位置).堆的操作会进⾏⼀些简单的改动,打破堆的状态,然后再按照要求将堆的状态恢复.这个过程叫做堆的有序化.由下⾄上的堆有序化(上浮):如果堆的有序状态因为某个结点变得⽐它的⽗结点更⼤⽽被打破,就需要交换它和它的⽗结点.位置k的结点的⽗结点的位置是k/2.重复这个过程直到它不再⼤于它的⽗结点为⽌.由上⾄下的堆有序化(下沉):如果堆的有序状态因为某个结点变得⽐它的⽗结点更⼩⽽被打破,可以通过交换它和它的两个⼦结点中的较⼤者来恢复堆.位置k的结点的⼦结点为2k和2k+1.重复这个过程直到它的⼦结点都⽐它更⼩或是到达了堆的底部为⽌.插⼊元素:将新元素加到末尾,增加堆的⼤⼩并让新元素上浮到合适的位置.删除最⼤元素:从堆顶删去最⼤的元素,并将最后⼀个元素放到顶端,减⼩堆的⼤⼩并让这个元素下沉到合适的位置.对于⼀个含有N个元素的基于堆的优先队列,插⼊元素和删除最⼤元素的时间复杂度都是O(lgN)堆排序:时间复杂度为O(NlgN)1. 构造:从数组的中间元素开始,从右到左地对每个元素⽤下沉⽅法构造⼦堆.2. 排序:将最⼤的元素a[1]和末尾元素a[N]交换,将堆的⼤⼩-1,并对交换到堆顶的末尾元素使⽤下沉来修复堆,直到堆变空,此时数组中的元素已经有序.因为⼤多数在下沉排序期间重新插⼊堆的元素会被直接加⼊到堆底,所以可以使⽤先下沉后上浮的⽅法优化,即直接提升较⼤的⼦结点直⾄到达堆底,然后再使元素上浮到正确的位置.2.5 应⽤插⼊排序和归并排序是稳定的,即不会改变重复元素的相对位置.选择排序,希尔排序,快速排序和堆排序则不是稳定的.快速排序是最快的通⽤排序算法.归约:为解决某个问题⽽发明的算法正好可以⽤来解决另⼀种问题1. 找出重复元素:⾸先将数组排序,然后遍历有序的数组,记录连续出现的重复元素即可.2. 排名:求两组数列的Kendall tau距离,即在两组排列中相对顺序不同的数字组数.某个排列和标准排列的Kendall tau距离就是其中逆序数对的数量.可以由其中⼀个排列确定⼀个标准索引,然后以这个标准索引为标准对两组数列进⾏归并排序,移动的次数即为Kendall tau距离.3. 查找中位数:使⽤快速排序的分割算法,当切分点j⼩于N/2时只⽤切分右数组,切分点j⼤于2/N时只⽤切分左数组,切分点j=N/2时a[j]即为中位数.如果是海量数据,则可以将数据⽤⼆进制表⽰,根据最⼤位是0或1划分为两个⽂件,然后不断对包含中位数的那个⽂件做此操作,直到可以将剩余的数全部读进内存时再使⽤快速排序.3.1 符号表符号表最主要的⽬的就是将⼀个键和⼀个值联系起来.它⽀持插⼊和查找两种操作.在本书的符号表中,每个键只对应着⼀个值,键和值都不能为空.有序符号表是值键都为可⽐较对象的符号表.它具有最⼤键,最⼩键,向下取整(floor)和向上取整(ceiling)等操作,还可以进⾏排名(rank),选择(select)和范围查找.⼀种简单的符号表实现是使⽤⽆序链表.插⼊和查找都需要对链表进⾏遍历,时间复杂度都为O(N).有序符号表可以⽤⼀对平⾏数组来实现,⼀个存储键,⼀个存储值.⽤⼆分查找来实现rank函数,⼤⼤减少了每次查找所需的⽐较次数.查找的时间复杂度为O(lgN).但是插⼊需要移动⼤量元素,所以插⼊的时间复杂度仍为O(N).它适⽤于只需要⼤量查找的符号表.3.2 ⼆叉查找树⼀棵⼆叉查找树(BST)是⼀棵⼆叉树,其中每个结点都含有⼀个Comparable的键以及值,且每个结点的键都⼤于其左⼦树中的任意结点的键⽽⼩于其右⼦树的任意结点的键.每个结点还会有⼀个结点计数器,它给出了以该结点为根的⼦树的结点总数.size(x)=size(x.left)+size(x.right)+1⼀棵⼆叉查找树代表了⼀组键的集合,⽽同⼀个集合可以⽤多颗不同的⼆叉查找树表⽰.如果将⼀棵⼆叉查找树的所有键按从左到右的顺序投影到⼀条直线上,那么会得到⼀条有序的键列.⽤递归的⽅法查找:1. 如果树是空的,则查找未命中;2. 如果被查找的键较⼩就选择左⼦树;3. 如果被查找的键较⼤就选择右⼦树;插⼊和查找的难度差不多,如果⼀个结点不存在,只需要将链接指向⼀个含有被查找的键的新结点,并更新搜索路径上每个⽗结点中结点计数器的值.两者的时间复杂度都为O(lnN).排名也是递归实现的:1. 如果给定的键和根结点的键相等,返回左⼦树的结点总数t;2. 如果给定的键⼩于根结点,返回该键在左⼦树中的排名;3. 如果给定的键⼤于根结点,返回t+1加上它在右⼦树中的排名;删除操作通过将x替换为它的后继结点(其右⼦树中的最⼩结点)完成.1. 将指向即将被删除结点的链接保存为t2. 将x指向它的后继结点min(t.right)3. 将x的右链接指向删掉后继结点的原右⼦树4. 将x的左链接设为t.left5. 修改结点计数器的值使⽤中序遍历来进⾏范围查找，将符合条件的键放⼊⼀个队列,跳过不可能符合条件的⼦树.在⼀棵⼆叉查找树中,所有操作在最坏情况下所需的时间都和树的⾼度成正⽐.因此在某些场景下⼆叉查找树是不可接受的.3.3 平衡查找树2-3查找树:⼀棵2-3查找树或为⼀棵空树,或由以下结点组成:1. 2-结点:含有⼀个键和两条链接,左链接指向的2-3树中的键都⼩于该结点,右链接指向的2-3树中的键都⼤于该结点2. 3-结点:含有两个键和三条链接,左链接指向的2-3树中的键都⼩于该结点,中链接指向的2-3树中的键都位于该结点的两个键之间,右链接指向的2-3树中的键都⼤于该结点⼀棵完美平衡的2-3查找树中的所有空链接到根结点的距离都应该是相同的.这⾥⽤2-3树指代⼀棵完美平衡的2-3查找树.2-3树的查找:先将键和根结点中的键⽐较,如果它和其中任意⼀个相等,查找命中,否则根据⽐较的结果找到指向相应区间的链接,并在其指向的⼦树中递归地继续查找,如果是空链接则查找未命中.2-3树的插⼊:2-3树应该在插⼊后继续保持平衡.我们先进⾏⼀次未命中的查找1. 如果结束于2-结点,就将要插⼊的键保存在其中,把这个2结点替换为⼀个3结点2. 如果结束于根3-结点,就临时将新键存⼊该结点,使之成为4-结点,再把中键变为根结点,最⼩键变为它的左⼦树,最⼤键变为它的右⼦树3. 如果结束于⽗结点为2-结点的3-结点,先使其成为4-结点,再把中键移动到⽗结点中,最⼩键变为它的左⼦树,最⼤键变为它的右⼦树4. 如果结束于⽗结点为3-结点的3-结点,先使其成为4-结点,再把中间插⼊到它的⽗结点中,此时⽗结点也为⼀个4-结点,在这个结点上进⾏相同的变换,⼀直向上直到遇到2-结点或根结点2-3树是由下向上⽣长的,因为插⼊后始终保持平衡,所以即使在最坏情况下插⼊和查找的时间复杂度也为O(lgN).2-3树的缺点是具有两种结构的结点,因此需要⼤量代码实现,额外开销很⼤红⿊⼆叉查找树(红⿊树)是⽤来实现2-3树的⼀种简单的数据结构.它的基本思想是⽤标准的⼆叉查找树和⼀些额外的信息来表⽰2-3树.树中的链接被分为两种类型:⿊链接是普通链接,红链接将两个2-结点连接起来构成⼀个3结点红⿊树的另⼀种定义是含有红⿊链接并满⾜下列条件的⼆叉查找树,满⾜这样定义的红⿊树和相应的2-3树是⼀⼀对应的:1. 红链接均为左链接2. 没有任何⼀个结点同时和两条红链接相连3. 该树是完美⿊⾊平衡的,即任意空链接到根结点的路径上的⿊链接数量相同红⿊树既是⼆叉查找树,也是2-3树(将由红链接相连的结点合并),所以能够同时实现⼆叉查找树中简洁⾼效的查找⽅法和2-3树中⾼效的平衡插⼊算法旋转:如果出现了红⾊右链接或两条连续的红链接,就需要旋转.左旋转右链接也就是将两个键中较⼤者的左结点变为较⼩者的右结点,并将较⼤者作为根结点,较⼩者作为它的左结点.右旋转只需将左旋转中的左右对调即可.1. 向单个2-结点或树底部的2-结点插⼊新键:如果新键⼩于⽼键,新增⼀个红链接的结点即可.如果新键⼤于⽼键,新增的结点会产⽣⼀条红⾊的右链接,将其左旋转.2. 向3-结点插⼊⼤于两个键的新键:新键被连接到3-结点的右链接,直接将3-结点的两条链接都由红变⿊,就得到了⼀棵由3个结点组成的平衡树3. 向3-结点插⼊⼩于两个键的新键:新键被连接到最左边的空链接,即产⽣了两条连续的红链接,只需将上层的红链接右旋转即可变为情况24. 向3-结点插⼊介于两个键之间的新键:此时产⽣⼀左⼀右两条连续的红链接,只需将下层的红链接左旋转即可变为情况3颜⾊转换:⽤于将⼦结点的颜⾊由红变⿊,⽗结点的颜⾊由⿊变红每次插⼊后都要将根结点设为⿊⾊,当根结点由红变⿊时树的⿊链接⾼度加1插⼊:1. 如果右⼦结点是红⾊的⽽左⼦结点是⿊⾊的,进⾏左旋转2. 如果左⼦结点是红⾊的且它的左⼦结点也是红⾊的,进⾏右旋转3. 如果左右⼦结点均为红⾊,进⾏颜⾊转换4. 不断地将红链接由中间键传递给⽗结点,直⾄遇到⼀个2-结点或根结点时,插⼊就完成了红⿊树查找,插⼊,删除和范围查询的时间复杂度在最坏情况下都为O(lgN)3.4 散列表使⽤散列表的查找算法分为两步.第⼀步是⽤散列函数将被查找的键转化为数组的⼀个索引,第⼆步是处理碰撞冲突(多个键散列到相同索引值的情况).常⽤散列⽅法:1. 整数:散列最常⽤的⽅法是除留余数法.选择⼤⼩为素数M的数组,对于任意正整数k,计算k除以M的余数2. 浮点数:表⽰为⼆进制数然后再使⽤除留余数法3. 字符串:将每位字符表⽰为⼀个整数,然后⼀个⽐任何字符的值都⼤的数R来将字符串转化为⼀个R进制值,再在每⼀步⽤除留余数法4. 组合键:类似于字符串,将组合值⽤R进制表⽰并在每⼀步⽤除留余数法拉链法:将⼤⼩为M的数组中的每个元素指向⼀条链表,链表中的每个结点都存储了散列值为该元素的索引的键值对.基本思想是选择⾜够⼤的M,使得所有链表都尽可能短在⼀张含有M条链表和N个键的散列表中,未命中查找和插⼊的时间复杂度是O(N/M)散列后键的顺序信息丢失了,所以散列表不适合⽤来寻找最值或范围查找依靠数组中的空位解决碰撞冲突的⽅法叫开放地址散列表.其中最简单的是线性探测法:当碰撞发⽣时,检查散列表中的下⼀个位置,直到命中或遇到空元素为⽌.开放地址散列表的删除需要将被删除键右侧的所有键重新插⼊散列表,以防之后的元素⽆法被查找.元素在数组中聚集成的⼀组连续的条⽬叫键簇,为了保证性能,应该使键簇尽可能短⼩.可以证明数组的使⽤率应该在1/8~1/2之间,所以在每次插⼊元素前都需动态调整⼤⼩.3.5 应⽤使⽤put操作构造⼀张符号表以备get查询,这种应⽤叫做字典⼀个键和多个值相关联的符号表叫做索引.⽤值来查找键的操作叫做反向索引.使⽤散列表表⽰稀疏矩阵可以⼤⼤提⾼矩阵与向量相乘的效率.它所需的时间和N+⾮零元素成正⽐,⽽⽤数组表⽰的话则为N^2.N为矩阵的尺⼨.4.1 ⽆向图图是由⼀组顶点和⼀组能够将两个顶点相连的边组成的,⼀般⽤0⾄V-1表⽰⼀张含有V个顶点的图中的各个顶点,⽤v-w或w-v表⽰;连接v和w的边.边仅仅是两个顶点之间的连接的图称为⽆向图.⼀条连接⼀个顶点和其⾃⾝的边称为⾃环.连接同⼀对顶点的两条边称为平⾏边.⼀般将含有平⾏边的图称为多重图,将没有平⾏边或⾃环的图称为简单图.某个顶点的度数即为依附于它的边的总数.⼦图是由⼀幅图的所有边的⼀个⼦集组成的图.路径是由边顺序连接的⼀系列顶点.简单路径是⼀条没有重复顶点的路径.环是⼀条⾄少含有⼀条边且起点和终点相同的路径.简单环是⼀条不含有重复顶点和边的环.如果从任意⼀个顶点都存在⼀条路径到达另⼀个任意顶点,那么这幅图是连通图.图的密度是指已经连接的顶点对斩所有可能被连接的顶点对的⽐例,由此分出稀疏图和稠密图.⼆分图是⼀种能够将所有结点分为两部分的图,其中图的每条边所连接的两个顶点都分别属于不同的部分.⼀般采⽤邻接表数组来表⽰图.它将每个顶点的所有相邻顶点都保存在该顶点对应的元素所指向的⼀张链表中.它使⽤的空间和V+E成正⽐.添加⼀条边所需的时间为常数.遍历顶点v的所有相邻顶点所需的时间和v的度数成正⽐.深度优先搜索(DFS)是搜索连通图的经典递归算法,所需的时间和顶点的度数之和成正⽐.使⽤的是栈:1. 在访问其中⼀个顶点时将它标记为已访问2. 递归地访问该顶点的所有没有被标记过的邻居顶点⼴度优先搜索(BFS)是解决单点最短路径的经典算法,它所需的时间在最坏情况下和V+E成正⽐.使⽤的是队列,先将起点加⼊队列,重复以下步骤直到队列为空:1. 将与v相邻的所有未被标记过的顶点加⼊队列,删除v2. 取队列中的下⼀个顶点v并标记它DFS和BFS的区别在于DFS总是获取最晚加⼊的顶点,⽽BFS总是获取最早加⼊的结点.DFS更适合实现图的抽象数据类型,因为它能更有效地利⽤已有的数据结构.⽽union-find算法适合于只需要判断连通性的任务.利⽤⼀个符号表保存字符和索引,⼀个数组保存反向索引和⼀张图就可以实现符号图.4.2 有向图⼀幅有向图是由⼀组顶点和⼀组有⽅向的边组成的,每条有⽅向的边都连接着有序的⼀对顶点.在有向图中,⼀个顶点的出度为由该顶点指出的边的总数;⼀个顶点的⼊度为指向该顶点的边的总数.⽤v→w表⽰有向图中⼀条由v指向w的边.有向路径由⼀系列顶点组成,对于其中的每个顶点都存在⼀条有向边从它指向序列中的下⼀个顶点.有向环为⼀条⾄少含有⼀条边且起点和终点相同的有向路径.简单有向环是⼀条不含有重复的顶点和边的环.和⽆向图类似,⼀般使⽤邻接表来表⽰有向图,⽤顶点v所对应的邻接链表中包含⼀个w顶点来表⽰边v→w.每条边都只会在其中出现⼀次.DFS和BFS 同样可⽤于有向图.拓扑排序:给定⼀幅有向图,将所有的顶点排序,使得所有的有向边均从排在前⾯的元素指向排在后⾯的元素.即有优先级限制下的调度问题.当且仅当⼀幅有向图是⽆环图时它才能进⾏拓扑排序.有向⽆环图(DAG)是⼀幅不含有环的有向图.想要进⾏有向环检测,可以基于DFS,⼀旦找到⼀条边v→w且w已经存在于栈中,就找到了⼀个环.DFS遍历⼀幅图以后,有以下三种排列顺序:1. 前序:在递归调⽤之前将顶点加⼊队列,即dfs()的调⽤顺序2. 后序:在递归调⽤之后将顶点加⼊队列,即顶点遍历完成的顺序3. 逆后序:在递归调⽤之后将顶点压⼊栈,即这幅图的拓扑排序(如果是有向⽆环图)如果两个顶点v和w是互相可达的,则称它们为强连通的.如果⼀幅有向图中的任意两个顶点都是强连通的,则称这幅有向图也是强连通的.两个顶点是强连通的当且仅当它们都在⼀个普通的有向环中.通常⽤Kosaraju算法来计算强连通分量:1. 在给定的⼀幅有向图G中,计算它的反向图的逆后序排列2. 在G中进⾏DFS,但是要按照1得到的顺序来访问所有未被标记的顶点3. 所有在同⼀个递归DFS调⽤中被访问到的顶点都在同⼀个强连通分量中4.3 最⼩⽣成树加权图是⼀种为每条边关联⼀个权值或是成本的图模型.图的⽣成树是它的⼀棵含有其所有顶点的⽆环连通⼦图.⼀幅加权⽆向图的最⼩⽣成树(MST)是它的⼀棵权值最⼩的⽣成树.在计算最⼩⽣成树时,做以下约定:1. 只考虑连通图2. 边的权重不⼀定表⽰距离3. 边的权重可能是0或者负数4. 所有边的权重都各不相同树的两个重要性质:1. ⽤⼀条边连接树中的任意两个顶点都会产⽣⼀个新的环2. 从树中删去⼀条边将会得到两颗独⽴的树图的⼀种切分是将图的所有顶点分为两个⾮空且不重复的两个集合.横切边是⼀条连接两个属于不同集合的顶点的边.切分定理:在⼀幅加权图中,给定任意的切分,它的横切边中的权重最⼩者必然属于图的最⼩⽣成树.切分定理是解决最⼩⽣成树问题的所有算法的基础.这些算法都是⼀种贪⼼算法的特殊情况.即找到⼀种切分,它产⽣的横切边均不为⿊⾊,将它权重最⼩的横切边标记为⿊⾊,直到标记了V-1条⿊⾊边为⽌.不同之处在于保存切分和判定权重最⼩的横切边的⽅式.同样可以使⽤邻接表来表⽰加权⽆向图,只需要增加⼀个权重域.Prim算法:1. ⼀开始最⼩⽣成树只有⼀个顶点,然后会向它添加V-1条边.每次总是将下⼀条连接树顶点与⾮树顶点且权重最⼩的边加⼊树中.每⼀步总是为⼀棵树添加⼀条边.2. 使⽤优先队列来根据权重⽐较所有边3. 分为延时实现和即时实现.区别在于是否⽴即删除失效的横切边(即连接新加⼊的顶点和树中已有顶点之间的边).4. 延时实现所需空间与E成正⽐,所需时间与ElogE成正⽐.5. 即时实现不仅删除失效的边,⽽是仅保存⾮树顶点到树顶点的边中权重最⼩的那条,并在每次加⼊新顶点后检查是否需要更新.所需空间与V成正⽐,时间与ElogV成正⽐.Kruskal算法:1. 按照边的权重顺序处理它们,将边加⼊最⼩⽣成树中,加⼊的边不会与已经加⼊的边构成环,直到树中含有V-1条边为⽌.每⼀步总是连接森林中的两。
算法-第四版-习题-答案1.1.1 给出以下表达式的值：a. ( 0 + 15 ) / 2b. 2.0e-6 * 100000000.1c. true && false || true && true答案：a.7,b.200.0000002 c.ture1.1.2 给出以下表达式的类型和值：a. (1 + 2.236)/2b. 1 + 2 + 3 + 4.0c. 4.1 >= 4d. 1 + 2 + "3"答案：a.1.618 b. 10.0 c.true d.331.1.3 编写一个程序，从命令行得到三个整数参数。
如果它们都相等则打印equal，否则打印not equal。
public class TestUqual{public static void main(String[] args){int a,b,c;a=b=c=0;StdOut.println("Please enter three numbers");a =StdIn.readInt();b=StdIn.readInt();c=StdIn.readInt();if(equals(a,b,c)==1){StdOut.print("equal");}else{StdOut.print("not equal");}}public static int equals(int a ,int b , int c){if(a==b&&b==c){return 1;}else{return 0;}}}1.1.4 下列语句各有什么问题（如果有的话）？a. if (a > b) then c = 0;b. if a > b { c = 0; }c. if (a > b) c = 0;d. if (a > b) c = 0 else b = 0;答案：a. if (a > b) c = 0; b. if (a > b) { c = 0; }1.1.5 编写一段程序，如果double 类型的变量x 和y 都严格位于0 和1 之间则打印true，否则打印false。
public class TestUqual{public static void main(String[] args){double x;double y;x=StdIn.readDouble();y=StdIn.readDouble();StdOut.print(compare(x)&& compare(y));}public static boolean compare(double x){If(x>0&&x<1)returen ture;elsereturn false;}}1.1.6 下面这段程序会打印出什么？int f = 0;int g = 1;for (int i = 0; i <= 15; i++){StdOut.println(f);f = f + g;g = f - g;}答案：0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 6101.1.7 分别给出以下代码段打印出的值：a. double t = 9.0;while (Math.abs(t - 9.0/t) > .001) t = (9.0/t + t) / 2.0;StdOut.printf("%.5f\n", t);b. int sum = 0;for (int i = 1; i < 1000; i++)for (int j = 0; j < i; j++)sum++;StdOut.println(sum);c. int sum = 0;for (int i = 1; i < 1000; i *= 2) for (int j = 0; j < 1000; j++)sum++;StdOut.println(sum);答案：a.3.00009 b.499500 c. 100001.1.8 下列语句会打印出什么结果？给出解释。
a. System.out.println('b');b. System.out.println('b' + 'c');c. System.out.println((char) ('a' + 4)); 答案：a. b b. 197 c. e1.1.9 编写一段代码，将一个正整数N 用二进制表示并转换为一个String 类型的值s。
解答：Java 有一个内置方法Integer.toBinaryString(N) 专门完成这个任务，但该题的目的就是给出这个方法的其他实现方法。
下面就是一个特别简洁的答案：String s = "";for (int n = N; n > 0; n /= 2)s = (n % 2) + s;1.1.10 下面这段代码有什么问题？int[] a;for (int i = 0; i < 10; i++)a[i] = i * i;解答：它没有用new 为a[] 分配内存。
这段代码会产生一个variable a might not havebeen initialized 的编译错误。
1.1.11 编写一段代码，打印出一个二维布尔数组的内容。
其中，使用* 表示真，空格表示假。
打印出行号和列号。
public class Test {public Test() {// TODO Auto-generated constructor stub}public static void main(String[] args) {// TODO Auto-generated method stubboolean[][] a = new boolean[10][10];a=RandomInitial(a);//随机初始化TestPrint(a);//打印数组}public static void TestPrint(boolean [][] a){for(int i=0;i<a.length;i++)//打印行号StdOut.print(" "+i);StdOut.println(" ");for(int i=0;i<10;i++){StdOut.print(i);for(int j=0;j<10;j++){if(a[i][j])StdOut.print("*"+" ");elseStdOut.print(" "+" ");}StdOut.println(" ");}}public static boolean[][] RandomInitial( boolean [][] a){for(int i=0;i<a.length;i++){for(int j=0;j<a.length;j++){if(StdRandom.bernoulli(0.1))a[i][j]=true;elsea[i][j]=false;}}return a;}}1.1.12 以下代码段会打印出什么结果？int[] a = new int[10];for (int i = 0; i < 10; i++)a[i] = 9 - i;for (int i = 0; i < 10; i++)a[i] = a[a[i]];for (int i = 0; i < 10; i++)System.out.println(i);答案：0 1 2 3 4 5 6 7 8 9如System.out.println(a[i]);0 1 2 3 4 4 3 2 1 01.1.13 编写一段代码，打印出一个M 行N 列的二维数组的转置（交换行和列）。
public class Migrate {public Migrate() {// TODO Auto-generated constructor stub}public static void main(String[] args) {// TODO Auto-generated method stubint m=5;int n=5;int [][] a=new int [m][n];int [][] b=new int [n][m];a=RandomInitial(a,n); //初始化二维数组b=MigrateArrays(a,b); //转置二维数组MigratePrint(b);//输出转置二维数组}public static void MigratePrint(int [][] a){StdOut.println("输出转置二维数组:");for (int i=0;i<a.length;i++){f or(int j=0;j<a[0].length;j++){StdOut.print(a[i][j]+" ");}S tdOut.println();}}public static int[][] MigrateArrays(int [][] a,int [][] b){for (int i=0;i<a.length;i++){f or(int j=0;j<a[0].length;j++){b[j][i]=a[i][j];}}return b;}public static int[][] RandomInitial(int [][] a,int N){StdOut.println("初始化二维数组:");for (int i=0;i<a.length;i++){for(int j=0;j<a[0].length;j++){a[i][j]=StdRandom.uniform(N);StdOut.print(a[i][j]+" ");}StdOut.println();}return a;}}1.1.14 编写一个静态方法lg()，接受一个整型参数N，返回不大于log2N 的最大整数。
不要使用Math 库。
public static int lga(int N,int M){int a=0;while(N>=M){N=N/M;a++;}return a;}1.1.15 编写一个静态方法histogram()，接受一个整型数组a[] 和一个整数M 为参数并返回一个大小为M的数组，其中第i个元素的值为整数i在参数数组中出现的次数。
