Etsi kaikki tripletit lajitetusta taulukosta, joka muodostaa geometrisen etenemisen
Kun annetaan lajiteltu joukko erillisiä positiivisia kokonaislukuja, tulosta kaikki kolmiot, jotka muodostavat geometrisen etenemisen integraalisella yhteisellä suhteella.
Geometrinen progressio on lukujono, jossa jokainen termi ensimmäisen jälkeen löydetään kertomalla edellinen kiinteällä nollasta poikkeavalla luvulla, jota kutsutaan yhteiseksi suhteeksi. Esimerkiksi sekvenssi 2 6 18 54... on geometrinen progressio, jolla on yhteinen suhde 3.
Esimerkkejä:
Input: arr = [1 2 6 10 18 54] Output: 2 6 18 6 18 54 Input: arr = [2 8 10 15 16 30 32 64] Output: 2 8 32 8 16 32 16 32 64 Input: arr = [ 1 2 6 18 36 54] Output: 2 6 18 1 6 36 6 18 54
Ideana on aloittaa toisesta elementistä ja kiinnittää jokainen elementti keskielementiksi ja etsiä kaksi muuta elementtiä tripletistä (yksi pienempi ja yksi suurempi). Jotta elementti arr[j] olisi geometrisen etenemisen keskellä, täytyy olla elementtejä arr[i] ja arr[k], jotka -
arr[j] / arr[i] = r and arr[k] / arr[j] = r where r is an positive integer and 0 <= i < j and j < k <= n - 1
Alla yllä olevan idean toteutus
C++ // C++ program to find if there exist three elements in // Geometric Progression or not #include using namespace std ; // The function prints three elements in GP if exists // Assumption: arr[0..n-1] is sorted. void findGeometricTriplets ( int arr [] int n ) { // One by fix every element as middle element for ( int j = 1 ; j < n - 1 ; j ++ ) { // Initialize i and k for the current j int i = j - 1 k = j + 1 ; // Find all i and k such that (i j k) // forms a triplet of GP while ( i >= 0 && k <= n - 1 ) { // if arr[j]/arr[i] = r and arr[k]/arr[j] = r // and r is an integer (i j k) forms Geometric // Progression while ( arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 && arr [ j ] / arr [ i ] == arr [ k ] / arr [ j ]) { // print the triplet cout < < arr [ i ] < < ' ' < < arr [ j ] < < ' ' < < arr [ k ] < < endl ; // Since the array is sorted and elements // are distinct. k ++ i -- ; } // if arr[j] is multiple of arr[i] and arr[k] is // multiple of arr[j] then arr[j] / arr[i] != // arr[k] / arr[j]. We compare their values to // move to next k or previous i. if ( arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 ) { if ( arr [ j ] / arr [ i ] < arr [ k ] / arr [ j ]) i -- ; else k ++ ; } // else if arr[j] is multiple of arr[i] then // try next k. Else try previous i. else if ( arr [ j ] % arr [ i ] == 0 ) k ++ ; else i -- ; } } } // Driver code int main () { // int arr[] = {1 2 6 10 18 54}; // int arr[] = {2 8 10 15 16 30 32 64}; // int arr[] = {1 2 6 18 36 54}; int arr [] = { 1 2 4 16 }; // int arr[] = {1 2 3 6 18 22}; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); findGeometricTriplets ( arr n ); return 0 ; }
Java // Java program to find if there exist three elements in // Geometric Progression or not import java.util.* ; class GFG { // The function prints three elements in GP if exists // Assumption: arr[0..n-1] is sorted. static void findGeometricTriplets ( int arr [] int n ) { // One by fix every element as middle element for ( int j = 1 ; j < n - 1 ; j ++ ) { // Initialize i and k for the current j int i = j - 1 k = j + 1 ; // Find all i and k such that (i j k) // forms a triplet of GP while ( i >= 0 && k <= n - 1 ) { // if arr[j]/arr[i] = r and arr[k]/arr[j] = r // and r is an integer (i j k) forms Geometric // Progression while ( i >= 0 && arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 && arr [ j ] / arr [ i ] == arr [ k ] / arr [ j ] ) { // print the triplet System . out . println ( arr [ i ] + ' ' + arr [ j ] + ' ' + arr [ k ] ); // Since the array is sorted and elements // are distinct. k ++ ; i -- ; } // if arr[j] is multiple of arr[i] and arr[k] is // multiple of arr[j] then arr[j] / arr[i] != // arr[k] / arr[j]. We compare their values to // move to next k or previous i. if ( i >= 0 && arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 ) { if ( i >= 0 && arr [ j ] / arr [ i ] < arr [ k ] / arr [ j ] ) i -- ; else k ++ ; } // else if arr[j] is multiple of arr[i] then // try next k. Else try previous i. else if ( i >= 0 && arr [ j ] % arr [ i ] == 0 ) k ++ ; else i -- ; } } } // Driver code public static void main ( String [] args ) { // int arr[] = {1 2 6 10 18 54}; // int arr[] = {2 8 10 15 16 30 32 64}; // int arr[] = {1 2 6 18 36 54}; int arr [] = { 1 2 4 16 }; // int arr[] = {1 2 3 6 18 22}; int n = arr . length ; findGeometricTriplets ( arr n ); } } // This code is contributed by Rajput-Ji
Python 3 # Python 3 program to find if # there exist three elements in # Geometric Progression or not # The function prints three elements # in GP if exists. # Assumption: arr[0..n-1] is sorted. def findGeometricTriplets ( arr n ): # One by fix every element # as middle element for j in range ( 1 n - 1 ): # Initialize i and k for # the current j i = j - 1 k = j + 1 # Find all i and k such that # (i j k) forms a triplet of GP while ( i >= 0 and k <= n - 1 ): # if arr[j]/arr[i] = r and # arr[k]/arr[j] = r and r # is an integer (i j k) forms # Geometric Progression while ( arr [ j ] % arr [ i ] == 0 and arr [ k ] % arr [ j ] == 0 and arr [ j ] // arr [ i ] == arr [ k ] // arr [ j ]): # print the triplet print ( arr [ i ] ' ' arr [ j ] ' ' arr [ k ]) # Since the array is sorted and # elements are distinct. k += 1 i -= 1 # if arr[j] is multiple of arr[i] # and arr[k] is multiple of arr[j] # then arr[j] / arr[i] != arr[k] / arr[j]. # We compare their values to # move to next k or previous i. if ( arr [ j ] % arr [ i ] == 0 and arr [ k ] % arr [ j ] == 0 ): if ( arr [ j ] // arr [ i ] < arr [ k ] // arr [ j ]): i -= 1 else : k += 1 # else if arr[j] is multiple of # arr[i] then try next k. Else # try previous i. elif ( arr [ j ] % arr [ i ] == 0 ): k += 1 else : i -= 1 # Driver code if __name__ == '__main__' : arr = [ 1 2 4 16 ] n = len ( arr ) findGeometricTriplets ( arr n ) # This code is contributed # by ChitraNayal
C# // C# program to find if there exist three elements // in Geometric Progression or not using System ; class GFG { // The function prints three elements in GP if exists // Assumption: arr[0..n-1] is sorted. static void findGeometricTriplets ( int [] arr int n ) { // One by fix every element as middle element for ( int j = 1 ; j < n - 1 ; j ++ ) { // Initialize i and k for the current j int i = j - 1 k = j + 1 ; // Find all i and k such that (i j k) // forms a triplet of GP while ( i >= 0 && k <= n - 1 ) { // if arr[j]/arr[i] = r and arr[k]/arr[j] = r // and r is an integer (i j k) forms Geometric // Progression while ( i >= 0 && arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 && arr [ j ] / arr [ i ] == arr [ k ] / arr [ j ]) { // print the triplet Console . WriteLine ( arr [ i ] + ' ' + arr [ j ] + ' ' + arr [ k ]); // Since the array is sorted and elements // are distinct. k ++ ; i -- ; } // if arr[j] is multiple of arr[i] and arr[k] is // multiple of arr[j] then arr[j] / arr[i] != // arr[k] / arr[j]. We compare their values to // move to next k or previous i. if ( i >= 0 && arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 ) { if ( i >= 0 && arr [ j ] / arr [ i ] < arr [ k ] / arr [ j ]) i -- ; else k ++ ; } // else if arr[j] is multiple of arr[i] then // try next k. Else try previous i. else if ( i >= 0 && arr [ j ] % arr [ i ] == 0 ) k ++ ; else i -- ; } } } // Driver code static public void Main () { // int arr[] = {1 2 6 10 18 54}; // int arr[] = {2 8 10 15 16 30 32 64}; // int arr[] = {1 2 6 18 36 54}; int [] arr = { 1 2 4 16 }; // int arr[] = {1 2 3 6 18 22}; int n = arr . Length ; findGeometricTriplets ( arr n ); } } // This code is contributed by ajit.
JavaScript < script > // Javascript program to find if there exist three elements in // Geometric Progression or not // The function prints three elements in GP if exists // Assumption: arr[0..n-1] is sorted. function findGeometricTriplets ( arr n ) { // One by fix every element as middle element for ( let j = 1 ; j < n - 1 ; j ++ ) { // Initialize i and k for the current j let i = j - 1 k = j + 1 ; // Find all i and k such that (i j k) // forms a triplet of GP while ( i >= 0 && k <= n - 1 ) { // if arr[j]/arr[i] = r and arr[k]/arr[j] = r // and r is an integer (i j k) forms Geometric // Progression while ( i >= 0 && arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 && arr [ j ] / arr [ i ] == arr [ k ] / arr [ j ]) { // print the triplet document . write ( arr [ i ] + ' ' + arr [ j ] + ' ' + arr [ k ] + '
' ); // Since the array is sorted and elements // are distinct. k ++ ; i -- ; } // if arr[j] is multiple of arr[i] and arr[k] is // multiple of arr[j] then arr[j] / arr[i] != // arr[k] / arr[j]. We compare their values to // move to next k or previous i. if ( i >= 0 && arr [ j ] % arr [ i ] == 0 && arr [ k ] % arr [ j ] == 0 ) { if ( i >= 0 && arr [ j ] / arr [ i ] < arr [ k ] / arr [ j ]) i -- ; else k ++ ; } // else if arr[j] is multiple of arr[i] then // try next k. Else try previous i. else if ( i >= 0 && arr [ j ] % arr [ i ] == 0 ) k ++ ; else i -- ; } } } // Driver code // int arr[] = {1 2 6 10 18 54}; // int arr[] = {2 8 10 15 16 30 32 64}; // int arr[] = {1 2 6 18 36 54}; let arr = [ 1 2 4 16 ]; // int arr[] = {1 2 3 6 18 22}; let n = arr . length ; findGeometricTriplets ( arr n ); // This code is contributed by avanitrachhadiya2155 < /script>
Lähtö
1 2 4 1 4 16
Aika monimutkaisuus yllä oleva ratkaisu on O(n 2 ) kuten jokaiselle j:lle, löydämme i:n ja k:n lineaarisessa ajassa.
Aputila: O(1) koska emme käyttäneet ylimääräistä tilaa.
