遞歸函數停止處理的條件分支

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包含分支或它的反面。你的一個操作會反轉字符串，並且此操作可能會應用於你所知的所有奇數次。