C++ หาจำนวนสามเหลี่ยมจากจุดบนสามเส้นตรง

เราได้รับจำนวนจุดบน 3 เส้นตรง ต้องการหาว่าจุดเหล่านี้สามารถสร้างสามเหลี่ยมได้กี่รูป เช่น

Input: m = 3, n = 4, k = 5 Output: 205
Input: m = 2, n = 2, k = 1 Output: 10

เราจะใช้คณิตศาสตร์การจัดหมู่ (Combinatorics) สร้างสูตรเพื่อแก้ปัญหา

วิธีการแก้ปัญหา

สร้างสูตรโดยใช้คณิตศาสตร์การจัดหมู่กับสถานการณ์ปัจจุบัน ซึ่งจะให้คำตอบที่ต้องการ

โค้ด C++ สำหรับวิธีการข้างต้น

นี่คือโค้ด C++ ที่ใช้แก้ปัญหานี้

ตัวอย่าง

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

long long fact(long long n) { 
    if(n <= 1) return 1; 
    return ((n % MOD) * (fact(n-1) % MOD)) % MOD; 
} 

long long comb(int n, int r) { 
    return (((fact(n)) % MOD) / ((fact(r) % MOD) * (fact(n-r) % MOD)) % MOD); 
} 

int main() { 
    int n = 3; 
    int m = 4; 
    int r = 5; 
    long long linen = comb(n, 3); 
    long long linem = comb(m, 3); 
    long long liner = comb(r, 3); 
    long long answer = comb(n + m + r, 3); 
    answer -= (linen + linem + liner); 
    cout << answer << "\n"; 
    return 0; 
}

ผลลัพธ์

205

คำอธิบายโค้ด

ในวิธีนี้ เราหาการจัดหมู่ทั้งหมดของ n+m+r เลือก 3 คือ comb(n+m+r, 3) เนื่องจากเงื่อนไข 3 จุดจะเป็นสามเหลี่ยมคือต้องไม่อยู่บนเส้นตรงเดียวกัน เราจึงหาจุด一直線 (collinear) ทั้งหมด ซึ่งคือผลรวมของการจัดหมู่ n, m, r เลือก 3 เมื่อลบผลรวมนี้ออกจาก comb(n+m+r, 3) จะได้คำตอบ

สรุป

บทความนี้อภิบัติว่าจุดบนสามเส้นตรงสามารถสร้างสามเหลี่ยมได้กี่รูป โดยใช้คณิตศาสตร์การจัดหมู่ เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์