posts - 7, comments - 5, trackbacks - 0, articles - 4

算法题_以后慢慢做

Posted on 2008-11-04 22:40 阿呆 阅读(1252) 评论(0)  编辑 收藏 引用 所属分类: 编码练习题


递归与分治一章:

        给定一个由n个互不相同的数组成的集合S,及一个正整数k<=n,试设计
        一个O(n)时间算法找出S中最接近S的中位数的k个数

动态规划一章:

        设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些
        面值的硬币来找钱。可以使用的各种面值的硬币个数不限。

        1)当只用硬币面值T[1],T[2],……T[i]时,可找出钱数j的最少硬币个数
        记为C(i,j)。若只用这些硬币面值,找不出钱数j时,记C(i,j)=无穷。给
        出C(i,j)的递归表达式,及其初始条件。1<=i<=n,1<=j<=L

        2)设计一个动态规划算法,对1<=j<=L,计算出所有的C(n,j)。算法中只
        允许使用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂
        性。

        3)在C(n,j),1<=j<=L,已计算出的情况下,设计一个贪心算法,对任意
        钱数m<=L,给出用最少硬币找钱m的方法。当C(n,m)不等于无穷时,算法的
        计算时间应为O(n+C(n,m))。

贪心算法一章:

        在黑板上写了n个正数组成的一个数列,进行如下操作:每一次擦去其中两
        个数设为a和b,然后在数列中加入一个数a*b+1,如此下去直至黑板上只剩
        下一个数。在所有按这种操作方式最后得到的数中,最大的数记为max,最
        小的数记为min,则该数列的极差M定义为M=max-min。对于给定的数列,设
        计一个有效算法计算出其极差M。并说明算法的正确性。

回溯法一章:
      
        运动员最佳配对问题。一个羽毛球队有男女运动员各n人,给定2个n*n矩阵P
        和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打时的竞赛优势;
        Q[i][j]则是女运动员i和男运动员j配合时的竞赛优势。显然,由于技术的
        配合和心理状态等各种因素的影响,P[i][j]不一定等于Q[i][j]。设计一个
        算法,计算出男女运动员的最佳配对法,使各组男女双方竞赛优势乘积达到
        最大。

分支界限法一章:

        栈式分支界限法将活结点表以后进先出(LIFO)的方式存储于一个栈中。
        试设计一个解0-1背包问题的分支界限法,并说明栈式分支界限法与回溯
        法的区别。


        试设计一个解n后问题的优先队列式分支界限法。


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理