Самая длинная геометрическая прогрессия
Учитывая набор чисел, найти L ength из L ongest G eometrix P rogression (LLGP) в нем. Общее отношение GP должно быть целым числом.
Примеры:
set [] = {5, 7, 10, 15, 20, 29} output = 3 Самая длинная геометрическая прогрессия - {5, 10, 20} set [] = {3, 9, 27, 81} output = 4
This problem is similar to Longest Arithmetic Progression Problem. We can solve this problem using Dynamic Programming.
We first sort the given set. We use an auxiliary table L[n][n] to store results of subproblems. An entry L[i][j] in this table stores LLGP with set[i] and set[j] as first two elements of GP and j > i. The table is filled from bottom right to top left. To fill the table, j (second element in GP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an GP, then the value of L[i][j] is set as L[j][k] + 1. Note that the value of L[j][k] must have been filled before as the loop traverses from right to left columns.
Following is the implementation of the Dynamic Programming algorithm.
C++
// C++ program to find length // of the longest geometric // progression in a given set #include <iostream> #include <algorithm> using namespace std; // Returns length of the // longest GP subset of set[] int lenOfLongestGP( int set[], int n) { // Base cases if (n < 2) return n; if (n == 2) return (set[1] % set[0] == 0) ? 2 : 1; // Let us sort the set first sort(set, set+n); // An entry L[i][j] in this // table stores LLGP with // set[i] and set[j] as first // two elements of GP // and j > i. int L[n][n]; // Initialize result (A single element // is always a GP) int llgp = 1; // Initialize values of last column for ( int i = 0; i < n - 1; ++i) { if (set[n-1] % set[i] == 0) { L[i][n-1] = 2; if (2 > llgp) llgp = 2; } else { L[i][n-1] = 1; } } L[n-1][n-1] = 1; // Consider every element as // second element of GP for ( int j = n - 2; j >= 1; --j) { // Search for i and k for j int i = j - 1, k = j+1; while (i>=0 && k <= n-1) { // Two cases when i, j and k don"t form // a GP. if (set[i] * set[k] < set[j]*set[j]) { ++k; } else if (set[i] * set[k] > set[j]*set[j]) { if (set[j] % set[i] == 0) { L[i][j] = 2; } else { L[i][j] = 1; } --i; } // i, j and k form GP, LLGP with i and j as // first two elements is equal to LLGP with // j and k as first two elements plus 1. // L[j][k] must have been filled before as // we run the loop from right side else { if (set[j] % set[i] == 0) { L[i][j] = L[j][k] + 1; // Update overall LLGP if (L[i][j] > llgp) llgp = L[i][j]; } else { L[i][j] = 1; } // Change i and k to fill more L[i][j] // values for current j --i; ++k; } } // If the loop was stopped due to k becoming // more than n-1, set the remaining entries // in column j as 1 or 2 based on divisibility // of set[j] by set[i] while (i >= 0) { if (set[j] % set[i] == 0) { L[i][j] = 2; if (2 > llgp) llgp = 2; } else L[i][j] = 1; --i; } } // Return result return llgp; } // Driver code int main() { int set1[] = {1, 3, 9, 27, 81, 243}; int n1 = sizeof (set1)/ sizeof (set1[0]); cout << lenOfLongestGP(set1, n1) << "
" ; int set2[] = {1, 3, 4, 9, 7, 27}; int n2 = sizeof (set2)/ sizeof (set2[0]); cout << lenOfLongestGP(set2, n2) << "
" ; int set3[] = {2, 3, 5, 7, 11, 13}; int n3 = sizeof (set3)/ sizeof (set3[0]); cout << lenOfLongestGP(set3, n3) << "
" ; return 0; } |
Java
// Java program to find length // of the longest geometric // progression in a given set import java.util.*; class GFG { // Returns length of the longest GP subset of set[] static int lenOfLongestGP( int set[], int n) { // Base cases if (n < 2 ) { return n; } if (n == 2 ) { return (set[ 1 ] % set[ 0 ] == 0 ? 2 : 1 ); } // Let us sort the set first Arrays.sort(set); // An entry L[i][j] in this table // stores LLGP with set[i] and set[j] // as first two elements of GP // and j > i. int L[][] = new int [n][n]; // Initialize result (A single // element is always a GP) int llgp = 1 ; // Initialize values of last column for ( int i = 0 ; i < n - 1 ; ++i) { if (set[n - 1 ] % set[i] == 0 ) { L[i][n - 1 ] = 2 ; if ( 2 > llgp) llgp = 2 ; } else { L[i][n - 1 ] = 1 ; } } L[n - 1 ][n - 1 ] = 1 ; // Consider every element as second element of GP for ( int j = n - 2 ; j >= 1 ; --j) { // Search for i and k for j int i = j - 1 , k = j + 1 ; while (i >= 0 && k <= n - 1 ) { // Two cases when i, j and k // don"t form a GP. if (set[i] * set[k] < set[j] * set[j]) { ++k; } else if (set[i] * set[k] > set[j] * set[j]) { if (set[j] % set[i] == 0 ) { L[i][j] = 2 ; if ( 2 > llgp) llgp = 2 ; } else { L[i][j] = 1 ; } --i; } // i, j and k form GP, LLGP with i and j as // first two elements is equal to LLGP with // j and k as first two elements plus 1. // L[j][k] must have been filled before as // we run the loop from right side else { if (set[j] % set[i] == 0 ) { L[i][j] = L[j][k] + 1 ; // Update overall LLGP if (L[i][j] > llgp) { llgp = L[i][j]; } } else { L[i][j] = 1 ; } // Change i and k to fill more L[i][j] // values for current j --i; ++k; } } // If the loop was stopped due to k becoming // more than n-1, set the remaining entries // in column j as 1 or 2 based on divisibility // of set[j] by set[i] while (i >= 0 ) { if (set[j] % set[i] == 0 ) { L[i][j] = 2 ; if ( 2 > llgp) llgp = 2 ; } else { L[i][j] = 1 ; } --i; } } // Return result return llgp; } // Driver code public static void main(String[] args) { int set1[] = { 1 , 3 , 9 , 27 , 81 , 243 }; int n1 = set1.length; System.out.print(lenOfLongestGP(set1, n1) + "
" ); int set2[] = { 1 , 3 , 4 , 9 , 7 , 27 }; int n2 = set2.length; System.out.print(lenOfLongestGP(set2, n2) + "
" ); int set3[] = { 2 , 3 , 5 , 7 , 11 , 13 }; int n3 = set3.length; System.out.print(lenOfLongestGP(set3, n3) + "
" ); } } /* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 program to find length # of the longest geometric # progression in a given sett # Returns length of the longest GP # subset of sett[] def lenOfLongestGP(sett, n): # Base cases if n < 2 : return n if n = = 2 : return 2 if (sett[ 1 ] % sett[ 0 ] = = 0 ) else 1 # let us sort the sett first sett.sort() # An entry L[i][j] in this # table stores LLGP with # sett[i] and sett[j] as first # two elements of GP # and j > i. L = [[ 0 for i in range (n)] for i in range (n)] # Initialize result (A single # element is always a GP) llgp = 1 # Initialize values of last column for i in range ( 0 , n - 1 ): if sett[n - 1 ] % sett[i] = = 0 : L[i][n - 1 ] = 2 if 2 > llgp: llgp = 2 else : L[i][n - 1 ] = 1 L[n - 1 ][n - 1 ] = 1 # Consider every element as second element of GP for j in range (n - 2 , 0 , - 1 ): # Search for i and k for j i = j - 1 k = j + 1 while i > = 0 and k < = n - 1 : # Two cases when i, j and k don"t form # a GP. if sett[i] * sett[k]
РЕКОМЕНДУЕМЫЕ СТАТЬИ |