前言
大家好,我是bigsai,好久不见甚是想念。
昨晚有个同学参加了阿里的笔试题,笔试完后同学说这次笔试感觉难,跟我说了其中一道题,我看了感觉还是挺有质量的,看着这个难度都是第二题,总共三题感觉还是有难度的(瑟瑟发抖),想着还是和大家分享一下。
描述
一个正m边形,他想知道多边形中等腰锐角三角形的数量。(三角形的顶点要在多边形的顶点上)
不同的三角形的定义:两个三角形,只要有一个点不在同一个位置上就算做不同的三角形。
数据范围3-10^7
分析
昨天看到这个问题,觉得还是比较新颖,也有很多细节,但是刚拿到这个问题自己懵逼的画了好久也才想出来,这里给大家share一下。
瞎折腾问题的描述很简单,边为n的正多边形有多少等腰锐角三角形。
遇到这种问题我们该怎么分析呢?当然是先画几个案例分析一下。
这么一看,你可能觉得好像没啥规律哇。
你可能对奇数的有点眉目:奇数的每个边直直的就是对应一个点,那么有多少条边就有多少个等腰锐角三角形?
但是这个显然是错误的,有可能以不同的顶点作为等腰锐角三角形它刚好是个等边三角形,这样就会出现重复,然后还有的底边可能并不是恰好是多边形的一个边,而是多边形多个边组成底边(参考上图的正6边型)。
并且从这来看奇数边和偶数边还是有点区别的:放正来看,奇数的是点对边,而偶数的是点对点,结构上有些区别,那么有可能奇偶在结果上是有点区别的。
上面都是一个懵懵懂懂的状态,咱们整理一下有用的信息:
正多边形,多少边就是多少个顶点
正多边形,有轴对称的特性,等腰锐角三角形,也有轴对称的特性。
等腰锐角三角形,腰有两个,而底边有一个,要么从底边考虑,要么从顶点考虑,这里底边如上面的正6边型甚至更多边型显然不容易考虑,但是各个顶点都是多边形的顶点,所以肯定从顶点考虑。算出一个顶点为等腰锐角顶角的所有三角形乘以顶点数量(如正五边形)然后减去重复(如正3、正6边形)的就是总结果了。
奇数偶数分开讨论。
偶数情况
我们先用偶数的情况分析,先不考虑重复情况(考虑太多脑子混淆),将 图形摆一下成这样:
因为为正多边形,所以也就相当于各个顶点在圆上,这样更容易分析是不是锐角,这样的分析每个点,就很容易看出每个顶点对应多少个锐角了,正6、正8每个顶点都对应一个锐角,其实有的人可能已经看出规律了,就是在直角下方的线都能组成锐角。
为了更清晰的观察,看下面这个图更清晰:
其实就是计算直角下面的蓝色线的数量,这个直观一点是所有横线数量的一半(向下取整),每个横线由两个点组成,我们计算一下:
总共n个点,去掉两个顶点和最底下单个点,n-2个点组成(n-2)/2
的线。其中直角下面的占一半就是[(n-2)/2]/2=(n-2)/4
个,然后乘以顶点数量n,那么在偶数情况不考虑重复所有等腰锐角三角形数量为:
total=n*((n-2)/4))
奇数情况
回了偶数分析,奇数也很简单,奇数顶点不变,底边固定,也就是找能够组成锐角三角形的边数。
对于横线数量,如果是偶数个没疑问下面是锐角(上面多个顶点所以角度比直角小),而奇数个中间那条线同样也是锐角(如果去掉顶点才在中央),所以这种情况是横线数量的一半(向上取整),我们计算一下:
总计n个点,一个顶点,n-1个点组成线。那么有(n-1)/2
个线,其中组成锐角三角形的一半向上取整那就是(n-1)/2+1
,然后乘以顶点数量n,那么在奇数情况不考虑重复所有等腰锐角三角形数量为:
total=n*(((n-1)/2+1)/2))
重复三角形
上面考虑了不重复的三角形的情况,那么重复的三角形该怎么考虑了,上面看到正三角形、正6边型都遇到等边三角形而导致重复计算。
而正5、正7好像没有重复的等边三角形。
我们认真分析一下:等腰锐角三角形三个顶点都在正多边形的边上,其实也在一个圆上,如果构成等边三角形,说明这三个顶点能够将空间均分分开(也就是顶点、圆可以均匀分成三份)。那么顶点数量 n必须是三的倍数才可以啊!
顶点数量n是3的倍数,那么具体重复了多少呢?
就是看这种等边三角形每个作为顶点,本来应该有n个,但是每种情况出现了三次,所以只考虑其中1/3作为顶点的等边三角形才不重复!所以我们要总次数去掉n的(2/3)。
那么总次数:
total-=(n/3)*2;
具体代码
这里代码有个小坑,n是10^7,那么这个数量级会越界int范围,需要用long,但是输入有的人用int计算这么样代码:
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long total;
if(n%2==0)
total=n*((n-2)/4);
else
total=n*(((n-1)/2+1)/2);
if(n%3==0){
total-=(n/3)*2;
}
System.out.println(total);
}
但是还是错了,有的人还不知道为啥,主要的原因是下面这两句越界了:
total=n*((n-2)/4);
total=n*(((n-1)/2+1)/2);
有人说我已经total设成total设成long为啥还是错的,因为赋值运算符是先计算右侧n*((n-2)/4)
此时相当于这么一个流程:
int temp=n*((n-2)/4);
long total=temp;
因为计算的数值范围都是int,所以最后结果也是int已经越界,然后将越界的这个int结果赋值给long范围的total。
和这个很类似的还有:
double a=3/2;
System.out.println(a);
会输出1.0而不是1.5,如果想要正确计算那么要提前将计算的值转成double计算:
double a=(double) 3/2;
同样这个问题正确的代码为:
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long total;
if(n%2==0)
total=(long)n*((n-2)/4);
else
total=(long)n* (((n-1)/2+1)/2);
if(n%3==0){
total-=(n/3)*2;
}
System.out.println(total);
}
总结
这种数学题、或者找规律的题还是偶尔可能碰到,多会一题多长个经验!当前还是以积累为主。
大家一起加油,有需要的也欢迎一起打卡力扣。
我是bigsai,肝了一本数据结构与算法pdf和一本动态规划pdf
欢迎添加 「bigsai66」,备注[pdf]领取
原创不易,希望路过彦祖仙女点个赞、再看
本文同步分享在 博客“Big sai”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。