Crea algoritmos sencillos

Skip to content

¡Este es un texto traducido automáticamente que puede contener errores!

Quote

“Algoritmo”, una palabra utilizada por los programadores cuando no quieren explicar lo que hicieron.

Algoritme?

¿Qué es un algoritmo?

Un algoritmo es una función lógica que realiza una operación dada. Por lo tanto, técnicamente puedes llamar “algoritmo” a una función que suma dos números, pero con frecuencia un algoritmo es algo un poco más complicado que eso. A menudo, los algoritmos se utilizan para acelerar operaciones que requieren mucho tiempo.

Algorithm Meme

¿Debo usar Python en estas tareas?

¡No! Puedes usar cualquier lenguaje de programación que prefieras en estas tareas.

¿Bibliotecas integradas?

La idea en estos ejercicios es evitar usar bibliotecas integradas o funciones especiales de Python. Por ejemplo, existe una “línea” simple para invertir texto: text[::-1], pero aquí queremos que intentes resolver este tipo de ejercicios sin usar esto. Puede que mencionemos una función integrada si la solución es un poco difícil de encontrar. Esto se marcará con ❗.

En la práctica, debería ser totalmente posible resolver todos estos ejercicios con if, for, while y operaciones de lista comunes.

¿Cómo “diseñar” un algoritmo?

Lo más común es que los algoritmos se diseñen iterativamente. ¿Qué significa esto?

1. ✅ Primero, descompón el problema en partes más pequeñas.
  • Piensa, ante todo, en lo más importante que necesitas para que el algoritmo funcione
    • ¿Debe devolver un valor? ¿Un boolean? ¿Una lista?
    • ¿Necesito alguna función de ayuda?

2. ❓ ¿Hay algún “caso límite”?
  • ¿Qué ocurre si introduces una lista o texto vacío?

3. ✅ Comienza simplemente intentando crear una solución

4. ✅ Comprueba si el algoritmo funciona bien en tiempo de ejecución
  • Prueba con entradas más grandes, ¿tarda mucho?

5. ❓ Considera tu solución, ¿necesitas todos los pasos que has utilizado?
  • ¿Son necesarias todas las comprobaciones if?
  • Si tienes más de un bucle for, ¿hay alguna forma clara de hacer esto con un bucle for?
    • Esto es diferente si tienes bucles anidados o bucles uno tras otro. Los bucles uno tras otro a menudo se pueden evitar.

6. ✅ Considera escenarios extremos con entradas:
  • Ejemplo con números: números grandes, números pequeños, números negativos
  • Ejemplo de texto: mucho texto, muchas palabras pequeñas, espacios adicionales, mayúsculas y minúsculas.

7. ❓ ¿Es útil usar pseudo-código para comprender mejor la lógica?

Easy Tarea 1 - Determinar si una lista contiene un número dado

Crea un algoritmo (función) que determine si una lista contiene un número dado. Debe devolver True o False según si el número existe en la lista o no.

Aquí hay una lista con datos de prueba:

Test-data for algoritme:
Test-Data Sjekk Svar
[1, 2, 3, 4, 5, 6, 7, 8, 9] 5 True
[1, 2, 3, 4, 5, 6, 7, 8, 9] 10 False
[2, 3, 5, 7, 11, 13, 17, 19, 23] 2 True
[2, 3, 5, 7, 11, 13, 17, 19, 23] 10 False
[-1, 0, 1, -34, 321, 22, 98, -214] -214 True
[-1, 0, 1, -34, 321, 22, 98, -214] 0 True
[-1, 0, 1, -34, 321, 22, 98, -214] 2 False

Tips til framgangsmåte
  1. Toma una lista y un valor de lista como entrada en una función. En esta tarea, serán números, pero pueden ser texto.
  2. Usa un bucle for para recorrer la lista.
  3. Si el número es igual al número de comprobación, devuelve True.
  4. Si el bucle for termina y no lo has encontrado, devuelve False.

Svaret (i python) 
def exists_in_list(the_list, check):
    for number in the_list:
        if number == check:
            return True
    return False

Easy Tarea 2 - Sumatorio

