นับวิธีแบ่งวงกลมด้วยเส้นเชื่อม N เส้นที่ไม่กันเองด้วย C++

ได้รับจำนวนเต็ม N เป็นอินพุตสำหรับจำนวนเส้นเชื่อม (chords) ในวงกลมที่มีจุดปลาย 2×N จุด เป้าหมายคือนับจำนวนวิธีที่สามารถแบ่งวงกลมได้โดยใช้เส้นเชื่อมเหล่านี้ โดยที่ไม่มีเส้นเชื่อมไหนตัดกัน

สำหรับ N=3 จะมี 6 จุด 1 วิธีได้ 3 เส้นเชื่อมคือระหว่าง 1-2, 3-4, 5-6

วิธีอื่นๆ:

1-6, 2-5, 3-4
1-2, 3-6, 4-5
1-4, 2-3, 5-6
1-6, 2-3, 4-5

รวม 5 วิธี

ตัวอย่าง

Input

N=4

Output

Count of ways to divide circle using N non-intersecting chords are: 14

Explanation

There will be a total 8 points between which we can draw chords. After drawing the first chord, the rest of the points will be divided into two sets. No chord can be drawn between points from set 1 and set 2 as they will intersect with the first chord.

Input

N=6

Output

Count of ways to divide circle using N non-intersecting chords are: 132

Explanation

There will be a total 12 points between which we can draw chords. After drawing the first chord, the rest of the points will be divided into two sets. No chord can be drawn between points from set 1 and set 2 as they will intersect with the first chord.

วิธีการที่ใช้ในโปรแกรม

วิธีนี้นับวิธีจากจำนวนวิธีก่อนหน้า ถ้าเราวาดเส้นเชื่อมระหว่าง 2 จุด จุดที่เหลือจะถูกแบ่งเป็นสองชุด set1 และ set2 ถ้าเราวาดเส้นเชื่อมระหว่างจุดในสองชุดนี้ จะตัดกับเส้นแรก

• รับจำนวนเต็ม N เป็นอินพุต
• ฟังก์ชัน divide_circle(int N) คืนค่าจำนวนวิธีแบ่งวงกลม
• จำนวนจุดทั้งหมด = 2*N เป็น total_points
• สร้างอาร์เรย์ total_cuts[] เก็บจำนวนวิธี
• สำหรับ 0 หรือ 2 จุด จะมี 1 วิธี เริ่มต้น total_cuts[0], total_cuts[2] = 1
• สำหรับจุดอื่นๆ เริ่มจาก points=4 จำนวนวิธีทั้งหมด = วิธีกับ i จุด และ n-i-1 จุดที่เหลือ
• ดังนั้น total_cuts[i] += (total_cuts[j] * total_cuts[i-2-j])
• ในที่สุด total_cuts[total_points] จะเป็นจำนวนวิธีทั้งหมด
• คืนค่า total_cuts[total_points] เป็นผลลัพธ์

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int divide_circle(int N){
    int total_points = 2 * N;
    int total_cuts[total_points + 1] = { 0 };
    total_cuts[0] = 1;
    total_cuts[2] = 1;
    for (int i = 4; i <= total_points; i += 2){
        for (int j = 0; j < i-1; j += 2){
            total_cuts[i] += (total_cuts[j] * total_cuts[i-2-j]);
        }
    }
    return total_cuts[total_points];
}

int main(){
    int N = 3;
    cout << "Count of ways to divide circle using N non-intersecting chords are: " << divide_circle(N);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of ways to divide circle using N non-intersecting chords are: 5