สมมติว่าเรามีตัวเลข n เราต้องหาจำนวนสตริงที่มีขนาด n ที่ประกอบด้วยสระเท่านั้น (a, e, i, o, u) และจัดเรียงตามพจนานุกรม เราสามารถพูดได้ว่าสตริง s ถูกจัดเรียงตามพจนานุกรมเมื่อสำหรับดัชนีที่ถูกต้องทั้งหมด i, s[i] จะเหมือนกับหรือมาก่อน s[i+1] ในตัวอักษร
ดังนั้น หากอินพุตเป็น n =2 เอาต์พุตจะเป็น 15 เนื่องจากมีหลายสตริง เช่น ["aa", "ae", "ai", "ao", "au", "ee", "ei ", "eo", "eu", "ii", "io", "iu", "oo", "ou", "uu"].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ถ้า n เหมือนกับ 1 แล้ว
- คืน 5
- จำนวน :=อาร์เรย์ขนาด 6 และเริ่มต้นด้วย 1
- สำหรับฉันในช่วง 3 ถึง n ทำ
- นับ[1] :=นับ[1]+นับ[2]+นับ[3]+นับ[4]+นับ[5]
- นับ[2] :=นับ[2]+นับ[3]+นับ[4]+นับ[5]
- นับ[3] :=นับ[3]+นับ[4]+นับ[5]
- นับ[4] :=นับ[4]+นับ[5]
- รวม :=0
- สำหรับผมในช่วง 1 ถึง 5 ทำ
- รวม :=ทั้งหมด + i*count[i]
- ผลตอบแทนรวม
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(n): if n==1: return 5 count = [1 for i in range(6)] for i in range(3,n+1): count[1] = count[1]+count[2]+count[3]+count[4]+count[5] count[2] = count[2]+count[3]+count[4]+count[5] count[3] = count[3]+count[4]+count[5] count[4] = count[4]+count[5] total = 0 for i in range(1,6): total += i*count[i] return total n = 2 print(solve(n))
อินพุต
2
ผลลัพธ์
15
