Ҳамаи сегоникҳоро дар массиви мураттаб, ки AP ташкил медиҳанд, чоп кунед  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Accenture Акколити Cadence Ҳиндустон Google InfoEdge Шабака ба дӯстат
тартиботи ҳарбӣ Хаш Ҷустуҷӯ

Масъалаи "Чоп кардани ҳамаи сегоникҳо дар массиви ҷудошуда, ки АП-ро ташкил медиҳанд" гуфта мешавад, ки мо як навъ додаем ҳамаҷониба массиви. Вазифа аз он иборат аст, ки ҳамаи сегоникҳои имконпазирро, ки метавонанд Прогресси Арифметикиро ташкил диҳанд, пайдо кунем.

Ҳамаи сегоникҳоро дар массиви мураттаб, ки 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. Маблағи ду элементро аз унсури дигар камтар аз ду маротиба камтар кунед, пас к-ро ба 1 зиёд кунед.
    3. Тафтиш кунед, ки агар ҳосили ду элемент аз ду маротиба аз дигар элемент зиёд бошад, пас j-ро ба 1 коҳиш диҳед.

Шарҳ

Мо додем мураттаб карда шудааст асал. Аз мо хоҳиш карда мешавад, ки ҳамаи сегоникҳоро, ки метавонанд пешрафти арифметикиро ташкил диҳанд, фаҳмем. Пешрафти арифметикиро ҳамчун пайдарпаии адад муайян кардан мумкин аст, ки дар он ҳамаи элементҳо пай дар пай бо масофаи мушаххаси байни онҳо дар тӯли тамоми пайдарпаӣ меоянд. Мо сегоникро аз рӯи формулаи АП пайдо мекунем, ки дар он a + c = 2b навишта шудааст, ки агар ҳосили ду адад ба дукаратаи шумораи сеюм баробар бошад.

ҳамчунин нигаред
Арзиши ҳадди ақал барои ба даст овардани қадами мусбӣ ҳалли Leetcode Solution

Тамоми массивро бо як for loop ва a гузаред дар ҳоле ки ҳалқа, 'while loop' тафтиш мекунад, ки оё се унсури AP-ро ташкил карда метавонанд ё не. Мо ҳар вақт, ки аз давр барои for мегузарем, арзиши j-ро аз арзиши i камтар ва қимати k-ро аз арзиши i ба як бештар таъин хоҳем кард. Он як унсуреро барои тафтиш мегирад, ки ҳар дафъае ки мо се унсури санҷиши arr [i], arr [j] ва arr [k] дошта бошем, арзиши i, j ва k, ки барои ҳар яки онҳо фарқ мекунад ҳаракат кардан дар for loop ё дар дар ҳоле ки ҳалқа.

Агар мо ҷамъи ду унсурро ба элементи сеюм баробар дидем, мо он се унсури массивро чоп мекунем, онҳо метавонанд 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ки дар "Н"  шумораи унсурҳои массив аст. Азбаски мо ду ҳалқаи лона дорем, ки ҳалқаи аввал то ба охир расидан кор мекунад ва сипас ҳалқаи дуюм барои ёфтани унсурҳои АП истифода мешавад.

ҳамчунин нигаред
Маблағи ҳадди аққали зеркатраса ба k баробар аст

Мураккабии фазо

О (1) зеро ягон ҷои иловагӣ лозим нест.