IBM Ponder This #297 · 2023 年 1 月

长度为 $n$ 的基因，是由 G、A、C、T 组成的 $n$ 字符串。每步只改变一个位置。最左字符可自由改为任意一种字符，其余位置只允许：

• T→C：左侧所有字符都是 C；
• T→G：紧邻左侧为 C，更左侧全为 A；
• C→T：左侧全为 T；
• C→A 或 A→C：紧邻左侧为 C，更左侧全为 A；
• G→T：左侧全为 T。

目标是以最少步数变成全 G。例子 CTTGG 可依次变为 CCTGG、ACTGG、ACGGG、TCGGG、TTGGG、CTGGG、CGGGG、GGGGG，共八步，对应 [(2,C),(1,A),(3,G),(1,T),(2,T),(1,C),(2,G),(1,G)]，位置从 1 起。ACAC 的最少步数为 25。

任务：找出一个只含 A、C 的二十位初态，使变为全 G 的最少步数在 880,000 至 890,000 之间。第一行给初态，第二行给准确最少步数。

附加问题：求一百位全 T 变为全 G 的最少步数。

解答

认真尝试后再打开

待补充。