三角形：确定是否可以从一组给定的边构建一个三角形 [英] Triangle : Determine whether a triangle can be built from a given set of edges

问题描述

我在网络上发现了一个解决方案，用于下面的编码问题：

给出了一个由N个整数组成的零索引数组A.如果0≤P<3，则三元组（P，Q，R）是三角形的。 Q< R& N和：

  A [P] + A [Q]> A [R]，
 A [Q] + A [R]> A [P]，
 A [R] + A [P]> A [Q]。 
  

例如，考虑数组A：

A [0] = 10 A [1] = 2 A [2] = 5
A [3] = 1 A [4] = 8 A [5] = 20

b

三元组（0,2,4）是三角形的。

写一个函数：

  int solution（int A []，int N）; 
  

给定一个由N个整数组成的零索引数组A，如果存在一个三角形

解决方案如下所示：

 <$ （int i = 0; i< A.length-2&& A [i]> 0; i ++）
 {
 if （A [i] + A [i + 1]> A [i + 2]）
返回1; 
} 
  

但是，当我们对数组排序时，原始索引不再有效，在我的位置可以移动到j位置j> i或j

解决方案假设验证断言（三角形）的值在排序数组中自动相邻。

A [0] = 10 A [1]在示例数组中，如果我们这样更改：

= 6（替换2）A [2] = 5
A [3] = 1 A [4] = 8 A [5] = 20
这里我们得到2个新tragle 10 6 5和6 5 8.（和10 5 8）

我们排序：1 5 6 8 10 20 - >这里，原始解（10,5,8）值不相邻（没有traingle），但是我们有（5,6,8）和（6 8 10）。然后算法返回1.
似乎如果三角形存在，那么至少一个三角形的值将会相邻，但我没有找到任何证据。

解决方案

这真的很简单，我相信振动是正确的，但我会尝试以更简单的方式。

让我们假设你有三个元素是三角形的，值为 u，v，w ，那么它们（至少）有一个最大值。让我们认为是 w ，所以 u <= w 并且 v < = w

• 三角形的定义相当于 u + v> ; w ，因为如果这是真的，那么包含 w 的任何总和将总是大于其他单个值*


• 如果您在重新排序时跟踪 w 的新位置，您可以看到它之前的两个元素可以是
  
  
  
  • 或者 u 和 v ，所以您保持相同的三角形
  
  
  • ，或者它们可以用其他值 u'和 v'替换，它们大于或等于 u 和 v 但小于 w ，然后 u'+ v'> = u + v> w ，所以通过我们对三角形的新定义，我们有另一个三角形。
    
  
  
  
  
  

  因此，数组中存在一个三角形证明在有序数组中至少存在一个相邻的三角形，它不一定是相同的。

  
  
  

  ---

  
  
  

  *由于 w 是最大值，所以它对于正数是微不足道的。以下是一般性演示，并不仅仅假设正整数。我们的假设是 v <= w ， u <= w 并且 u + v >瓦特。让我们相反证明 u + w <= v 这是不可能的。

  
  
  

  假设 u + w <= v ，我们通过在两边加上 v 得到， u + v + w < = v + v ，并且由于 u + v 严格优于 w 通过假设，我们有 w + w < u + v + w <= v + v 因此 w < v ，这与我们的假设相矛盾。
  

  I have found a solution on the net for the codility problem below :

  A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

      A[P] + A[Q] > A[R],
      A[Q] + A[R] > A[P],
      A[R] + A[P] > A[Q].
  

  For example, consider array A such that:

  A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

  Triplet (0, 2, 4) is triangular.

  Write a function:

   int solution(int A[], int N);
  

  that, given a zero-indexed array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

  The solution is like this :

  A.Sort
    for (int i = 0; i < A.length - 2 && A[i] > 0; i++)
    {
           if (A[i] + A[i + 1] > A[i + 2])
              return 1;
    }
  

  But when we sort the array, the original index are no more valid and item in i position can move to j position with j>i or j

  The solutin suppose that values that verify assertion (Triangle) is automaticly adjacent in sorted array.

  In example array, if we change like this :

  A[0] = 10 A[1] = 6 (replace 2) A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20 Here we get 2 new traingle 10 6 5 and 6 5 8. (and 10 5 8)

  We sort : 1 5 6 8 10 20 --> Here, original solution (10,5,8) values are not adjacent (no traingle) but instead we have (5,6,8) and (6 8 10). Then algorithm return 1. It seem that if triangle exist then at least values of one triangle will be adjacent but I doesn't find any proof.

  解决方案

  It's pretty simple really, and I believe vib to be right but I'll try to put it in a simpler way.

  Let us suppose you have three elements that are triangular with values u, v, w, then they have (at least) one maximum value. Let us consider that to be w, so u <= w and v <= w

  • The definition of "triangular" is equivalent to u + v > w, because if this is true then any sum containing w will always be greater than the other individual values *
  • If you keep track of the new position of w when reordering, you can see that the two elements just before it can be
    • either u and v, so you keep the same triangle,
    • or they can be replaced with other values u' and v', which are greater or equal to u and v but smaller than w, and then u' + v' >= u + v > w, so by our new definition of triangular we have another triangle.

  So the existence of a triangle in the array proves that there exists at least one adjacent triangle in the sorted array, which does not have to be the same.

  ---

  * It's completely trivial for positive numbers since w is the max. Here's a general demonstration that does not suppose only positive integers. Our hypothesis are v <= w, u <= w and u + v > w. Let us prove by contradiction that u + w <= v it is impossible.

  Supposing u + w <= v, we get by adding v on both sides, u + v + w <= v + v, and since u + v is strictly superior to w by hypothesis, we have w + w < u + v + w <= v + v thus w < v, which is contradicting our hypothesis.

  这篇关于三角形：确定是否可以从一组给定的边构建一个三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！