እስከ አንድ የተሰጠ እሴት የሚደምሩ ሁሉም ልዩ ሦስትነቶች


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ አማዞን አፍቃሪዎች
ሰልፍ ሃምሽንግ በመፈለግ ላይ

አንድ ሰጥተናል ደርድር የቁጥር ቁጥሮች እና ‹ድምር› የተባለ የተወሰነ ቁጥር ፡፡ የችግሩ መግለጫ በተጠቀሰው ቁጥር ‘ድምር’ ላይ የሚደመሩትን ሶስት እጥፍ ለማወቅ ይጠይቃል።

ለምሳሌ

ግቤት

arr [] = {3,5,7,5,6,1}

ድምር = 16

ውጤት

(3, 7, 6) ፣ (5, 5, 6)

ማብራሪያ:

ከተሰጠው ድምር ጋር እኩል የሆነ ሶስት እጥፍ.

ግቤት

arr [] = {3,4,1,5,4}

ድምር = 20

ውጤት

ከተጠቀሰው ቁጥር ጋር ሊመሠረቱ የሚችሉ ሦስት (ሦስት) የሉም

አልጎሪዝም

  1. የተሰጠውን ድርድር ደርድር።
  2. የቦሊያን ተለዋዋጭ isFound ን ወደ ሐሰት ያቀናብሩ።
  3. እኔ = 0 እስከ እኔ እያለ
    1. J = i + 1, k = n-1 ን ያዘጋጁ.
    2. J <k እያለ
      1. ሶስቱም ንጥረ ነገሮች አንድ ላይ ወደተጠቀሰው ድምር የሚደመሩ ከሆነ ያረጋግጡ።
        1. እውነት ከሆነ ከዚያ ሶስቱን ቁጥር ያትሙ እና ያዋቅሩ ወደ እውነት ይላኩ።
      2. የሶስቱ አካላት ድምር ከድምርው የበለጠ ከሆነ ሌላውን ያረጋግጡ።
        1. እውነት ከሆነ ፣ ከዚያ የ k እሴት በ 1 ይቀንሱ።
      3. የሶስት አካላት ድምር (የአሁኑ የድርድር አካላት) ከድምርው በታች መሆኑን ያረጋግጡ።
        1. እውነት ከሆነ ፣ ከዚያ የ j ዋጋን በ 1 ይጨምሩ።
  4. ፋውንዴሽን ሐሰተኛ ሆኖ የሚቆይ ከሆነ ያረጋግጡ ፣ ምንም ዓይነት ሶስት ሊፈጠር እንደማይችል ይደመድማል።

ማስረጃ

እናደርጋለን ዓይነት እኛ የምንጠቀምበት ስለሆነ እሴቶቹ በቅደም ተከተል እንዲጨምሩ በመጀመሪያ ድርድሩ ሁለትዮሽ ፍለጋ አቀራረብ ፣ ትንሽ ፡፡ እኛ እናውጃለን የቦሊያን ተለዋዋጭ መጀመሪያ ላይ ዋጋውን ወደ ሐሰት አውጥተን ፣ ሶስት እጥፍ እንደጨረስነው እናዘምነዋለን ፡፡ ይህ ማለት በተጠቀሰው ቁጥር የሚደመሩ ንጥረ ነገሮችን የያዙ ማናቸውንም ሶስትዎች ካላገኘን እሴቱ እሴቱ እንደቀጠለ ነው ፣ እኛ አንድ ባለሶስት ባገኘን ጊዜ ወደ እውነት እናዘምነዋለን ፡፡ ፣ ምንም ሶስት እጥፍ አልተገኘም ብለን መደምደም እንችላለን።

