מספר משולש תקף


רמת קושי בינוני
נשאל לעתים קרובות בלומברג רובין הוד
מערך

בעיה

ב מספר משולש תקף הבעיה, נתנו מערך של מספרים שלמים שאינם שליליים. מצא את מספר השלישיות שיכולות ליצור משולש. אם ניקח בחשבון את המספרים ב מערך כאורכי צד של המשולש.

דוגמה

קֶלֶט

[2, 2, 3, 4]

תְפוּקָה

3

הסבר

אנו יכולים ליצור שלוש שלישיות שיכולות ליצור משולש.

שלישיות הן:

  1. 2,3,4 (באמצעות 2 הראשונים)
  2. 2,3,4 (באמצעות השני 2)
  3. 2,2,3

גישת כוח אכזרי

שלישייה יכולה ליצור משולש אם ורק אם היא עומדת בתנאי a + b> c. פירוש הדבר שסכום של שני צלעות משולש חייב להיות גדול יותר מהצד השלישי.

גישת כוח הברוטה מאוד פשוטה וקלה. אנו נבדוק אם קיימת כל שלישיות אם הן עומדות בתנאי ליצירת משולש. נשמור גם על משתנה כדי לעקוב אחר ספירת השלישיות שיכולות ליצור משולש. לכן כאשר אנו נתקלים בשלישייה שיכולה ליצור משולש נגדיל את הספירה. באופן זה, לאחר שנבדוק את כל השלשות האפשריות יהיה לנו את המספר הכולל של השלישיות שניתן ליצור.

יישום מספר המשולש התקף

קוד C ++ למספר משולש תקף

// C++ code to count the number of 
// possible triangles using brute 
// force approach 
#include <bits/stdc++.h> 
using namespace std; 

// Function to count all possible 
// triangles with arr[] elements 
int findNumberOfTriangles(int arr[], int n) 
{ 
  // Count of triangles 
  int count = 0; 

  // The three loops select three 
  // different values from array 
  for (int i = 0; i < n; i++) { 
    for (int j = i + 1; j < n; j++) { 

      // The innermost loop checks for 
      // the triangle property 
      for (int k = j + 1; k < n; k++) 

        // Sum of two sides is greater 
        // than the third 
        if ( 
          arr[i] + arr[j] > arr[k] 
          && arr[i] + arr[k] > arr[j] 
          && arr[k] + arr[j] > arr[i]) 
          count++; 
    } 
  } 
  return count; 
} 

// Driver code 
int main() 
{ 
  int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; 
  int size = sizeof(arr) / sizeof(arr[0]); 

  cout 
    << "Total number of triangles possible is "
    << findNumberOfTriangles(arr, size); 

  return 0; 
} 
Total number of triangles possible is 6

קוד Java למספר משולש תקף

// Java code to count the number of 
// possible triangles using brute 
// force approach 
import java.io.*; 
import java.util.*; 

class check
{ 

  // Function to count all possible 
  // triangles with arr[] elements 
  static int findNumberOfTriangles(int arr[], int n) 
  { 
    // Count of triangles 
    int count = 0; 
  
    // The three loops select three 
    // different values from array 
    for (int i = 0; i < n; i++) { 
      for (int j = i + 1; j < n; j++) { 
  
        // The innermost loop checks for 
        // the triangle property 
        for (int k = j + 1; k < n; k++) 
  
          // Sum of two sides is greater 
          // than the third 
          if ( 
            arr[i] + arr[j] > arr[k] 
            && arr[i] + arr[k] > arr[j] 
            && arr[k] + arr[j] > arr[i]) 
            count++; 
      } 
    } 
    return count; 
  } 
  
  // Driver code 
  public static void main(String[] args) 
  { 
    int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; 
    int size = arr.length; 
  
    System.out.println( "Total number of triangles possible is "+ 
    findNumberOfTriangles(arr, size)); 
  } 
}
Total number of triangles possible is 6

מורכבות זמן

O (n ^ 3) מכיוון שאנחנו משתמשים בשלוש לולאות כדי למצוא את השלישיות.

מורכבות חלל

O (1) מכיוון שאנחנו שומרים על משתנה הספירה כדי לעקוב אחר שלישיות שיכולות ליצור משולשים.

גישה יעילה

כדי לייעל את הפתרון אנו ממיינים את המערך. נפעיל שתי לולאות.

  1. הלולאה הראשונה תעקוב אחר הצד הראשון והלולאה השנייה תעקוב אחר הצד השני של המשולש.
  2. הלולאה הראשונה עוברת מההתחלה ועד הסוף והלולאה השנייה עוברת מ- i + 1 עד הסוף.
  3.  נשמור על משתנה k = i + 2;
  4. לאחר תיקון הצד הראשון והשני אנו זקוקים לצד השלישי כך ש- + b> c. אנו נמצא מיקום (k) בו הערך של c הוא המרבי האפשרי המספק את התנאי ליצירת משולש.
  5. לאחר מכן נוסיף (kj) לספירה הכוללת.

מספר משולש תקף

יישום מספר המשולש התקף

תוכנית C ++ למספר משולש תקף

// C++ program to count number of triangles that can be 
// formed from given array 
#include <bits/stdc++.h> 
using namespace std; 
int comp(const void* a, const void* b) 
{ 
  return *(int*)a > *(int*)b; 
} 
int findNumberOfTriangles(int arr[], int n) 
{ 
  // Sort the array elements in non-decreasing order 
  qsort(arr, n, sizeof(arr[0]), comp); 

  // Initialize count of triangles 
  int count = 0; 
  for (int i = 0; i < n - 2; ++i) { 
    // Initialize index of the rightmost third 
    // element 
    int k = i + 2; 

    // Fix the second element 
    for (int j = i + 1; j < n; ++j) { 
      while (k < n && arr[i] + arr[j] > arr[k]) 
        ++k; 
      if (k > j) 
        count += k - j - 1; 
    } 
  } 

  return count; 
} 

// Driver code 
int main() 
{ 
  int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; 
  int size = sizeof(arr) / sizeof(arr[0]); 

  cout << "Total number of triangles possible is " << findNumberOfTriangles(arr, size); 

  return 0; 
} 
Total number of triangles possible is 6

תוכנית Java למספר משולש תקף

// Java program to count number of triangles that can be 
// formed from given array 
import java.io.*; 
import java.util.*; 

class CountTriangles { 
  // Function to count all possible triangles with arr[] 
  // elements 
  static int findNumberOfTriangles(int arr[]) 
  { 
    int n = arr.length; 
    // Sort the array elements in non-decreasing order 
    Arrays.sort(arr); 

    // Initialize count of triangles 
    int count = 0; 
    for (int i = 0; i < n - 2; ++i) { 
      // Initialize index of the rightmost third element 
      int k = i + 2; 

      // Fix the second element 
      for (int j = i + 1; j < n; ++j) { 
        while (k < n && arr[i] + arr[j] > arr[k]) 
          ++k; 
        if (k > j) 
          count += k - j - 1; 
      } 
    } 
    return count; 
  } 

  public static void main(String[] args) 
  { 
    int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; 
    System.out.println("Total number of triangles is " + findNumberOfTriangles(arr)); 
  } 
}
Total number of triangles possible is 6

מורכבות זמן

O (n ^ 2)

מכיוון שאנחנו משתמשים בשתי לולאות כדי למצוא את השלישייה.

מורכבות חלל

O (1) מכיוון שאנחנו שומרים על משתנה הספירה כדי לעקוב אחר שלישיות שיכולות ליצור משולשים.

הפניות