递归函数停止处理的条件分支

Question

我有一个函数can_obtain，以证明如果一个串init可以转化为字符串target与下列条件：

• 串init和target仅由字母“X”的和/或 “Y”（如 “XY”， “XXX”， “YYXY”， “Y” 等）
• 串target比init
• 选择不再去target是
  • 串连 “X” 到init或
  • 反向并连接 “Y” 到init

下面是函数，具有用于去除简洁琐碎的操作，如containsreverse和。

let can_obtain init target = 
    let final = 
    let rec reduce i text = 
     if i >= String.length target then text 
     else 
     let next = 
      let branchX = text^"X" in 
      let branchY = (reverse text)^"Y" in 
      if contains target branchX then branchX 
      else if contains target branchY then branchY 
      else text 
     in 
      reduce (i+1) next 
    in 
     reduce (String.length init) init 
    in 
    final = target 
;; 

问题是与这些转变它返回true，这是正确

(* concat "X" only *) 
(* "XY" -> "XYX" -> "XYXX" *) 
can_obtain "XY" "XYXX";; 

(* reverse and concat "Y" only *) 
(* "XY" -> "YXY" -> "YXYY" -> "YXYYY" *) 
can_obtain "XY" "YXYYY";; 

(* reverse and concat "Y", then concat "X" lastly *) 
(* "XY" -> "YXY" -> "YXYY" -> "YYXYY" -> "YYXYYX" *) 
can_obtain "XY" "YYXYYX";; 

但是，如果在过渡“X”的某一点是级联，则该函数将拒绝切换到反向分支，就回到false：

(* concat "X", then tries to reverse then concat "Y" *) 
(* "XY" -> "XYX" -> "XYXY" *) 
can_obtain "XY" "XYXY";; (* false *) 

我知道我在这里失去了只是一小部分，并且代码看起来真的太凌乱。我真的很感谢一些帮助。

Answer 1

can_obtain是递归函数 - 所以让我们定义停止条件第一：

停止条件：

• 如果n = i，那么这是一个成功
• 如果长度i>长度为n然后失败

如果停止条件不符合，那么我们必须进一步尝试2假设：(init^"X"),((reverse init)^"Y")

所以在代码的结果：

let rec can_obtain init target = 
    if init = target then 
    true 
    else if String.length init >= String.length target then 
    false 
    else 
    (can_obtain (init^"X") target) || (can_obtain ((reverse init)^"Y") target) 

Answer 2

只看你的代码，显而易见的问题是N可能同时包含branchX和branchY。在这种情况下（在我看来）你想追求两种可能性，但你只追求第一种可能性。

更新

另一种看法是，你可能想追求的一个分支，如果N包含分支或它的反面。你的一个操作会反转字符串，并且此操作可能会应用于你所知的所有奇数次。