(算法试卷答案ypf.docxVIP

优先选择顺序:要优先选择分治算法,回溯算法,贪心算法,动态规划算法和分支限界算法一、给定一个含有n个元素的集合，且存放在一维数组A[1…n]中，试利用分治算法设计算法，找出集合中前k个最小的元素，且结果存放在A[1….k]中。要求：给定任意的k（1=k=n），最好的时间复杂度为O（n）.假设：1）集合中没有重复的元素 2）k不是常量，而是通过参数带入的参数 3）前k个最小元素不需要排序思路分析:分治法的基本思想?：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。利用快速排序的分治基本思想?：设当前待数组的无序区为R[low..high]，需要查找前k个小的元素,数组长度为n.利用分治法可将问题的基本思想描述为：(1) 分解?在R[low..high]中任选一个记录作为基准（Pivot），以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1]和R[pivotpos+1..high]，并使 左边子区间中所有记录的关键字均=基准记录的关键字pivot.key，右边的子区间中所有记录的关键字均=pivot.key，而基准记录pivot则位于正确的位置（pivotpos）上，它无须参加后续的排序。如果当前的基准位置恰好等于K,则无需进行第二步的快速排序,直接返回结果即可.(2) 求解?通过递归调用快速排序,如果当前的基准小于K则在K到high之间继续进行一次快速排序,找到K所在的位置,如果大于K,则在low-k之间继续进行一次快速排序,找打K所在的位置. (3) 组合?因为当“求解”步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，“组合”步骤无须做什么，可看做是空操作。//分治思想中的快速排序程序代码?利用分治策略，在n个不同元素中找出第k个最小元素?代码如下：?#include?stdio.h?//一次快速排序?int?partition(int?s[],?int?low,?int?high)?{???if?(low?high?)??return?0;??????if(low==high)??return?low;??????s[0]=s[low];??????while?(low??high)????{??while?(low??high??s[high]?s[0])?high--;?if?(low??high)?s[low++]?=?s[high];?while?(low??high??s[low]?s[0])?low++;???if?(low??high)?s[high--]?=?s[low];?}??s[low]?=?s[0];????????return?low;?}??//分治找K-th?Numberint?Select(int?s[],?int?low,?int?high,?int?k){?//得到中间数的下标??int?i?=?partition(s,?low,?high);??????//j为左区间长度?int?j?=?i?-?low?+?1;?//位置大就在左区间找，否则就在右区间找?if?(j?==?k)????return?s[i];else?if?(kj)?return?Select(s,?low,?i,?k);??else?return?Select(s,?i+1,?high,?k-j);??}int?main(){???int?n;?int?low,?high,?k;int?a[20];??printf(请输入数目\n);scanf(%d,n);printf(请输入数据:\n);???for?(int?i?=?1;?i?=?n;?i++)??scanf(%d,a[i]);???printf(\n);?printf(请输入第几个最小值:\n);scanf(%d,k);???printf(第%d个最小的数为:%d\n,k,Select(a,?1,?n,?k));???}二、动态规划算法在一个由n个数字组成的数字串中插入r个乘号（1=rn16），使它分成r+1个整数，找出一种乘号的插入方法，使得这r+1个整数的乘积最大，试用动态规划算法解决此问题，并分析算法的时间复杂度。算法分析:建立递推关系?设f(i,k)表示在前i位数中插入k个乘号所得乘积的最大值，a(i,j)表示从第i个数字到第j个数字所组成的j-i+1(i=j)位整数值。为了寻求递推关系，先看一个实例：对给定的847313926，如何插入r=5个乘号，使其乘积最大？我们的目标是为了求取最优值f(9,5)。?①设前8个数字中已插入4个乘号，则最大乘积为f(8,4)*6； ②设前7个数字中已插入4个乘号，则最大乘积为f(7,4)*26； ③