ድርድርን ከተደረደሩ በኋላ ፣ ከተጠለፈው ሉፕ ውስጥ በመጀመር ፣ ድርደራውን እስከ n-1 ርዝመት እናልፋለን። ከተለዋጭ እሴቶቹ ውስጥ አንዱን እንደ i + 1 ፣ ሌላ እሴት ወደ n-1 ማቀናበር ፡፡ በውስጠኛው ዙር ውስጥ የአንድ ድርድር እሴቶችን ሁሉ እናቋርጣለን እና የተሰጠው ቁጥር 'ድምር' ከሶስቱ የወቅቱ የድርጅት አካላት ድምር ጋር እኩል መሆኑን እናረጋግጣለን ]) እኩል ነው ወይም አይደለም ፡፡ ሁኔታው የሚያረካ ከሆነ ሁሉንም የአንድ ወቅታዊ እሴቶችን ማተም እና isFound እሴትን ወደ እውነት እንወስዳለን ፣ የውሸት እሴት መመለስ እንደሌለብን ያረጋግጣል።

የአንድ ድርድር ሶስት የአሁኑ እሴቶች ድምር ከተጠቀሰው ቁጥር ጋር እኩል ካልሆነ የሶስት የአሁኑ ንጥረ ነገሮች ድምር ከተጠቀሰው ድምር ያነሰ ከሆነ ከድምርው በታች ከሆነ ዋጋውን እንጨምራለን የ j ማለት የግራ አመላካችን ማለት ከግራ የሚያመለክተውን ማለት ነው መተላለፍ መጨመር ሲሆን ይህ ሁኔታ ደግሞ የማያረካ ከሆነ ድምር ከድምርው የበለጠ መሆኑን እናጣራለን ፣ እውነት ከሆነ የ k ዋጋን እንቀንሳለን ፡፡

የድርድሩ እሴቶች ሁሉ እስኪሻገሩ ድረስ ይቀጥላል። እናም እኛ ሶስቱን ማናችንም ያገኘን ካልሆንን ሐሰተኛ ሆኖ ካገኘነው እንደ እውነት ሊመለስ የሚችል የአይፎን እሴትን እንመልሳለን ፡፡

አፈጻጸም

ለተሰጠ እሴት የሚደመደሙ ለሁሉም ልዩ ሦስትነቶች የ C ++ ፕሮግራም

#include<iostream>
#include<algorithm>

using namespace std;

int getTripletOfSum(int arr[], int n, int sum)
{
    int i, j, k;
    bool isFound=false;
    sort(arr, arr + n);
    for(i = 0; i < n - 2; i++)
    {
        j = i + 1;
        k = n - 1;

        while(j < k)
        {
            if(arr[i] + arr[j] + arr[k] == sum)
            {
                cout<<"["<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<"]"<<endl;
                j++;
                k--;
                isFound=true;
            }
            else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    return isFound;
}
int main()
{
    int nums[] = {3,5,7,5,6,1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 16;
    if(!getTripletOfSum(nums, n, sum))
        cout << "There are no triplets that can be formed with the given number";

    return 0;
}
[3 6 7]
[5 5 6]

ለተሰጠው እሴት የሚደመደሙ ለሁሉም ልዩ ሦስትዎች የጃቫ ፕሮግራም

import java.util.Arrays;

public class TripletsWithSum
{
    public static boolean getTripletOfSum(int arr[], int sum)
    {
        Arrays.sort(arr);

        boolean isFound=false;

        for (int i = 0; i < arr.length - 2; i++)
        {
            int j = i + 1;
            int k = arr.length - 1;
            while (j < k)
            {
                if (arr[i] + arr[j] + arr[k] == sum)
                {
                    System.out.println("["+arr[i] + " " + arr[j] +" " +arr[k]+"]");
                    j++;
                    k--;
                    isFound=true;
                }
                else if (arr[i] + arr[j] + arr[k] < sum)
                    j++;

                else
                    k--;
            }
        }
        return isFound;
    }
    public static void main(String[] args)
    {
        int arr[] = {3,5,7,5,6,1};
        int sum = 16;
        if (!getTripletOfSum(arr, sum))
        {
            System.out.println("There are no triplets that can be formed with the given number");
        }
    }
}
[3 6 7]
[5 5 6]

ለተሰጠው እሴት የሚደመደሙ ለሁሉም ልዩ ልዩ ሦስትነቶች ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n2የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።