5 exercícios avançados de algoritmos matemáticos em Python

Publicado por Henrique Vedovato em 23/12/2024

Categorias

Desenvolvimento

Conteúdo

O que são algoritmos matemáticos em Python?
Vantagens de usar Python em algoritmos matemáticos
5 exercícios de Python de algoritmos matemáticos
Conclusão

O que são algoritmos matemáticos em Python?

Os algoritmos matemáticos em Python são sequências de instruções lógicas que resolvem problemas matemáticos de forma automatizada. Eles utilizam as operações e estruturas da linguagem para calcular, processar e analisar dados com base em conceitos matemáticos, como divisores, números primos, séries numéricas, e muito mais.

Python é uma linguagem amplamente utilizada no desenvolvimento desses algoritmos devido à sua legibilidade e suporte nativo para operações matemáticas. Com o uso de loops, funções e recursões, você pode implementar algoritmos matemáticos de maneira eficiente e com menos esforço.

Para se aprofundar na carreira como desenvolvedor Python, veja nosso artigo completo sobre suas aplicações em desenvolvimento web, análise de dados e muito mais, e as melhores dicas para dominar essa linguagem.

Vantagens de usar Python em algoritmos matemáticos

Simplicidade: A sintaxe limpa de Python permite uma implementação direta e acessível.
Flexibilidade: Python suporta tanto cálculos básicos quanto operações matemáticas complexas.
Comunidade: Uma vasta base de usuários e recursos para consulta.
Integração com bibliotecas: Além do código puro, Python oferece bibliotecas como NumPy e SciPy para cálculos avançados.

Com base nesses fatores, a implementação de algoritmos matemáticos em Python se tornou uma prática comum, tanto para aprendizado quanto para aplicações práticas.

5 exercícios de Python de algoritmos matemáticos

Vamos explorar agora cinco exercícios Python essenciais que demonstram como criar e aplicar algoritmos matemáticos. Cada exemplo inclui explicações detalhadas e exemplos práticos para ajudar você a entender o processo.

1. Cálculo de números primos (Crivo de Eratóstenes)

Este código implementa o Crivo de Eratóstenes, um algoritmo eficiente para encontrar todos os números primos até um número n. Ele funciona excluindo múltiplos de números primos, começando com 2, de forma iterativa.

def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5) + 1):
if primes[i]:
for j in range(i * i, n + 1, i):
primes[j] = False
return [i for i, prime in enumerate(primes) if prime]

print(sieve_of_eratosthenes(50)) # Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Função sieve_of_eratosthenes(n)

Parâmetros:

n: O número até o qual os primos devem ser encontrados.

Passos do algoritmo:

1. Inicialização do vetor primes:

Cria-se uma lista chamada primes de tamanho n + 1, onde todos os valores são inicialmente True (indicando que todos os números são presumidos como primos).
Os índices 0 e 1 são ajustados para False, pois 0 e 1 não são primos.

primes = [True] * (n + 1)

primes[0] = primes[1] = False

2. Iteração para marcar os múltiplos:

O loop começa em i = 2, já que 2 é o primeiro número primo.
Para cada número i, se ele for primo (ou seja, primes[i] for True), o algoritmo marca todos os seus múltiplos a partir de i * i como não primos (definindo primes[j] como False), já que todos esses múltiplos não são primos.
O valor int(n**0.5) + 1 é usado como limite para o loop, já que os múltiplos de números maiores que a raiz quadrada de n já terão sido marcados por números menores.

for i in range(2, int(n**0.5) + 1):

    if primes[i]:

        for j in range(i * i, n + 1, i):

            primes[j] = False

3. Criação da lista de primos:

Após o fim do loop, a lista primes contém True nos índices dos números primos e False nos índices dos números compostos.
A função retorna uma lista com os índices que têm valor True, que correspondem aos números primos.

return [i for i, prime in enumerate(primes) if prime]

Exemplo de execução:

Entrada: sieve_of_eratosthenes(50)

Inicializa a lista primes com True para todos os números de 0 a 50, exceto 0 e 1 que são False.
Marca os múltiplos de 2, 3, 5, 7 e outros números como False.
Retorna os índices que ainda são True: os números primos.

Saída: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Aplicabilidade:

Geração de números primos: É amplamente utilizado para gerar uma lista de números primos de forma eficiente, sendo útil em problemas de criptografia e segurança.

