ኤ.ፒ. በሚመሠርተው ድርድር ውስጥ ሁሉንም ሶስትዎች ያትሙ  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ Accenture የተከማቸ ካዴንስ ህንድ google መረጃEdge ኢላማዊ Pinterest
ሰልፍ ሃሽ በመፈለግ ላይ

ችግሩ “ኤ.ፒ.ኤን በሚመሠረተው ድርድር ውስጥ ሁሉንም ሶስት እጥፍ ያትሙ” የሚለው እኛ የተደረደርን እንደሆንን ይገልጻል ኢንቲጀር ድርድር ተግባሩ የሂሳብ እድገትን ሊፈጥር የሚችል ሁሉንም ሊሆኑ የሚችሉ ሶስት ሰዎችን መፈለግ ነው ፡፡

ኤ.ፒ. በሚመሠርተው ድርድር ውስጥ ሁሉንም ሶስትዎች ያትሙጭንቅላታም መያያዣ መርፌ

ለምሳሌ  

arr[] = {1,3,5,7,8,12,15,16,20,30}
(1, 3, 5), (3, 5, 7), (1, 8, 15), (8, 12, 16), (12, 16, 20)

ማስረጃ

እነዚህ ሁሉ ኤ.ፒ.

arr[] = {2,4,5,6,9,14,18,24}
(2, 4, 6), (4, 5, 6), (4, 9, 14), (4, 14, 24)

ማስረጃ

እነዚህ ሁሉ ኤ.ፒ.

አልጎሪዝም  

  1. ከሉጥ i = 1 እስከ n-1(አልተካተተም).
  2. የጄ ዋጋን ከእኔ ያነሰ እና የ k ዋጋን ከአንድ ወደ እኔ ያኑሩ።
  3. ቢሆንም j> = 0 && ኪ <n.
    1. የሁለቱ የአሁኑ ድርድር አካላት ድምር ከሌላው ድርድር አካል ጋር እኩል ከሆነ ያረጋግጡ ፣
      1. እውነት ከሆነ ፣ ከዚያ የአሁኑን ሶስት አካላት ያትሙ እና በቅደም ተከተል የ k እና j ዋጋን ይጨምሩ እና ይጨምሩ።
    2. የሁለቱ አካላት ድምር ከሌላው ንጥረ ነገር እጥፍ እጥፍ ያነሰ መሆኑን ያረጋግጡ ፣ ከዚያ ፣ k በ 1 ይጨምሩ።
    3. የሁለቱ አካላት ድምር ከሌላው ንጥረ ነገር እጥፍ ይበልጣል የሚለውን ያረጋግጡ ፣ ከዚያ j በ 1 ይቀንሱ።

ማስረጃ

እኛ ሰጥተናል መደርደር ደርድር. የሂሳብ እድገት ሊፈጥሩ የሚችሉትን ሁሉንም ሶስትዎች እንድናውቅ እንጠየቃለን ፡፡ የሂሳብ ቅደም ተከተል እድገት ሁሉም ንጥረ ነገሮች በጠቅላላው ቅደም ተከተል በመካከላቸው ካለው የተወሰነ ርቀት ጋር በተከታታይ የሚመጡበት የቁጥር ቅደም ተከተል ተብሎ ሊተረጎም ይችላል። የሁለት ቁጥሮች ድምር ከሶስተኛው ቁጥር ሁለት እጥፍ ጋር እኩል ከሆነ አንድ + c = 2b በሚለው የ ‹AP› ቀመር ሶስት እናገኛለን ፡፡

ተመልከት
በደረጃ አዎንታዊ ውጤትን ለማግኘት አነስተኛ እሴት ድምር Leetcode መፍትሔ

