算法（复习题）1.docx

本文格式为Word版，下载可任意编辑算法（复习题）1 平均处境: 设待查找的元素在数组中的概率为P，不在数组中的概率为1-P,若展现在数组中每个位置的概率是均等的为p/n T(n)=P1D1+P2D2+...+PiDi+(1-P)Dn+1 =p/2+n(1-p/2) 1.表达分治算法和动态规划算法的根本思想，并对比两种算法的异同 答:分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解. 动态规划将待求解的问题分解成若干的子问题，自底向上地通过求解子问题的解得到原问题的解动态规划将每个子问题只求解一次并将其解保存在一个表格中,当需要再次求解此子问题时,只是简朴的通过查表过的该子问题的解,制止了大量的重复计算. 异同：分治法求解的问题分解后的子问题都是独立的，而使用动态规划求解的问题分解后得到的子问题往往不是相互独立的 分治法是自顶向下用递归的方法解决问题，而动态规划那么是自底向上非递归解决问题 1. 简述分治算法求解过程的三个阶段 答:（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致一致。

（2）求解子问题：各子问题的解法与原问题的解法通常是一致的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现 （3）合并：把各个子问题的解合并起来，合并的代价因处境不同有很大差异，分治算法的有效 性很大程度上凭借于合并的实现 2. 表达分治法的根本思想，并分析分治法与减治法二者的识别 答：分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解. 识别：分治法是把一个大问题划分成若干个子问题，分别求解各个子问题，然后把子问题的解举行合并并得到原问题的解减治法同样是把一个大问题划分成若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解举行合并 3. 设计分治算法求一个数组中最大元素的位置，建立该算法时间繁杂性的 递推式并给出其繁杂性的大O表示 答：设数组a1,a2...an int maxpos(a[],i,j); {if(i==j) return i; mid=(i+j)/2; lmaxpos=maxpos(a,i,mid); rmaxpos=maxpos(a,mid+1,j); if(a[lmaxpos]>=a[rmoxpos]) return lmaxpos; else return rmaxpos;} T(1)=O(n) n=1; T(n)=2T(n/2)+O(1) n>1; 求得繁杂性为O(n) 4. 阅读下面一段折半查找算法，回复问题。

int BinarySearch(int a[],int x,int n) { int left=0,right=n-1; while(lefta[middle]) left=middle+1; else right=middle-1; } return -1; } （1） 给出该算法的繁杂性递归方程，用开展法求解，并给出其渐进繁杂性的 大O表示 T(1)=1 n=1 T(n)=T(n/2)+1 (n>=2) O(logn) （2） 修改折半查找算法使之能够举行范围查找所谓范围查找是要找出在给 定值a和b之间的全体元素（a≤b） int BinarySearch(int s[],int r,int l,a,b) { mid=(l+r)/2; if(s[mid]>b) BinarySearch(s,mid-1,l,a.b); else (s[mid] BinarySearch（s,mid-1,l,a,s[mid]）; BinarySearch (s,r,mid+1,s[mid],b); } 5. 什么是最优化问题？ 答：最优化问题有n个输入，它的解由这n个输入的一个子集组成，这个子集务必得志某些事先给定的条件，这些条件称为约束条件，得志约束条件的解称为可行解。

得志约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出确定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数使目标函数取得极值（极大或微小）的可行解称为最优解这类问题就称为最优化问题 6. 最大子段和问题：给定由n个整数组成的序列(a1, a2, …, an)，最大子段 和问题要求该序列形如ai+…+aj的最大值（1≤i≤j≤n），当序列中全体整数均为负整数时，其最大子段和为0分别用蛮力法、分治法和动态规划法设计求解最大子段和问题的算法的伪代码描述，并分析每种方法的渐进繁杂性 （1）蛮力法 int maxsum (int n,int a[],int besti,int bestj){ int sum=0; for(int i;isum){ sum=thissum; besti=i; bestj=j;}} }return sum; } 根本操作为：其次个for循环中的条件语句，故繁杂性为:O(n^2) （2）分治法 将a1,a2,……,an划分为两个长度相等的子序列a1,a2…..,an/2和 1原序列最大子段和为前一个子序列的最大子段和。

2原an/2+1,an/2+2,……,an○○ 3原序列的最大子段和序列最大子段和为后一个子序列的最大子段和○ 1○2递归求解，3s1=Max(ai+….+ak) =ai+….+aj 11;解得时间繁杂度:O（nlogn） （3）动态规划法 int maxsum (int n,int a[]){ int sum=0,b=0; for(int i=1;i0) b+=a[i]; else b=a[i]; if(b>sum) sum=b;} return sum;} 递归方程 b(j)=b(j-1)+aj b(j-1)>0 b(j)=aj b(j-1)=1) 4.1 当(Sk 没有被穷举)循环执行以下操作 4.1.1 xk =Sk 中的下一个元素; 4.1.2 将xk 参与X; 4.1.3 if (X为最终解) flag=true; 转步骤5; 4.1.4 else if (X为片面解) k=k+1; 转步骤4; 4.2 k=k-1; //回溯 5．if flag 输出解X; else 输出“无解”; 13. 设计用回溯法求解0/1背包问题的剪枝函数，并给出相应算法的伪代码描述。

X=(x1,x2,….,xn) xi={0,1} x1w1+x2w2+…+xiwic 右子树：cp+lefts(i+1)n) { if(bestPbestP）那么 cw=cw-w[i];cp=cp-p[i]; 14. 给定一个正整数集合X={x1,x2,…,xn}和一个正整数y，设计回溯算法，求集合X的一个子集Y，使得Y中元素之和等于y若X={1,2,3,5,7},y=8，用设计的回溯算法求解该问题的全体解 答：解形式：Y={y1.y2,……yn} yi={0.1} 约束条件: n ∑=yixi=y i=1 左子树：sum+xi>y 右子树：sum=lefts(i+1)=y) Backtrack(i+1); } 解是：（1，1,0,1,0） 15. n皇后问题：在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一 行、同一列或同一斜线上 （1） 给出n皇后问题的解向量形式及解释 X=(x1,x2,…,xn) 1<=i<=n 每一行可以而且务必摆放一个皇后，所以N皇后问题可以用X=(x1,x2,…,xn) 表示1<=i<=n并且1<=xi<=n,即第i个皇后放在第i行第xi列上。

（2） 分析并表示n皇后问题可行解的约束条件 两个皇后不能位于同一行同一列上，xi不等于xj 两个皇后不能位于同一斜线上，|i-xi|不等于|j-xj| — 6 —。