Crea un algoritmo que sume una lista de números.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], da como respuesta 21.
  • [5, 1, 23, 68, 22, 13, 4], da como respuesta 136
  • [3, 3, -3, -3, 3] da como respuesta 3. Eventualmente, puedes ignorar los números negativos y dar como respuesta 9.

Tips til framgangsmåte
  1. Toma una lista en una función
  2. Guarda una suma temporal como 0.
  3. Usa un bucle for para recorrer la lista.
  4. return la suma de la lista.

Svaret (i python) 
def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Medium Tarea 3a - Valor máximo en una lista

Crea un algoritmo que encuentre el valor más grande en una lista.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], da como respuesta 6.
  • [6, 17, 227, 1, 23, 42, 12], da como respuesta 227
  • [2, -2, 2, -2, -2, 2] da como respuesta 2.

Tips til framgangsmåte
  1. Introduce una lista en una función
  2. Establece un valor temporal al primer elemento de la lista.
  3. Usa un bucle for para recorrer la lista y compararlo con el valor que estableciste en 2.
  4. Si el valor es mayor, establece el valor temporal al nuevo valor.
  5. return este valor temporal.

Svaret (i python) 
def find_max(numbers):
    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Easy Tarea 3b - ¿Si la lista está vacía?

Agrega una comprobación que pruebe si la lista contiene elementos. Si no, devuelve None.

Svaret (i python) 
def find_max(numbers):
    if len(numbers) == 0:
        return None

    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Easy Tarea 4 - Contar el número de un elemento dado en una lista

Crea un algoritmo que cuente el número de un elemento dado en una lista.

Test-data for algoritme:
  • ["apple", "banana", "orange", "apple", "apple", "banana"] con apple da como respuesta 3.
  • [1, 4, 5, 2, 4, -3, -4, 4, 2, 4, 221, 3, 1, 1, 4, 1, 12, 33, 4, 4, 2, -4, 1, 4] con 4 da como respuesta 8.
  • ["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] con dog da como respuesta 3.
  • [7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] con 7 da como respuesta 5.
  • ["red", "blue", "green", "red", "yellow", "red"] con red da como respuesta 3.
  • [10, -2, -2, -2, 5, 10, 10, -2] con -2 da como respuesta 4.

Tips til framgangsmåte
  1. Toma una lista y un valor de comprobación en una función
  2. Comienza con un valor de conteo temporal establecido en 0.
  3. Recorre la lista con un bucle for.
  4. Si el elemento es igual a la comprobación, incrementa el valor de conteo en 1.
  5. Devuelve el valor de conteo.

Svaret (i python) 
def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

Medium Tarea 5 - Invertir una string, texto

Crea un algoritmo que invierta una string dada.

Test-data for algoritme:
  • Hello there! se convierte en !ereht olleH.
  • heisann alle sammen se convierte en nemmas ella nnasieh
  • Python se convierte en nohtyP
  • racecar se convierte en racecar
  • 12345abc se convierte en cba54321
  • god morgen se convierte en negrom dog

Tips til framgangsmåte
  1. Toma una string en una función
  2. Crea un valor temporal para almacenar una string vacía.
  3. Recorre el texto con un bucle for con range. Aquí puedes recorrer la lista hacia atrás, pero es posible resolver esto recorriendo la lista hacia adelante.
  4. Agrega cada carácter al valor temporal en orden.
  5. Devuelve el texto temporal.

Svaret (i python) 
def reverse(text):
    result = ""
    # Esta línea es un poco complicada, pero comienza
    # al final, va (incluido) a 0 (escribiendo
    # -1 como final) y cuenta hacia abajo de 1 cada vez
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

Eventualmente, puedes usar un algoritmo que agregue al principio en su lugar:

def reverse(text):
   result = ""
   for i in range(0, len(text)):
       # agrega al principio en su lugar
       result = text[i] + result
   return result

Medium Tarea 6 - Algoritmo de Palíndromo

Crea un algoritmo que verifique si una palabra dada es un palíndromo. Ejemplos de palíndromos son abba, racecar, regninger.

Tips til framgangsmåte
  1. Crea una función que reciba el texto a verificar.
  2. Usa un bucle for para verificar si las letras a cada lado del texto son iguales.
  3. Devuelve False si una letra no coincide, si todas coinciden (el bucle for termina), devuelve True.

Ekstra:
¿Ves cómo puedes hacer que el algoritmo sea el doble de rápido?

Hint

Du trenger bare å sjekke halvparten!

Respuesta (en python) 
def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True
Algoritmo más rápido

def palindrome(text):
for i in range(0, int(len(text) / 2)):
if text[i] != text[len(text) - i - 1]:
return False
return True

Medium Tarea 7 - Comprobar si una lista está ordenada

Crea un algoritmo que compruebe si una lista está ordenada. La forma más fácil de comprobar esto es empezar desde el principio y comparar si el siguiente elemento es “mayor”. Si un elemento no es “mayor”, la lista no está ordenada.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], da como respuesta True.
  • [6, 17, 227, 1, 23, 42, 12], da como respuesta False
  • [2, -2, 2, -2, -2, 2] da como respuesta False.
  • [2, 2, 3, 4, 4, 6], da como respuesta True.
  • [12, 23, 34, 45, 56, 67], da como respuesta True.

