พิมพ์แฝดทั้งหมดในอาร์เรย์ที่เรียงลำดับซึ่งเป็นรูปแบบ AP


ระดับความยาก กลาง
ถามบ่อยใน แอคเซนเจอร์ แอคโคไลท์ จังหวะอินเดีย Google 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)

คำอธิบาย

ทั้งหมดนี้คือแฝดสามที่สร้าง 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 นั่นคือถ้าผลรวมของตัวเลขสองตัวนั้นเท่ากับสองของจำนวนที่สาม

สำรวจอาร์เรย์ทั้งหมดด้วยหนึ่งสำหรับลูปและ ในขณะที่วนซ้ำ'while loop' จะตรวจสอบว่าเราพบว่าองค์ประกอบทั้งสามสามารถสร้าง AP ได้หรือไม่ เราจะกำหนดค่าของ 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

รหัส 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ที่ไหน “ n”  คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากเรามีลูปซ้อนกันสองวงโดยที่วงแรกทำงานจนไปถึงจุดสิ้นสุดจากนั้นจึงใช้ลูปซ้อนที่สองเพื่อค้นหาองค์ประกอบของ AP

ความซับซ้อนของอวกาศ

O (1) เนื่องจากไม่จำเป็นต้องมีพื้นที่เพิ่มเติม