กำหนดจำนวนเต็ม N เป็นอินพุตสำหรับคอร์ดจำนวนหนึ่งในวงกลมที่มีจุดสิ้นสุด 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 วิธี
ตัวอย่าง
อินพุต
N=4
ผลลัพธ์
Count of ways to divide circle using N non-intersecting chords are: 14
คำอธิบาย
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.
อินพุต
N=6
ผลลัพธ์
Count of ways to divide circle using N non−intersecting chords are: 132
คำอธิบาย
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) รับค่าตัวเลขและคืนค่าจำนวนวิธีในการหารวงกลมโดยใช้คอร์ดที่ไม่ตัดกันของ N
-
จำนวนคะแนนทั้งหมดจะเป็น 2*N เป็นจำนวนคะแนนทั้งหมด
-
ใช้อาร์เรย์ total_cuts[] ในการนับจำนวนวิธี
-
สำหรับ 0 หรือ 2 คะแนน จะมีเพียง 1 วิธีในการเริ่มต้น total_cuts[0], total_cuts[2] ด้วย 1
-
สำหรับจุดอื่นๆ ที่เริ่มจากจุด=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;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of ways to divide circle using N non-intersecting chords are: 5