Tips til framgangsmåte
  1. Crea una función que reciba una lista
  2. Usa un bucle for para recorrer toda la lista (usa range para la longitud de la lista, menos 1 len(list) - 1)
  3. Compara el elemento \(n\) con \(n + 1\), es decir, el elemento actual con el siguiente elemento.
  4. Si \(n\) es menor que \(n + 1\), ve a la siguiente comparación.
  5. Si no es menor, sino mayor, la lista no está ordenada. Devuelve False aquí.
  6. Si llegas al final, la lista está ordenada, devuelve True.

Svaret (i Python) 
def is_sorted(the_list):
    for i in range(len(the_list) - 1):
        if the_list[i] > the_list[i + 1]:
            return False
    return True

Medium Tarea 8 - Barajar

Crea un algoritmo que baraje una lista de elementos. Hay muchas maneras de hacerlo, pero una buena manera es lo que se conoce como el algoritmo Fisher-Yates shuffle. Puedes leer más sobre esto aquí Wikipedia.

Test Data
  • ["a", "b", "c", "d", "e"] → puede convertirse, por ejemplo, en ["c", "e", "a", "d", "b"]
  • [1, 2, 3, 4, 5, 6] → puede convertirse, por ejemplo, en [4, 1, 6, 3, 2, 5]
  • ["apple", "banana", "orange"] → puede convertirse, por ejemplo, en ["orange", "apple", "banana"]
  • ["x"] → sigue siendo ["x"]
  • [] → sigue siendo []

Así funciona:

Algoritmen
  1. Crea una función que reciba la lista de números
  2. Crea una nueva lista vacía que contendrá el resultado mezclado.
  3. Usa un random para elegir un índice aleatorio en la lista.
  4. Agrega este elemento a la lista vacía y elimínalo de la antigua
  5. Devuelve la nueva lista desde la función

Svaret (i Python) 
import random

def shuffle(the_list):
    shuffled = []

    while len(the_list) > 0:
        i = random.randrange(0, len(the_list))
        shuffled.append(the_list[i])
        the_list.pop(i)

    return shuffled

Medium Tarea 9 - Bogo-sort

En esta tarea, debes crear un algoritmo de ordenación (prácticamente) horrible, pero extremadamente simple. Es extremadamente malo cuando se trata de listas grandes (le tomará eternidades con más de 12-13 elementos). En el Nivel 2, crearemos un mejor algoritmo de ordenación, bubble-sort.

Test Data
  • [3, 1, 2] → [1, 2, 3]
  • [5, 4, 3, 2, 1] → [1, 2, 3, 4, 5]
  • [10, 7, 8, 2] → [2, 7, 8, 10]
  • [1, 1, 1] → [1, 1, 1]
  • [9, 3, 6, 3, 9] → [3, 3, 6, 9, 9]
  • [0, -1, 4, -2] → [-2, -1, 0, 4]

El algoritmo funciona de la siguiente manera:

Algoritmen
  1. Crea una función que reciba la lista de números no ordenados.
  2. Mezcla la lista aleatoriamente (usa shuffle del ejercicio 8).
  3. Comprueba si la lista está ordenada (usa la comprobación que creaste en el ejercicio 7).
  4. Si la lista no está ordenada, repite los pasos 2 y 3.
  5. Repite hasta que la lista esté ordenada, luego devuelve.

