Skip to main content
se añadieron 42 caracteres en el cuerpo
Origen Enlace
abulafia
  • 58.7k
  • 3
  • 54
  • 89
  • Se prepara una variable (que llama actual) para contener la sub-cadena ordenada que se ha encontrado de momento. Una subcadena ordenada contiene sólo elementos que se hallan en orden alfabético, es decir, que cada elemento de la cadena es "mayor o igual" que el anterior (alfabéticamente). Una subcadena ordenada se termina tan pronto como aparezca una letra que es menor (alfabéticamente) que la anterior. Por ejemplo, si de momento llevamos encontradas las letras "mrs" esa es una subcadena ordenada. Si la letra siguiente es por ejemplo "t" se añadiría a esa subcadena, pues "t" es mayor (alfabéticamente) que "s". Pero si se encuentra "f", entonces la subcadena ordenada que llevábamos hasta ese punto se da por terminada y se comienza una nueva que comienza porde momento sería "f".
  • Cada letra que se vaya procesando de la cadena de entrada o bien se añade a la subcadena actual (si es menor o igual que su última letra), o bien da comienzo a una nueva subcadena.
  • A la vez, se tiene otra variable (llamada larga) para contener la subcadena más larga encontrada hasta el momento. Esta variable se actualiza cada vez que la subcadena contenida en actual es mayor (en longitud) que la que había en larga.
  1. La sub-cadena ordenada encontrada hasta el momento consiste solo en la primera letra s[0] que es "a".
  2. La sub-cadena más larga encontrada hasta el momento es obviamente esa misma letra.
  3. Iteramos por las restantes letras una a una (s[1:] significa todas las letras desde la 1 en adelante, pues la 0 ya la hemos procesado). En cada iteración la variable c tomará el valor de una de las letras.
    • En la primera iteración la letra c tomará el valor de `s[1]p , que es "z".
    • Se compara esta letra con la última que teníamos en actual (el subíndice -1 significa en python el último elemento de una cadena o lista). Por tanto estamos comparando "a" con "z".
    • Ya que es mayor, se añade a actual que pasa ahora a valer "az"
    • Ya que la longitud de actual es mayor que la longitud de larga, significa que hemos encontrado una cadena más larga que la más larga hasta ahora. De modo que actualizamos larga para que sea igual a actual. Ahora larga vale también "az"

Primera iteración del bucle:

  • En la primera iteración la letra c tomará el valor de s[1] , que es "z".
  • Se compara esta letra con la última que teníamos en actual (el subíndice -1 significa en python el último elemento de una cadena o lista). Por tanto estamos comparando "a" con "z".
  • Ya que es mayor, se añade a actual que pasa ahora a valer "az"
  • Ya que la longitud de actual es mayor que la longitud de larga, significa que hemos encontrado una cadena más larga que la más larga hasta ahora. De modo que actualizamos larga para que sea igual a actual. Ahora larga vale también "az"
  • Se prepara una variable (que llama actual) para contener la sub-cadena ordenada que se ha encontrado de momento. Una subcadena ordenada contiene sólo elementos que se hallan en orden alfabético, es decir, que cada elemento de la cadena es "mayor o igual" que el anterior (alfabéticamente). Una subcadena ordenada se termina tan pronto como aparezca una letra que es menor (alfabéticamente) que la anterior. Por ejemplo, si de momento llevamos encontradas las letras "mrs" esa es una subcadena ordenada. Si la letra siguiente es por ejemplo "t" se añadiría a esa subcadena, pues "t" es mayor (alfabéticamente) que "s". Pero si se encuentra "f", entonces la subcadena ordenada que llevábamos hasta ese punto se da por terminada y se comienza una nueva que comienza por "f".
  • Cada letra que se vaya procesando de la cadena de entrada o bien se añade a la subcadena actual (si es menor o igual que su última letra), o bien da comienzo a una nueva subcadena.
  • A la vez, se tiene otra variable (llamada larga) para contener la subcadena más larga encontrada hasta el momento. Esta variable se actualiza cada vez que la subcadena contenida en actual es mayor que la que había en larga.
  1. La sub-cadena ordenada encontrada hasta el momento consiste solo en la primera letra s[0] que es "a".
  2. La sub-cadena más larga encontrada hasta el momento es obviamente esa misma letra.
  3. Iteramos por las restantes letras una a una (s[1:] significa todas las letras desde la 1 en adelante, pues la 0 ya la hemos procesado). En cada iteración la variable c tomará el valor de una de las letras.
    • En la primera iteración la letra c tomará el valor de `s[1]p , que es "z".
    • Se compara esta letra con la última que teníamos en actual (el subíndice -1 significa en python el último elemento de una cadena o lista). Por tanto estamos comparando "a" con "z".
    • Ya que es mayor, se añade a actual que pasa ahora a valer "az"
    • Ya que la longitud de actual es mayor que la longitud de larga, significa que hemos encontrado una cadena más larga que la más larga hasta ahora. De modo que actualizamos larga para que sea igual a actual. Ahora larga vale también "az"
  • Se prepara una variable (que llama actual) para contener la sub-cadena ordenada que se ha encontrado de momento. Una subcadena ordenada contiene sólo elementos que se hallan en orden alfabético, es decir, que cada elemento de la cadena es "mayor o igual" que el anterior (alfabéticamente). Una subcadena ordenada se termina tan pronto como aparezca una letra que es menor (alfabéticamente) que la anterior. Por ejemplo, si de momento llevamos encontradas las letras "mrs" esa es una subcadena ordenada. Si la letra siguiente es por ejemplo "t" se añadiría a esa subcadena, pues "t" es mayor (alfabéticamente) que "s". Pero si se encuentra "f", entonces la subcadena ordenada que llevábamos hasta ese punto se da por terminada y se comienza una nueva que de momento sería "f".
  • Cada letra que se vaya procesando de la cadena de entrada o bien se añade a la subcadena actual (si es menor o igual que su última letra), o bien da comienzo a una nueva subcadena.
  • A la vez, se tiene otra variable (llamada larga) para contener la subcadena más larga encontrada hasta el momento. Esta variable se actualiza cada vez que la subcadena contenida en actual es mayor (en longitud) que la que había en larga.
  1. La sub-cadena ordenada encontrada hasta el momento consiste solo en la primera letra s[0] que es "a".
  2. La sub-cadena más larga encontrada hasta el momento es obviamente esa misma letra.
  3. Iteramos por las restantes letras una a una (s[1:] significa todas las letras desde la 1 en adelante, pues la 0 ya la hemos procesado). En cada iteración la variable c tomará el valor de una de las letras.

