Giả sử chúng ta có hai chuỗi s, t và một số dương n khác cũng được cho trước, chúng ta phải tìm trả về số hạng thứ n của chuỗi A trong đó -
- A [0] =s
- A [1] =t
- A [n] =A [n - 1] + A [n - 2] khi n chẵn, ngược lại A [n] =A [n - 2] + A [n - 1].
Ví dụ:nếu s ="a" và t ="b", thì chuỗi A sẽ là - ["a", "b", "ba" ("a" + "b"), "bba" ( "b" + "ba"), "bbaba" ("bba" + "ba")]
Vì vậy, nếu đầu vào là s ="pk", t ="r", n =4, thì đầu ra sẽ là "rrpkrpk"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- nếu n giống 0, thì
- trả lại s
- ngược lại khi n giống 1 thì
- trả lại t
- a:=s, b:=t
- đối với tôi trong phạm vi từ 2 đến n, thực hiện
- nếu tôi mod 2 giống 0, thì
- c:=b nối a
- nếu không,
- c:=a nối liền b
- a:=b
- b:=c
- nếu tôi mod 2 giống 0, thì
- trả lại c
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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