算法设计与分析习题与实验题(12.18)
《算法设计与分析》习题
第一章引论
习题1-1 写一个通用方法用于判定给定数组是否已排好序。
解答：
Algorithm compare(a,n)
Begin
J=1;
While (j If j=n then return true Else While (j If j=n then return true else return false end if End if end 习题1-2 写一个算法交换两个变量的值不使用第三个变量。 解答：x=x+y; y=x-y; x=x-y; 习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件(n2-mn-m2)2=1 且使n2+m2达到最大的m、n。 解答： m:=k; flag:=0; repeat n:=m; repeat l:=n*n-m*n-m*n; if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) if n=0 then m:=m-1 until (flag=1) or (m=0); 第二章基础知识 习题2-1 求下列函数的渐进表达式： 3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。 解答： 3n 2+10n=O （n 2）， n 2/10+2n =O （2n ）， 21+1/n=O （1）， log n 3=O （log n ），10 log3n =O （n ）。 习题2-2 说明O (1)和 O (2)的区别。 习题2-3 照渐进阶从低到高的顺序排列以下表达式：!n ， 3 /22 ,2,20,3,log ,4n n n n n 。 解答：照渐进阶从低到高的顺序为：!n 、 3n 、 2 4n 、2 3n 、20n 、log n 、2 习题2-4 （1） 假设某算法在输入规模为n 时的计算时间为n n T 23)(?=。在某台计算机 上实现并完成该算法的时间为t 秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t 秒内能解输入规模为多大的问题？ （2） 若上述算法的计算时间改进为2)(n n T =，其余条件不变，则在新机器上用 t 秒时间能解输入规模多大的问题？ （3） 若上述算法的计算时间进一步改进为8)(=n T ,其余条件不变，那么在新机 器上用t 秒时间能解输入规模多大的问题？ 解答： （1） 设新机器用同一算法在t 秒内能解输入规模为1n 的问题。因此有 64 /2 3231 n n t ?=?=，解得61+=n n 。 （2） n n n n 8641221==>=。 （3） 由于=)(n T 常数，因此算法可解任意规模的问题。 习题2-5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC 公司同类产品的100倍。对于计算复杂性分别为n ，2n ，3n 和!n 的各算法，若用ABC 公司的计算机能在1小时内能解输入规模为n 的问题，那么用XYZ 公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答： n n 100='。 n n n n 101002 2='=>='。 n n n n 64.41001003 3 3==> ='。 64.6100log !100!+=+<'=>='n n n n n 。 习题2-6对于下列各组函数)(n f 和)(n g ，确定))(()(n g O n f =或 ))(()(n g n f Ω=或))(()(n g n f θ=，并简述理由。 （1）5log )(;log )(2+==n n g n n f 。 （2）n n g n n f = =)(;log )(2。 （3）n n g n n f 2log )(;)(==。 （4）n n g n n n n f log )(;log )(=+=。 （5）10log )(;10)(==n g n f 。 （6）n n g n n f log )(;log )(2==。 （7）2100)(;2)(n n g n f n ==。 （8）n n n g n f 3)(;2)(==。 解答： （1）)5(log log 2 +=n n θ。 （2）)(log 2 n O n =。 （3）)(log 2 n n Ω=。 （4）)(log log n n n n Ω=+。 （5）)10(log 10θ=。 （6）)(log log 2 n n Ω=。 （7）)100(22 n n Ω=。 （8）)3(2n n O =。 习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为))((n f θ，则该算法在最坏情况下所需的计算时间为))((n f Ω。 证明： ) (),() () ,() ,(max )() ,()()(max * * N T I N T I P I N T I N T I P I N T I P N T N N N N D I D I D I D I avg ==='≤ = ∑∑ ∑∈∈∈'∈ 因此，))(()))((())(()(max n f n f N T N T avg Ω=Ω=Ω=θ。 习题2-7 求解下列递归方程: s 0=0 s n =2s n -1+2n -1 解答： 步骤: 1应用零化子化为齐次方程， 2解此齐次方程的特征方程， 3由特征根构造一般解， 4再由初始条件确定待定系数，得到解为： 习题2-8 求解下列递归方程: 01122844n n n h h h h h --=? ? =? ?=-? 解 h n =2n +1(n +1) 第三章 递归与分治策略 习题3-1 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算 (1)21 n n s n =-+ 法的正确性证明。 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 设]1 a是已排好序的数组。请改写二分搜索算法，使得当搜 n 0[- : 索元素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 设]1 ≤n k是非负整数。试设 ≤ k n : 0[- a是有n个元素的数组，)1 1(- 计一个算法讲子数组]1:0[-k a 与]1:[-n k a 换位。要求算法在最坏情况下耗时为 )(n O ，且只用到)1(O 的辅助空间。 分析与解答： 算法： 三次求反法 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=12j i -+?? ? ??? ; 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 如果在合并排序算法的分割步中，讲数组]1:0[-n a 划分为??n 个子数组，每个子数组中有)(n O 个元素。然后递归地对分割后的子数组进行排序，最后将所得到的 ??n 个排好序的子数组合并成所要求的排好序的数组 ]1:0[-n a 。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。 分析与解答： 实现上述策略的合并排序算法如下： 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 其中，算法mergeall 合并n 个排好序的数组段。在最坏情况下，算法mergeall 需要)log (n n O 时间。因此上述算法所需的计算时间)(n T 满足： ?? ?>≤=1 ) (1) 1()(n n T n n O n T 此递归式的解为：)log ()(n n O n T =。 习题3-5 设k S S S ,...,21是整数集合，其中每个集合)1(k i S i ≤≤中整数取值 范围是n ~1，且n S k i i =∑=1 ，试设计一个算法，在)(n O 时间内将k S S S ,...,21分别 排序。 分析与解答： 用桶排序或基数排序算法思想可以实现整数集合排序。 习题6 设]1:0[-n X 和]1:0[-n Y 为两个数组，每个数组中还有n 个已排好序的数。试设计一个)(log n O 时间的算法，找出X 和Y 的2n 个数的中位数。 分析与解答： （1） 算法设计思想 考虑稍一般的问题：设]:[11j i X 和]:[22j i Y 是X 和Y 的排序好的子数组，且长度相同，即2211i j i j -=-。找出这两个数组中)1(211+-j i 个数的中位数。 首先注意到，若][][21j Y i X ≤，则中位数 median 满足 ][][21j Y m e d i a n i X ≤≤。同理若][][21j Y i X ≥，则][][12i X median j Y ≤≤。 设 2 /)(111j i m +=， 2 /)(222j i m +=，则 2 /)(2/)()(2/)(2/)(2/)(221121222111221121i j i j i i i j i i j i j i j i m m -+-++=-++-+=+++=+ 由于2211i j i j -=-，故221122112/)(2/)(i j i j i j i j -=-=-+-。 因此21222112112121j i i j i i j i i j i i m m +=-++=+==++=+。 当][][21m Y m X =时，][][21m Y m X median ==。 当][][21m Y m X <时，设1median 是]:[11j m X 和]:[22m j Y 的中位数，则 1 median median =。 当][][21m Y m X >时，设2median 是]:[11m i X 和]:[22j m Y 的中位数，类似地有2median median =。 通过以上讨论，可以设计出找出两个子数组]:[11j i X 和]:[22j i Y 的中位数median 的算法。 （2） 设在最坏情况下，算法所需的计算时间为)2(n T 。由算法中1m 和2m 的选 取策略可知，在递归调用时，数组X 和Y 的大小都减少了一半。因此，)2(n T 满足递归式： ?? ?≥+<=c n O n T c n O n T ) 1()() 1()2( 解此递归方程可得：)(log )2(n O n T =。 习题3-6 Gray 码是一个长度为n 2的序列。序列中无相同元素，每个元素都是长度为n 位的（0，1）串，相邻元素恰好只有1位不同。用分治策略设计一个算法，对任意的n 构造相应的Gray 码。 分析与解答： 考察3,2,1=n 的简单情形。 设n 位Gray 码序列为)(n G 以相反顺序排列的序列为)(1n G -。从上面的简单情形可以看出)(n G 的构造规律：)(1)(0)1(1n G n G n G -=+。 注意到)(n G 的最后一个n 位串与)(1n G -的第1个n 位串相同，可用数学归纳法证明)(n G 的上述构造规律。由此规律容易设计构造)(n G 的分治法如下。 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 个串存储在][i a 中。 完成计算之后，由out 输出Gray 码序列。 public static void out(int n) { int m=1< 第四章 动态规划 习题4-1 设计一个)(2n O 时间的算法，找出由n 个数组成的序列的最长单调递增子序列。 分析与解答： 用数组]1:0[-n b 记录以n i i a <≤0],[为结尾元素的最长递增子序列的长度。序列a 的最长递增子序列的长度为]}[{max 0i b n i <≤。易知，][i b 满足最优子结构性 质，可以递归地定义为： 1]}[{max ][, 1]0[] [][0+==≤<≤k b i b b i a k a i k 据此将计算][i b 转化为i 个规模更小的子问题。 按此思想设计的动态规划算法描述如下： public static int LISdyna() { int i, j, k; for ( i=1, b[0]=1; i static int maxL(int n) { int temp=0; for ( int i= 0; i 上述算法LISdyna 按照递归式计算出]1:0[-n b 的值，然后由maxL 计算出序列a 的最长递增子序列的长度。从算法LISdyna 的二重循环容易看出，算法所需的计算时间为)(2n O 。 习题4-2 考虑下面的整数线性规划问题： b x a x c n i i i n i i i ≤∑∑==1 1max i x 为非负整数，n i ≤≤1 试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。 分析与解答： 该问题是一般情况下的背包问题，具有最优子结构性质。 设所给背包问题的子问题： j x a x c i k k k i k k k ≤∑∑==1 1max 的最优值为),(j i m ，即),(j i m 是背包容量为j ，可选择物品为1，2，…，i 时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算),(j i m 的递归式如下： ?? ?<≤-≥+--=i i i i a j j i m a j c a j i m j i m j i m 0) ,1(} ),(),,1(max{),( 0, ),();0,(),0(<-∞==j j i m i m j m 。 按此递归式计算出的),(b n m 为最优值。算法所需的计算时间为)(nb O 。 习题4-3 给定一个由n 行数字组成的数字三角形如图3-2所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 分析与解答： 记f(u ij )为至ij 元素的最大路径值, a ij ：元素(i,j)之值。 递归式: F(u ij )=max{f(u i-1,j )+a ij , f(u i-1,j+1)+a ij } (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; 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 数字三角形 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背包问题，设计一个有效算法找出最优解，并说明算法的正确性。 分析与解答： 设所给的输入为n i W i i ≤≤>>>1,0,0,0νω。不妨设n ωωω≤≤≤<...021。由题意知0...21>≥≥≥n ννν。由此可知 1 1++≥ i i i i ωνων，11-≤≤n i 贪心选择性质： 当W >1ω时问题无解。 当W ≤1ω时，存在0-1背包问题的一个最优解},...,2,1{n S ?使得S ∈1。 事实上，设},...,2,1{n S ?使0-1背包问题的一个最优解，且S ?1。对任意S i ∈，取 }{}1{i S S i -?=，则i S 满足贪心选择性质的最优解。 习题5-2 Fibonacci 序列的Huffman 编码 试证明：若n 个字符的频率恰好是前n 个Fibonacci 数，用贪心法得到它们的Huffman 编码树一定为一棵“偏斜树”。 分析与解答： 频率恰好是前8个Fibonacci 数的哈夫曼编码树如图所示。 图 哈夫曼编码树 证明：n 个字符的频率恰好是前n 个Fibonacci 数，则相应的哈夫曼编码树自底向上第 i 个内结点中的数为∑=i k k f 0 。用数学归纳法容易证明20 +=<∑i i k k f f 。 因f 1=1,f 2=1,f 3=2,可知i =1时，上述结论成立。 设对i+2上述结论成立，即有20 +=<∑i i k k f f ， 因 1 32111 1 i i i i i k i k k k f f f f f f +++++===+> += ∑ ∑ ， 说明对i+3上述结论成立. 该性质保证了频率恰好是前n 个Fibonacci 数的哈夫曼编码树具有“偏斜树”形状。 习题5-3 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 分析与解答： 设所给的n 个活动为1，2，…，n ，它们的开始时间和结束时间分别为][i s 和][i f ， n i ~1=，且][...]2[]1[n f f f <<<。 可以将n 个活动1，2，…，n 看作实直线上的n 个半闭活动区间n i i f i s ~1]),[],[[=。所讨论的问题实际上是求这n 个半闭区间的最大重叠数。因为重叠的活动区间所相应的活动是互不相容的。若这n 个活动区间的最大重叠数为m ，则这m 个重叠区间所对应的活动互不相容，因此至少安排m 个会场来容纳这m 个活动。 为了有效地对这n 个活动进行安排，首先将n 个活动区间的2n 个端点排序。然后，用扫描算法，从左到右扫描整个实直线。在每个事件点处（即活动的开始时刻或结束时刻）作会场安排。当遇到一个开始时刻][i s ，就将活动i 安排在一个空闲的会场中。遇到一个结束时候][i f ，就将活动i 占用的会场释放到空闲会场栈中，以备使用。经过这样一遍扫描后，最多安排了m 个会场（m 是最大重叠区间数）。因此所作的会场安排是最优的。上述算法所需的计算时间主要用于对2n 个区间端点的排序，这需要)log (n n O 计算时间。 具体算法描述如下。 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-4 假设要在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-5 删数问题 问题描述 k 个数字后，剩下的数字按原次序排列组成一个新的给定n位正整数a，去掉其中任意n 正整数。对于给定的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 } while (a.length()>1 && a.charAt(0)==?0?) a=a.Remove(0,1); System.out.println(a); } 第六章 回溯法 习题6-1 子集和问题 子集和问题的一个实例,A sum <>。其中，12{,,...,}n A a a a =是一个正整数的集合，sum 是一个正整数。子集和问题判定是否存在A 的一个子集A 1，使得1 a A a sum ∈=∑。 试设计一个解子集和问题的回溯法。 分析与解答： 设计解子集和问题的回溯法如下。 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。计算所有可能的填法。 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 then 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-1. 试写出采用分支界限法求解下面的0、1背包问题实例的过程：物品的个数n=4, 背包的重量m=15, 各个物品的重量依次为2，4，6，9，各个物品的价值依次为10，10，12，18。 对于第i层上的每个节点x，其价值的上界定义为有贪心法所求出的一般背包问题的解S u(x)，下界为S l(x)为S u(x)中减去最后放入背包的x i≠1的物品的相应部分价值。 解答： (0000)(0001)(0010)(0011)(0100)(0101)(0110)(0111)(1000)(1001)(1010)(1011)(1100)(1101)(1110)(1111) 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 实验三分治算法（2） 一、实验目的与要求 1、熟悉合并排序算法（掌握分治算法） 二、实验题 1、问题陈述: 对所给元素存储于数组中和存储于链表中两中情况，写出自然合并排序算法. 2、解题思路: 将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序. 三、实验步骤 程序代码: #include int target[N],head[N],tail[N]; int i=0,n,m; for(; i 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号： 05 学生姓名：俞梦真 指导教师：郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 归式，就是如何将原问题划分成子问题。 2.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。 3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢（2）递归与非递归之间如何实现程序的转换？ （3）分析二分查找和快速排序中使用的分治思想。 答： 1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。 2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。 （4）分析二次取中法和锦标赛算法中的分治思想。 二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 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. 回溯法解TSP问题时的解空间树是（ 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、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日 实验一：递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2018年10月10日16:00。 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： 【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序代码如下： #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai算法设计与分析考试题及答案
中科院陈玉福计算机算法设计与分析期末简答题答案
算法设计与分析实验三
算法设计与分析实验报告
算法设计与分析考试题及答案
算法设计与分析试卷(2010)
算法设计与分析试卷(2010)
计算机算法设计与分析期末考试复习题
《算法设计与分析》实验一
算法设计与分析试卷及答案
《算法设计与分析》递归算法典型例题
算法设计与分析期末试题答案解析
《算法设计与分析》实验报告
算法设计与分析试卷及答案.doc
算法设计与分析实验报告 统计数字问题
南京邮电大学算法设计实验报告——动态规划法
算法设计与分析试题与答案