精华内容
下载资源
问答
  • N顶点凸多边形对角线交点个数

    千次阅读 2020-02-28 11:02:47
    题目描述 对于一个N个定点多边形,他任何三条...如果我们确定了4个顶点组合方式,我们也就能确定有多少个四边形,进而确定有多少对角线交点。用排列组合计算公式就是 即N*(N-1)(N-2)(N-3)/(4321) 考...

    题目描述
    对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。

    例如,6边形:
    在这里插入图片描述
    我们可以发现,两条不平行对角线才会有一个交点,同时,两条对角线又确定了一个四边形,也就是确定了4个顶点。如果我们确定了4个顶点的组合方式,我们也就能确定有多少个四边形,进而确定有多少个对角线交点。用排列组合的计算公式就是
    在这里插入图片描述
    即N*(N-1)(N-2)(N-3)/(4321)
    考虑到如果初始N很大时,上面结果会超级大,可以改写成N
    (N-1)/2*(N-2)*/3(N-3)/4

    那为什么这样一定是对的呢?难道不会因为除不尽却向下取整而导致错误吗?

    事实上是一定除得尽的

    首先n和n-1一定有一个是2的倍数,因此2可以除尽,

    同理n,n-1,n-2中一定有一个是3的倍数,因此3可以除尽(除掉2只会消除因数2而对3没有影响)

    同理4也可以除尽
    用C语言描述就是:

    #include<stdio.h>
    
    int main()
    {
    	unsigned long long n;
    	scanf("%lld",&n);
    	if(n<=3)
    		printf("0\n");
    	else
    		printf("%lld\n",n*(n-1)/2*(n-2)/3*(n-3)/4);
    	return 0;
    }
    
    
    

    (此代码在VC++6.0中无法运行,会出现error C2632: ‘long’ followed by ‘long’ is illegal
    原因:

    因为 VC6中所使用的编译器是C90标准的,而 long long 型是在C99中新加入的

    (longlong int双长整型是C 99扩充的数据类型,同时扩充的还有float_complex,double_complex,long

    long_complex,bool等),故无法实现编译。(——此答案搜索于百度)
    VisualC++6.0 环境运行下,将long long 用 _int64 进行替换,则输入输出的格式字符串应该写成%I64d以输入输出long long类型的整数。)

    在这里插入图片描述

    展开全文
  • P2181 对角线

    2021-02-27 18:27:08
    对于一个N个定点多边形,他任何三条对角线都不会交于一点。请求楚图形中对角线交点个数。 例如,6边形: 题解: 首先由于不会三条对角线交于一点,所以过某一个交点且只能条对角线 而这两条对角线...

    P2181 对角线

    原题链接及题解
    题目描述
    对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。

    例如,6边形:
    在这里插入图片描述

    题解:

    首先由于不会有三条对角线交于一点,所以过某一个交点有且只能有2条对角线

    而这两条对角线实质上是确定了4个顶点(也可以看做是一个四边形的两条对角线交于一点,求四边形的数量)。

    因此我们只需要确定4个顶点就得到了这个唯一确定的交点。

    因此我们只需要求这样4个顶点的搭配有多少个了

    也就是从n个顶点中取4个出来。

    根据组合数的公式,(如果你不知道组合数的公式可以这么推:第一次取可以n个点都是可以取的,第二次取的时候第一个取的点就不能取了,所以只能取(n-1)种,以此类推)

    由于改变四个点的顺序不会改变对角线,因此是求的组合而不是排列,也就要除以4!,也就是24

    于是我们就得到了公式: n * (n-1) * (n-2) * (n-3) / 24

    同时为了防止爆掉,但又不想写高精,

    我们可以采用一种化简的技巧

    于是原式可以化为:

    n * (n-1) / 2 * (n-2) / 3 * (n-3) / 4

    那为什么这样一定是对的呢?难道不会因为除不尽却向下取整而导致错误吗?

    事实上是一定除得尽的

    首先n和n-1一定有一个是2的倍数,因此2可以除尽,

    同理n,n-1,n-2中一定有一个是3的倍数,因此3可以除尽(除掉2只会消除因数2而对3没有影响)

    同理4也可以除尽

    #include <bits/stdc++.h>
    using namespace std;
    int main(){
    	unsigned long long n,ans;
    	scanf("%lld",&n);
    	ans=n*(n-1)/2*(n-2)/3*(n-3)/4;
    	printf("%lld",ans);
    	return 0;
    }
    
    展开全文
  • 欧拉问题:凸多边形划分为三角形方法数 2017-05-14 08:29 触摸标题下面一行中“北京 邵勇”后面蓝字“数学教学研究本公众号内容均由邵勇本人独创。...一个正七边形有多少条对角线?(7个点之间两两连线,...

    欧拉的问题:凸多边形划分为三角形的方法数

    触摸标题下面一行中“北京 邵勇”后面的蓝字“数学教学研究本公众号内容均由邵勇本人独创。每周推送两到三篇内容上有分量的数学文章,但在行文上力争做到深入浅出。几分钟便可读完,轻松学数学。

    今天是5月14日,我们按照规定,给出几道答案等于14的题目。

    (一)

    一个正七边形有多少条对角线?(7个点之间两两连线,可以连接出7*6/2=21条线段,其中有七条是正七边形的边,那么,剩余线段的数量就是正七边形对角线的数量,请您自己计算。另外,也可以从另一角度来计算对角线的数量:广义的正七边形还包括星状七边形。星状七边形有两种,一种是从任意一个顶点出发,相隔一个顶点依次进行连线,这样,连接七次后,回到出发点,形成下图中红色的星状七边形。第二种也是从任意一个顶点出发,但这次是相隔两个顶点依次进行连线,于是,也是连接七次后回到出发点,连接出下图中绿色星状七边形。红绿两种星状七边形是不同的,互相不会重复或重叠。两种星状七边形的边合在一起,构成全部正七边形的对角线。)

    (二)

    一个正四边形(正方形)可以有两种方法把它划分成两个三角形:

    一个正五边形有下面五种方法把它划分成三角形:

    那么,一个正六边形可以有多少种方法把它划分成三角形呢?

    下面是几个公式:

    (1)欧拉给出的公式(n代表正多边形的边数):

    (2)塞格纳(Johann Andreas Segner)的公式(其中规定E2=1):

    请您自行验证一下正六边形内划分出三角形的方法共有多少种(n取6时)。上面是对正多边形进行的讨论。其实对凸多边形都是成立的。

    转载于:https://www.cnblogs.com/vectors07/p/8053427.html

    展开全文
  • 卡特兰数之凸多边形的三角分割数

    千次阅读 2018-03-27 16:04:38
    给定一个n多边形,要求用n-3不相交的对角线把它分成n-2个三角形。求有多少种不同的方法。 分析 为什么是n-3不相交的对角线? n多边形有n个顶点,依次将其编号为V1、V2、V3、…、Vn。 从V1号到V3号连线,分成...

    题意

    给定一个n多边形,要求用n-3条不相交的对角线把它分成n-2个三角形。求有多少种不同的方法。

    分析

    为什么是n-3条不相交的对角线?

    n多边形有n个顶点,依次将其编号为V1、V2、V3、…、Vn。
    从V1号到V3号连线,分成一个三角形和一个(n-2)边形(因为顶点有n-3+1个)。再对(n-2)边形重新编号,并从V1号到V3号连线,如此重复,连n-3次就可以n-2个三角形。
    也就是说用不相交的对角线来分割多边形为三角形,一定是n-3条线和n-2个三角形。

    有多少种方法?
    对于边V1Vn,任选一顶点Vk,向V1和Vn连边。将三角形V1VnVk分割出去,剩下两个多边形,一个多边形有顶点{1,2,3,…,k},所以是k边形;另一个多边形有顶点{k,k+1,…,n},所以是(n-k+1)边形。然后继续分割多边形直到都变成了三角形,这个过程可以用递归或递推实现。
    设d(n)表示将n边形分割成三角形的方法数。

    回顾下我们分割的过程:先选边V1Vn,因为编号是我们遍的,所以不管我们选哪条边,都可以看成V1Vn。选边V1Vn只有一种可能。然后选顶点Vk,Vk的取值范围为[V2,Vn-1],选顶点有n-2种可能。再递归调用d(k)和d(n-k+1)去计算。
    综上,枚举k从2到n-1,累加d(k)*d(n-k+1)的值即可。

    怎么去实现?
    递推版:
    由下及上,边界d[2]=d[3]=1,
    d[n]=d[2]*d[n-1]+d[3]*d[n-2]+…+d[n-2]*d[2].

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef unsigned long long ll;
    
    const int maxn=25;
    int d[maxn];
    void catalan()
    {
        d[2]=d[3]=1;
        for(int i=4;i<maxn;i++)
        {
            d[i]=0;
            for(int j=2;j<=i-1;j++)
                d[i]+=d[j]*d[i-j+1];
        }
    }
    int main()
    {
        int n;
        catalan();
        while(cin>>n)
        {
            cout<<d[n]<<endl;
        }
        return 0;
    }
    

    递归版:
    由上及下,记忆化搜索。

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef unsigned long long ll;
    
    const int maxn=25;
    int d[maxn],vis[maxn];
    int dp(int n)
    {
        if(n==2||n==3) return d[n]=1;
        if(vis[n]) return d[n];
        vis[n]=1;
        int &ans=d[n];
        ans=0;
        for(int i=2;i<=n-1;i++)
            ans+=dp(i)*dp(n-i+1);
        return ans;
    }
    int main()
    {
        int n;
        memset(vis,0,sizeof(vis));
        while(cin>>n)
        {
            cout<<dp(n)<<endl;
        }
        return 0;
    }
    
    展开全文
  • 题意 给定一个n多边形,要求用n-3不相交的对角线把它分成n-2个三角形。求有多少种不同的方法。 分析 为什么是n-3不相交的对角线...
  • 高中教育试讲

    2014-05-03 19:13:00
    解答:去边法,现将这个多边形的对角线的去掉.假设第一对角线与其他内部对角线有$k_{1}$个交点,那么去掉它这个多边形内部减少$k_{1}+1$个;再去掉第二,内部区域减少$k_{2}+1$个去掉第三,内部区域减少$k...
  • 同样,如果知道多边形有多少条边,我们可以计算出所有多边形的对角线数量。 计算内接圆的正方形的周长要稍微复杂一些。 我们可以使用半径来计算正方形尺寸的长度,然后使用它们来计算其周长。 使用勾股定理,我们...
  • 原题链接 卡特兰数有一个重要的应用:  求将一个凸多边形区域分成三角形区域的方法数。 ... 类似:一位大城市的律师在她住所以北n...如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
  • 一个多边形,三角剖分,求一条对角线最多能经过多少三角形 题解: 因为不涉及坐标之类,所以根几何肯定一点关系都没有。 我们会发现,对于共边两个三角形,可以被同一线穿过,而这就相当于这两个三角形之间...
  • //随便画一个正方形知道, 知道任意两个点后, 可以算出其他两个点坐标(画一画就知道了), 而实际上我们枚举了一个正方形条对角线和两边, 即一个正方形我们算了4次,所以最后答案要除4. // 画一个正方形,
  • 组合数学入门

    2020-11-23 12:22:14
    如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路? 在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 对角线不相交的情况下,将一个凸多边形区域分成...
  • 枚举正方形的对角线,因为对角线,最后答案要/2 也可以枚举正方形的边,因为边,答案要/4 看当前对角线确定的正方形是否存在,用几何知识求出目标点的坐标,然后二分查找目标点是否存在 【Acc...
  • 2、枚举每边,通过枚举边,查询以当前边为对角线的正方形,另外两个点是否存在,查询用二分实现 3、由于每个正方形条对角线,所以答案要除以2 #include using namespace std; #define LL long ...
  • 组合数学各类公式及应用总结

    千次阅读 2018-07-24 15:24:47
    转载注明出处 卡特兰数 应用 矩阵连乘: P=a1×a2×a3×……...在一个凸多边形中,通过若干互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数 ...
  • 卡特兰数

    2018-09-06 21:47:11
    先放一张图 ...4.欧拉多边形分割问题(凸n边形用n-3不相交的对角线分成n-2个互相没有重叠的三角形) 5.在圆上选择2n个点,将这些点成对链接起来使得所得到的n线段不相交,一共有多少种方法 6.一...
  • 那么边长一定相等,且任意对角线都会大于边长(三角形除外),所以只需要先对任意一个点与其他所有点进行距离计算,再遍历所有可能任意两点,找出最短路径有多少条,如果正好是n条,就是正多边形。(因为n最多...
  • 题意:给定一个由n个顶点组成多边形,顶点都是整点,求有多少条对角线可以把该多边形分成两部分,满足两部分面积都是整数。 分析:多边形面积S=1/2 |∑(xi*y(i+1)-x(i+1)*yi)|,只需要判断绝对值里东西是否...
  • 将一个凸多边形区域分成三角形区域(划分线不交叉)方法数? 类似:在圆上选择2n个点,将这些点成连接起来使得所得到n线段不相交方法数? 3.出栈次序问题。一个栈(无穷大)进栈序列为1,2,3,..n,有多少个不同...
  • 在一个平面直角坐标系中给出一个多边形,相邻边垂直且每边与坐标轴平行,要求在所有顶点放置发射器或者接收器,每个发射器能发射光线,且方向为平分线,可以在到达每边后进行反射,每个接收器只能接受一个发射...
  • GSP5.exe

    2020-04-01 09:16:40
    简言之,《几何画板》循环就是“图画”中“图画”,循环记录可以用无限循环来定义,但是当你播放这些记录时,先要指定循环深度,以确定有多少次重复,否则,记录文件播放将不会停止。 [例]作“以三角形三边...
  • UnmapViewOfFile 在当前应用程序内存地址空间解除一个文件映射对象映射 VerFindFile 用这个函数决定一个文件应安装到哪里 VerInstallFile 用这个函数安装一个文件 VerLanguageName 这个函数能根据16位语言...
  • 转来备用,以后慢慢学

    2010-05-21 14:14:33
    在信息面板可视前提下,选择度量工具点击并拖出一直线,按住Alt键从第一条线的节点上再拖出第二直线,这样两条线夹角和线的长度都显示在信息面板上。用测量工具拖动可以移动测量线(也可以只单独移动测量线...
  • protel2004封装

    2012-10-23 10:43:48
    如果创建不是DIP封装元件,要根据焊盘的多少设置,当然由于是DIP封装设置一般要采用双数,如果设置和具体封装区别,在后面我们还可以修改,设置好后单击“Next”; ⑦、在这个对话框中是设置封装元件名称...
  • 顶部鼠标右键菜单,可动态控制时间CPU+左上面板+左下面板+右上面板+右下面板显示和隐藏,支持恢复默认布局。 工具栏可以放置多个小图标和关闭图标。 左侧右侧可拖动拉伸,并自动记忆宽高位置,重启后恢复...
  • 多媒体教室

    2013-06-14 08:10:31
    如果网络中 Windows NT 4.0 或 Windows 2000 服务器,并且服务器上安装 DHCP 服务,此时学生机网卡所绑定 TCP/IP 协议设置上可以设为自动获取 IP 地址。如果网络中没有服务器或服务器上没有安装 DHCP 服务,...

空空如也

空空如也

1 2
收藏数 29
精华内容 11
热门标签
关键字:

多边形的对角线有多少条