ค้นหาจำนวนสามเหลี่ยมที่เกิดขึ้นจากชุดของคะแนนในสามบรรทัดโดยใช้ C++

เราได้รับคะแนนหลายจุดใน 3 บรรทัดตอนนี้ เราจะต้องหาจำนวนสามเหลี่ยมที่จุดเหล่านี้สามารถเกิดขึ้นได้ เช่น

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

Input: m = 2, n = 2, k = 1
Output: 10

เราจะใช้ combinatorics กับคำถามนี้และสร้างสูตรขึ้นมาเพื่อแก้ปัญหานี้

แนวทางในการหาทางออก

ในแนวทางนี้ เราจะคิดค้นสูตรโดยใช้ 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); // the combination of n with 3.
   long long linem = comb(m, 3); // the combination of m with 3.
   long long liner = comb(r, 3); //the combination of r with 3.
   long long answer = comb(n + m + r, 3); // all possible comb of n, m , r with 3.
   answer -= (linen + linem + liner);
   cout << answer << "\n";
   return 0;
}

ผลลัพธ์

205

คำอธิบายของโค้ดด้านบน

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

บทสรุป

บทความนี้กล่าวถึงจำนวนสามเหลี่ยมที่สามารถเกิดขึ้นได้จากชุดของจุดในสามบรรทัดโดยใช้เครื่องมือเชิงผสมผสาน นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์