Problema del algoritmo: encontrar la cadena de nombres de pares más larga.

Answer

1. 

   davy.ai

   July 22, 2023 at 4:07 pm

   Algoritmo para encontrar la longitud de la cadena de pares más larga

   Podemos utilizar un enfoque de programación dinámica para resolver este problema. Definamos una lista dp del tamaño igual al número de pares en la lista de entrada. El dp[i] representará la longitud de la cadena más larga que termina en el i-ésimo par de la lista. Inicialmente, todos los elementos de dp se establecerán en 1, ya que cada par se puede considerar como una cadena de longitud 1.

   A continuación, ordenaremos los pares en función del segundo elemento del par. Como queremos encontrar la cadena más larga donde el primer elemento del segundo par sea igual al último elemento del primer par, ordenarlos en función del segundo elemento nos ayudará a verificar eficientemente los pares anteriores en la lista que podrían formar parte de la cadena.

   Ahora, podemos iterar sobre la lista ordenada de pares y, para cada par en el índice i, comprobaremos todos los pares anteriores (en el índice j, donde j<i) tal que el segundo elemento del par j-ésimo sea igual al primer elemento del par i-ésimo. si se encuentra dicho par, podemos actualizar dp[i] como dp[i] = max(dp[i], dp[j]+1). esto se debe a que agregar el i-ésimo par a la cadena formada por el j-ésimo par dará como resultado una cadena más larga.

   finalmente, podemos devolver el valor máximo de dp como la respuesta, lo cual nos dará la longitud de la cadena más larga.

   veamos la implementación del algoritmo anterior en python:

   def find_longest_chain(pairs):
       n = len(pairs)
       dp = [1]*n  # inicializar dp con 1, ya que cada par es una cadena de longitud 1
       pairs = sorted(pairs, key=lambda x: x[1])  # ordenar pares en función del segundo elemento
   
       for i in range(n):
           for j in range(i):
               if pairs[i][0] == pairs[j][1]:
                   dp[i] = max(dp[i], dp[j]+1)
   
       return max(dp)
   
   pairs = [['jason', 'nick'], ['nick', 'bob'], ['bob', 'mac']]
   print(find_longest_chain(pairs))  # salida: 3
   

   en el código anterior, primero inicializamos dp con todos los elementos como 1, y luego ordenamos los pares en función del segundo elemento. luego, iteramos sobre la lista ordenada de pares y, para cada par, verificamos todos los pares anteriores para ver si pueden formar una cadena con el par actual. si es así, actualizamos el valor de dp en consecuencia. finalmente, devolvemos el valor máximo de dp como la respuesta, que es la longitud de la cadena más larga. tal=”” que=”” el=”” segundo=”” elemento=”” del=”” par=”” j-ésimo=”” sea=”” igual=”” al=”” primer=”” elemento=”” del=”” par=”” i-ésimo.=”” si=”” se=”” encuentra=”” dicho=”” par,=”” podemos=”” actualizar=”” dp[i]=”” como=”” dp[i]="max(dp[i]," dp[j]+1).=”” esto=”” se=”” debe=”” a=”” que=”” agregar=”” el=”” i-ésimo=”” par=”” a=”” la=”” cadena=”” formada=”” por=”” el=”” j-ésimo=”” par=”” dará=”” como=”” resultado=”” una=”” cadena=”” más=”” larga.=”” finalmente,=”” podemos=”” devolver=”” el=”” valor=”” máximo=”” de=”” dp=”” como=”” la=”” respuesta,=”” lo=”” cual=”” nos=”” dará=”” la=”” longitud=”” de=”” la=”” cadena=”” más=”” larga.=”” veamos=”” la=”” implementación=”” del=”” algoritmo=”” anterior=”” en=”” python:=”” python="" def="" find_longest_chain(pairs):="" n="len(pairs)" dp="[1]*n" #="" inicializar="" dp="" con="" 1,="" ya="" que="" cada="" par="" es="" una="" cadena="" de="" longitud="" 1="" pairs="sorted(pairs," key="lambda" x:="" x[1])="" #="" ordenar="" pares="" en="" función="" del="" segundo="" elemento="" for="" i="" in="" range(n):="" for="" j="" in="" range(i):="" if="" pairs[i][0]="=" pairs[j][1]:="" dp[i]="max(dp[i]," dp[j]+1)="" return="" max(dp)="" pairs="[['Jason'," 'nick'],="" ['nick',="" 'bob'],="" ['bob',="" 'mac']]="" print(find_longest_chain(pairs))="" #="" salida:="" 3=""=”” en=”” el=”” código=”” anterior,=”” primero=”” inicializamos=”” dp=”” con=”” todos=”” los=”” elementos=”” como=”” 1,=”” y=”” luego=”” ordenamos=”” los=”” pares=”” en=”” función=”” del=”” segundo=”” elemento.=”” luego,=”” iteramos=”” sobre=”” la=”” lista=”” ordenada=”” de=”” pares=”” y,=”” para=”” cada=”” par,=”” verificamos=”” todos=”” los=”” pares=”” anteriores=”” para=”” ver=”” si=”” pueden=”” formar=”” una=”” cadena=”” con=”” el=”” par=”” actual.=”” si=”” es=”” así,=”” actualizamos=”” el=”” valor=”” de=”” dp=”” en=”” consecuencia.=”” finalmente,=”” devolvemos=”” el=”” valor=”” máximo=”” de=”” dp=”” como=”” la=”” respuesta,=”” que=”” es=”” la=”” longitud=”” de=”” la=”” cadena=”” más=””></i) tal que el segundo elemento del parj-ésimosea igual al primer elemento del pari-ésimo. si se encuentra dicho par, podemos actualizardp[i]comodp[i] = max(dp[i], dp[j]+1). esto se debe a que agregar eli-ésimopar a la cadena formada por elj-ésimo` par dará como resultado una cadena más larga.

   finalmente, podemos devolver el valor máximo de dp como la respuesta, lo cual nos dará la longitud de la cadena más larga.

   veamos la implementación del algoritmo anterior en python:

   def find_longest_chain(pairs):
       n = len(pairs)
       dp = [1]*n  # inicializar dp con 1, ya que cada par es una cadena de longitud 1
       pairs = sorted(pairs, key=lambda x: x[1])  # ordenar pares en función del segundo elemento
   
       for i in range(n):
           for j in range(i):
               if pairs[i][0] == pairs[j][1]:
                   dp[i] = max(dp[i], dp[j]+1)
   
       return max(dp)
   
   pairs = [['jason', 'nick'], ['nick', 'bob'], ['bob', 'mac']]
   print(find_longest_chain(pairs))  # salida: 3
   

   en el código anterior, primero inicializamos dp con todos los elementos como 1, y luego ordenamos los pares en función del segundo elemento. luego, iteramos sobre la lista ordenada de pares y, para cada par, verificamos todos los pares anteriores para ver si pueden formar una cadena con el par actual. si es así, actualizamos el valor de dp en consecuencia. finalmente, devolvemos el valor máximo de dp como la respuesta, que es la longitud de la cadena más larga.>

Comments are closed.