สมมติว่าเรามีโหนดต่างกัน n โหนด ทั้งหมดมีความแตกต่างกัน เราต้องหาจำนวนวิธีที่เราสามารถจัดเรียงพวกมันเพื่อสร้างแผนผังการค้นหาแบบไบนารี ดังที่เราทราบสำหรับแผนผังการค้นหาแบบไบนารี ทรีย่อยด้านซ้ายจะมีค่าที่น้อยกว่าเสมอ และแผนผังย่อยด้านขวาจะเก็บค่าที่มากกว่า
เพื่อแก้ปัญหานี้ เราจะหาหมายเลขคาตาลัน หมายเลขคาตาลัน C(n) แสดงถึงแผนผังการค้นหาแบบไบนารีที่มี n คีย์ที่แตกต่างกัน สูตรก็เหมือน
$$C(n)=\frac{(2n)!}{(n+1)!\times n!}$$
ดังนั้นหากอินพุตเป็น n =3 เอาต์พุตจะเป็น 5 เพราะ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน ncr() นี่จะใช้เวลา n, r
- res :=1
- ถ้า r> n - r แล้ว
- r :=n - r
- สำหรับฉันในช่วง 0 ถึง r - 1 ทำ
- res :=res *(n - i)
- res :=ชั้นของ (res/(i + 1))
- ผลตอบแทน
- จากวิธีหลัก ให้ทำดังนี้
- c :=ncr(2 * n, n)
- ชั้นกลับของ c /(n + 1)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from math import factorial def ncr(n, r): res = 1 if r > n - r: r = n - r for i in range(r): res *= (n - i) res //= (i + 1) return res def solve(n): c = ncr(2 * n, n) return c // (n + 1) n = 3 print(solve(n))
อินพุต
3
ผลลัพธ์
5