Algoritmos de criptografia: O Crivo de Eratóstenes é utilizado em várias técnicas de criptografia, onde a fatoração de números grandes em primos é um passo fundamental (exemplo: RSA).

Teoria dos números: Pode ser utilizado para estudos sobre números primos e suas propriedades, além de ser um dos algoritmos mais antigos e conhecidos.

Redução de complexidade: Ao invés de verificar a primalidade de cada número individualmente, o algoritmo marca múltiplos e elimina números compostos de forma mais eficiente.

Vantagens:

Eficiência: O Crivo de Eratóstenes é muito eficiente para encontrar todos os primos até um número n, com complexidade de tempo O(n log log n).
Simplicidade: O algoritmo é relativamente simples e pode ser facilmente implementado.

Desvantagens:

Espaço: O algoritmo requer uma lista de tamanho n + 1, o que pode consumir muita memória para valores muito grandes de n.
Limitação para números gigantes: Embora eficiente, o Crivo de Eratóstenes pode se tornar impraticável para números extremamente grandes, a menos que técnicas de otimização, como o Crivo de Atkin ou segmentação, sejam usadas.

2. Calculadora de MDC usando o algoritmo de Euclides

O código fornecido implementa o Algoritmo de Euclides, uma maneira eficiente de calcular o Máximo Divisor Comum (MDC) de dois números inteiros a e b. O MDC é o maior número que divide ambos os números sem deixar resto.

def gcd(a, b):
while b:
a, b = b, a % b
return a

print(gcd(48, 18)) # Output: 6

Função gcd(a, b)

Parâmetros:

a: O primeiro número inteiro.
b: O segundo número inteiro.

Passos do algoritmo (Algoritmo de Euclides):

Estrutura de repetição (while):

O algoritmo começa verificando se b é diferente de zero (while b:). Se b for zero, o valor de a será o MDC.
Enquanto b for diferente de zero, o valor de a e b é atualizado em cada iteração:
- a recebe o valor de b.
- b recebe o valor de a % b (o resto da divisão de a por b).

Troca de valores:

Em cada iteração do loop, a função vai trocando os valores de a e b, e calcula o novo valor de b como o resto da divisão de a por b.

Condição de parada:

Quando b se torna zero, o loop termina, e o valor de a é o MDC dos dois números. O algoritmo funciona porque, após várias iterações, o resto da divisão vai ficando cada vez menor até ser zero, momento em que a será o maior número divisor comum.

def gcd(a, b):

    while b:

        a, b = b, a % b

    return a

Retorno:

O valor de a será o MDC de a e b, retornado pela função.

Exemplo de execução:

Entrada: gcd(48, 18)

Primeira iteração:

a = 48, b = 18
Resto de 48 % 18 = 12
Troca: a = 18, b = 12

Segunda iteração:

a = 18, b = 12
Resto de 18 % 12 = 6
Troca: a = 12, b = 6

Terceira iteração:

a = 12, b = 6
Resto de 12 % 6 = 0
Troca: a = 6, b = 0

O loop termina porque b agora é zero, e o valor de a (que é 6) é retornado como o MDC de 48 e 18.

Saída: 6

Aplicabilidade:

Cálculo de divisores comuns: O MDC é amplamente utilizado em problemas de teoria dos números e álgebra. Ele pode ser usado para simplificar frações, calcular a forma canônica de expressões algébricas, e muito mais.

Criptografia: O MDC é fundamental em algoritmos de criptografia como RSA, onde é necessário calcular inversos modulares, o que envolve o uso do MDC para garantir que dois números sejam coprimos.

Algoritmos de fatoração: Pode ser usado como parte de algoritmos de fatoração, como na decomposição de números em seus fatores primos.

Redução de frações: O cálculo do MDC é usado para simplificar frações, dividindo o numerador e o denominador pelo seu MDC.

Vantagens:

Eficiência: O Algoritmo de Euclides é muito eficiente com uma complexidade de tempo O(log(min(a, b))), o que o torna adequado até para números grandes.
Simplicidade: O algoritmo é simples de entender e fácil de implementar, como mostrado no código.

3. Números de Fibonacci (iterativo e recursivo)

Descrição de Imagem: Uma mão aponta para um texto brilhante "PYTHON" em uma interface digital, cercado por ícones hexagonais que representam conceitos de programação como código, rede e lupa, destacando o poder dos algoritmos matemáticos em python contra um fundo azul.

Legenda: A sintaxe limpa de Python permite uma implementação direta e acessível. | Imagem: Freepik

