Criar algoritmos simples

Este é um texto traduzido automaticamente que pode conter erros!

Quote

“Algoritmo”, uma palavra usada por programadores quando eles não querem explicar o que fizeram.

Algoritme?

O que é um algoritmo?

Um algoritmo é uma função lógica que executa uma determinada operação. Portanto, você pode tecnicamente chamar uma função que soma dois números de “algoritmo”, mas, na maioria das vezes, um algoritmo é algo um pouco mais complicado do que isso. Frequentemente, algoritmos são usados para acelerar operações que levam muito tempo.

Preciso usar Python nessas tarefas?

Não! Você pode usar qualquer linguagem de programação que preferir nessas tarefas.

Bibliotecas integradas?

A ideia nestes exercícios é evitar usar bibliotecas integradas ou funções especiais do Python. Por exemplo, existe uma “one-liner” simples para reverter texto: text[::-1], mas aqui queremos que você tente resolver essas tarefas sem usar isso. Pode ser que mencionemos uma função integrada se a solução for um pouco difícil de encontrar. Isso será marcado com ❗.

Na prática, deve ser totalmente possível resolver todas essas tarefas com if, for, while e operações de lista comuns.

Como “desenhar” um algoritmo?

Na maioria das vezes, os algoritmos são projetados iterativamente. O que isso significa?

1. ✅ Quebre primeiro o problema em partes menores.

Pense primeiramente no mais importante que você precisa para que o algoritmo funcione
- Ele deve retornar um valor? Um boolean? Uma lista?
- Preciso de alguma função auxiliar?

2. ❓ Existem alguns “casos extremos”?

O que acontece se você inserir uma lista ou texto vazio?

3. ✅ Comece apenas tentando criar uma solução

4. ✅ Verifique se o algoritmo parece bom em tempo de execução

Tente entradas maiores, leva muito tempo?

5. ❓ Pense na sua solução, precisa de todos os passos que usou?

Todas as verificações if são necessárias?
Se você tem mais de um for-loop, existem maneiras claras de fazer isso em um for-loop?
- Isso é diferente se você tem loops aninhados ou loops um após o outro. Um após o outro é frequentemente possível evitar.

6. ✅ Considere cenários extremos com inputs:

Exemplo com números: números grandes, números pequenos, números negativos
Exemplo de texto: muito texto, muitas palavras pequenas, espaços extras, letras maiúsculas e minúsculas.

7. ❓ É útil usar pseudo-código para entender melhor a lógica?

Tarefa 1 - Descobrir se uma lista contém um determinado número

Crie um algoritmo (função) que descubra se uma lista contém um determinado número. Ele deve retornar True ou False com base em se o número existe na lista ou não.

