همه سه قلوها را در آرایه مرتب شده ای که AP را تشکیل می دهند چاپ کنید  


سطح دشواری متوسط
اغلب در Accenture همبستگی کادنس هند گوگل InfoEdge تعلیم دادن پینترست
صف مخلوط جستجو

مسئله "چاپ همه سه تایی در آرایه مرتب شده که به شکل AP هستند" بیان می کند که ما مرتب سازی کرده ایم عدد صحیح آرایه. وظیفه این است که تمام سه قلوهای ممکن را که می توانند یک پیشرفت حسابی را تشکیل دهند ، کشف کنید.

همه سه قلوها را در آرایه مرتب شده ای که AP را تشکیل می دهند چاپ کنید

مثال  

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)

توضیح

اینها همه سه قلوهای تشکیل دهنده AP هستند

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

توضیح

اینها همه سه قلوهای تشکیل دهنده AP هستند

الگوریتم  

  1. حلقه از من = 1 تا n-1(شامل نمی شود).
  2. مقدار j را به یک کمتر از i و مقدار k را به یک بیشتر از i قرار دهید.
  3. در حالی که j> = 0 && k <n.
    1. بررسی کنید که آیا مجموع دو عنصر آرایه فعلی برابر با دو برابر عنصر آرایه دیگر است ،
      1. اگر درست است ، سه عنصر فعلی را چاپ کنید و مقدار k و j را به ترتیب کاهش و افزایش دهید.
    2. بررسی کنید که جمع این دو عنصر کمتر از دو برابر عنصر دیگر باشد ، سپس ، k را 1 افزایش دهید.
    3. بررسی کنید که آیا مجموع دو عنصر از دو عنصر دیگر بیشتر است یا خیر ، سپس j را 1 کاهش دهید.

توضیح

ما داده ایم مرتب شده اند صف. از ما خواسته شده است تا تمام سه گانه هایی را که می توانند یک پیشرفت حساب را تشکیل دهند ، پیدا کنیم. یک پیشرفت حساب را می توان یک توالی عددی تعریف کرد که در آن تمام عناصر به طور متوالی با فاصله خاصی بین آنها در طول کل دنباله آمده باشند. ما سه گانه را با فرمول AP پیدا خواهیم کرد که بیانگر a + c = 2b است ، در صورتی که مجموع دو عدد برابر با دو برابر عدد سوم باشد.

همچنین مشاهده کنید
حداقل مقدار مثبت گام به گام مثبت حل محلول کد

کل آرایه را با یک حلقه و a رد کنید حلقه در حالی که، 'while loop' قصد دارد بررسی کند که آیا سه عنصر می توانند AP را تشکیل دهند یا خیر. هر زمان که ما از حلقه for عبور کنیم مقدار j را به یک کمتر از مقدار i و مقدار k را به یک بیشتر از مقدار i می دهیم. این یک عنصر را برای بررسی انتخاب می کند ، بنابراین هر زمان که سه عنصر برای بررسی arr [i] ، arr [j] و arr [k] داشته باشیم ، مقدار i ، j و k برای هر کدام متفاوت است پیمایش چه برای حلقه باشد چه داخل حلقه در حالی که.

اگر متوجه شدیم که مجموع دو عنصر برابر با عنصر سوم است ، ما می خواهیم آن سه عنصر آرایه را چاپ کنیم ، آنها می توانند یک AP تشکیل دهند. ما مقدار j و k را با توجه به الگوریتم خود به روز خواهیم کرد. اگر جمع دو عنصر را کمتر از دو برابر عنصر سوم پیدا کنیم. ما مقدار k را افزایش می دهیم ، یا اگر حاصل جمع بیش از دو برابر عنصر سوم بود ، مقدار j را کاهش می دهیم. این کار ادامه خواهد یافت تا زمانی که کل آرایه را پیمایش کرده و تمام عناصر ممکن را که می توانند AP ایجاد کنند کشف کنیم.

رمز  

کد ++ C برای چاپ همه سه تایی ها در آرایه مرتب شده که به صورت AP هستند

#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

کد جاوا برای چاپ همه سه قلوها در آرایه مرتب شده که به صورت AP هستند

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

تحلیل پیچیدگی  

پیچیدگی زمان

بر2جایی که "n"  تعداد عناصر آرایه است. زیرا ما دو حلقه تو در تو داریم که حلقه اول اجرا می شود تا اینکه به انتها برسیم و سپس از حلقه تو در تو دوم برای یافتن عناصر AP استفاده می شود.

همچنین مشاهده کنید
حداکثر اندازه زیر مجموعه آرایه برابر k است

پیچیدگی فضا

O (1) زیرا فضای اضافی مورد نیاز نیست.