資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中計算總點數為 n，共線點數為 m 的三角形數量
給定兩個變數 n 和 m，分別表示二維平面上點的數量。在 n 個點中，有 m 個點共線。目標是找到可以使用這些 n 個點形成的三角形的數量。
共線點 - 位於同一條直線上的點稱為共線點。點 A 和 B 是共線點。
給定 n=4 (A,B,C,D )，m=2 (A,B)
三角形數量 -
從 4 個點中選擇任意 3 個點 = 4C3
但共線點不能形成三角形，因此刪除上面計算中將計入的可能三角形 = 2C3
三角形總數 = 4C3 - 2C3 = 4 - 0 = 4 (ABC, ACD, BCD, ABD)
對於 n 和 m = nC3 - mC3
讓我們透過示例來理解。
輸入 - n=5，m=3
輸出 - 總點數為 n，共線點數為 m 的三角形數量為 - 9
解釋 - 三角形總數 = 5C3 - 3C3 = 10 - 1 = 9
輸入 - n=10，m=5
輸出 - 總點數為 n，共線點數為 m 的三角形數量為 - 110
解釋 - 三角形總數 = 10C3 - 5C3 = 120 - 10 = 110
下面程式中使用的演算法如下
我們將建立一個帕斯卡三角形來包含組合的計算。每一行都是使用上一行列的加法計算的。
將變數 n 和 m 作為輸入，表示點的數量。
函式 collinear_points(int n,int m) 獲取 n 和 m 並返回總點數為 n，共線點數為 m 的三角形數量。
設定 count = check(n, 3) - check(m, 3); (用於計算 nC3 - mC3)
函式 check(int n, int r) 獲取 n 和 r 並返回 nCr 的值
獲取一個長度為 r+1 的陣列 arr。
使用 memset 將整個陣列設定為 0。
設定 arr[0] = 1。
使用兩個 for 迴圈，從 i=0 到 i<=n。以及 j=min (i,r) 到 j>0 計算帕斯卡三角形為 arr[j]=arr[j]+arr[j-1]。
最後我們將得到 arr[r] 作為 nCr。返回它。
在 check() 函式結束之後。我們將獲得三角形的數量
返回 count 作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int check(int n, int r){
int arr[r+1];
memset(arr, 0, sizeof(arr));
arr[0] = 1;
for (int i = 1; i <= n; i++){
for (int j = min(i, r); j > 0; j--){
arr[j] = arr[j] + arr[j-1];
}
}
return arr[r];
}
int collinear_points(int n,int m){
int count = check(n, 3) - check(m, 3);
return count;
}
int main(){
int n = 6, m = 2;
cout<<"Count of triangles with total n points with m collinear are: "<< collinear_points(n, m);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出 -
Count of triangles with total n points with m collinear are: 20
123 次瀏覽
