Python程式：根據給定字串序列規則查詢第n個序列

假設我們有兩個字串s、t，還有一個給定的正數n，我們需要找到序列A的第n項，其中：

  • A[0] = s
  • A[1] = t
  • 當n為偶數時，A[n] = A[n - 1] + A[n - 2]；否則，A[n] = A[n - 2] + A[n - 1]。

例如，如果s = "a"，t = "b"，則序列A將是：["a", "b", "ba" ("a" + "b"), "bba" ("b" + "ba"), "bbaba" ("bba" + "ba")]

因此，如果輸入為s = "pk"，t = "r"，n = 4，則輸出將為"rrpkrpk"

為了解決這個問題，我們將遵循以下步驟：

  • 如果n等於0，則
    • 返回s
  • 否則，如果n等於1，則
    • 返回t
  • a := s，b := t
  • 對於範圍從2到n的i，執行：
    • 如果i mod 2等於0，則
      • c := b連線a
    • 否則，
      • c := a連線b
    • a := b
    • b := c
  • 返回c

讓我們來看下面的實現，以便更好地理解：

示例

 線上演示

class Solution:
   def solve(self, s, t, n):
      if n == 0:
         return s
      elif n == 1:
         return t
         a = s
         b = t
      for i in range(2, n+1):
         if i%2 == 0:
            c = b + a
         else:
            c = a + b
            a = b
            b = c
      return c
ob = Solution()
print(ob.solve("pk", "r", 4))

輸入

"pk", "r", 4

輸出

rrpkrpk

更新於：2020年10月5日

235 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始
廣告