O exercicio implementa duas abordagens para calcular o n-ésimo número da sequência de Fibonacci: uma iterativa e outra recursiva. A sequência de Fibonacci é definida por:

$F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2) para n≥2F(0) = 0, \, F(1) = 1, \, F(n) = F(n-1) + F(n-2) \, \text{para} \, n \geq 2$

Como funciona a função iterativa?

Inicializamos duas variáveis:

$a = 0$ o primeiro número da sequência.
$b=1$ o segundo número da sequência.

O loop for itera $n$ vezes.

A cada iteração, calculamos o próximo número da sequência de Fibonacci como a soma dos dois anteriores.
As variáveis são atualizadas usando a expressão: $a,b=b,a+b$ Onde $b$ (o próximo número) se torna o novo $a,$ e $a + b$ (a soma atual) se torna o novo $b$.

Após o loop, o valor de aaa é retornado como o $n$-ésimo número de Fibonacci.

Exemplo: $n=10$

Iterações do loop:

$(a,b)=(0,1)$
$(a,b)=(1,1)$
$(a,b)=(1,2)$
$(a,b)=(2,3)$
$(a,b)=(3,5)$
$(a,b)=(5,8)$
$(a,b)=(8,13)$
$(a,b)=(13,21)$
$(a,b)=(21,34)$
$(a,b)=(34,55)$

O valor retornado será $a=55$, que é o 10º número da sequência de Fibonacci.

Como funciona a função recursiva?

O caso base é definido:

Se $n≤1,$ a função retorna $n$, pois os dois primeiros números da sequência são $F(0)=0$ e $F(1)=1.$

Para $n>1$ a função chama a si mesma recursivamente:

Calcula o $n$-ésimo número como a soma dos dois anteriores: $F(n)=F(n−1)+F(n−2)$

Esse processo continua até atingir o caso base ($n=0$ ou $n=1$) para cada ramificação da recursão.

Exemplo: $n=10$:

A função será chamada várias vezes, dividindo-se em uma "árvore" de chamadas:

$F(10)=F(9)+F(8)$
$F(9)=F(8)+F(7)$
$F(8)=F(7)+F(6)$
```
 ...
```

Esse processo continua até que cada subproblema seja reduzido ao caso base.

Problema de desempenho

A abordagem recursiva recalcula os mesmos valores várias vezes, tornando-a ineficiente para valores altos de $n$. O tempo de execução é exponencial $(O(2^n))$.