Primera iteración del bucle:

  • En la primera iteración la letra c tomará el valor de s[1] , que es "z".
  • Se compara esta letra con la última que teníamos en actual (el subíndice -1 significa en python el último elemento de una cadena o lista). Por tanto estamos comparando "a" con "z".
  • Ya que es mayor, se añade a actual que pasa ahora a valer "az"
  • Ya que la longitud de actual es mayor que la longitud de larga, significa que hemos encontrado una cadena más larga que la más larga hasta ahora. De modo que actualizamos larga para que sea igual a actual. Ahora larga vale también "az"
Origen Enlace
abulafia
  • 58.7k
  • 3
  • 54
  • 89

Lógica del algoritmo

La lógica es la siguiente:

  • Se prepara una variable (que llama actual) para contener la sub-cadena ordenada que se ha encontrado de momento. Una subcadena ordenada contiene sólo elementos que se hallan en orden alfabético, es decir, que cada elemento de la cadena es "mayor o igual" que el anterior (alfabéticamente). Una subcadena ordenada se termina tan pronto como aparezca una letra que es menor (alfabéticamente) que la anterior. Por ejemplo, si de momento llevamos encontradas las letras "mrs" esa es una subcadena ordenada. Si la letra siguiente es por ejemplo "t" se añadiría a esa subcadena, pues "t" es mayor (alfabéticamente) que "s". Pero si se encuentra "f", entonces la subcadena ordenada que llevábamos hasta ese punto se da por terminada y se comienza una nueva que comienza por "f".
  • Cada letra que se vaya procesando de la cadena de entrada o bien se añade a la subcadena actual (si es menor o igual que su última letra), o bien da comienzo a una nueva subcadena.
  • A la vez, se tiene otra variable (llamada larga) para contener la subcadena más larga encontrada hasta el momento. Esta variable se actualiza cada vez que la subcadena contenida en actual es mayor que la que había en larga.

