สมมติว่าเรามีสตริงที่มีจำนวน n ของ A และจำนวน 2n ของ B เราต้องหาจำนวนการจัดเรียงที่เป็นไปได้ว่าในแต่ละคำนำหน้าและแต่ละส่วนต่อท้ายมีจำนวนของ B มากกว่าหรือเท่ากับจำนวนของ A
ดังนั้น ถ้าอินพุตเป็นเหมือน n =2 ผลลัพธ์จะเป็น 4 เพราะมี A สองตัวและ B สี่ตัว ดังนั้นการจัดเรียงที่เป็นไปได้คือ [BBAABB, BABABB, BBABAB, BABBAB]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดวิธีการแก้ จะใช้เวลา n
- ถ้า n เหมือนกับ 1 แล้ว
- คืน 1
- ถ้า n เหมือนกับ 2 แล้ว
- คืน 4
- ถ้า n เป็นเลขคี่
- ส่งคืน find(ชั้นของ (n-1)/2)^2
- มิฉะนั้น
- ผลตอบแทนการค้นหา(ชั้นของ n/2)^2
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(n): if n==1: return 1 if n==2: return 4 if n%2 != 0: return solve((n-1)//2)**2 else: return solve(n//2)**2 n = 2 print(solve(n))
อินพุต
2
ผลลัพธ์
4
