算法设计方案分析晓东
习题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'=100n
n'^2=100n^2得到n'=10n
n'^3=100n^3得到n'=4.64n
n'!=100n!得到n' 习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。 解答：（1）f(n)=logn^2。g(n)=logn+5. logn^2=θ（logn+5） (2)f(n)=logn^2。g(n)=根号n. logn^2=O(根号n) (3)f(n)=n。g(n)=(logn)^2. n=Ω(（logn）^2) (4)f(n)=nlogn+n。g(n)=logn. nlogn+n=Ω（logn） (5)f(n)=10。g(n)=log10. 10=θ(log10) (6)f(n)=(logn)^2。g(n)=logn. (logn)^2=Ω（logn） (7)f(n)=2^n。g(n)=100n^2. 2^n=Ω（100n^2） (8)f(n)=2^n。g(n)=3^n. 2^n=O(3^n) 习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为θ（f(n)），则该算法在最坏情况下所需的计算时间为Ω（f(n)）。 证明：Tavg(N)=IeDn∑P(I)T(N,I) ≤IeDn∑P(I)IeDnmaxT(N,I') =T(N,I*)IeDn∑P(I) =T(N,I*)=Tmax(N) 因此，Tmax(N)=Ω（Tavg(N)）=Ω（θ(f(n))）=Ω（f(n)） 习题2-8 求解下列递归方程： So=0。 Sn=2Sn-1+2^n-1. 解答： 1应用零化子化为齐次方程， 2解此齐次方程的特征方程， 3由特征根构造一般解， 4再由初始条件确定待定系数，得到解为：Sn=(n-1)2^n+1 习题2-9 求解下列递归方程 Ho=2。 H1=8。 Hn=4Hn-1-4Hn-2. 解：Hn=2^(n+1)(n+1) 第三章递归与分治策略 习题3-1 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。 public static int binarySearch1(int []a,int x,int n) { int left=0。int right =n-1。 while (left<=right) { int middle = ( left + right )/2。 if ( x == a[middle]) return middle。 if ( x> a[middle]) left = middle。 else right = middle。 return -1。 } public static int binarySearch2(int []a, int x, int n) { int left = 0。int right = n-1。 while ( left < right-1 ) { int middle = ( left + right )/2。 if ( x < a[middle]) right = middle。 else left = middle。 } if (x == a[left]) return left。 else return -1 } public static int binarySearch3(int []a, int x, int n) { int left = 0。int right = n-1。 while ( left +1 != right) { int middle = ( left + right)/2。 if ( x>= a[middle]) left = middle。 else right = middle。 } if ( x == a[left]) return left 。 else return -1。 } public static int binarySearch4(int []a, int x, int n) { if (n>0 && x>= a[0]) { int left = 0。int right = n-1。 while (left < right ) { int middle = (left + right )/2。 if ( x < a[middle]) right = middle -1 。 else left = middle。 } if ( x == a[left]) return left。 } return -1。 } public static int binarySearch5(int []a, int x, int n) { if ( n>0 && x >= a[0] ) { int left = 0。int right = n-1。 while (left < right ) { int middle = ( left + right +1)/2。 if ( x < a[middle]) right = middle -1。 else left = middle 。 } if ( x == a[left]) return left。 } return -1。 } public static int binarySearch6(int []a, int x, int n) { if ( n>0 && x>= a[0]) { int left = 0。int right = n-1。 while ( left < right) { int middle = (left + right +1)/2。 if (x < a[middle]) right = middle – 1。 else left = middle + 1。 } if ( x == a[left]) return left 。 } return -1。 } public static int binarySearch7(int []a, int x, int n) { if ( n>0 && x>=a[0]) { int left = 0。int right = n-1。 while ( left < right) { int middle = ( left + right + 1)/2。 if ( x < a[middle]) right = middle。 else left = middle。 } if ( x == a[left]) return left。 } return -1。 } 分析与解答： 算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。 算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。 算法binarySearch3数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。 算法binarySearch4数组段左右游标left和right的调整不正确，导致陷入死循环。 算法binarySearch5正确，且当数组中有重复元素时，返回满足条件的最右元素。 算法binarySearch6数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。 算法binarySearch7数组段左右游标left和right的调整不正确，导致当x=a[n-1]时陷入死循环。 习题3-2 设a[0:n-1] 是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 分析与解答： 改写二分搜索算法如下： public static boolean binarySearch(int []a, int x, int left, int right, int []ind) { int middle。 while ( left <= right ) { middle = (left + right)/2。 if (x == a[middle]) { ind[0]=ind[1]=middle。return true。} if (x > a[middle]) left = middle + 1。 else right = middle -1。 } ind[0] = right。ind[1]=left。 return false。 } 返回的ind[1]是小于x的最大元素位置，ind[0]是大于x的最小元素的位置。 习题3-3 设a[0:n-1] 是有n个元素的数组，是非负整数。试设计一个算法讲子数组与换位。要求算法在最坏情况下耗时为，且只用到的辅助空间。 分析与解答： 算法：三次求反法 Algorithm exchange(a, k, n)。 Begin Inverse(n,0,k-1)。inverse(n,k,n-1)；inverse（n,0,n-1） End. Algorithm inverse(a, i, j)。 Begin h=[(j-i+1)/2] 。 For k=0 to h-1 do Begin x=a[i+k]。a[i+k]=a[j-k]。a[j-k]= x end 。 end 习题3-4 如果在合并排序算法的分割步中，讲数组a[0。n-1] 划分为[根号2】个子数组，每个子数组中有个元素。然后递归地对分割后的子数组进行排序，最后将所得到的个排好序的子数组合并成所要求的排好序的数组。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。 分析与解答： 实现上述策略的合并排序算法如下： public static void mergesort(int []a, int left ,int right) { if (left < right ) { int j = (int) Math.sqrt(right –left+1)。 if (j>1) { for (int i=0。i mergesort(a,left+i*j,right)。 } mergeall(a,left,right)。 } } 其中，算法mergeall合并根号n 个排好序的数组段。在最坏情况下，算法mergeall需要O（nlogn) 时间。因此上述算法所需的计算时间T(n)满足： T(n)=O(1),n<=1 T(n)=根号n*T(根号n),n>1 T(n)=O(nlogn) 此递归式的解为：。 习题3-5 设S1,S2...Sk 是整数集合，其中每个集合中整数取值范围是，且，试设计一个算法，在时间内将分别排序。 分析与解答： 用桶排序或基数排序算法思想可以实现整数集合排序。 习题3-6 设X[0:n-1] 和Y[0:n-1] 为两个数组，每个数组中还有n个已排好序的数。试设计一个时间的算法，找出X和Y的2n个数的中位数。 分析与解答： （1）算法设计思想 考虑稍一般的问题：设X[i1:j1] 和y[i2。j2] 是X和Y的排序好的子数组，且长度相同，即j1-i1=j2-i2 。找出这两个数组中2(i1-j1+1) 个数的中位数。 首先注意到，若X(i1)<=Y(j2) ，则中位数median满足X(i)<=median<=Y(j2) 。同理若X(i1)>=Y(j2) ，则Y(j2)<=median<=X(i1) 。 设m1=(i1+j1)/2,m2=(i2+j2)/2 ，则m1+m2=i1+i2+(j1-i1)/2+(j2-i2)/2 由于j1-i1=j2-i2 ，故(j1-i1)/2+(j2-i2)/2=j2-i2。 因此m1+m2=i1+j2 。 当X(m1)=Y(m2) 时，median=X(m1)=Y(m2) 。 当X(m1)>Y(m2) 时，设median1 是X(m1:j1) 和Y(j2:m2) 的中位数，则median=median1 。 当X(m1) 通过以上讨论，可以设计出找出两个子数组X(i1:j1) 和Y(i2:j2) 的中位数median的算法。 （2）设在最坏情况下，算法所需的计算时间为T(2n) 。由算法中m1 和m2 的选取策略可知，在递归调用时，数组X和Y的大小都减少了一半。因此，T(2n) 满足递归式： T(2n)=(1),n<=1 T(2n)=T(n)+O(1),n>=c 解此递归方程可得：T(2n)=O(logn) 。 习题3-7 Gray码是一个长度为2^n 的序列。序列中无相同元素，每个元素都是长度为n位的（0，1）串，相邻元素恰好只有1位不同。用分治策略设计一个算法，对任意的n构造相应的Gray码。 分析与解答： 考察的简单情形。 n=1 0 1 n=2 00 01 11 10 n=3 000 001 011 010 110 111 101 100 设n位Gray码序列为G(n) 以相反顺序排列的序列为G^-1(n)。从上面的简单情形可以看出G(n) 的构造规律：G(n+1)=OG(n)1G^-1(n) 。 注意到G(n) 的最后一个n位串与G^-1(n) 的第1个n位串相同，可用数学归纳法证明G(n) 的上述构造规律。由此规律容易设计构造G(n) 的分治法如下。 public static void Gray(int n) { if ( n == 1) { a[1] = 0。a[2] = 1。return。} Gray(n-1)。 for ( int k = 1<< ( n - 1), i = k。i > 0。i--) a[2*k-i+1]=a[i] + k。 } 上述算法中将n位（0，1）串看做是二进制整数，第i个串存储在中。 完成计算之后，由out输出Gray码序列。 public static void out(int n) { int m=1< for (int i=1。i<=m。i++) { String str=Integer.toBinaryString(a[i])。 int s=str.length()。 for ( int j=0。j System.out.println(Integer.toBinaryString(a[i])+” ”)。 } System.out.println()。 } 第四章动态规划 习题4-1 设计一个时间的算法，找出由n个数组成的序列的最长单调递增子序列。 分析与解答： 引入一个数组b，使b[i]为已扫描部分的长度为ｉ的升序子序列的最小终值。 按此思想设计的动态规划算法描述如下： j:=0。b[0]:=-maxint。 FOR i:=1 TO n DO IF a[i]>b[j] THEN BEGIN j:=j+1。b[j]:=a[i]。END ELSE BEGIN k:=1。 while a[i]>b[k] DO k:=k+1。 b[k]:=a[i]。 END。 习题4-2 考虑下面的整数线性规划问题： 为非负整数， 试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。 分析与解答： 该问题是一般情况下的背包问题，具有最优子结构性质。 设所给背包问题的子问题：max∑CkXk(1..i)∑AkXk<=j 的最优值为m(i,j) ，即m(i,j)是背包容量为j，可选择物品为1，2，…，i时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算m(i,j）的递归式如下： m(i,j)=max{m(i-1,j),m(i,j-ai)+ci} j>=ai, m(i,j)=m(i-1,j),0<=j,ai m(0,j)=m(i,0)。m(i,j)=-*,j<0 按此递归式计算出的m(n,b) 为最优值。算法所需的计算时间为O(nb) 。 习题4-3 给定一个由n行数字组成的数字三角形如图3-2所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 分析与解答： 记f(uij)为至ij元素的最大路径值, aij ：元素(i,j)之值。 递归式: F(uij)=max{f(ui-1,j)+aij, f(ui-1,j+1)+aij} (i=1,…n，j=1,…i) 经过一次顺推，便可求出从顶至底n个数的n条路径（这n条路径为至底上n个数的n个最大总和的路径），求出这n个总和的最大值，即为正确答案。 数据结构: a[i,j].val: 三角形上的数字， a[i,j].f: 由（1，1）至该点的最大总和路径的总和值。 type node=record val, f: integer。 end。 var a:array [1.. maxn, 1..maxn] of node。 procedure findmax。 begin a [1,1]. f :=a[1,1].val。 for i:=2 to n do for j:=1 to i do begin a[i,j]. f:=-1。 if (j<>1) and (a [i-1,j-1].f+a[i,j].val > a [i,j].f) then a[i,j]. f:=a [i-1,j-1]. f+a[i,j].val。 if (j<>i) and(a [i-1,j].f+a[i,j].val > a[i,j].f) then a[i,j]. f:=a[i-1,j]. f+a[i,j]. val end。 max:=1。 for i:=2 to n do if a[n,i]. f> a[n, max] .f then max:=i。 writeln (a [n, max]. f) end。 第五章贪心算法 习题5-1 特殊的0-1背包问题 若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，设计一个有效算法找出最优解，并说明算法的正确性。 分析与解答： 设所给的输入为W>0，wi>1,vi>0,1≤i≤n。不妨设0≤w1≤w2≤..≤wn。由题意知v1≥v2≥..≥vn>0。由此可知vi/wi≥vi+1/wi+1，1≤i≤n-1. 贪心选择性质： 当w1>W时问题无解。 当w1≤W时，存在0-1背包问题的一个最优解S包含｛1,2,..,n｝使得1∈S。 事实上，设S包含｛1,2,..,n｝使0-1背包问题的一个最优解，且1不∈S。对任意i∈S，取Si=S∪{1}-{i}，则Si满足贪心选择性质的最优解。 习题5-2 Fibonacci序列的Huffman编码 试证明：若n个字符的频率恰好是前n个Fibonacci数，用贪心法得到它们的Huffman编码树一定为一棵“偏斜树”。 证明：n个字符的频率恰好是前n个Fibonacci数，则相应的哈夫曼编码树自底向上第i个内结点中的数为k=0∑if(k)。用数学归纳法容易证明k=0∑ifk 因f1=1,f2=1,f3=2,可知i=1时，上述结论成立。 设对i+2上述结论成立，即有k=0 ∑ i fk fi+3=fi+2 + fi+1>k=1 ∑ i fk + fi+1= k=1 ∑ i+1 fk， 说明对i+3上述结论成立. 该性质保证了频率恰好是前n个Fibonacci数的哈夫曼编码树具有“偏斜树”形状。 习题5-3 记T为图G= (V, E) 的最小生成树，同时设顶点集合A包含V，设(u, v) ∈E 为连接A 和V–A 的权重最小的边，证明：必有(u, v) ∈T. 证明： 用反证法。因为T为图G= (V, E) 的最小生成树，在连接A 和V–A的边中至少有一条属于T中。假设(u, v) 不属于T，则必有(u’, v’) 属于T, 这里(u’, v’) 也是连接A 和V–A的边, 且(u’, v’)的权重大于(u, v) 的权重. 若将T中的(u’, v’)换成(u, v)得到T’, 显然T’也是G的一个生成树。但由于(u’, v’)的权重大于(u, v) 的权重，可知T的权重大于T’ 的权重，这与” T为图G= (V, E) 的最小生成树” 矛盾。 习题5-4 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 分析与解答： 设所给的n个活动为1，2，…，n，它们的开始时间和结束时间分别为s[i]和f[i]，i=1~n，且 f[1] 可以将n个活动1，2，…，n看作实直线上的n个半闭活动区间(s[i],f[i],i=1~n)。所讨论的问题实际上是求这n个半闭区间的最大重叠数。因为重叠的活动区间所相应的活动是互不相容的。若这n个活动区间的最大重叠数为m，则这m个重叠区间所对应的活动互不相容，因此至少安排m个会场来容纳这m个活动。 为了有效地对这n个活动进行安排，首先将n个活动区间的2n个端点排序。然后，用扫描算法，从左到右扫描整个实直线。在每个事件点处（即活动的开始时刻或结束时刻）作会场安排。当遇到一个开始时刻s[i]，就将活动i安排在一个空闲的会场中。遇到一个结束时候f[i]，就将活动i占用的会场释放到空闲会场栈中，以备使用。经过这样一遍扫描后，最多安排了m个会场（m是最大重叠区间数）。因此所作的会场安排是最优的。上述算法所需的计算时间主要用于对2n个区间端点的排序，这需要O(nlogn)计算时间。具体算法描述如下。 public static int greedy(point []x) { int sum=0, curr=0, n=x.length。 MergeSort.mergeSort(x)。 for (int i=0。i if (x[i].leftend()) curr++。 else curr--。 //处理x[i]=x[i+1]的情况 if (( i == n-1∣∣x[i].compareTo(x[i+1])<0)&& curr>sum) sum=curr。 } return sum。 } 习题5-5 假设要在m个会场里安排一批活动，并希望使用尽可能多地安排活动。设计一个有效的贪心算法进行安排。 Algorithm greedy(s,f,m,n)。 Input s[1:n], f[1:n]。 Output x[1:m, 1:n]。 Begin 对数组s和f中的2n个元素排序存入数组y[1:2n]中； 空闲栈清空；d数组所有元素置初值0； For i=1 to 2n do Begin If 元素y[i] 原属于s then If 空闲栈不空then 取出栈顶场地j。d[j]=d[j]+1。y[i] 存入x[j, d[j] ]。 If 元素y[i] 原属于f then 设其相应的s 存于x[j,k] 中，将j存入空闲栈中； End For i= 1 to m do For j=1 to d[j] do Output x[i,j]。 End 习题5-6 删数问题 问题描述 给定n位正整数a，去掉其中任意个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n 位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。 分析与解答： 贪心策略：最近下降点优先。 public static void delek(String a) { int i,m=a.length()。 if ( k>= m) {System.out.println(0)。return。} while (k>0) { for (i=0。(i a= a.Remove(i,1)。k--。 } while (a.length()>1 && a.charAt(0)==’0’) a=a.Remove(0,1)。 System.out.println(a)。 } 第六章回溯法 习题6-1 子集和问题 子集和问题的一个实例。其中，是一个正整数的集合，sum是一个正整数。子集和问题判定是否存在A 的一个子集A1，使得。 试设计一个解子集和问题的回溯法。 分析与解答： 设计解子集和问题的回溯法如下。 Algorithm subset-sum begin For j=1 to n do Begin sp=0。t=sum。i=j。finish=false。 repeat if t>=a[i] then begin sp=sp+1；s[sp]=i。t=t-a[i]。if t=0 then i=n。 end。 i=i+1。 while i>n do if sp>1 then begin if t=0 then out。t=t+a[s[sp]]。i=s[sp]+1。sp=sp-1 end else begin finish=true。i=1 end until finish end end 习题6-2 中国象棋的半个棋盘如图所示，马自左下角往右上角跳。规定只许向右跳，不许向左跳，计算所有的行走路线。 Algorithm chess Begin top=0。y0=0。x0=0。di=1。r=0。 push。 repeat pop。 while di<=4 do begin g=x0+x[di]。h=y0+y[di]。 if (g=8) and (h=4) then out else begin di=di+1；push。x0=g。y0=h。di=1 end end until empty end algorithm push begin top=top+1；sx[top]=x0。sy[top]=y0。d[top]=di。 end algorithm pop begin x0=sx[top]。y0=sy[top]。di =d[top]。top=top－1； end 习题6-3. 在n个连成排的方格内填入R或B，但相邻连个方格内不能都填R。计算所有可能的填法。R B B R B Algorithm Red-Black。 Begin For i=1 to n do b[i]=0。 T=1。 Repeat b[t]=b[t]+1 。 if b[t]>2 then {回溯} begin b[t]=0 。t=t-1 。end else begin if b[t]=2 the n a[t]= ‘B’ else if a[t-1]=’R’ then t=t-1 else a[t]=‘R’。 if t=n then output a else t=t+1 end until t=0 第七章分支限界法 习题7-2. 写出用分支界限法求解下面的重排九宫问题的算法。 解答： 我们对九宫中的位置做如下的编号： 位置编号 1 2 3 8 9 4 7 6 5 则初始状态用向量S0=（8，1，2，3，4，5，7，0，6）表示，目标状态用S*=（1，2，3，4，5，6，7，8，0）表示。 我们使用一个堆heap, 将启发函数值H(x)最小的状态x置于堆顶优先搜索。H(x)定义如下： H(x)=h1(x)+3h2(x) 其中，h1(x)为状态x与目标状态不相同的数字的数目，h2（x)= y=e ∑N(y) ， 这里， N(y)=0,y和其后继的相对位置不变 N(y)=1,y处于中心 N(y)=2,q其他 算法： Algorithm LC(S0, S*) Input: 初始状态向量S0 , 目标状态S*； Output: 达到目标状态的状态序列； Begin S=S0。 if S目标状态S* then Output(S及其所有前驱) else add (S, heap) while heap非空do 取出堆heap顶部状态E ； for E 的每个可能的后继状态x do if x为目标状态S* then Output(x及其所有前驱)。return else 计算x的启发函数H(x)。 add(x, heap) endif endfor endwhile end 第八章NP完全问题 习题8-1 证明析取范式的可满足性问题属于P类。 分析与解答： 析取范式α是由因子之和的和式给出的。这里因子是指变量x或x拔，每个因子之积称为一个析取式。例如x1x2+x2x3+ x3就是一个析取范式。 设给定一个析取范式α= i=1 ∑ m fi(x1,x2,x3,...,xn)，其中fi(x1,x2,..,xn) 是变量xj 或xj拔，j=1~n 的一个析取范式，i=1~m。α是可满足的，当且仅当存在i, 1≤i≤m ，使fi(x1,x2,..,xn) 是可满足的。如果有一个多项式时间算法能判断任何一个析取式的可满足性，则用该算法对α的每个析取项逐一判断就可以在多项式时间内确定析取范式α的可满足性。因此，问题可简化为找一个确定析取式可满足性的多项式时间算法。 设析取范式f(x1,x2,..,xn) =α1α2..αk ，其中αi∈{xj,｜1≤j≤n} 。 可以设计在O(n+k)时间内确定析取式f(x1,x2,..,xn)=α1α2...αn可满足性的算法。因此，析取范式的可满足性问题是多项式时间可解的，即它属于P类。 网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 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。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解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的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311. 习题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'=100n n'^2=100n^2得到n'=10n n'^3=100n^3得到n'=4.64n n'!=100n!得到n' 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x = 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 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 ） 第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 统计分析方法有哪几种？下面天互数据将详细阐述，并介绍一些常用的统计分析软件。 一、指标对比分析法指标对比分析法 统计分析的八种方法一、指标对比分析法指标对比分析法，又称比较分析法，是统计分析中最常用的方法。是通过有关的指标对比来反映事物数量上差异和变化的方法,有比较才能鉴别。 指标分析对比分析方法可分为静态比较和动态比较分析。静态比较是同一时间条件下不同总体指标比较，如不同部门、不同地区、不同国家的比较，也叫横向比较；动态比较是同一总体条件不同时期指标数值的比较，也叫纵向比较。 二、分组分析法指标对比分析法 分组分析法指标对比分析法对比，但组成统计总体的各单位具有多种特征，这就使得在同一总体范围内的各单位之间产生了许多差别，统计分析不仅要对总体数量特征和数量关系进行分析，还要深入总体的内部进行分组分析。分组分析法就是根据统计分析的目的要求，把所研究的总体按照一个或者几个标志划分为若干个部分，加以整理，进行观察、分析，以揭示其内在的联系和规律性。 统计分组法的关键问题在于正确选择分组标值和划分各组界限。 三、时间数列及动态分析法 时间数列。是将同一指标在时间上变化和发展的一系列数值，按时间先后顺序排列，就形成时间数列，又称动态数列。它能反映社会经济现象的发展变动情况，通过时间数列的编制和分析，可以找出动态变化规律，为预测未来的发展趋势提供依据。时间数列可分为绝对数时间数列、相对数时间数列、平均数时间数列。 时间数列速度指标。根据绝对数时间数列可以计算的速度指标：有发展速度、增长速度、平均发展速度、平均增长速度。 动态分析法。在统计分析中，如果只有孤立的一个时期指标值，是很难作出判断的。如果编制了时间数列，就可以进行动态分析，反映其发展水平和速度的变化规律。 HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日 一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。 绪论第1章 √(2)×(3)2.(1)×C ）C（3（1）A（2）3. 的语句频度5.计算下列程序中x=x+1for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 的语句频度为：【解答】x=x+1=n(n+1)(n+2)/6 ）+……+（1+2+……+n）T(n)=1+(1+2)+（1+2+3 并确定算法中每一),p(xx+ax+a+…….+ax的值6.编写算法，求一元多项式p(x)=a n20nn20n1规定算法中不能使用要求时间复杂度尽可能小，语句的执行次数和整个算法的时间复杂度，算法的输入和输出)。n,输出为P(x求幂函数。注意：本题中的输入为a(i=0,1,…n)、x和0in采用下列方法1）通过参数表中的参数显式传递（）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实（2 现输入输出。【解答】1）通过参数表中的参数显式传递（优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用 性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。 ）通过全局变量隐式传递（2 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数PolyValue() { int i,n; float x,a[],p; nn=”);printf(“\ scanf(“%f”,&n); nx=”);printf(“\ scanf(“%f”,&x); for(i=0;i 一、描述统计 描述性统计是指运用制表和分类，图形以及计筠概括性数据来描述数据的集中趋势、离散趋势、偏度、峰度。 1、缺失值填充：常用方法：剔除法、均值法、最小邻居法、比率回归法、决策树法。 2、正态性检验：很多统计方法都要求数值服从或近似服从正态分布，所以之前需要进行正态性检验。常用方法：非参数检验的K-量检验、P-P图、Q-Q图、W检验、动差法。 二、假设检验 1、参数检验 参数检验是在已知总体分布的条件下（一股要求总体服从正态分布）对一些主要的参数(如均值、百分数、方差、相关系数等）进行的检验。 1）U验使用条件：当样本含量n较大时，样本值符合正态分布 2）T检验使用条件：当样本含量n较小时，样本值符合正态分布 A 单样本t检验：推断该样本来自的总体均数μ与已知的某一总体均数μ0 (常为理论值或标准值)有无差别； B 配对样本t检验：当总体均数未知时，且两个样本可以配对，同对中的两者在可能会影响处理效果的各种条件方面扱为相似； C 两独立样本t检验：无法找到在各方面极为相似的两样本作配对比较时使用。 2、非参数检验 非参数检验则不考虑总体分布是否已知，常常也不是针对总体参数，而是针对总体的某些一股性假设（如总体分布的位罝是否相同，总体分布是否正态）进行检验。适用情况：顺序类型的数据资料，这类数据的分布形态一般是未知的。 A 虽然是连续数据，但总体分布形态未知或者非正态； B 体分布虽然正态，数据也是连续类型，但样本容量极小，如10以下； 主要方法包括：卡方检验、秩和检验、二项检验、游程检验、K-量检验等。 三、信度分析 检査测量的可信度，例如调查问卷的真实性。 分类： 1、外在信度：不同时间测量时量表的一致性程度，常用方法重测信度 2、内在信度；每个量表是否测量到单一的概念，同时组成两表的内在体项一致性如何，常用方法分半信度。 四、列联表分析 用于分析离散变量或定型变量之间是否存在相关。 算法设计与分析(第2版)-王红梅-胡明-习题 答案 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783） 提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图 1.7是这条河以及河上的两个岛和七座桥的 草图。请将该问题的数据模型抽象出来，并判 断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n 2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 图1.7 七桥问题 #include 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 第一章习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型 （5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作 （9）有限性、输入、可行性 4、（1）A（2）C（3）C 5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定 （4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A B：H、L、I、E、A C：F、M D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下： int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)； return(0); } while(i<=L->last&&L->elem[i] L->last++; return(1); } 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2)) { printf(“输入的i，k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink 一、选择题（多选） 1.算法必须满足哪些条件？ 算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足条件： (1)输入：有零个或多个由外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 2.哪些问题比较适合用递归算法？ 阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题分治策略（是高级的递归算法）：（1）二分搜索技术、（2）大整数的乘法、（3）Strassen 矩阵乘法、（4）棋盘覆盖、（5）合并排序、（6）快速排序、（7）线性时间选择、（8）最接近点对问题、（9）循环赛日程表 3. 哪些问题比较适合用贪心算法？ （1）活动安排问题（2）最优装载问题（3）哈夫曼编码（4）单源最短路径（5）最小生成树（6）多机调度问题 4. 哪些问题比较适合用回溯法？ （1）装载问题（2）批处理作业调度（3）符号三角形问题（4）n后问题（5）0-1背包问题（6）最大团问题（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题 二、概念题 1.递归的概念是什么？ 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。2.什么是0-1背包问题？ 给定n种物品和一个背包：物品i的重量是wi，其价值为vi，背包的容量为C。选择装入背包的物品，对于每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能只装入部分的物品i，最终要使得装入背包中物品的总价值最大。该问题被称为0-1背包问题。 3.什么是哈夫曼编码，它有什么优缺点？ 由哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼编码是广泛地用于数据文件压缩。用于数据的无损耗压缩。其压缩率通常在20%～90%之间。 优点：给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。 缺点：依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，而实际应用中，通常可在经验基础上预先提供Huffman码表，此时其性能有所下降。 4.什么是图的m着色问题？ 给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2的顶点着有不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称现这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。 5.什么是单源最短路径问题？ Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。 数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。 结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" void main() { int n,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 《算法设计与分析》课程实验与设计 福州大学王晓东 第1章算法引论 算法实现题1-1 统计数字问题 算法实现题1-2 字典序问题 算法实现题1-3 最多约数问题 算法实现题1-4 金币阵列问题 算法实现题1-5 最大间隙问题 第2章递归与分治策略 算法实现题2-1 输油管道问题 算法实现题2-2 众数问题 算法实现题2-3 邮局选址问题 算法实现题2-4 马的Hamilton周游路线问题 算法实现题2-5 半数集问题 算法实现题2-6 半数单集问题 算法实现题2-7 士兵站队问题 算法实现题2-8 有重复元素的排列问题 算法实现题2-9 排列的字典序问题 算法实现题2-10 集合划分问题 算法实现题2-11 集合划分问题2 算法实现题2-12 双色Hanoi塔问题 算法实现题2-13 标准2维表问题 算法实现题2-14 整数因子分解问题 算法实现题2-15 有向直线2中值问题 第3章动态规划 算法实现题3-1 独立任务最优调度问题 算法实现题3-2 最少硬币问题 算法实现题3-3 序关系计数问题 算法实现题3-4 多重幂计数问题 算法实现题3-5 编辑距离问题 算法实现题3-6 石子合并问题 算法实现题3-7 数字三角形问题 算法实现题3-8 乘法表问题 算法实现题3-9 租用游艇问题 算法实现题3-10 汽车加油行驶问题 算法实现题3-11 圈乘运算问题 算法实现题3-12 最少费用购物 算法实现题3-13 最大长方体问题 算法实现题3-14 正则表达式匹配问题 算法实现题3-15 双调旅行售货员问题 算法实现题3-16 最大k乘积问题 算法实现题3-17 最小m段和问题 算法实现题3-18 红黑树的红色内结点问题 第4章贪心算法 算法实现题4-1 会场安排问题 算法实现题4-2 最优合并问题 算法实现题4-3 磁带最优存储问题 算法实现题4-4 磁盘文件最优存储问题 第一章绪论 1.数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。 2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据元素的组成：一个数据元素通常由一个或若干数据项组成。 数据项：指具有独立含义的最小标识单位。 3.数据对象：性质相同的数据元素的集合，是数据的一个子集。 4.数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所定义的算法在计算机上运行的学科。 5.算法：是对待定问题求解步骤的一种描述，是指令的有限序列。算法应满足以下性质： 1)输入性：具有零个或若干个输入量； 2)输出性：至少产生一个输出； 3)有穷性：每条指令的执行次数是有限的； 4)确定性：每条指令的含义明确，无二义性； 5)可行性：每条指令都应在有限的时间内完成。 6.评价算法优劣的主要指标： 1)执行算法后，计算机运行所消耗的时间，即所需的机器时间； 2)执行算法时，计算机所占存储量的大小，即所需的存储空间； 3)所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。 7.会估算某一算法的总执行时间和时间复杂度。 8.熟悉习题P32:3(5)-(9)、4(2)(3) 第二章线性表 1.线性表(P7)：是性质相同的一组数据元素序列。 线性表的特性： 1)数据元素在线性表中是连续的，表中数据元素的个数可以增加或减少，但调整后数据元素仍必须是连续的，即线性表是一种线性结构。 2)数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。 3)线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。 线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。 线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元，这种存储方法叫做顺序分配，又称顺序映像。其特点：逻辑上相邻的数据元素， 它们的物理次序也是相邻的。)，存储地址的计算方式(Loc(a i )=Loc(a )+i*s)。 2.线性表的查找、插入和删除 熟悉线性表的查找算法(P38)、插入算法(P39)和删除算法(P40)。 3.理解线性表的顺序存储结构的优缺点。 4.熟悉线性链表的存储结构(P43) 线性链表(由若干结点链接而成的一种存储结构。)、结点(由存放数据元素值的部分—数据域和存放另一元素存储地址的部分—指针域或链域两部分信息组成的存储结构。)、单链表(线性链表)的概念。 5.熟悉线性链表的建立(P45-47)、查找(P47-48)、插入(P49-50)和删除(P50-51)的算法； 6.明了什么是循环链表(链表中最后一个结点指针域回指向链表的第一个结点，使得整个链表通过链指针成为一个环形，这种形式的链表称为循环链表。)？ 7.明了双向链表的结构(链表中的每个结点有两个指针域，一个是向前链接的左指针(Lnext或prior)，另一个是向后链接的右指针(Rnext或next)，同时还有一个数据域(Data)。)；了解双向链表的插入和删除的算法。 8.理解链表的优缺点(P48)。 9.熟悉习题P68：1、2 第三章限定性线性表----栈和队列 1.栈和队列 明确什么是栈及其特点(只允许在一端进行插入和删除的线性表。允许插入和删除 16种常用的数据分析方法汇总 2015-11-10分类：数据分析评论（0） 经常会有朋友问到一个朋友，数据分析常用的分析方法有哪些，我需要学习哪个等等之类的问题，今天数据分析精选给大家整理了十六种常用的数据分析方法，供大家参考学习。 一、描述统计 描述性统计是指运用制表和分类，图形以及计筠概括性数据来描述数据的集中趋势、离散趋势、偏度、峰度。 1、缺失值填充：常用方法：易9除法、均值法、最小邻居法、比率回归法、决策树法。 2、正态性检验：很多统计方法都要求数值服从或近似服从正态分布，所以之前 需要进行正态性检验。常用方法：非参数检验的K-量检验、P-P图、Q-Q图、W 检验、动差法。 二、假设检验 1、参数检验 参数检验是在已知总体分布的条件下（一股要求总体服从正态分布）对一些主要的参数（如均值、百分数、方差、相关系数等）进行的检验。 1）U验使用条件：当样本含量n较大时，样本值符合正态分布 2）T检验使用条件：当样本含量n较小时，样本值符合正态分布 A单样本t检验：推断该样本来自的总体均数卩与已知的某一总体均数卩0常为理论值或标准值）有无差别； B配对样本t检验：当总体均数未知时，且两个样本可以配对，同对中的两者在可能会影响处理效果的各种条件方面扱为相似； C两独立样本t检验：无法找到在各方面极为相似的两样本作配对比较时使用。 2、非参数检验 非参数检验则不考虑总体分布是否已知，常常也不是针对总体参数，而是针对总体的某些一股性假设（如总体分布的位罝是否相同，总体分布是否正态）进行检验。 适用情况：顺序类型的数据资料，这类数据的分布形态一般是未知的 A 虽然是连续数据，但总体分布形态未知或者非正态； B 体分布虽然正态，数据也是连续类型，但样本容量极小，如10 以下； 主要方法包括：卡方检验、秩和检验、二项检验、游程检验、K-量检验等。 三、信度分析检査测量的可信度，例如调查问卷的真实性。 分类： 1、外在信度：不同时间测量时量表的一致性程度，常用方法重测信度 2、内在信度；每个量表是否测量到单一的概念，同时组成两表的内在体项一致性如何，常用方法分半信度。 四、列联表分析 用于分析离散变量或定型变量之间是否存在相关。对于二维表，可进行卡方检验，对于三维表，可作Mentel-Hanszel 分层分析。 列联表分析还包括配对计数资料的卡方检验、行列均为顺序变量的相关检验。 五、相关分析 研究现象之间是否存在某种依存关系，对具体有依存关系的现象探讨相关方向及相关程度。 1、单相关：两个因素之间的相关关系叫单相关，即研究时只涉及一个自变量和一个因变量； 2、复相关：三个或三个以上因素的相关关系叫复相关，即研究时涉及两个或两个以上的自变量和因变量相关； 3、偏相关：在某一现象与多种现象相关的场合，当假定其他变量不变时，其中两个变量之间的相关关系称为偏相关。 六、方差分析 使用条件：各样本须是相互独立的随机样本；各样本来自正态分布总体；各总体方差相等。 分类1、单因素方差分析：一项试验只有一个影响因素，或者存在多个影响因素时, 只分析一个因素与响应变量的关系2、多因素有交互方差分析：一顼实验有多个影响算法分析与设计复习题及参考答案
算法设计与分析王晓东
算法设计与分析试卷A及答案
算法设计与分析复习题目及答案
最全数据结构课后习题答案(耿国华版[12bb]
大数据的统计分析方法
算法设计与分析课程设计(完整版)
最全数据结构课后习题答案耿国华版
16种常用的数据分析方法汇总
算法设计与分析第2版王红梅胡明习题答案
耿国华数据结构习题答案完整版
(完整版)数据结构---C语言描述-(耿国华)-课后习题答案
算法设计与分析复习题
算法设计与分析基础课后习题答案
算法设计与分析第三版王晓东算法实现题部分答案_可复制编辑!
《算法设计与分析》课程实验与设计 福州大学 王晓东
《数据结构(C语言-耿国华版)》复习大纲
16种统计分析方法-统计分析方法有多少种
- 计算机算法设计与分析(王晓东第4版)第6章
- 《算法设计与分析》
- 《计算机算法设计与分析(第3版)》(王晓东编著) 算法分析题1-6和1-9
- 算法设计与分析第三版王晓东算法实现题部分答案_可复制编辑!
- 计算机算法设计与分析(王晓东第4版)第4章
- 算法设计与分析+王晓东(第三版)第7章
- 计算机算法设计与分析第4版王晓东电子
- 计算机算法设计与分析(第4版) 王晓东习题解答
- 计算机算法设计与分析(第3版)王晓东__第6章
- 计算机算法设计与分析课后题答案(第三版)王晓东
- 计算机算法设计与分析课后题答案(第三版)王晓东
- 算法设计方案书与分析报告王晓东
- 算法设计与分析王晓东
- 算法设计与分析(清华第二版,王晓东)
- 王晓东电子教案计算机算法设计与分析第4版
- 计算机算法设计与分析课后题答案(第三版)王晓东
- 王晓东电子计算机算法设计与分析第4版
- 算法设计与分析王晓东第三版
- 《算法设计与分析》课程实验与设计 福州大学 王晓东
- 计算机算法设计与分析 王晓东第 版