መላውን ድርድር በአንዱ ለሉፕ እና ለ ዘንበል እያለ፣ ‹ሎፕ ሉፕ› ሶስቱም ንጥረ ነገሮች ኤ.ፒ መፍጠር ወይም አለመቻላቸውን ካገኘን ለመፈተሽ ነው ፡፡ የ j ዋጋን ከ I ዋጋ በታች ወደ አንድ እና የ k ዋጋን ከአንድ ወደ እኔ ከ I ዋጋ በላይ እናደርጋለን ፣ በዞረሩ ውስጥ በምንጓዝበት ጊዜ ሁሉ ፡፡ እኛ የምንፈትሽበትን አንድ ንጥረ ነገር ያነሳል ፣ ስለሆነም አርአር [i] ፣ arr [j] እና arr [k] ን ለመፈተሽ ሦስት አካላት ባሉን ቁጥር ለእያንዳንዱ የሚለያይ የ i ፣ j እና k ዋጋ ነው ፡፡ በሉፍም ይሁን በ ውስጥ መተላለፍ ዘንበል እያለ.

የሁለት አካላት ድምር ከሶስተኛው አካል ጋር እኩል ሆኖ ካገኘን እነዚያን ሶስት ድርድር አባላትን ማተም እንጀምራለን እነሱ ኤ.ፒ. በእኛ ስልተ-ቀመር መሠረት የ j እና k ዋጋን እናዘምነዋለን ፡፡ የሁለቱን ንጥረ ነገሮች ድምር ከሶስተኛው አካል ሁለት እጥፍ ያነሰ ካገኘን ፡፡ የ k ዋጋን እንጨምራለን ፣ ወይም ድምር ከሶስተኛው ንጥረ ነገር እጥፍ ይበልጣል ካገኘን የ j ዋጋን እንቀንሳለን። መላውን ድርድር እስክናልፍ እና ኤ.ፒ ሊፈጠሩ የሚችሉ ሁሉንም አካላት እስክናገኝ ድረስ ይሄ ይቀጥላል።

ኮድ  

ሁሉንም የሶስት ዓይነቶች በ AP በሚመሠረት ድርድር ለማተም የ C ++ ኮድ

#include<iostream>

using namespace std;

void getTripletsWithAP(int arr[], int n)
{
  for (int i = 1; i < n - 1; i++)
  {
    int j = i - 1, k = i + 1;
        while(j >= 0 && k < n)
        {
            if (arr[j] + arr[k] == 2 * arr[i])
            {
        cout <<arr[j]<< " "<<arr[i]<<" "<<arr[k]<< endl;
                k++;
                j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++;
            else
                j--;
        }
  }
}
int main()
{
  int arr[] = {1,3,5,7,8,12,15,16,20,30};
  int n = sizeof(arr) / sizeof(arr[0]);
  getTripletsWithAP(arr, n);
  return 0;
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

ኤ.ፒ.ን በሚመሠርተው ድርድር ውስጥ ሁሉንም ሶስት ዓይነቶች ለማተም የጃቫ ኮድ

class TripletAP
{
    public static void getTripletsWithAP(int arr[], int n)
    {
        for (int i = 1; i < n - 1; i++)
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < n)
            {
                if (arr[j] + arr[k] == 2 * arr[i])
                {
                    System.out.println(arr[j] +" " +arr[i]+ " " + arr[k]);
                    k++;
                    j--;
                }
                else if (arr[j] + arr[k] < 2 * arr[i])
                    k++;
                else
                    j--;
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {1,3,5,7,8,12,15,16,20,30};
        int n = arr.length;
        getTripletsWithAP(arr, n);
    }
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (n2የት “N”  በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ምክንያቱም እስከ መጨረሻው እስክንደርስ ድረስ የመጀመሪያው ዙር በሚሠራበት ሁለት የጎጆ ጥብጣብ (ሉፕ) አለን ከዚያም ሁለተኛው የጎጆው ዑደት የ AP ን ንጥረ ነገሮችን ለማግኘት ይጠቅማል ፡፡

ተመልከት
ከፍተኛ መጠን ያለው ንዑስ ክፍል ድምር እኩል ይሆናል k

የቦታ ውስብስብነት

ኦ (1) ተጨማሪ ቦታ ስለማያስፈልግ ፡፡