问题主题:三角形
|
问题描述:
有n根棍子,棍子i的长度为ai,想要从中选出三根棍子组成周长尽可能长的三角形。请输出最大的周长,若无法组成三角形则输出0。
|
样例:
输入
n=5
a={2,3,4,5,10}
输出
12(选择3,4,5时)
输入
n=4
a={4,5,10,20}
输出
0(无法构成三角形)
|
【解法一】
解题分析:
我的思路(java实现)是:
1.先将棍子根据长度从小到大排序;
2.第一根棍子取最长的a1=a[n-1];
3.第二根棍子取次长的a2=a[n-2];
4.第三根棍子取a3=a[n-3],如果a1+a2>a3,则说明可以构成三角形,输出最大周长;
5.如不能构成三角形,则a3依次取a[n-4],a[n-5]...
6.如果a3=a[0]时依旧不行,则要循环a2,使a2依次取a[n-3],a[n-4]...
7.如果再不行,要变换a1值,a1=a[n-2],a2=a[n-3]...也就是使a1,a2,a3依次从高到低取值。
8.a1,a2,a3分别取到最小值a[2],a[1],a[0]还是不能构成三角形时,输出0,结束计算.
书上的分析(用C++实现)是:
直接用三重循环枚举所有的根子选择方案。再用以下公式判断能否构成三角形。
最长棍子的长度<其余两个棍子的长度之和
程序实现:
C++
publicvoidcontructTriangle(inta[]){
//对数组a进行排序
Arrays.sort(a);
intn=a.length;
inta1,a2,a3;
for(inti=n-1;i>=0;i--){
a1=a[i];
for(intj=i-1;j>=0;j--){
a2=a[j];
for(intk=j-1;k>=0;k--){
a3=a[k];
if(a2+a3>a1){
System.out.println("最大"+(a1+a2+a3)+"三角形为"+a1+","+a2+","
+a3);
return;
}
}
}
}
System.out.println("0,不能构成三角形");
}
|
Java
#include <iostream>
#include <algorithm>
void constriangle(int* a, int n) {
int ans = 0; //答案
int len, ma, result;
//让i<j<k,这样棍子就不会被重复选了
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++) {
for(int k=j+1; k<n; k++) {
len = a[i] + a[j] + a[k];
ma = max(a[i], max(a[j], a[k]));
int rest = len-ma;
if(ma <rest) {
ans = max(ans, len);
}
}
}
}
cout<<ans<<endl;
}
int main() {
int a[5] = {2, 3, 4, 5, 10};
constriangle(a, 5);
return 0;
}
|
算法复杂度:
时间复杂度:O(n3)
分享到:
相关推荐
这是一个用WebGL编写的三维分裂三角形,实现了三角形的自动分裂,可以开始,暂停,终止,代码简单,可以参考,这也是西南石油大学南充校区,计算机图形学第三个实验!
选择一个随机点开始,然后通过随机选择一个顶点并计算从顶点到旧点的线段中点的位置来生成每个新点。 然后,中点变为新点,并且算法迭代10,000次,生成三角形的近似值。 Sierpinski三角形是具有Hausdorff尺寸log(3...
帕斯卡三角形的行通常从顶部的行 n = 0 开始枚举。 每行中的条目从左开始编号,从 k = 0 开始,并且通常相对于相邻行中的数字交错排列。 三角形的简单构造按以下方式进行。 在第 0 行,只写数字 1。然后,为了构造...
只要是做好了准备,不管什么事情,那就扎扎实实地开始吧,最后的结果一定很漂亮——至少我是这么认为的。 “哪怕我们深知自己和这个世界都不是精密仪器。但是能完美满足所有人的期待的人又将如何活着呢?” “我们将...
通过本次实验,将老师在课堂上讲解的多边形集合变换算法进行具体代码的实现,对于多边形的几何变换从实现最基本的几何变换开始写起,一开始的图形也不要太过复杂,后面我在扩展功能的时候,才逐渐如鱼得水,说明理论...
内容: OpenGL 4: 你好三角: 使用纯普通JOGL的 ,无需其他库 ... 如果您不知道如何使用Gradle,请按照以下简单 如果您有任何问题/疑问/疑问,请随时在或上或打开 如果您发现上述示例过于复杂或难以理
从本篇文章开始,我会分享给大家canvas绘制的各种基础图形和酷炫的图形,注意:是一系列!欢迎关注! 后续每篇文章我会着重分享给大家一些使用Canvas开发的实例和这些实例的实现思路。 本文看点:使用canvas来绘制...
复制代码代码如下: ”demo” width=”600″ height=”600″></canvas>...开始绘制,有两种形式,一种是描边(fill),一种是填充(stroke)。 javascript代码: 复制代码代码如下: <script language=”javascrip
java 蛇形矩阵 最简单的 初学者用
IDL是一个很强大的开发语言 用IDL开发 一些很简单的程序 是学习IDL的开始
您可以使用4x4矩阵来实现3D空间中的任何旋转都可以表示为3个基本旋转的组合:XY平面中的旋转,YZ平面中的旋转和XZ平面中的旋转:XY旋转矩阵:YZ旋转矩阵:XZ旋转矩阵: 现在我们需要开始用某种物质填充那些三角形。...
最初的想法很简单,认为就是以一个点起点连接和它不相邻的点所有三角形就区分完了。这样写完后放到ue4里面测试,开始比较顺利,当但遇到凹多边形时,就发现问题了。着实一想确实有问题,这样只能判断凸多边形,对于...
从1.8.0版开始,可以将扩展名配置为显示或隐藏文件夹附近的旋转三角形/箭头:只需将simpleIcons.hideArrows更改为true或false 。 从1.10.0版本开始,可以使用带有十六进制颜色代码(例如#bf9f7f )的simpleIcons....
MeshPy:从Python生成简单网格 MeshPy为Python提供了高质量的三角形和四面体网格生成。 这种类型的网格主要用于有限元仿真代码中,但也有许多其他应用,从计算机图形学到机器人技术。 为了产生二维和三维网格,...
码长 列重 编码 误码性能 LDPC码的编码方法及其实现本文首先回顾了数字通信系统和信道编码的内容,简单了解了LDPC编码的研究现状和发展前景之后,从第二章开始从校验矩阵构造方法、LDPC编码方法、LDPC译码方法这三个...
简单,直观的工作流程 只需选择您的对象并开始绘制您希望物理船体包含的内容。向对象添加尽可能多的外壳,因为您需要获得...从平面或三角形创建实体对撞机。非常适合四边形。 并且刚刚添加了“选择范围”和“从选择中生
从与三角形碰撞的任何体素开始,然后进行bfs搜索以检查相邻的体素。 第一种方法是轻量级的,但当(三角形的体积/边界框的体积)的比率小时,可能会变得更糟。 而第二种方式具有相当大的恒定开销。 对于线程池中的每...
用简略的轮廓线(圆形、三角形、方形)来开始你的设计。即使一个图标在自然状况下是有机的,也最好从AI的形状工具开始。当我们开始制作图标,特别是屏幕上小尺寸的图标,手绘导致的不规则的边缘会让一个图标看起来不...