q********c
发帖数: 1774 | 1 给一array of ints, 找出三个数使他们能组成一个三角形。刷刷刷！！！ |
r****y
发帖数: 26819 | 2 这啥题啊，组成三角形三个边？
【在 q********c 的大作中提到】
: 给一array of ints, 找出三个数使他们能组成一个三角形。刷刷刷！！！
|
q********c
发帖数: 1774 | 3 对，比如找到A,B,C满足
A+B>C
A+C>B
B+C>A
【在 r****y 的大作中提到】
: 这啥题啊，组成三角形三个边？
|
l*********8
发帖数: 4642 | 4 bool canBuildTriangle(int a[], int n) {
sort(a, a+n);
for (int *p = a+1; p < a+n-1; p++)
if (*p + *(p-1) > *(p+1))
return true;
return false;
}
【在 q********c 的大作中提到】
: 给一array of ints, 找出三个数使他们能组成一个三角形。刷刷刷！！！
|
d********i
发帖数: 582 | |
r****y
发帖数: 26819 | 6 要求找数，不是真假
【在 l*********8 的大作中提到】
: bool canBuildTriangle(int a[], int n) {
: sort(a, a+n);
: for (int *p = a+1; p < a+n-1; p++)
: if (*p + *(p-1) > *(p+1))
: return true;
: return false;
: }
|
l*********8
发帖数: 4642 | 7 我只是用程序表达一下思路，懒得返回三个数了。 要改的话，就是把return 语句改改.
【在 r****y 的大作中提到】
: 要求找数，不是真假
|
q********c
发帖数: 1774 | 8 G. longway的思路是对的。
【在 r****y 的大作中提到】
: 要求找数，不是真假
|
d********i
发帖数: 582 | |
r****y
发帖数: 26819 | 10 显然没找全啊
只找了排序后相邻的两个较小边加起来的情况
排序后不相邻的两个边为啥不能加起来大于第三边呢
【在 q********c 的大作中提到】
: G. longway的思路是对的。
|
|
|
r****y
发帖数: 26819 | 11 抱歉，程序也不对
改.
【在 l*********8 的大作中提到】
: 我只是用程序表达一下思路，懒得返回三个数了。 要改的话，就是把return 语句改改.
|
l*********8
发帖数: 4642 | 12 请指教，谢谢了
【在 r****y 的大作中提到】
: 抱歉，程序也不对
:
: 改.
|
q********c
发帖数: 1774 | 13 不须要找全，只需返回第一个满足条件的三个数
【在 r****y 的大作中提到】
: 显然没找全啊
: 只找了排序后相邻的两个较小边加起来的情况
: 排序后不相邻的两个边为啥不能加起来大于第三边呢
|
r****y
发帖数: 26819 | 14 我只知道sort以后老老实实简简单单：
for (int *p = a; p < a+n-2; p++) {
for (int *q = p+1; q < a+n-1; q++) {
for (int *r = q+1; r < a+n; r++) {
if (*p + *q > *r) {
printf("%d, %d, %d\n", *p, *q, *r);
}
else {
break;
}
}
}
}
【在 l*********8 的大作中提到】
: 请指教，谢谢了
|
r****y
发帖数: 26819 | 15 写法一样，找到一个就停下即可。
【在 q********c 的大作中提到】
: 不须要找全，只需返回第一个满足条件的三个数
|
w****m
发帖数: 146 | 16 your solution is much more slower..
It could be done within single loop
【在 r****y 的大作中提到】
: 我只知道sort以后老老实实简简单单：
: for (int *p = a; p < a+n-2; p++) {
: for (int *q = p+1; q < a+n-1; q++) {
: for (int *r = q+1; r < a+n; r++) {
: if (*p + *q > *r) {
: printf("%d, %d, %d\n", *p, *q, *r);
: }
: else {
: break;
: }
|
r****y
发帖数: 26819 | 17 do you have this loop? :-)
【在 w****m 的大作中提到】
: your solution is much more slower..
: It could be done within single loop
|
w****m
发帖数: 146 | 18 longway2008's solution is the one
【在 r****y 的大作中提到】
: do you have this loop? :-)
|
w****3
发帖数: 110 | 19 如果输出真假是可以的，如果要求全部就只能brute force了
【在 l*********8 的大作中提到】
: bool canBuildTriangle(int a[], int n) {
: sort(a, a+n);
: for (int *p = a+1; p < a+n-1; p++)
: if (*p + *(p-1) > *(p+1))
: return true;
: return false;
: }
|
r****y
发帖数: 26819 | 20 for different question, right?
【在 w****m 的大作中提到】
: longway2008's solution is the one
|
|
|
s********e
发帖数: 23 | 21 三角形的条件就是任意两边之和大于第三边。 所以，先排序，最小的两边相加之和大
于第三边的话，那其他任意俩边之和无疑是大于第三边的。
java:
public boolean isTriangle(int[] arr) {
Arrays.sort(arr);
for (int i = 0; i < arr.length - 2; i++) {
if (arr[i] + arr[i + 1] > arr[i + 2])
return true;
}
return false;
} |
o***g
发帖数: 2784 | 22 程序结果是对的，但是逻辑不够严谨
比如排好序之后，序号相邻的0 1 2 3四个数
如果0 1 2 不满足，那还有0 1 3， 0 2 3， 1 2 3三组数。为什么只检查1 2 3就可以
了呢
因为0 1 2 不满足，那0 1 3肯定也不满足，因为3>=2。
如果0 2 3满足，则1 2 3必然满足，反之不一定。
因为题目是只需要找到一组就行了。所以只检查1 2 3这组就好了。
【在 s********e 的大作中提到】
: 三角形的条件就是任意两边之和大于第三边。 所以，先排序，最小的两边相加之和大
: 于第三边的话，那其他任意俩边之和无疑是大于第三边的。
: java:
: public boolean isTriangle(int[] arr) {
: Arrays.sort(arr);
: for (int i = 0; i < arr.length - 2; i++) {
: if (arr[i] + arr[i + 1] > arr[i + 2])
: return true;
: }
: return false;
|
x***2
发帖数: 93 | |
G****A
发帖数: 4160 | 24 证明只需要check相邻的三个数：
假设有三个不相邻的数也符合要求:a_k-i + a_k > a_k+j where i and j are任意正整
数。
因为a_k-1 >= a_k-i,所以 a_k-1 + a_k > a_k+j
因为a_k+1 <= a_k+j,所以 a_k-1 + a_k > a_k+1
【在 o***g 的大作中提到】
: 程序结果是对的，但是逻辑不够严谨
: 比如排好序之后，序号相邻的0 1 2 3四个数
: 如果0 1 2 不满足，那还有0 1 3， 0 2 3， 1 2 3三组数。为什么只检查1 2 3就可以
: 了呢
: 因为0 1 2 不满足，那0 1 3肯定也不满足，因为3>=2。
: 如果0 2 3满足，则1 2 3必然满足，反之不一定。
: 因为题目是只需要找到一组就行了。所以只检查1 2 3这组就好了。
|
d********i
发帖数: 582 | |
G****A
发帖数: 4160 | 26 6 + 7 > 3 满足么？
“任意2边和大于第三边”是必要条件，但是不是充要条件我忘记论证方法了。
【在 d********i 的大作中提到】
: 我能请教下为什么3,6,7可以组成一个三角形吗？
: 参考链接：http://www.geeksforgeeks.org/find-number-of-triangles-possible/
|
