Տպեք բոլոր եռյակները տեսակավորված զանգվածով, որոնք կազմում են AP  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Accenture Ակոլիտ Կադենս Հնդկաստան Google InfoEdge Intuit Pinterest
Դասավորություն Խանգարել Որոնում

«ԱՊ-ն կազմող բոլոր եռյակները տպել տեսակավորված զանգվածում» խնդիրը ասում է, որ մենք տվել ենք տեսակավորված ամբողջ թիվ զանգված Խնդիրն է պարզել բոլոր հնարավոր երեք եռյակները, որոնք կարող են կազմել թվաբանական առաջընթաց:

Տպեք բոլոր եռյակները տեսակավորված զանգվածով, որոնք կազմում են 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. Օղակ ՝ i = 1-ից n-1(ներառված չէ).
  2. Սահմանեք j- ի արժեքը i- ից պակաս մեկի վրա, իսկ k- ի արժեքը `i- ով մեկ:
  3. Ժամանակ j> = 0 && կ <ն.
    1. Ստուգեք, արդյոք զանգվածի երկու ընթացիկ տարրերի հանրագումարը հավասար է զանգվածի մյուս տարրի կրկնակի,
      1. Եթե ​​ճիշտ է, ապա տպիր ընթացիկ երեք տարրերը և համապատասխանաբար նվազեցրու և մեծացրու k- ի և j արժեքը:
    2. Ստուգեք, արդյոք երկու տարրերի գումարը պակաս է մեկ այլ տարրի երկու անգամից, ապա, k- ն ավելացրեք 1-ով:
    3. Ստուգեք, արդյոք երկու տարրերի հանրագումարը ավելի մեծ է, քան մեկ այլ տարրի երկու անգամ, ապա, j- ով նվազեցրեք 1-ով:

բացատրություն

Մենք տվել ենք ա տեսակավորված է դասավորություն, Մեզ խնդրում են պարզել բոլոր այն եռյակները, որոնք կարող են կազմել Թվաբանական առաջընթաց: Թվաբանական պրոգրեսիան կարող է սահմանվել որպես թվային հաջորդականություն, որի ընթացքում բոլոր տարրերը գալիս են հաջորդաբար `նրանց միջև որոշակի հաջորդականությամբ` ամբողջ հաջորդականության երկայնքով: Եռյակը կգտնենք AP- ի բանաձևով, որը նշում է a + c = 2b, այսինքն, եթե երկու թվերի գումարը հավասար է երրորդ թվի կրկնակիին:

Տես նաեւ,
Նվազագույն արժեքը քայլ առ քայլ գումար ստանալու համար Leetcode լուծում գումար

Ամբողջ զանգվածը հատեք օղակի և a- ի հետ իսկ հանգույց, 'while loop' - ը պատրաստվում է ստուգել `արդյոք մենք գտնում ենք, որ տարրերից երեքը կարող են AP- ն կազմել, թե ոչ: Մենք կսահմանենք j- ի արժեքը մեկից պակաս i- ից և k- ի արժեքը մեկից ավելի i- ի արժեքից, երբ անցնենք for օղակի միջով: Այն կստանա մի տարր, որը մենք կստուգենք, այնպես որ ամեն անգամ, երբ ունենք երեք տարր ՝ arr [i], arr [j] և ar [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

Բարդության վերլուծություն  

Timeամանակի բարդություն

Վրա2որտեղ «Ն»  զանգվածում տարրերի քանակն է: Քանի որ մենք ունենք երկու տեղադրված օղակ, որտեղ առաջին օղակը անցնում է մինչև հասնենք վերջը, ապա երկրորդ ներդիր օղակը օգտագործվում է AP- ի տարրերը գտնելու համար:

Տես նաեւ,
Ենթանկարի առավելագույն չափի գումարը հավասար է k- ի

Տիեզերական բարդություն

Ո (1) քանի որ լրացուցիչ տարածք չի պահանջվում: