最长公共子序列

Biological applications often need to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by its initial letter, we can express a strand of DNA as a string over the finite set {A,C,G,T}.

这是生物学应用中最为常见的“最长公共子序列问题”。

阅读全文

动态规划概论

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。

阅读全文

约瑟夫环

Josephus问题的定义如下:假设n个人排成环形,且有以正整数m<=n。从某个制定的人开始,沿环报数,每遇到第m个人就让其出列,且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数1,2,…,n的(n, m)-Josephus排列。例如,(7,3)-Josephus排列为<3,6,2,7,5,1,4>。

a)假设m为整数。请描述一个O(n)时间的算法,使之对给定的整数n,输出(n, m)-Josephus排列。
b)假设m不是个常数。请描述一个O(nlgn)时间的算法,使给定的整数n和m,输出(n, m)-Josephus排列。

阅读全文