数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
