Ditulis dalam C++, cari bilangan empat kali ganda yang tiga sebutan pertamanya ialah jujukan aritmetik dan tiga sebutan terakhir ialah jujukan geometri.

Dalam artikel ini kami akan menerangkan semua cara yang mungkin untuk mencari kuarteron, di mana 3 sebutan pertama adalah dalam A.P. dan 3 sebutan terakhir adalah dalam G.P. Pertama, kami akan menerangkan definisi asas janjang aritmetik (A.P.) dan janjang geometri (G.P.).

Arithmetic Progression (A.P.) - Ia adalah urutan nombor di mana perbezaan sepunya (d) adalah sama atau malar, bermakna perbezaan dua nombor berturut-turut adalah malar. Contohnya: 1,3,5,7,9 |. d = 2

Geometrik Progression (G.P.) - Ini ialah urutan nombor di mana nisbah sepunya (r) adalah sama, yang bermaksud kita boleh mendarabkan yang sebelumnya nombor dengan dengan nombor tetap. Contohnya: 3, 6, 12, 24, .... |. r = 2

Dalam masalah ini, kita perlu menentukan berapa banyak indeks empat kali ganda (a, b, c) dalam susunan arr[] N integer , d). Akibatnya, arr[a], arr[b] dan arr[c] berada dalam A.P., manakala arr[d], arr[c] dan arr[b] berada dalam G.P. Semua empat tupel di dalamnya harus bersifat deterministik. Berikut adalah contoh -

Input : arr[ ] = { 9, 6, 4, 2, 1, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 3, 2, 1, 0 } and { 5, 2, 1, 0 } indexes where quadruples are { 2, 4, 6, 9 } for both positions.

Input : arr[ ] = { 2, 6, 1, 4, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 1, 3, 0, 2 } and { 1, 3, 4, 2 } indexes where quadruples are { 6, 4, 2, 1 } for both positions.

Kaedah mencari penyelesaian

Sekarang kita akan menerangkan dua kaedah yang berbeza untuk mencari penyelesaian -

Kaedah brute force

Ini adalah kaedah mudah untuk menyelesaikan menggunakan empat gelung bersarang Soalan ini kemudiannya menyemak sama ada tiga elemen pertama adalah dalam A.P. Jika ya, semak sama ada 3 elemen terakhir berada dalam G.P. Jika ya, tambahkan 1 pada pembolehubah kiraan. Walau bagaimanapun, kaedah ini sangat memakan masa kerana kerumitan masanya ialah O(n4).

Kaedah yang cekap

Dalam kaedah ini kita mula-mula mencari kiraan setiap elemen tatasusunan dan kemudian menganggap kedua-dua elemen ini sebagai nombor kedua dan ketiga dan menjalankan dua gelung bersarang kemudian yang pertama Elemen akan menjadi arr[b] – (arr[c ] – arr[b]) dan elemen keempat ialah arr[c] * arr[c] / arr[b].

Contoh

#include <bits/stdc++.h>
using namespace std;
int main (){
    unordered_map < int, int >map;
    int arr[] = { 2, 6, 1, 4, 2 };
    int size = sizeof (arr) / sizeof (arr[0]);
    // Processing every elent and increasing the count
    for (int a = 0; a < size; a++)
      map[arr[a]]++;

    int count = 0;
    // Running two nested loops for second & third element
    for (int b = 0; b < size; b++){
        for (int c = 0; c < size; c++){
            if (b == c)
                continue;
                // Decreasing the count
                map[arr[b]]--;
            map[arr[c]]--;
            // Finding the first element using common difference
            int first = arr[b] - (arr[c] - arr[b]);
            // Finding the fourth element using GP
            int fourth = (arr[c] * arr[c]) / arr[b];
            if ((arr[c] * arr[c]) % arr[b] == 0){
                // Increment count if not equal
                if (arr[b] != arr[c])
                    count += map[first] * map[fourth];
                else
                 count += map[first] * (map[fourth] - 1);
            }
            map[arr[b]]++;
            map[arr[c]]++;
        }
    }
    cout <<"Number of quadruples: " << count;
    return 0;
}

Output

Number of quadruples: 2

Penjelasan kod di atas

Dalam kod ini, kami menggunakan gabungan, menggunakan dua gelung bersarang untuk elemen kedua dan ketiga, dan menggunakan arr[a] – (arr[c] mencari elemen pertama – ​​arr[b]) dan elemen keempat arr[c] * arr[c] / arr[b]. Jadi, dengan mengekalkan unsur kedua dan ketiga tetap, bilangan kuaternion yang diindeks oleh A dan B ialah kiraan nombor pertama * nombor keempat. kerumitan masa kod di atas ialah O(n2).

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mencari kuaternion di mana tiga sebutan pertama adalah dalam AP dan tiga sebutan terakhir dalam GP Kami berbincang menggunakan kaedah Bruteforce [ O(n4) ] dan Efficient [ O (n2 ) ] Dua cara untuk menyelesaikan masalah ini.

Kami menyelesaikan masalah ini menggunakan C++, ini juga boleh diselesaikan dalam pelbagai bahasa lain seperti java, python, C atau mana-mana bahasa pengaturcaraan lain.

Atas ialah kandungan terperinci Ditulis dalam C++, cari bilangan empat kali ganda yang tiga sebutan pertamanya ialah jujukan aritmetik dan tiga sebutan terakhir ialah jujukan geometri.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!