Explicado simplemente: bogo-sort mezcla toda la lista y espera que esté ordenada.

Gru bogo sort meme
Aprende sobre la notación Big O en el Nivel 2.

Pista: Utiliza shuffle del ejercicio 8 para crear una lista desordenada para tu algoritmo.

Svaret (i Python) 
def bogo_sort(the_list):
    while not is_sorted(the_list):
        the_list = shuffle(the_list)
    return the_list

Hard Tarea 10a - Buscar texto - “substring” (¡Difícil!)

Crea un algoritmo que pueda encontrar una palabra clave en un texto. Es decir, si tienes una oración como hello there devolverás True con la palabra clave hello, False con una palabra clave como hahah. Este algoritmo debe funcionar independientemente de la entrada y la salida.

Utiliza los datos de texto a continuación para comprobar si tu algoritmo funciona.

Test-data for algoritme:
  • hello there everyone con there = True
  • hello there everyone con ever = True
  • hello there everyone con then = False
  • qwecvyufavsjekkftyergwcery con sjekk = True

Tips til framgangsmåte
  1. Crea una función que reciba dos strings, datos y palabra clave.
  2. Usa un for-loop con range para recorrer el texto.
  3. Aquí es importante pensar en hasta dónde debe llegar el loop.
  4. Crea una variable temporal que indique si la palabra clave se ha encontrado, configúrala en True por defecto.
  5. Usa otro for-loop con range para comparar dónde estás en el texto con la palabra clave.
  6. Si algo en la palabra clave no coincide con donde estás comprobando ahora, establece la variable temporal en True y break del loop interno.
  7. Si llegas al final del texto sin encontrar nada, devuelve False.

Svaret (i Python) 
def search(data, word): 
    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Easy Tarea 10b

Añade también una comprobación adicional que se asegure de que la palabra clave no sea más larga que la frase.

Tips til framgangsmåte
  • Agrega esta comprobación antes del bucle for.

Svaret (i python) 
def search(data, word): 
    if len(word) > len(data):
        return False

    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Hard Tarea 11 - Inversión de palabras en una oración (Difícil)

Recuerda la Tarea 5 sobre la inversión de una oración. Modifica (o comienza de nuevo) para crear un algoritmo que invierta cada palabra individual en una oración y luego las vuelva a unir.

Test-data for algoritme:
  • hello there everyone se convierte en olleh ereht enoyreve
  • This is the way it goes! se convierte en sihT si eht yaw ti !seog
  • does this racecar go? of course! se convierte en seod siht racecar ?og fo !esruoc

Tips til framgangsmåte
  1. Crea una función que reciba una string.
  2. ❗Divide el texto usando .split(" ").
  3. Crea una variable temporal para almacenar el valor final.
  4. Usa un bucle for para recorrer cada palabra.
  5. Usa el mismo método de inversión que en la Tarea 5
  6. Usa el resultado y añádelo a la variable que creaste en el paso 2.
  7. Devuelve el valor final

Svaret (i Python) 
def reverse_words(words):
    sentence = words.split(" ")
    output = ""

    for word in sentence:
        reversed_word = ""
        for i in range(0, len(word)):
            reversed_word = word[i] + reversed_word
        output += reversed_word + " "

    return output

➕Extra:

Cracked Tarea E1 - Eliminar duplicados de una lista

Supongamos que tienes una lista que contiene números o texto, pero queremos eliminar los duplicados. Crea un algoritmo que elimine todos los duplicados de una lista y contenga solo el primero de cada elemento único que exista en la lista.

Tips til framgangsmåte
  1. Comienza con una función que reciba una lista
  2. Aquí utilizaremos bucles while en lugar de for. Esto lo hace más fácil en Python, en otros lenguajes for con variables de conteo funciona bien.
  3. Crea una variable de conteo idx (para índice, o i)
  4. Utiliza un bucle while que vaya hasta la longitud de la lista
  5. Compararemos el elemento en idx con todos los demás elementos
  6. Crea una variable de conteo para jdx (o j) que comience en idx + 1
  7. Compara el elemento en idx con el elemento en jdx, si son iguales, elimina jdx usando pop(jdx).
  8. ¡RECUERDA! Si eliminas el elemento, la lista se hace más pequeña, por lo tanto, debemos retroceder un paso en jdx -= 1.
  9. Incrementa jdx en 1 y prueba el siguiente elemento
  10. Después del bucle while interno, incrementa idx en 1 y el bucle while externo continuará
  11. Finalmente, devuelve la lista con los duplicados eliminados