Una vez tenemos claro (más o menos) el funcionamiento del algoritmo, la forma de comprenderlo de verdad es ejecutarlo "paso a paso", es decir, seguir instrucción a instrucción lo que va ocurriendo con cada variable.

Ejecución paso a paso

Para este tipo de ejecuciones paso a paso un depurador es una herramienta muy útil. Visual Studio Code es un editor que se integra bien con Python y que tiene un depurador que te permite ejecutar paso a paso los programas e inspeccionar las variables. Si no tienes acceso a él o no sabes cómo configurarlo y usarlo, también puedes utilizar algún servicio on-line como pythontutor

Pero incluso sin nada de eso puedes ejecutar paso a paso el programa "mentalmente" y si en algún momento te pierdes, insertar en tu código algún print() que te muestre los valores de las variables según va pasando por las iteraciones.

Intentemos ejecutar paso a paso el programa "mentalmente" con la entrada s = "azcbobobegghakl"

  1. La sub-cadena ordenada encontrada hasta el momento consiste solo en la primera letra s[0] que es "a".
  2. La sub-cadena más larga encontrada hasta el momento es obviamente esa misma letra.
  3. Iteramos por las restantes letras una a una (s[1:] significa todas las letras desde la 1 en adelante, pues la 0 ya la hemos procesado). En cada iteración la variable c tomará el valor de una de las letras.
    • En la primera iteración la letra c tomará el valor de `s[1]p , que es "z".
    • Se compara esta letra con la última que teníamos en actual (el subíndice -1 significa en python el último elemento de una cadena o lista). Por tanto estamos comparando "a" con "z".
    • Ya que es mayor, se añade a actual que pasa ahora a valer "az"
    • Ya que la longitud de actual es mayor que la longitud de larga, significa que hemos encontrado una cadena más larga que la más larga hasta ahora. De modo que actualizamos larga para que sea igual a actual. Ahora larga vale también "az"

Pasemos a la siguiente iteración del bucle, en la que c vale "c" (la siguiente letra de la cadena).

  • Se compara con la última letra de actual, que era "z".
  • Como no es mayor o igual, esto dará comienzo a una nueva subcadena. El valor de actual pasa a ser "c".
  • Como la longitud de actual no es mayor que la longitud de larga, no cambiamos el valor de esta última. larga sigue valiendo "ac", que es la subcadena ordenada más larga encontrada hasta este momento.

En la siguiente iteración encontramos "b" que al ser menor que "c" da comienzo a una nueva subcadena. actual pasa a valer "c".

No voy a continuar. Puedes seguir tú ejecutando "paso a paso" (es un buen ejercicio) y descubrir cómo al llegar a "beggh" y ser cada una de estas letras mayor que la anterior, se van actualizando las variables actual y también larga. Después de esto viene una "a" que "reseteará" la variable actual (por ser menor que la última letra) al valor "a". Y después vienen "k" y "l" que se irán añadiendo a actual, que llega a tomar el valor "akl", pero que al tener sólo tres letras (menos que las cinco letras que contiene larga) no causan que esta última se actualice.

Al salir del bucle tendrás en actual el valor "akl" (la última subcadena ordenada encontrada) y en larga "beggh" (la subcadena ordenada más larga encontrada).

"Depuración" mediante print

Si te has perdido con esta explicación, prueba a insertar prints en el código como los siguientes:

s = "azcbobobegghakl"

larga = s[0]
actual = s[0]

for c in s[1:]:
    print("Letra que se está procesando:", c)
    print("Letra anterior:", actual[-1])
    if c >= actual[-1]:
        actual += c
        if len(actual) > len(larga):
            larga = actual
    else:
        actual = c
    print("actual=", actual)
    print("larga=", larga)

print("La subcadena más larga en orden alfabético es:", larga)