# Iterativo
def fibonacci_iterative(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a

# Recursivo
def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

print(fibonacci_iterative(10)) # Output: 55
print(fibonacci_recursive(10)) # Output: 55

Aplicabilidade

Modelagem de Crescimento: Usada em biologia e economia.

Otimização: Base para problemas como o da mochila.

Análise de Algoritmos: Exemplifica conceitos de recursão.

4. Cálculo de fatoriais com recursão

O exercício implementa a função para calcular o fatorial de um número usando uma abordagem recursiva. O fatorial de um número 𝑛 é definido como o produto de todos os inteiros positivos de 1 até 𝑛, e é representado como 𝑛!. Entenda como funciona:

Caso base: A função verifica se $n==0$. Nesse caso, retorna 1, pois $0!=10$ (definido matematicamente).

Passo recursivo: Se $n>0$, a função multiplica nnn pelo fatorial de $n−1$ Esse processo continua chamando a função repetidamente com valores menores de $n$, até atingir o caso base.

Exemplo com n=5n = 5n=5:

$factorial(5)=5⋅factorial(4)$
$factorial(4)=4⋅factorial(3)$
$factorial(3)=3⋅factorial(2)$
$factorial(2)=2⋅factorial(1)$
$factorial(1)=1⋅factorial(0)$
$factorial(0)=1 (caso base)$

Retornando os valores:

$factorial(1)=1$
$factorial(2)=2⋅1=2$
$factorial(3)=3⋅2=6$
$factorial(4)=4⋅6=24$
$factorial(5)=5⋅24=120$

def factorial(n):
return 1 if n == 0 else n * factorial(n - 1)

print(factorial(5)) # Output: 120

Passos do código

Condição de base (Caso Simples):

A função verifica se n=0. Nesse caso, retorna 1, encerrando a recursão. Essa é a condição de parada.

n=0n = 0

11

return 1 if n == 0

Recursão:

Para n>0, a função retorna n×factorial(n−1), chamando a si mesma com o valor reduzido de n.

n>0n > 0

n×factorial(n−1)n \times \text{factorial}(n-1)

nn
Essa chamada recursiva continua até que n alcance 0.

nn

else n * factorial(n - 1)

Aplicabilidade

Matemática e estatística: Cálculos combinatórios (ex.: permutações e combinações) e modelos probabilísticos.

Análise de algoritmos: O fatorial é utilizado em fórmulas para determinar a complexidade de certos algoritmos.

Aprendizado de programação: O cálculo do fatorial é um exemplo clássico para ensinar e entender a recursão.

5 - Soma de números em uma matriz triangular superior

O código fornecido realiza a soma dos elementos da parte superior de uma matriz triangular superior, ou seja, a soma de todos os elementos da matriz que estão na diagonal principal ou acima dela (incluindo a diagonal). Vamos entender o funcionamento detalhado do código.

def sum_upper_triangle(matrix):
n = len(matrix)
total = 0
for i in range(n):
for j in range(i, n):
total += matrix[i][j]
return total

matrix = [
[1, 2, 3],
[0, 4, 5],
[0, 0, 6]
]
print(sum_upper_triangle(matrix)) # Output: 21

Função sum_upper_triangle(matrix)

Parâmetros:

matrix: Uma matriz quadrada (ou seja, número de linhas igual ao número de colunas), representada como uma lista de listas em Python.

Passos do código

Inicialização:

A variável n recebe o tamanho da matriz (número de linhas ou colunas, já que é uma matriz quadrada).
A variável total é inicializada com zero e será usada para armazenar a soma dos elementos da parte superior da matriz.

Laço cuplo:

O primeiro laço (for i in range(n)) percorre as linhas da matriz.
O segundo laço (for j in range(i, n)) percorre as colunas, mas com uma peculiaridade: começa da coluna i e vai até a última coluna n-1. Isso garante que o laço apenas percorra os elementos na diagonal principal e acima dela.

Essa configuração de índices (i para as linhas e j para as colunas) assegura que apenas os elementos da parte superior (diagonal e acima) da matriz sejam somados.

Soma dos Elementos:

Dentro do segundo laço, o valor de matrix[i][j] é somado à variável total para cada elemento na parte superior da matriz.

Retorno:

Após os dois laços, o valor de total será a soma de todos os elementos da parte superior da matriz, incluindo a diagonal.

Exemplo de execução:

Entrada:

A matriz fornecida é:

[

    [1, 2, 3],

    [0, 4, 5],

    [0, 0, 6]

]

O código irá somar os elementos acima ou na diagonal principal.

O laço interno percorre as colunas a partir da posição atual da linha, garantindo que a soma seja feita apenas na parte superior da matriz:

Para i = 0 (primeira linha):

j = 0: matrix[0][0] = 1
j = 1: matrix[0][1] = 2
j = 2: matrix[0][2] = 3
Soma: 1 + 2 + 3 = 6

Para i = 1 (segunda linha):

j = 1: matrix[1][1] = 4
j = 2: matrix[1][2] = 5
Soma: 4 + 5 = 9

Para i = 2 (terceira linha):

j = 2: matrix[2][2] = 6
Soma: 6

Total: 6 + 9 + 6 = 21

Saída: 21

Conclusão

Os exercícios Python apresentados neste artigo são fundamentais para consolidar habilidades em programação e resolver problemas matemáticos de forma eficiente. Cada exemplo, como o Crivo de Eratóstenes e o cálculo de fatoriais, ilustra não apenas a implementação de algoritmos, mas também suas aplicações práticas em áreas como criptografia, ciência de dados e análise combinatória.

Estamos iniciando uma série especial de artigos com exercícios avançados em Python, abrangendo temas variados e desafiadores. Acompanhe os próximos conteúdos:

30 exercícios de Python para iniciantes
Manipulação avançada de strings [Em breve]
Estruturas de dados personalizadas [Em breve]
Algoritmos de ordenação [Em breve]
Problemas com grafos [Em breve]

Se surgir alguma dúvida ou você quiser trocar ideias com outros desenvolvedores, participe do nosso fórum da Casa do Desenvolvedor. Lá você pode fazer perguntas, compartilhar experiências e aprender com a comunidade. Clique aqui para acessar o fórum e dar continuidade ao seu aprendizado.

Pratique e explore as possibilidades que esses exercícios oferecem – seu próximo grande projeto pode começar agora!

Troque conhecimento sobre Python no fórum!