Test Data
  • [1, 2, 2, 3, 1, 4, 3] → se convierte en [1, 2, 3, 4]
  • ["a", "b", "a", "c", "b", "d"] → se convierte en ["a", "b", "c", "d"]
  • [5, 5, 5, 5] → se convierte en [5]
  • ["x", "y", "z", "x", "y", "x"] → se convierte en ["x", "y", "z"]
  • [10, -1, 10, -1, 0, 0, 10] → se convierte en [10, -1, 0]
  • ["apple", "apple', "banana", "orange", "apple", "orange", "pear", "apple"]
    • Debe dar: ["apple", "banana", "orange", "pear"]

Svaret (i Python) 
def delete_duplicates(the_list):
    idx = 0

    while idx < len(the_list):
        jdx = idx + 1

        while jdx < len(the_list):
            if the_list[idx] == the_list[jdx]:
                the_list.pop(jdx)
                jdx -= 1
            jdx += 1
        idx += 1

    return the_list

Cracked Tarea E2 - Counting Sort

Counting sort es uno de los pocos algoritmos de ordenación que funciona en lo que llamamos tiempo \(O(n)\). Es decir, no tarda mucho más tiempo que el número de elementos en la lista. Lee más sobre la notación Big O en Level 2.

Depende un poco de lo grande que sea el rango de elementos. Si el más pequeño es 0 y el más grande es 100000, puede tardar un poco, por lo que se puede usar si el rango de valores es pequeño. Tampoco funciona para números negativos, pero es posible modificar el algoritmo para que funcione con números negativos.

El algoritmo funciona así:

  • Averigua cuál es el elemento más grande, guarda el valor de este elemento como \(k\).
  • Crea una lista que contenga \(k + 1\) elementos, count.
  • Recorre la lista no ordenada y usa el valor del número como índice. Es decir, si el elemento tiene el valor 47, ve a count[47] y auméntalo en 1.
  • Recorre la lista count y coloca el número de números que es el índice. Ejemplo: Si hay 3 en el índice 1, agrega tres números 1.

Testdata
Datos no ordenados Datos ordenados
[7, 3, 9, 1, 4, 3, 0, 6, 8, 6, 2, 1, 9, 0, 5, 4] [0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9]
[12, 13, 15, 0, 8, 15, 8, 5, 16, 8, 0, 20, 4, 9, 17, 16, 1, 3, 6, 15, 5, 2, 3, 1, 19, 13, 17, 5, 3, 10] [0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 8, 8, 8, 9, 10, 12, 13, 13, 15, 15, 15, 16, 16, 17, 17, 19, 20]

Tips til framgangsmåte
  1. Comienza creando una función con una lista como entrada
  2. Crea una lista output vacía
  3. Usa un bucle for para recorrer toda la lista
  4. Realiza un seguimiento del valor máximo en una variable antes del bucle for
  5. Actualiza el valor máximo si encuentras algo más grande
  6. Crea una lista que contenga este número de ceros + 1. Ejemplo: el valor más grande es 47, entonces crea una lista con 48 ceros. Puedes hacerlo con [0] * (max + 1), o un bucle for. Llama a esta lista count.
  7. Recorre la lista una vez más con un bucle for
  8. Usa el valor del elemento como índice y aumenta en 1. count[value] += 1
  9. Usa un bucle for para recorrer la lista count.
  10. Usa el valor que está en cada índice para agregar ese número de números
  11. Devuelve la lista ordenada

Svaret (i Python) 
def counting_sort(input_list):
    output = []

    max_val = input_list[0]

    for n in input_list:
        if n > max_val:
            max_val = n

    # esto creará un montón de ceros
    count = [0] * (max_val + 1)

    for n in input_list:
        count[n] += 1

    for i in range(len(count)):
        # usa _ para ignorar un valor
        for _ in range(count[i]):
            output.append(i)

    return output