Aqui está uma lista com dados de teste:

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`

Dicas de procedimento

Insira uma lista e um valor de lista em uma função. Nesta tarefa, serão números, mas podem ser texto.
Use um loop for para percorrer a lista
Se o número for igual ao número de verificação, retorne True
Se o loop for terminar e você não o encontrar, retorne False

Svaret (i python)

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

Tarefa 2 - Sumarização

Crie um algoritmo que some uma lista de números.

Test-data for algoritmo:

[1, 2, 3, 4, 5, 6], dá a resposta 21.
[5, 1, 23, 68, 22, 13, 4], dá a resposta 136
[3, 3, -3, -3, 3] dá a resposta 3. Eventualmente, você pode ignorar números negativos e dar a resposta 9.

Tips til framgangsmåte

Insira uma lista em uma função
Guarde uma soma temporária como 0.
Use um loop for para percorrer a lista.
return a soma da lista.

Svaret (i python)

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

Tarefa 3a - Valor Máximo em uma Lista

Crie um algoritmo que encontre o maior valor em uma lista.

Test-data for algoritmo:

[1, 2, 3, 4, 5, 6], dá a resposta 6.
[6, 17, 227, 1, 23, 42, 12], dá a resposta 227
[2, -2, 2, -2, -2, 2] dá a resposta 2.

Tips til framgangsmåte

Insira uma lista em uma função
Defina um valor temporário para o primeiro elemento da lista.
Use um loop for para percorrer a lista e comparar com o valor que você definiu em 2.
Se o valor for maior, defina o valor temporário para o novo valor.
return este valor temporário.

Svaret (i python)

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

    return largest

Tarefa 3b - Se a lista estiver vazia?

Adicione uma verificação que teste se a lista contém elementos. Se não, retorne 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

Tarefa 4 - Contar o número de um determinado elemento em uma lista

Crie um algoritmo que conte o número de um determinado elemento em uma lista.

Test-data for algoritme:

["apple", "banana", "orange", "apple", "apple", "banana"] com apple dá a resposta 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] com 4 dá a resposta 8.
["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] com dog dá a resposta 3.
[7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] com 7 dá a resposta 5.
["red", "blue", "green", "red", "yellow", "red"] com red dá a resposta 3.
[10, -2, -2, -2, 5, 10, 10, -2] com -2 dá a resposta 4.

Tips til framgangsmåte

Insira uma lista e um valor de verificação em uma função
Comece com um valor temporário de contagem definido como 0.
Percorra a lista com um loop for.
Se o elemento for igual à verificação, aumente o valor da contagem em 1.
Retorne o valor da contagem.

Svaret (i python)

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

    return count

Tarefa 5 - Reverter uma `string`, texto

Crie um algoritmo que reverta uma string dada.

Test-data for algoritme:

Hello there! torna-se !ereht olleH.
heisann alle sammen torna-se nemmas ella nnasieh
Python torna-se nohtyP
racecar torna-se racecar
12345abc torna-se cba54321
god morgen torna-se negrom dog

Tips til framgangsmåte

Receba uma string em uma função
Crie um valor temporário para armazenar uma string vazia.
Percorra o texto com um loop for com range. Aqui você pode percorrer a lista de trás para frente, mas é possível resolver isso percorrendo a lista para frente.
Adicione cada caractere ao valor temporário em ordem.
Retorne o texto temporário.

Svaret (i python)

def reverse(text):
    result = ""
    # Esta linha é um pouco complicada, mas ela começa
    # no final, vai (incluindo) até 0 (escrevendo
    # -1 como fim) e conta regressivamente de 1 cada vez
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

Eventualmente, você pode usar um algoritmo que adiciona no início em vez disso:

def reverse(text):
   result = ""
   for i in range(0, len(text)):
       # adicione no início em vez disso
       result = text[i] + result
   return result

Tarefa 6 - Algoritmo de Palíndromo

Crie um algoritmo que verifique se uma determinada palavra é um palíndromo. Exemplos de palíndromos são abba, racecar, regninger.

Dicas de procedimento

Crie uma função que receba o texto a ser verificado.
Use um for-loop para verificar se as letras de cada lado do texto são iguais.
Retorne False se uma letra não corresponder, se todas corresponderem (for-loop terminar), retorne True.

Extra:
Vê como podes tornar o algoritmo duas vezes mais rápido?

Dica

Só precisas verificar metade!

Resposta (em python)

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

Algoritmo mais 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

Tarefa 7 - Verificar se uma lista está ordenada

Crie um algoritmo que verifique se uma lista está ordenada. A maneira mais fácil de verificar isso é começar do início e comparar se o próximo elemento é “maior”. Se um elemento não for “maior”, então a lista não está ordenada.

Test-data for algoritme:

[1, 2, 3, 4, 5, 6], dá a resposta True.
[6, 17, 227, 1, 23, 42, 12], dá a resposta False
[2, -2, 2, -2, -2, 2] dá a resposta False.
[2, 2, 3, 4, 4, 6], dá a resposta True.
[12, 23, 34, 45, 56, 67], dá a resposta True.

Tips til framgangsmåte

Crie uma função que receba uma lista
Use um loop for para percorrer toda a lista (use range para o comprimento da lista, menos 1 len(list) - 1)
Compare o elemento \(n\) com \(n + 1\), ou seja, o elemento atual com o próximo elemento.
Se \(n\) for menor que \(n + 1\), vá para a próxima comparação.
Se não for menor, mas maior, a lista não está ordenada. Retorne False aqui.
Se você chegar ao final, a lista está ordenada, retorne 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

Tarefa 8 - Embaralhar

Crie um algoritmo que embaralhe uma lista de itens. Existem muitas maneiras de fazer isso, mas uma boa maneira é o que é chamado de algoritmo Fisher-Yates shuffle. Você pode ler mais sobre isso aqui Wikipedia.

Test Data

["a", "b", "c", "d", "e"] → pode se tornar, por exemplo, ["c", "e", "a", "d", "b"]
[1, 2, 3, 4, 5, 6] → pode se tornar, por exemplo, [4, 1, 6, 3, 2, 5]
["apple", "banana", "orange"] → pode se tornar, por exemplo, ["orange", "apple", "banana"]
["x"] → permanece ["x"]
[] → permanece []

Funciona assim:

Algoritmen

Crie uma função que receba a lista de números
Crie uma nova lista vazia para armazenar o resultado misturado.
Use um random para escolher um índice aleatório na lista.
Adicione este elemento à lista vazia e exclua-o da lista antiga
Retorne a nova lista da função

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

Tarefa 9 - Bogo-sort

Nesta tarefa, você irá criar um algoritmo de ordenação (praticamente) terrível, mas extremamente simples. Ele é extremamente ruim quando se trata de listas grandes (demorará eternidades com mais de 12-13 itens). No Nível 2, criaremos um algoritmo de ordenação melhor, 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]

O algoritmo funciona da seguinte forma:

Algoritmo

Crie uma função que receba a lista de números não ordenados
Misture a lista aleatoriamente (use o shuffle da tarefa 8).
Verifique se a lista está ordenada (use a verificação que você criou na tarefa 7).
Se a lista não estiver ordenada, repita os passos 2 e 3.
Repita até que a lista esteja ordenada, então retorne

Explicado de forma simples: bogo-sort mistura toda a lista e espera que ela esteja ordenada.

Leia sobre a notação Big O no Nível 2.

Dica: Sinta-se à vontade para usar shuffle da tarefa 8 para criar uma lista não ordenada para o seu algoritmo.

Svaret (i Python)

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

Tarefa 10a - Procurar texto - “substring” (Difícil!)

Crie um algoritmo que possa encontrar uma palavra-chave em um texto. Ou seja, se você tem uma frase como hello there, você retornará True com a palavra-chave hello, False com uma palavra-chave como hahah. Este algoritmo deve funcionar independentemente da entrada e saída.

Use os dados de texto abaixo para verificar se o seu algoritmo funciona.

Test-data for algoritme:

hello there everyone com there = True
hello there everyone com ever = True
hello there everyone com then = False
qwecvyufavsjekkftyergwcery com sjekk = True

Dicas de procedimento

Crie uma função que receba duas strings, dados e palavra-chave.
Use um for-loop com range para percorrer o texto.
Aqui é importante pensar em até onde o loop deve ir.
Crie uma variável temporária que diga se a palavra-chave foi encontrada, defina-a como True por padrão.
Use outro for-loop com range para comparar onde você está no texto com a palavra-chave.
Se algo na palavra-chave não corresponder a onde você está verificando agora, defina a variável temporária como True e break do loop interno.
Se você chegar ao final do texto sem encontrar nada, retorne False.

Resposta (em 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

Tarefa 10b

Adicione também uma verificação extra para garantir que a palavra-chave não seja mais longa que a frase.

Dicas de procedimento

Adicione esta verificação antes do loop 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

Tarefa 11 - Reversão de palavras em frase (Difícil)

Lembre-se da Tarefa 5 sobre reverter uma frase. Modifique (ou comece de novo) para criar um algoritmo que reverta cada palavra individualmente em uma frase, e então as junte novamente.

Test-data for algoritme:

hello there everyone se torna olleh ereht enoyreve
This is the way it goes! se torna sihT si eht yaw ti !seog
does this racecar go? of course! se torna seod siht racecar ?og fo !esruoc

Dicas de procedimento

Crie uma função que receba uma string.
❗Divida o texto usando .split(" ").
Crie uma variável temporária para armazenar o valor final.
Use um loop for para percorrer cada palavra.
Use o mesmo método de inversão da Tarefa 5
Use o resultado e adicione à variável que você criou na etapa 2.
Retorne o 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:

Tarefa E1 - Excluir duplicatas de uma lista

Suponha que você tenha uma lista que contenha números ou texto, mas queira excluir as duplicatas. Crie um algoritmo que exclua todas as duplicatas de uma lista e contenha apenas o primeiro de cada elemento único que exista na lista.

Tips til framgangsmåte

Comece com uma função que recebe uma lista
Aqui usaremos loops while em vez de for. Isso torna mais fácil em Python, em outras linguagens for com variáveis de contagem funciona bem.
Crie uma variável de contagem idx (para índice, ou i)
Use um loop while que deve ir até o comprimento da lista
Vamos comparar o elemento em idx com todos os outros elementos
Crie uma variável de contagem para jdx (ou j) que começa em idx + 1
Compare o elemento em idx com o elemento em jdx, se eles forem iguais, exclua jdx usando pop(jdx).
LEMBRE-SE! Se você excluir o elemento, a lista se tornará menor, portanto, devemos voltar um passo em jdx -= 1.
Aumente jdx em 1 e teste o próximo elemento
Após o loop while interno, aumente idx em 1 e o loop while externo continuará
Finalmente, retorne a lista com duplicatas excluídas

Test Data

[1, 2, 2, 3, 1, 4, 3] → torna-se [1, 2, 3, 4]
["a", "b", "a", "c", "b", "d"] → torna-se ["a", "b", "c", "d"]
[5, 5, 5, 5] → torna-se [5]
["x", "y", "z", "x", "y", "x"] → torna-se ["x", "y", "z"]
[10, -1, 10, -1, 0, 0, 10] → torna-se [10, -1, 0]
["apple", "apple', "banana", "orange", "apple", "orange", "pear", "apple"]
- Deve retornar: ["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

Tarefa E2 - Counting Sort

Counting sort é um dos poucos algoritmos de ordenação que funciona em \(O(n)\) tempo. Ou seja, não demora muito mais tempo do que o número de elementos na lista. Leia mais sobre a notação Big O no Nível 2.

Depende um pouco de quão grande a amplitude dos elementos é. Se o menor for 0 e o maior for 100000, pode demorar um pouco, então isso pode ser usado se a amplitude dos valores for pequena. Também não funciona para números negativos, mas é possível modificar o algoritmo para funcionar com números negativos.

O algoritmo funciona assim:

Descubra qual é o maior elemento, salve o valor desse elemento como \(k\).
Crie uma lista que contenha \(k + 1\) elementos, count.
Percorra a lista não ordenada e use o valor do número como índice. Ou seja, se o elemento tiver o valor 47, vá para count[47] e aumente-o em 1.
Percorra a lista count e coloque o número de números que o índice é. Exemplo: Se houver 3 no índice 1, adicione três números 1.

Testdata

Dados Não Ordenados	Dados 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

Comece criando uma função com uma lista como entrada
Crie uma lista output vazia
Use um for-loop para percorrer toda a lista
Mantenha o controle do valor máximo em uma variável antes do for-loop
Atualize o valor máximo se você encontrar algo maior
Crie uma lista que contenha este número de zeros + 1. Exemplo: o maior valor é 47, então você cria uma lista com 48 zeros. Você pode fazer isso com [0] * (maks + 1), ou um for loop. Chame-a de count.
Percorra a lista mais uma vez com um for-loop
Use o valor do elemento como índice e incremente em 1. count[value] += 1
Use um for-loop para percorrer a lista count.
Use o valor que está em cada índice para adicionar esse número de números
Retorne a 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

    # isso criará uma pilha de zeros
    count = [0] * (max_val + 1)

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

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

    return output

Criar algoritmos simples

Como “desenhar” um algoritmo?

1. ✅ Quebre primeiro o problema em partes menores.

2. ❓ Existem alguns “casos extremos”?

3. ✅ Comece apenas tentando criar uma solução

4. ✅ Verifique se o algoritmo parece bom em tempo de execução

5. ❓ Pense na sua solução, precisa de todos os passos que usou?

6. ✅ Considere cenários extremos com inputs:

7. ❓ É útil usar pseudo-código para entender melhor a lógica?

Tarefa 1 - Descobrir se uma lista contém um determinado número

Tarefa 2 - Sumarização

Tarefa 3a - Valor Máximo em uma Lista

Tarefa 3b - Se a lista estiver vazia?

Tarefa 4 - Contar o número de um determinado elemento em uma lista

Tarefa 5 - Reverter uma string, texto

Tarefa 6 - Algoritmo de Palíndromo

Tarefa 7 - Verificar se uma lista está ordenada

Tarefa 8 - Embaralhar

Tarefa 9 - Bogo-sort

Tarefa 10a - Procurar texto - “substring” (Difícil!)

Tarefa 10b

Tarefa 11 - Reversão de palavras em frase (Difícil)

➕Extra:

Tarefa E1 - Excluir duplicatas de uma lista

Tarefa E2 - Counting Sort

Tarefa 5 - Reverter uma `string`, texto