Rumah >pembangunan bahagian belakang >C++ >Ditulis dalam C++, cari bilangan segi tiga yang dibentuk oleh set titik pada tiga garis

Ditulis dalam C++, cari bilangan segi tiga yang dibentuk oleh set titik pada tiga garis

王林
王林ke hadapan
2023-09-09 09:53:081283semak imbas

Ditulis dalam C++, cari bilangan segi tiga yang dibentuk oleh set titik pada tiga garis

Sekarang kita mempunyai beberapa titik yang terdapat dalam 3 baris sebagai contoh, kita perlu mengetahui berapa banyak segi tiga titik ini boleh membentuk

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

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

Kami akan menggunakan beberapa matematik gabungan untuk menyelesaikan masalah ini dan merumuskan beberapa formula untuk menyelesaikan Ini soalan.

Kaedah untuk mencari penyelesaian

Dalam kaedah ini kita akan merangka formula: menggunakan kombinatorik kepada situasi semasa, formula ini akan memberikan kita hasilnya.

Kod C++ untuk kaedah di atas

Ini adalah sintaks C++ yang boleh kita gunakan sebagai input untuk menyelesaikan masalah yang diberikan -

Contoh

#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;
}

Output

205

Penjelasan kod di atas

Semua dalam kaedah ini kita temui kemungkinan gabungan n+m+r dan tiga nombor, iaitu sikat(n+m+r, 3). Sekarang, anda tahu bahawa syarat untuk tiga titik menjadi segitiga ialah ia tidak boleh menjadi kolinear, jadi kita dapati semua titik kolinear yang mungkin diperoleh dengan menjumlahkan gabungan n, m, r, dan kemudian menggabungkan jumlah ini dengan n+ Dengan menolak perubahan dalam tiga nombor m+r, kita mendapat jawapan dan mencetaknya.

Kesimpulan

Artikel ini membincangkan cara mengira berapa banyak segi tiga boleh dibentuk daripada set titik pada tiga garisan dengan mengaplikasikan kombinatorik. Kami juga mempelajari program C++ dan kaedah lengkap (kaedah biasa) untuk menyelesaikan masalah ini. Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan bahasa lain. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Ditulis dalam C++, cari bilangan segi tiga yang dibentuk oleh set titik pada tiga garis. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Artikel ini dikembalikan pada:tutorialspoint.com. Jika ada pelanggaran, sila hubungi admin@php.cn Padam