Chương trình tìm chuỗi thứ n theo quy tắc chuỗi cho trước trong Python

Cho hai chuỗi s, t và số nguyên dương n. Tìm hạng thứ n của dãy A với:

• A[0] = s
• A[1] = t
• A[n] = A[n-1] + A[n-2] nếu n chẵn, ngược lại A[n] = A[n-2] + A[n-1].

Ví dụ, s = "pk", t = "r", n = 4, đầu ra "rrpkrpk".

Các bước giải quyết:

• Nếu n == 0 trả về s; nếu n == 1 trả về t.
• a := s, b := t.
• Với i từ 2 đến n:
  • Nếu i % 2 == 0: c = b + a.
  • Ngược lại: c = a + b.
  • a = b, b = c.
• Trả về c.

Ví dụ minh họa

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))

Đầu vào

"pk", "r", 4

Đầu ra

rrpkrpk