Progresión geométrica más larga

Dado un conjunto de números, encuentre la L ongitud de la Progresión G eometrix Más Larga ( LLGP ) en él. La razón común de GP debe ser un número entero. Ejemplos: 

set[] = {5, 7, 10, 15, 20, 29}
output = 3
The longest geometric progression is {5, 10, 20}

set[] = {3, 9, 27, 81}
output = 4

Este problema es similar al problema de progresión aritmética más larga . Podemos resolver este problema usando Programación Dinámica. 
Primero ordenamos el conjunto dado. Usamos una tabla auxiliar L[n][n] para almacenar los resultados de los subproblemas. Una entrada L[i][j] en esta tabla almacena LLGP con set[i] y set[j] como los dos primeros elementos de GP y j > i. La tabla se llena de abajo a la derecha a arriba a la izquierda. Para llenar la tabla, primero se fija j (segundo elemento en GP). i y k se buscan para un j fijo. Si i y k se encuentran de tal manera que i, j, k forman un GP, ​​entonces el valor de L[i][j] se establece como L[j][k] + 1. Tenga en cuenta que el valor de L[j] [k] debe haberse rellenado antes, ya que el ciclo atraviesa de las columnas de derecha a izquierda.
A continuación se muestra la implementación del algoritmo de Programación Dinámica. 

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) << "\n";
 
    int set2[] = {1, 3, 4, 9, 7, 27};
    int n2 = sizeof(set2)/sizeof(set2[0]);
    cout << lenOfLongestGP(set2, n2) << "\n";
 
    int set3[] = {2, 3, 5, 7, 11, 13};
    int n3 = sizeof(set3)/sizeof(set3[0]);
    cout << lenOfLongestGP(set3, n3) << "\n";
 
    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) + "\n");
 
        int set2[] = { 1, 3, 4, 9, 7, 27 };
        int n2 = set2.length;
        System.out.print(lenOfLongestGP(set2, n2) + "\n");
 
        int set3[] = { 2, 3, 5, 7, 11, 13 };
        int n3 = set3.length;
        System.out.print(lenOfLongestGP(set3, n3) + "\n");
    }
}
 
/* 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] < sett[j] * sett[j]:
                k += 1
            else if sett[i] * sett[k] > sett[j] * sett[j]:
                if sett[j] % sett[i] == 0:
                    L[i][j] = 2
                else:
                    L[i][j] = 1
                i -= 1
 
            # 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 sett[j] % sett[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 -= 1
                k += 1
 
        # 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 sett[j] by sett[i]
        while i >= 0:
            if sett[j] % sett[i] == 0:
                L[i][j] = 2
            else:
                L[i][j] = 1
            i -= 1
 
    return llgp
 
 
# Driver code
if __name__ == '__main__':
    set1 = [1, 3, 9, 27, 81, 243]
    n1 = len(set1)
    print(lenOfLongestGP(set1, n1))
 
    set2 = [1, 3, 4, 9, 7, 27]
    n2 = len(set2)
    print(lenOfLongestGP(set2, n2))
 
    set3 = [2, 3, 5, 7, 11, 13]
    n3 = len(set3)
    print(lenOfLongestGP(set3, n3))
 
# this code is contributed by sahilshelangia

C#

// C# program to find length
// of the longest geometric
// progression in a given Set
using System;
 
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
        Array.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;
        Console.Write(lenOfLongestGP(set1, n1) + "\n");
 
        int []set2 = {1, 3, 4, 9, 7, 27};
        int n2 = set2.Length;
        Console.Write(lenOfLongestGP(set2, n2) + "\n");
 
        int []set3 = {2, 3, 5, 7, 11, 13};
        int n3 = set3.Length;
        Console.Write(lenOfLongestGP(set3, n3) + "\n");
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
    // Javascript program to find length
    // of the longest geometric
    // progression in a given set
     
    // Returns length of the longest GP subset of set[]
    function lenOfLongestGP(set, 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
        set.sort(function(a, b){return a - b});
  
        // 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.
        let L = new Array(n);
        for (let i = 0; i < n; ++i)
        {
            L[i] = new Array(n);
            for (let j = 0; j < n; ++j)
            {
                L[i][j] = 0;
            }
        }
  
        // Initialize result (A single
        // element is always a GP)
        let llgp = 1;
  
        // Initialize values of last column
        for (let 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 (let j = n - 2; j >= 1; --j) {
            // Search for i and k for j
            let 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;
    }
     
    let set1 = [ 1, 3, 9, 27, 81, 243 ];
    let n1 = set1.length;
    document.write(lenOfLongestGP(set1, n1) + "</br>");
 
    let set2 = [ 1, 3, 4, 9, 7, 27 ];
    let n2 = set2.length;
    document.write(lenOfLongestGP(set2, n2) + "</br>");
 
    let set3 = [ 2, 3, 5, 7, 11, 13 ];
    let n3 = set3.length;
    document.write(lenOfLongestGP(set3, n3) + "</br>");
 
// This code is contributed by rameshtravel07.
</script>

Producción: 

6
4
1

Complejidad de tiempo: O(n 2
Espacio auxiliar: O(n 2 )
Este artículo es una contribución de Vivek Pandya . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *