اطبع كل ثلاثة توائم في مصفوفة مرتبة تشكل AP


مستوى الصعوبة متوسط
كثيرا ما يطلب في اكسنتشر Accolite إيقاع الهند جوجل InfoEdge يستشعر Pinterest
مجموعة مزيج البحث

توضح مشكلة "طباعة كل ثلاثة توائم في مصفوفة مرتبة تشكل 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)

تفسير

كل هؤلاء هم الثلاثة توائم الذين يشكلون نقطة وصول

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

تفسير

كل هؤلاء هم الثلاثة توائم الذين يشكلون نقطة وصول

خوارزمية

  1. حلقة من أنا = 1 إلى n-1(غير مشمول).
  2. عيّن قيمة j إلى واحد أقل من i وقيمة k إلى واحد أكبر من i.
  3. ليس ي> = 0 && ك <ن.
    1. تحقق مما إذا كان مجموع عنصري المصفوفة الحالية يساوي ضعف عنصر المصفوفة الأخرى ،
      1. إذا كان هذا صحيحًا ، فقم بطباعة العناصر الثلاثة الحالية وقم بتقليل قيمة k و j وزيادتها على التوالي.
    2. تحقق مما إذا كان مجموع العنصرين أقل من ضعف عنصر آخر ، ثم قم بزيادة k بمقدار 1.
    3. تحقق مما إذا كان مجموع العنصرين أكبر من ضعف عنصر آخر ، ثم قلل j بمقدار 1.

تفسير

لقد قدمنا ​​أ فرز مجموعة. يُطلب منا معرفة جميع التوائم الثلاثة التي يمكن أن تشكل تقدمًا حسابيًا. يمكن تعريف التقدم الحسابي على أنه تسلسل رقمي تأتي فيه جميع العناصر على التوالي بمسافة معينة بينها على طول التسلسل بأكمله. سنجد الثلاثي بواسطة صيغة AP التي تنص على أن a + c = 2b أي إذا كان مجموع العددين يساوي ضعف الرقم الثالث.

اجتياز المصفوفة بأكملها باستخدام حلقة for و a حائط اللوب، "while loop" ستتحقق مما إذا وجدنا أن العناصر الثلاثة يمكن أن تشكل AP أم لا. سنضبط قيمة j على قيمة أقل بواحد من قيمة i وقيمة k إلى قيمة واحدة أكبر من قيمة i ، كلما نجتاز الحلقة for. ستلتقط عنصرًا لكي نتحقق منه ، لذلك في كل مرة يكون لدينا ثلاثة عناصر للتحقق من 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

كود Java لطباعة كل ثلاثة توائم في مصفوفة مرتبة تشكل 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أين "ن"  هو عدد العناصر في المصفوفة. لأن لدينا حلقتين متداخلتين حيث تعمل الحلقة الأولى حتى نصل إلى النهاية ثم تُستخدم الحلقة المتداخلة الثانية للعثور على عناصر AP.

تعقيد الفضاء

يا (1) حيث لا توجد مساحة إضافية مطلوبة.