算法复习资料2

11!)1(00)(nnnnfnnf0)0()0(),(!)(ffnfnnf!)1()!1()(!nnfnnnfn1)1()(nfnfnfnfni01)0()(1!)(!)(nnnfnnf1.在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，使得所有相邻两个方格内的两个整数之和为质数。试给出该问题的回溯算法，求出所有满足这个要求的各种数字填法。递归形式的回溯算法：INPUT:数字1到N（N≥10）。OUTPUT:所有满足条件的填充方法。1.Fork=1to92.c[k]=03.Endfor4.flag=false5.tianzi(1)6.ifflag=falsethenoutput“nosolution”过程tianzi(k)1.Form=1toN2.c[k]=m3.Ifc为合法填充方法的then得到一个填充方法，输出c数组，flag=true4.Elseifc是部分的thentianzi(k+1)5.Endfor非递归的回溯算法：INPUT:数字1到N（N≥10）。OUTPUT:所有满足条件的填充方法。1.Fork=1to92.c[k]=03.Endfor4.falg=false5.k=16.Whilek≥17.Whilec[k]≤N-18.c[k]=c[k]+19.Ifc为合法的填充方法then得到一个填充方法，输出c数组，flag=true10.Elseifc是部分解thenk=k+111Endwhile12.c[k]=013.k=k-114.Endwhile15.ifflag=falsethenoutput“nosolution’2.分数背包问题的贪心算法给出n个物品，它们的体积为nsss,...,,21，价值为nvvv,...,,21，并设背包的容量为C。我们想找到一种选择将物品放入背包使得所得的价值最大。即要找niiivx1，在约束条件Csxniii1下最大。其中，nxxx,...,,21是非负实数，要求输出每种物品装入背包的体积，即每种物品对应的ix。算法：INPUT:n个物品，体积为nsss,...,,21,价值为nvvv,...,,21，背包的容量为C。OUTPUT:niiivx1总价值最大，并且满足Csxniii1，其中nxxx,...,,21是非负实数。1.对n个物品求出每个物品的iisv，并按iisv降序排列，相应的体积和价值存入v[n]和s[n]数组中。2.x[1…n]=0,value=0，space=C3.fori=1ton4.ifs[i]=spacethen5.x[i]=s[i];space=space-s[i];value=value+v[i];6.elsex[i]=space;value=value+space*v[i]/s[i];break;7.endfor8.outputx[1…n]和总的最大价值value;时间复杂度：算法的时间复杂性可描述为O(n)。3．钱币问题的动态规划算法有一个货币系统，它有n种硬币，它们的面值为v1,v2,…,vn，其中v1=1。想要兑换的钱数为y，给出兑换的最少硬币个数。算法：INPUT:n种硬币，以及它们的面值v1,v2,…,vn，要换的钱数y。OUTPUT:兑换y钱的最少硬币个数。1.fori=0ton2.N[i,0]=03.endfor4.forj=0toy5.N[0,j]=06.endfor7.fori=1ton8.forj=1toy9.N[i,j]=N[i-1,j]10.ifj≥vithen11.ivjk/12.N[i,j]=min{N[i,j],N[i-1,j-kvi]+k}13.endif14.endfor15.endfor16.returnN[n,y]时间复杂性：钱币兑换问题的动态规划算法有典型的循环迭代结构，并且每次循环都是在填一个表项，算法的时间复杂性刚好是表的大小，即Θ(ny)。4.合并排序的分治算法已知数组A[1..n]，要求算法首先把输入数组A[1…n]划分成4个部分A1,A2,A3和A4，然后分别对每部分递归排序，最后将4个已排序部分合并得到排好序的数组A。假定数组大小n是4的整数幂。要求：(1)写出该问题的分治算法；(2)求解递推式，给出算法的最大元素比较次数。(1)写出该问题的分治算法；算法：输入：n个元素的数组A[1…n]输出：按非降序排列的数组A[1…n]1.fourmergesort(A,1,n)过程fourmergesort(A,low,high)1.iflowhighthen2.2/)(highlowmid3.2/)(1midlowmid4.2/)1(2highmidmid5.fourmergesort(A,low,mid1)6.fourmergesort(A,mid1+1,mid)7.fourmergesort(A,mid+1,mid2)8.fourmergesort(A,mid2+1,high)9.MERGE(A,low,mid1,mid)10.MERGE(A,mid+1,mid2,high)11.MERGE(A,low,mid,high)12.endif(2)求解递推式，给出算法的最大元素比较次数。设C(n)是我们要计算的算法的最大元素比较次数。因为n是4的整数幂，如果n=1则算法不执行任何元素比较，如果n1，则执行了步骤2到11，算法中执行步骤5，6，7，8的最大元素比较次数为C(n/4)。步骤9，10，11主要是合并算法MERGE的比较次数，因此，步骤9，210的最大比较次数为n/2-1,步骤11的最大元素比较次数为n-1。因此可以得到求解最大元素比较次数的递推公式为：2),1()12/(2)4/(41,0)(nnnnCnnC若若简化为：2,32)4/(41,0)(nnnCnnC若若利用展开法求解递推式如下：1log2)14(31320432)1(4434343432)4/(443434332)4/(4434322)4/(432)342)4/(4(432)4/(4)(400110123301222nnnknknCknnCnnCnnCnnnCnnCnCkkjjkkkkk5.程序存储问题的贪心算法设有n个程序{1，2，…n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存放尽可能多的程序。(1)程序存储问题的贪心算法INPUT:n个程序的长度l1,l2,…,ln,磁带的长度L。OUTPUT:磁带上存放的最多的程序个数num，以及存入磁带的每个程序的编号数组pro[n]。1.对n个程序按长度升序排列，存入p[n]数组中。2.i=1，j=1,sum=03.while(sum+p[i])L4.sum=sum+p[i]5.m[j]=i6.num++7.i++,j++8.endwhile9.output装入的程序个数num，及装入的程序编号m(2)算法分析本算法是一个典型的循环迭代算法，因此算法的时间复杂性可以用算法中的循环次数来描述，算法中第三步的while循环最多执行次数不会超过n次，因此算法的时间复杂性可描述为O(n)。6．钱币问题的动态规划算法有一个货币系统，它有n种硬币，它们的面值为v1,v2,…,vn，其中v1=1。想要兑换的钱数为y，给出兑换的最少硬币个数。(1)算法：INPUT:n种硬币，以及它们的面值v1,v2,…,vn，要换的钱数y。OUTPUT:兑换y钱的最少硬币个数。1.fori=0ton2.N[i,0]=03.endfor4.forj=0toy5.N[0,j]=06.endfor7.fori=1ton8.forj=1toy9.N[i,j]=N[i-1,j]10.ifj≥vithen11.ivjk/12.N[i,j]=min{N[i,j],N[i-1,j-kvi]+k}13.endif14.endfor15.endfor16.returnN[n,y](2)算法时间复杂性分析钱币兑换问题的动态规划算法有典型的循环迭代结构，并且每次循环都是在填一个表项，算法的时间复杂性刚好是表的大小，即Θ(ny)。7、假设有7个物品，背包容量M＝150，物品ABCDEFG容量35306050401025价值10403050354030如果上述物品可以被分割，使用贪心算法求解（1）首先依据下述标准进行：重量、价值和单位价值。（2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。（3）显然使用单位价值作为标准得到的是最优解。8、排序和查找是经常遇到的问题。按照要求完成以下各题。（1）对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。（2）请描述递减数组进行二分搜索的基本思想，并给出非递归算法。（3）给出上述算法的递归算法。（4）使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。39、设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。使用回溯法求解有多少种不同的三角形？给出解答过程。410、为找零问题写一个贪心算法的伪代码,它以金额n和硬币的面额d1d2…dm作为输入.以n的函数形式给出该算法的效率类型.Algorithmschange(n,D[1..m])//输出:数组A[1..m]----每种面额硬币的数量,或者无解贪心策略：依据顾客的服务时间首先进行排序，然后从中依次安排每一个人进行服务，其中要注意s是提供服务的处所。（算法略，请自己写）