← 完整题目索引

PROJECT EULER · #0300

蛋白质折叠

Protein Folding

仅题目 · 已解决原题 ↗

以一种非常简化的形式,我们可以将蛋白质视为由疏水性 (H) 和极性 (P) 元素组成的字符串,例如哈哈哈哈哈哈哈。
对于这个问题,蛋白质的方向很重要。例如HPP 被认为与 PPH 不同。因此,有 2n 个不同的蛋白质由 n 个元素组成。

当人们在自然界中遇到这些弦时,它们总是以 H-H 接触点的数量尽可能多的方式折叠,因为这在能量上是有利的。
因此,H 元素倾向于积聚在内部,而 P 元素则积聚在外部。
天然蛋白质当然会在三个维度上折叠,但我们只会考虑二维上的蛋白质折叠。

下图显示了示例蛋白质折叠的两种可能方式(H-H 接触点用红点显示)。

0300_protein.gif

左边的折叠只有六个H-H接触点,因此永远不会自然发生。
另一方面,右侧的折叠有九个 H-H 接触点,这对于该弦来说是最佳的。

假设 H 和 P 元素出现在字符串中任何位置的可能性相同,则长度为 8 的随机蛋白质字符串的最佳折叠中 H-H 接触点的平均数量为 850/28=3.3203125

长度为 15 的随机蛋白质串的最佳折叠中 H-H 接触点的平均数量是多少?
给出答案时使用尽可能多的小数位以获得准确的结果。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。