按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
其中最长的那个就叫做“最长公共子序列”。
随机产生两个长度为n的01序列，其中数字1出现的概率是p，数字0出现的概率是1…p。用cp（n）来表示它们的最长公共子序列的长度，用cp来表示cp（n）/n的极限值。
关于cp的存在性，有一个非常巧妙的证明；然而，这个证明仅仅说明了cp的存在性，它完全没有给计算cp带来任何有用的提示。
即使是c1/2的值，也没人能成功算出来。michaelsteele猜想c1/2=2/（1＋√2）≈0。828427。后来，v。chvatal和d。sankoff证明了……，看上去michaelsteele的猜想似乎很可能是对的。2003年，geelueker证明了0。7880