计算器指定结果对应的期望按键按压次数求解咨询

嘿，你的思路其实挺有意思的——把clear键当成0来转化成序列问题，这个切入点没问题，但要算期望按键次数的话，直接算0123出现的概率还不够，得用马尔可夫状态转移的思路来拆解，我给你一步步理清楚：

第一步：定义状态 #

我们只需要关注当前显示屏内容的最长后缀是否匹配目标序列123，所以可以定义4个状态：

• S₀：空显示屏（初始状态）
• S₁：显示屏的最后一位是1（比如显示1、x1，只要最后一位是1就行）
• S₂：显示屏的最后两位是12（比如显示12、x12）
• S₃：显示屏的最后三位是123（终止状态，我们要的目标）

设从状态Sᵢ到S₃的期望按键次数为Eᵢ，显然E₃=0（已经达成目标，不需要再按键）。

第二步：列状态转移方程 #

每个按键（1、2、3、clear）被按下的概率都是1/4，我们针对每个状态分析转移情况：

对于初始状态S₀（空屏）：

• 按1：进入S₁，次数+1
• 按2/3/clear：都回到S₀，次数+1
  所以方程为：

E₀ = 1 + (E₁ + E₀ + E₀ + E₀)/4

整理后得到：E₀ = 4 + E₁

对于状态S₁（最后一位是1）：

• 按1：最后一位还是1，留在S₁，次数+1
• 按2：最后两位变成12，进入S₂，次数+1
• 按3/clear：回到S₀，次数+1
  方程为：

E₁ = 1 + (E₁ + E₂ + E₀ + E₀)/4

整理后得到：3E₁ = 4 + E₂ + 2E₀

对于状态S₂（最后两位是12）：

• 按1：最后一位变成1，进入S₁（最长匹配后缀是1），次数+1
• 按2：最后两位变成22，回到S₀，次数+1
• 按3：达成目标，进入S₃（E₃=0），次数+1
• 按clear：回到S₀，次数+1
  方程为：

E₂ = 1 + (E₁ + E₀ + 0 + E₀)/4

整理后得到：4E₂ = 4 + E₁ + 2E₀

第三步：解方程组 #

把E₀ = 4 + E₁代入后两个方程：

1. 代入3E₁ = 4 + E₂ + 2E₀，得到E₁ = 12 + E₂
2. 再把E₀ = 4 + E₁和E₁ = 12 + E₂代入4E₂ = 4 + E₁ + 2E₀，解得：
   • E₂ = 48
   • E₁ = 60
   • E₀ = 64

所以最终的期望按键次数是64次。

备注：内容来源于stack exchange，提问作者Alex Wang