算法复习资料 4页

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个物品，它们的体积为，价值为，并设背包的容量为C。我们想找到一种选择将物品放入背包使得所得的价值最大。即要找，在约束条件下最大。其中，是非负实数，要求输出每种物品装入背包的体积，即每种物品对应的。算法：INPUT:n个物品，体积为,价值为，背包的容量为C。OUTPUT:总价值最大，并且满足，其中是非负实数。1.对n个物品求出每个物品的，并按降序排列，相应的体积和价值存入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.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.iflow1，则执行了步骤2到11，算法中执行步骤5，6，7，8的最大元素比较次数为C(n/4)。步骤9，10，11主要是合并算法MERGE的比较次数，因此，步骤9，10的最大比较次数为n/2-1,步骤11的最大元素比较次数为n-1。因此可以得到求解最大元素比较次数的递推公式为：简化为：\n利用展开法求解递推式如下：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])d2>…>dm作为输入.以n的函数形式给出该算法的效率类型.Algorithmschange(n,D[1..m])//输出:数组A[1..m]----每种面额硬币的数量,或者无解贪心策略：依据顾客的服务时间首先进行排序，然后从中依次安排每一个人进行服务，其中要注意s是提供服务的处所。（算法略，请自己写）