Primeira Lista

Acesso rápido

Ex. 1 Ex. 2 Ex. 3 Ex. 4 Ex. 5 Ex. 6 Ex. 7 Ex. 8 Ex. 9 Ex. 10 Ex. 11 Ex. 12 Ex. 13 Ex. 14 Ex. 15 Ex. 16 Ex. 17 Ex. 18 Ex. 19 Ex. 20 Ex. 21 Ex. 22 Ex. 23 Ex. 24 Ex. 25 Ex. 26 Ex. 27 Ex. 28 Ex. 29 Ex. 30 Ex. 31

Instruções

  • os exercícios marcados em verde foram resolvidos em sala de aula. Uma possível solução é fornecida aqui, junto ao exercício.- os exercícios marcados em amarelo devem ser entregues no dia 08/10/2020.
  • os exercícios marcados em vermelho devem ser entregues no dia 05/11/2020.
  • as porcentagens no começo de cada exercício são uma maneira de indicar o seu grau de dificuldade. Mas não se apegue muito a esses valores: talvez você ache fáceis alguns que eu julgo como difíceis — e vice versa!

  • Legenda: : decisão; : repetição; : função; : dicionários; : listas; : strings; : recursão.

Exercício 1: Anos bissextos

  • dificuldade: 10%
  • utiliza:  

A maioria dos anos tem 365 dias. No entanto, o tempo necessário para a Terra orbitar o Sol é na verdade um pouco maior que isso. Para corrigir essa diferença, um dia extra, 29 de fevereiro, está incluído em alguns anos, ditos bissextos. As regras para determinar se um ano é ou não um ano bissexto são as seguintes:

1. qualquer ano que seja divisível por 400 é um ano bissexto;
2. dos anos restantes, qualquer ano que seja divisível por 100 não é um ano bissexto;
3. dos anos restantes, qualquer ano que seja divisível por 4 é um ano bissexto;
4. todos os outros anos não são anos bissextos.

Escreva um programa que leia um ano do usuário e exiba uma mensagem dizendo se ele é ou não um ano bissexto. Você consegue pensar num algoritmo mais eficiente, que faça em média menos testes?

Dicas para responder à pergunta final:

  • Veja que o algoritmo proposto no enunciado testa inicialmente se um número é múltiplo de 400. Apenas um em 400 números é múltiplo de 400. Portanto, 399 de 400 (99.75%) não passam no primeiro teste e vão para o segundo.
  • Similarmente, um a cada 100 números é múltiplo de 100, então 99 de 100 (99%) não passam pelo segundo teste e vão para o terceiro.
  • Assim, em média, o algoritmo proposto faz muito mais comparações do que o necessário. Repensando os testes a serem feitos, é possível reduzi-los em número. Por exemplo, se você começar com o teste ano % 4 != 0, 3 de 4 casos resultam em True, ou seja, esse é o único teste que você precisaria fazer em 75% dos casos.

Solução

# Entrada de dados

ano = input('Digite o ano: ')

# Código - algoritmos

ano = int(ano) # convertendo ano de string para int

if ano % 400 == 0:  # é múltiplo de 400
    resultado = True
elif ano % 100 == 0:  # é múltiplo de 100
    resultado = False
elif ano % 4 == 0:  # é múltiplo de 4
    resultado = True
else:  # não é múltiplo de 4
    resultado = False

# Saída de dados

if resultado == True:
    res = 'é'
else:
    res = 'não é'

s = f'{ano} {res} bissexto' # mensagem formatada
print(s)

Análise da Solução

Dado que, de cada 400 números, 100 (25%) são divisíveis por 4, 1 (0.25%) é divisível por 400 e 3 (0.75%) são divisíveis por 100 mas não por 400, concluimos que, de todos os anos possíveis,

  • 0.25%: apenas um teste (if) é necessário;
  • 0.75%: dois testes (if e 1º elif) são necessários;
  • 99%: três testes (24% passam no teste do 2º elif e 75% vão para o else) são necessários.

O número médio de testes é então

\[N = 1 \times \frac{0.25}{100} + 2 \times \frac{0.75}{100} + 3 \times \frac{99}{100} = 2.9875\]

Esse é um número de testes muito alto para um problema tão simples. Portanto, o algoritmo proposto no enunciado não é muito eficiente.

Solução otimizada

Com as dicas do enunciado e usando a construção if elif else, a melhor solução para o problema (melhor no sentido estatístico, ou seja, aquela que faz, em média, menos testes) é a seguinte:

if ano % 4 != 0:  # não é múltiplo de 4
    resultado = False
elif ano % 100 != 0:  # é multiplo de 4 mas não de 100
    resultado = True
elif ano % 400 != 0:  # é múltiplo de 100 mas não de 400
    resultado = False
else:  # é múltiplo de 400
    resultado = True

Vamos fazer a análise novamente. De todos os anos possíveis,

  • 75%: apenas um teste (if) é necessário;
  • 24% dois testes (if e 1º elif) são necessários;
  • 1%: três testes (0.75% passam no teste do 2º elif e 0.25% vão para o else) são necessários.

O número médio de testes nesse caso é então

\[N = 1 \times \frac{75}{100} + 2 \times \frac{24}{100} + 3 \times \frac{1}{100} = 1.26\]

Uma melhora excelente! Conseguimos reduzir em quase 60% o número de comparações, reduzindo de forma parecida o tempo de execução do código. Pense no caso em que seu código precisa ser rodado bilhões ou trilhões de vezes num único dia, qual seria a economia de energia e recursos!

Exercício 2: Tempo em segundos

  • dificuldade: 20%
  • utiliza:

Escreva um programa que, dada uma duração de tempo em segundos, calcule o número equivalente de dias, horas, minutos e segundos.

Por exemplo, 123554 segundos equivalem a 1 dia, 10 horas, 19 minutos e 14 segundos.

Dicas:

Nesse exercício, use os operadores // (divisão inteira) e % (resto de divisão). Alguns exemplos:

x = 18
y = x // 3 # retorna o int 6
y = x % 3 # retorna o int 0
y = x // 4 # retorna o int 4
y = x % 4 # retorna o int 2

Solução

Existem muitas maneiras de resolver este exercício. Uma proposta é encontrada abaixo:

t = 1423554  # tempo em segundos

s = t % 60  # segundos: 60 s = 1 min
t //= 60  # tempo restante em minutos
m = t % 60  # minutos: 60 min = 1 h
t //= 60  # tempo restante em horas
h = t % 24  # horas: 24 h = 1 dia
d = t // 24  # tempo restante em dias

print(f'{d}d {h}h {m}m {s}s')

# Teste da solução:
t = 60 * ( 60 * (d * 24 + h) + m) + s
print(f'{t}s')

Exercício 3: Triângulos

  • dificuldade: 20%
  • utiliza:  

Se você tem 3 varetas, possivelmente de diferentes comprimentos, pode ou não ser possível ajeitá-las para que elas formem um triângulo. Por exemplo, se todos as varetas tiverem um comprimento de 6cm, pode-se facilmente construir um triângulo equilátero. No entanto, se uma vareta tem 6cm e as outras duas têm apenas 2cm, não dá pra criar um triângulo. Em geral, se qualquer uma das varetas é maior ou igual à soma das outras duas, elas não podem ser usadas para formar um triângulo. Caso contrário, o triângulo existe. Escreva um programa que determine se três comprimentos podem ou não formar um triângulo. O programa recebe 3 parâmetros e retorna um resultado booleano (True ou False).

Solução

arestas = input('a b c = ').split()
a, b, c = map(int, arestas)  # o comando map(f, L) aplica a função f à lista L

if a >= b + c or b >= a + c or c >= a + b:
  triangulo = False
else:
  triangulo = True

if triangulo:
  print(f'Triângulo {a, b, c} existe')
else:
  print(f'Triângulo {a, b, c} não existe')

Exercício 4: 3-5-15

  • dificuldade: 10%
  • utiliza:   

Monte um código que imprima os números de 1 a 100 mas, para múltiplos de 3, imprime trei ao invés do número; se é múltiplo de 5, imprime cinci; mas, se é múltiplo de 3 e 5 ao mesmo tempo, imprime cincisprezece (3, 5 e 15 em romeno).

Solução

A solução abaixo é uma das muitas possíveis. Usei ifs aninhados e um elif. Defini os divisores e frases a serem impressos antes do código da impressão, de modo que é fácil alterá-los, se alguem assim desejar.

N = 100
d1, d2 = 3, 5
f1, f2, f3 = 'trei', 'cinci', 'cincisprezece'

for n in range(1, N+1):
  if n % d1 == 0:
    if n % d2 == 0:
      print(f3)
    else:
      print(f1)
  elif n % d2 == 0:
    print(f2)
  else:
    print(n)

Exercício 5: Divisores

  • dificuldade: 15%
  • utiliza:   

Crie um programa que peça ao usuário um número e imprima todos os seus divisores. Se você não lembra o que é um divisor, é um número que divide outro sem deixar resto. Por exemplo, 13 é um divisor de 26 porque 26/13 não tem nenhum resto.

Solução

n = int(input('Digite um número:'))

print(f'Divisores de {n}:')
for d in range(1, n):
    if n % d == 0:
        print(d)

Obs: este código não está otimizado, pois testa muito mais números do que o necessário (por exemplo, qualquer número maior do que n//2 não será um divisor de n, mas o código testa mesmo assim).

Exercício 6: Máximo divisor comum

  • dificuldade: 10%
  • utiliza:   

O máximo divisor comum (MDC) de dois inteiros positivos, $n$ e $m$, é o maior número, $d$, capaz de dividir $n$ e $m$ sem deixar resto. Existem vários algoritmos para determinar $d$, incluindo o seguinte:

1. inicialize $d$ como o menor entre $m$ e $n$;
2. enquanto $d$ não dividir exatamente $m$ e $n$, diminua o valor de $d$ de uma unidade.

Ao final do algoritmo, $d$ sera o MDC de $n$ e $m$. Escreva um programa que leia dois inteiros positivos do usuário e use esse algoritmo para determinar e relatar seu máximo divisor comum.

Solução:

# Entrada
m = int(input('m = '))
n = int(input('n = '))

# Algoritmo

# encontrando o menor valor
if m < n:
  d = m
else:
  d = n

# encontrando o MDC(m, n)
while m % d or n % d :
  d -= 1

'''
comentário:
veja que
while m % d or n % d:
é o mesmo que
while m % d != 0 or n % d != 0:
pois qualquer valor positivo significa True,
e qualquer valor zero ou negativo resulta em False
'''

# Saída

print(f'MDC({m}, {n}) = {d}')

Exercício 7: MIT I

  • dificuldade: 10%
  • utiliza:    

(MIT) Escreva um programa que conte o número de vogais numa string s composta unicamente de letras minúsculas. Por exemplo, se s = 'azcbobobegghakl', seu programa deve imprimir Número de vogais: 5.

Solução:

s = input('Digite uma string de letras minúsculas: ')

n = 0
v = 'aeiou'

for letter in s:
  if letter in v:
    n += 1

print(f'Número de vogais: {n}')

Exercício 8: MIT II

  • dificuldade: 30%
  • utiliza:    

(MIT) Escreva um código para contar o número de vezes que a sequência 'bob' aparece numa string s composta unicamente de letras minúsculas. Por exemplo, se s = 'azcbobobegghakl', seu programa deve imprimir Número de ocorrências de bob: 2.

Solução:

s='bobazcbobobobobegbobghakl'
ns = len(s)

v = 'bob'
nv = len(v)

n = 0
for i in range(ns-nv+1):
  if s[i:i+nv] == v:
    n += 1

print(f'Número de ocorrências de {v}: {n}')

Exercício 9: MIT III

  • dificuldade: 60%
  • utiliza:    

(MIT) Escreva um código para imprimir a maior sequência em ordem estritamente alfabética de uma string s composta unicamente de letras minúsculas. Por exemplo, se s = 'azcbobobegghakl', seu programa deve imprimir Maior sequência em ordem alfabética: beggh. Em caso de empate, imprima apenas a primeira subsequência. Por exemplo, se s = 'abcbcd', seu programa deve imprimir Maior sequência em ordem alfabética: abc.

Exercício 10: Números romanos

  • dificuldade: 50%
  • utiliza:     

Implemente um algoritmo para converter números em algarismos arábicos (por exemplo, 4, 18, 29, 98, 1746) em algarismos romanos (IV, XVIII, XXIX, XCVIII, MDCCXLVI). Limite-se aos valores de 1 a 3999. Se estiver inspirado, implemente a conversão de algarismos romanos para arábicos.

Solução

dict_unidade = {'1': 'I', '2': 'II', '3': 'III', '4': 'IV', '5': 'V',
                '6': 'VI', '7': 'VII', '8': 'VIII', '9': 'IX', '0': ''}
dict_dezena = {'1': 'X', '2': 'XX', '3': 'XXX', '4': 'XL', '5': 'L',
               '6': 'LX', '7': 'LXX', '8': 'LXXX', '9': 'XC', '0': ''}
dict_centena = {'1': 'C', '2': 'CC', '3': 'CCC', '4': 'CD', '5': 'D',
                '6': 'DC', '7': 'DCC', '8': 'DCCC', '9': 'CM', '0': ''}
dict_milhar = {'1': 'M', '2': 'MM', '3': 'MMM', '0': ''}
# inseri 0 nos milhares para facilitar a conversão de romanos para arábicos

dic = {'': 0, 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}


def arabico_para_romano(n):
    arab = f'{n:04d}'  # converte o inteiro n para string, padding com zeros
    rom = dict_milhar[arab[0]]
    rom += dict_centena[arab[1]]
    rom += dict_dezena[arab[2]]
    rom += dict_unidade[arab[3]]
    return rom


def romano_para_arabico(n):
    a = dic[n[-1]]
    N = len(n)
    for i in range(N-1):
        if dic[n[i]] < dic[n[i+1]]:
            a -= dic[n[i]]
        else:
            a += dic[n[i]]
    return a

Exercício 11: Só uma linha

  • dificuldade: 10%
  • utiliza:    

Digamos que eu lhe forneça uma lista de números: a = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]. Escreva uma única linha em Python que gere uma nova lista apenas com os elementos pares de a.

Solução

a = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
print([x for x in a if x % 2 == 0])

Exercício 12: Números binários I

  • dificuldade: 15%
  • utiliza:   

Escreva um programa que converta um número binário (base 2) em decimal (base 10). Seu programa deve ler o número binário do usuário como uma sequência de zeros e uns e exibir o número decimal equivalente, processando cada dígito da representação binária. Por exemplo, 1010011 (base 2) $\equiv$ 83 (base 10), obtido a partir da definição:

\[1010011 \text{ (base 2)} =\] \[= \mathbf{1} \times 2^6 + \mathbf{0} \times 2^5 + \mathbf{1} \times 2^4 +\] \[+ \mathbf{0} \times 2^3 + \mathbf{0} \times 2^2 + \mathbf{1} \times 2^1 + \mathbf{1} \times 2^0 =\] \[= 83 \text{ (base 10)}\]

Solução

# Input
binario = input('Digite um número em base 2: ')

# Algoritmo

soma = 0
p = 1  # = 2**expoente

for digito in binario[::-1]:  # slicing para inverter a string
    soma = soma + int(digito) * p
    p = 2 * p

# Output
print(f'{binario} (base 10) = {soma} (base 2)')

Exercício 13: Números binários II

  • dificuldade: 15%
  • utiliza:  

Escreva um programa que converta um número decimal (base 10) em binário (base 2). Leia o número decimal do usuário e use o seguinte algoritmo de divisão, exemplificado para o número 83 (base 10):

	83/2 = 41 resto 1
	41/2 = 20 resto 1
	20/2 = 10 resto 0
	10/2 = 5 resto 0
	5/2 = 2 resto 1
	2/2 = 1 resto 0
	1/2 = 0 resto 1

Os restos das divisões (começando do último valor) contém a representação binária do número, nesse caso 1010011 (base 2).

Exercício 14: Sistema RGB

  • dificuldade: 30%
  • utiliza:    

Uma das maneiras de se referir a cores em websites e outras aplicações é a notação RGB (red-green-blue): três inteiros $0 \le R,\,G,\,B \le 255$ como identificadores das tonalidades de vermelho, verde e azul, respectivamente, que, quando mescladas, fornecem a cor desejada. Ao invés de fornecer os três inteiros em base 10, no entanto, é comum usar base 16. Essa maneira de identificar cores é conhecida como código hexadecimal. Em base 16, precisamos de 16 caracteres para representar os “dígitos” de um número (veja que em base 2 precisamos de dois, e em base 10, de dez). Usualmente são escolhidos os caracteres 0–9, com os valores usuais, e portanto precisamos de mais seis caracteres para representar os “dígitos” de de 10 a 15. Usualmente usa-se as letras A–F. Por exemplo,

\[\small 42 \text{ (base 10)} = 2A \text{ (base 16)} =\] \[= 2 \times 16^1 + 10 \times 16^0 \,.\]

Números que em base 16 são formados por apenas dois caracteres equivalem aos números de 0 a 255 ($= 16 ^ 2 -1$) em base 10. Além disso, no código hexadecimal as três tonalidades são indicadas por uma única string de seis caracteres. Por exemplo, o código hexadecimal CD1F41 corresponde aos tons $R=205$, $G=31$ e $B=65$, como você pode conferir aqui. Esse sistema (ou seja, seis caracteres escolhidos do conjunto 0–9+A–F) é capaz de descrever $256^3=16\,777\,216$ cores diferentes, de 000000 (preto) a FFFFFF (branco). Com base nos exercícios anteriores sobre números binários, monte um algoritmo para converter uma string válida de seis caracteres representando uma cor em código hexadecimal para a notação RGB, ou seja, os três inteiros $0 \le R,\,G,\,B \le 255$ com as tonalidades de vermelho, verde e azul. Implemente também a conversão no sentido contrário, ou seja, dados três inteiros $R,\,G,\,B \in [0,\,255]$, determine o código hexadecimal da cor em questão.

Exercício 15: Cosseno como uma série

  • dificuldade: 30%
  • utiliza:   

Calcule uma aproximação para $\cos x$ através da série

\[\small \cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \ldots\]

até que o módulo do último termo seja menor que $10^{-6}$. O usuário deve fornecer o valor de $x$. Não use a função fatorial, pois isso é desperdício de tempo de processamento, já que boa parte das operações para o cálculo de um termo da série já foi feita para o termo anterior!

Solução

Vou criar uma função que pede como argumentos o valor de $x$ e, opcionalmente, a precisão do último termo (padrão: $10^{-6}$). Além disso, confere as unidades de $x$ –graus ou radianos–, considerando radianos por padrão.

import numpy as np


def cos_serie(x, tol=1.e-6, unid='rad'):

  '''
    cos_serie calcula cos(x) por série de Taylor com uma tolerância no número de termos

    entrada:
      - x (obrigatório): float de que se deseja calcular o cosseno
      - tol (opcional): módulo do útimo termo é menor do que isso
      - unid (opcional): unidade de x.
          Opções:
            - 'rad' (padrão): x em radianos
            - 'graus': x em graus
  '''

  x0 = x * np.pi / 180 if unid == 'graus' else x

  termo, soma = 1., 1.
  a, b = 2, 1
  while abs(termo) > tol:
    termo *= -x0*x0 / a / b
    soma += termo
    a, b = a+2, b+2

  return soma


# usando a função
x = float(input('x='))
print(f'cos({x}) = {cos_serie(x)}')

Exercício 16: Pi como uma série

  • dificuldade: 20%
  • utiliza:  

Calcule as quinze primeiras aproximações para $\pi$ de acordo com a série

\[\small \frac{\pi-3}{4} = \frac{1}{2\cdot3\cdot4} - \frac{1}{4\cdot5\cdot6} + \frac{1}{6\cdot7\cdot8} - \ldots\]

Novamente, não use uma função fatorial, é uma perda de tempo e de recursos computacionais!

Solução

'''
Solução usando for, e eliminando fatores de 4 da fórmula do enunciado:
(pi-3)/4 = 1/(2*3*4) - 1/(4*5*6) + 1/(6*7*8) - ...
é simplificada para
pi-3 = 1/(1*3*2) - 1/(2*5*3) + 1/(3*7*4) - ...
'''

soma = 3 # variável que vai receber as aproximações de pi
sinal = 1 # variável com o sinal dos termos da soma
for n in range(1, 16): # sequencia de 15 valores de 1 a 15
    soma += sinal / (n * (2 * n + 1) * (n + 1))
    print(n, soma)
    sinal = -sinal # alternando o sinal do termo

Exercício 17: Joguinho

  • dificuldade: 20%
  • utiliza:   

Implemente o seguinte joguinho de computador: o usuário deve adivinhar um número de 1 a 100 “pensado” pelo computador (use a função randint() do módulo numpy.random). A cada palpite do usuário, o programa vai “cercando” o número, informando o intervalo $[a,\,b]$ em que ele se encontra. Acompanhe o seguinte exemplo, em que o número secreto é 42:

Adivinhe o número:
Está entre 0 e 100: 25
Está entre 25 e 100: 60
Está entre 25 e 60: 40
Está entre 40 e 60:

E assim por diante, até o usuário acertar. Não precisa de interface gráfica! Use a função input() para pedir ao usuário seu palpite (ou seja, crie uma TUItext-based user interface). Qual é a melhor estratégia para ganhar o jogo no menor número de tentativas?

Aqui está um possível algoritmo para o jogo:

import numpy.random as rd

a, b = 1, 100  # o segredo estará em [a,b]

# número secreto a ser adivinhado pelo jogador:
segredo = np.randint(a, b+1)

# Início do jogo:
print('Adivinhe o número:')

n = 1  # n será o contador de tentativas e o indicador (flag) de acerto
while n > 0:
  chute = int(input(f'Está entre {a} e {b}:'))

  if chute > segredo:
    b = chute
    n += 1
  elif chute < segredo:
    a = chute
    n += 1
  else:
    print(f'Acertou em {n} tentativas!')
    n = 0  # zerando n para se tornar um flag de acerto

Exercício 18: Dia seguinte

  • dificuldade: 35%
  • utiliza:    

Escreva um programa que leia uma data do usuário e calcule o dia seguinte. Por exemplo, se o usuário inserir valores que representem 18/11/2013, o programa deve exibir 19/11/2013. A data deve ser inserida em formato numérico com três declarações de entrada separadas, uma para o ano, uma para o mês e uma para o dia. Certifique-se de que o seu programa funcione corretamente para anos bissextos.

Exercício 19: Código César

  • dificuldade: 40%
  • utiliza:     

Um dos primeiros exemplos conhecidos de criptografia foi usado por Júlio César, que precisava fornecer instruções escritas para seus generais, mas não queria que seus inimigos descobrissem seus planos se a mensagem caísse em mãos erradas. Como resultado, ele desenvolveu o que mais tarde ficou conhecido como Código de César. A ideia é simples mas, em consequência, não fornece proteção contra técnicas modernas de quebra de código. Cada letra na mensagem original é deslocada de 3 lugares. Por exemplo, A torna-se D, B torna-se E, C torna-se F, D torna-se G, etc. As últimas três letras do alfabeto são enroladas de volta do início: X torna-se A, Y torna-se B e Z torna-se C. Caracteres não alfabéticos ficam inalterados. Escreva um programa que implemente o Código de César. Permita ao usuário fornecer a mensagem e o valor do deslocamento (não necessariamente 3) e, em seguida, exiba a mensagem codificada. Garanta que seu programa codifique letras maiúsculas e minúsculas de modo coerente. Faça com que seu programa suporte também valores de deslocamento negativos, para que possa ser usado tanto para codificar quanto para decodificar mensagens.

Dicas

  1. Os caracteres da Tabela ASCII correspondentes às letras A-Z e a-z estão, respectivamente, nas posições 65-90 e 97-122. Os algarismos de 0 a 9 correspondem às posições de 48 a 57.
  2. Os seguintes comandos são úteis para esse (e outros) exercícios:
    • ord(c): retorna um int com a posição do caractere c na Tabela ASCII. Por exemplo, ord('A') retorna 65.
    • chr(n): retorna o caractere correspondente ao inteiro n. Por exemplo, chr(122) retorna 'z'.

Exercício 20: Raiz quadrada (Newton)

  • dificuldade: 20%
  • utiliza:   

Escreva um programa que implementa o método de Newton para extrair a raiz quadrada de um número digitado pelo usuário. O algoritmo é o seguinte:

1. leia x do usuário;
2. inicialize raiz em x / 2;
3. enquanto raiz não for “bom o suficiente,” atualize raiz para a média de raiz e x / raiz.

Quando o algoritmo é concluído, raiz contém uma aproximação da raiz quadrada de x. A qualidade da aproximação depende de como você define “bom o suficiente,” então adote o seguinte critério de parada: o valor absoluto da diferença entre raiz * raiz e x deve ser menor que $10^{-12}$.

Exercício 21: Senha aleatória

  • dificuldade: 20%
  • utiliza:    

Escreva um programa para gerar uma senha aleatória. A senha deve ter um comprimento aleatório entre 7 e 10 caracteres (use a função randint() do módulo numpy.random). Cada caractere deve ser aleatoriamente selecionado das posições 33 a 126 na tabela ASCII. Sua função deve retornar a senha gerada aleatoriamente como único resultado, sem necessidade de entrada do usuário. Dica: a função chr() é útil para resolver esse exercício.

Solução

import numpy.random as rd
L = rd.randint(7, 11)  # tamanho da senha
s = rd.randint(33, 127, size=L)  # senha com L caracteres no intervalo 33-126
# imprime a senha:
senha = ''
for c in s:
    senha += chr(c)
print(senha)

:bulb: Observação: existe uma maneira mais rápida de imprimir a senha usando o comando join() e list comprehension. Troque as últimas linhas do código acima (depois do comentário # imprime a senha) pelo que segue:

senha = ''.join(chr(c) for c in s)
print(senha)

Exercício 22: Senha forte

  • dificuldade: 25%
  • utiliza:     

Adapte o exercício anterior para gerar uma senha forte, tendo pelo menos 8 caracteres, pelo menos uma letra maiúscula, pelo menos uma letra minúscula, e pelo menos um número. Conte e exiba o número de tentativas que foram necessárias antes que uma senha forte fosse gerada.

Solução

A solução proposta abaixo faz extenso uso de funções. Apesar de não ser obrigatório, isso ajuda e muito a organização do código! Além disso, a solução apresentada aqui é ligeiramente diferente daquela que montamos em sala de aula. Compare para ver as diferenças. A principal delas é como fizemos as comparações. Veja que o comando 'A' <= c <= 'Z', sendo c um caractere (uma dado do tipo string) é equivalente a 65 <= ord(c) <= 90, que foi o que usamos em aula.

import numpy.random as rd

def gera_senha():
    '''
    função com a solução do ex anterior
    gera uma senha de tamanho 7-10
    com caracteres ASCII no intervalo 33-126
    '''
    L = rd.randint(7, 11)  # tamanho da senha
    s = rd.randint(33, 127, size=L)
    senha = ''.join(chr(c) for c in s)
    return senha

def verifica_senha(senha):
    '''
    função para verificar se a senha tem pelo menos:
    - 8 caracteres
    - uma letra maiúscula
    - uma letra minúscula
    - um número
    '''
    # verificando o tamanho
    if len(senha) < 8:
        return False

    # verificando presença de caracteres
    flag_M, flag_m, flag_n = False, False, False
    for c in senha:
        if 'A' <= c <= 'Z':
            flag_M = True  # o caractere é maiúsculo
        if 'a' <= c <= 'z':
            flag_m = True  # o caractere é minúsculo
        if '0' <= c <= '9':
            flag_n = True  # o caractere é dígito

    if flag_M == True and flag_m == True and flag_n == True:
        return True
    else:
        return False

def senha_forte():
    '''
    função para gerar uma senha forte
    usando as funções anteriores
    retorna também o número de chamadas à função gera_senha()
    '''
    n = 1
    while True:
        senha = gera_senha()
        if verifica_senha(senha) == True:
            return senha, n
        n += 1

# Chamando a função
SenhaForte, n = senha_forte()
print(f'Senha: {SenhaForte}\nTentativas: {n}')

:bulb: Em strings, \n é um código para quebra de linha. Ele corresponde ao caractere de no. 10 da Tabela ASCII

Exercício 23: Fatorial por recursão

  • dificuldade: 20%
  • utiliza:    

Interprete a saída da seguinte função, que usa uma propriedade conhecida como recursão:

def fatorial_recursivo(n):
    if n < 2:
        return 1
    else:
        return n * fatorial_recursivo(n-1)

A função retorna o fatorial de um inteiro, como você deve ter imaginado. Repare que a função chama ela mesma dentro dela. A isso chamamos de recursão.

Exercício 24: Fibonacci por recursão

  • dificuldade: 30%
  • utiliza:    

Usando recursão, implemente uma função para calcular o $n$-ésimo termo da série de Fibonacci,

\[0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ \ldots\]

que começa com $a_0=0$, $a_1=1$ e em que cada termo $a_n$ ($n \ge 2$) é calculado usando a equação recursiva

\[a_n = a_{n-1} + a_{n-2}\,.\]

Segue uma proposta de função recursiva:

def fibonacci(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fibonacci(n-1) + fibonacci(n-2)

Vamos usar a função acima para imprimir os dez primeiros valores da sequência:

for n in range(10):
  print(f'n={n}, a_n = {fibonacci(n)}')

Exercício 25: Ajuste linear

  • dificuldade: 25%
  • utiliza:    

Uma linha de melhor ajuste é uma linha reta que melhor se aproxima de uma coleção de $n$ pontos de dados. Neste exercício, vamos supor que cada ponto na coleção tem uma coordenada $(x_i,\,y_i)$, com $1\le i \le n$. A linha de melhor ajuste é representada pela equação $y = m x + b$, onde $m$ e $b$ são calculados usando as seguintes fórmulas:

\[m = \frac{ n \sum x_i y_i - \left( \sum x_i \right) \left( \sum y_i \right) }{n \sum x_i^2 - \left( \sum x_i \right)^2}\] \[b = \overline{y} - m \overline{x}\]

onde os símbolos $\overline{x}$ e $\overline{y}$ são os valores médios de $x$ e $y$, respectivamente. Escreva um programa para ler os pontos contidos num arquivo-texto fornecido pelo usuário (use a função genfromtxt() do módulo numpy). Então calcule e exiba a linha de melhor ajuste. Por exemplo, se o usuário fornece as coordenadas $(1,\,1)$, $(2,\,2.1)$ e $(3,\,2.9)$, o seu o programa deve exibir y = 0.95 x + 0.1. Faça também um gráfico com os pontos e a linha de melhor ajuste usando as funções scatter() e plot() do módulo matplotlib.pyplot.

Exercício 26: Máximo de uma lista

  • dificuldade: 20%
  • utiliza:     

Considere o problema de identificar o máximo valor de uma coleção de inteiros, todos selecionados aleatoriamente no intervalo $[1,\,100]$. A coleção pode conter valores duplicados, e alguns dos números entre 1 e 100 podem não estar presentes. Pare um pouco e pense em como você lidaria com esse problema no papel. A maioria checaria cada número em sequência e perguntaria se o valor da vez é maior que o máximo dentre os anteriores. Se for, eles esqueceriam o máximo anterior e lembrariam o número atual como o novo máximo. Essa é uma abordagem razoável e resultará na resposta correta quando o processo for executado com cuidado. Implemente o método em python. Quantas vezes você esperaria precisar atualizar o valor máximo e lembrar de um novo número?

Exercício 27: Código Morse

  • dificuldade: 25%
  • utiliza:    

O código Morse é um esquema de codificação que usa traços e pontos para representar números e letras. Neste exercício, você vai escrever um programa que usa um dicionário para armazenar o mapeamento de letras e números para código Morse, mostrado na tabela a seguir:

A . - J . - - - S . . . 1 . - - - -
B - . . . K - . - T - 2 . . - - -
C - . - . L . - . . U . . - 3 . . . - -
D - . . M - - V . . . - 4 . . . . -
E . N - . W . - - 5 . . . . .
F . . - . O - - - X - . . - 6 - . . . .
G - - . P .- -. Y - . - - 7 - - . . .
H . . . . Q - -.- Z - - . . 8 - - - . .
I . . R . - . 0 - - - - - 9 - - - - .

Seu programa deve ler uma mensagem do usuário. Então deve traduzir cada letra e número na mensagem para o código Morse, deixando um espaço entre cada seqüência de traços e pontos. Seu programa deve ignorar quaisquer caracteres que não sejam letras ou números. O código Morse para Hello, World! é mostrado abaixo:

....  .  .-..  .-..  ---   .--  ---  .-.  .-..  -..

A solução abaixo usa um dicionário e uma função para converter minúsculas em maiúsculas e eliminar caracteres não alfanuméricos

morse = {'A':	'.-',	'J':	'.---',	'S':	'...',	'1':	'.----',
'B':	'-...',	'K':	'-.-',	'T':	'-'	,	'2':	'..---',
'C':	'-.-.',	'L':	'.-..',	'U':	'..-',	'3':	'...--',
'D':	'-..',	'M':	'--',	'V':	'...-',	'4':	'....-',
'E':	'.',		'N':	'-.',	'W':	'.--',	'5':	'.....',
'F':	'..-.',	'O':	'---',	'X':	'-..-',	'6':	'-....',
'G':	'--.',	'P':	'.--.',	'Y':	'-.--',	'7':	'--...',
'H':	'....',	'Q':	'--.-',	'Z':	'--..',	'8':	'---..',
'I':	'..',	'R':	'.-.',	'0':	'-----',	'9':	'----.'}

def converte(msg):
  '''
    converte minúsculas e maiúsculas e
    elimina caracteres não alfanumericos
  '''
  msg1 = ''
  for c in msg:
    if 'a' <= c <= 'z':
      msg1 += chr(ord(c)-32)
    elif 'A' <= c <= 'Z' or '0' <= c <= '9':
      msg1 += c

  return msg1

mensagem = input('Digite sua mensagem: ')
mensagem = converte(mensagem)
for c in mensagem:
  print(morse[c], end=' ')
print()

Exercício 28: Cômputo da Páscoa

  • dificuldade: 15%
  • utiliza:   

A Páscoa cai no primeiro domingo do ano após a lua cheia (mas não a lua cheia real, e sim de acordo com um antigo cômputo (computus) eclesiástico que nada mais tem a ver com a lua que vemos no céu: é apenas um algoritmo…) que acontece no ou imediatamente após o equinócio de março (considera-se sempre 21 de março como a data do equinócio, o que nem sempre é verdade, pois pode ser um ou dois dias antes…). Na prática, é mais fácil calcular a data da Páscoa usando o algoritmo de Meeus–Jones–Butcher:

Divida por Quociente   Resto
o ano $x$ 19 $a$
o ano $x$ 100 $b$ $c$
$b$ 4 $d$ $e$
$b+8$ 25 $f$
$b-f+1$ 3 $g$
$19a+b-d-g+15$ 30 $h$
$c$ 4 $i$ $k$
$32+2e+2i-h-k$ 7 $l$
$a+11h+22l$ 451 $m$
$h+l-7m+114$ 31 $n$ $p$

O domingo de Páscoa será então no dia $p+1$ do mês $n$ (3: março, 4: abril). O algoritmo é válido para qualquer ano no calendário gregoriano, ou seja, a partir de 1583. Implemente-o em python e verifique aqui. Dica: não use o operador /, e sim // (divisão inteira) para as divisões.

def pascoa(ano):
    a = ano % 19
    b, c = ano // 100, ano % 100
    d, e = b // 4, b % 4
    f = ( b + 8 ) // 25
    g = ( b - f + 1 ) // 3
    h = ( 19 * a + b - d - g + 15 ) % 30
    i, k = c // 4, c % 4
    l = ( 32 + 2 * e + 2 * i - h - k ) % 7
    m = ( a + 11 * h + 22 * l ) // 451
    o = h + l - 7 * m + 114
    n, p = o // 31, o % 31
    return p + 1, n

# dicionário para converter mes de int para string
mes = {3:'Março', 4:'Abril'}

x = int(input('Ano: '))
d, m = pascoa(x)

# o formato 02d imprime um inteiro com 2 algarismos, com zeros à esquerda se necessário
print( f'Data da Páscoa em {x}: {d:02d} de {mes[m]}' )

Exercício 29: Triângulo de Pascal

  • dificuldade: 30%
  • utiliza:    

O triângulo de Pascal é uma tabela de números construída assim: o elemento da linha $i$ e coluna $j$ (com $0 \le j \le i$ e começando de cima, onde $i=j=0$) é dado por

\[a_{i,j} = \begin{cases} 1 \quad \text{ se } j=0 \text{ ou } j=i\\ a_{i-1,j} + a_{i-1,j-1} \,, \text{ se } 1 \lt j \lt i \end{cases}\]

As primeiras oito linhas (ou seja, até $i=7$) são mostradas abaixo:

  1
  1  1
  1  2  1
  1  3  3  1
  1  4  6  4  1
  1  5  10 10 5  1
  1  6  15 20 15 6  1
  1  7  21 35 35 21 7  1
  1. Implemente um algoritmo para calcular as primeiras $n$ linhas do triângulo de Pascal.
  2. Modifique o código para substituir os números ímpares do triângulo por 1 e os pares por 0. Use um valor alto de $n$ (algo em torno de 500) e salve o resultado numa matriz. Por fim, use o comando imshow() do módulo matplotlib.pyplot para exibir graficamente o resultado, que é muito parecido com o fractal chamado de Triângulo de Sierpinski (clique aqui e veja na Wikipedia).

Segue uma função usando um array em numpy:

import numpy as np

def pascal(N):
    '''
    gera as N primeiras linhas do triângulo de Pascal
    (supoe N inteiro não-negativo)
    '''
    v = np.zeros((N, N))  # uma matriz NxN de 0'
    for i in range(N):  # laço para gerar as linhas
        v[i, 0] = 1
        for j in range(1, i+1):  # laço pelas colunas
            v[i, j] = v[i-1, j] + v[i-1, j-1]

    return v

Para a segunda parte do exercício, podemos usar a função acima, aliada ao poder de arrays em numpy, e calcular diretamente o resto da divisão por 2. Isso automaticamente substituirá números pares por 0 e ímpares por 1:

N = 500
tri = pascal(N) % 2

import matplotlib.pyplot as plt

plt.figure()
plt.imshow(tri, interpolation='none')
plt.show()

:exclamation: É um bom hábito de programação carregar todos os módulos no começo do arquivo, e não fazer como no exemplo acima, em que carreguei o módulo matplotlib.pyplot no meio do código (um exemplo do ditado faça o que eu digo, não faça o que eu faço…).

O resultado é a imagem abaixo:

Pascal modificado - Sierpinski
Pascal modificado - Sierpinski

Exercício 30: Quadrado mágico

  • dificuldade: 40%
  • utiliza:    

Um quadrado mágico é uma tabela de números em que a soma nas linhas, colunas e diagonais dá sempre o mesmo valor. Por exemplo, na gravura Melencholia I de Albrecht Dürer (1471–1528),

a soma dos números é sempre igual a 34 (o quadrádo mágico de Dürer serviu de inspiração para o nome e o logotipo da Editora 34). Outro exemplo simples é o seguinte, em que estão presentes todos os inteiros de 1 a 9 num quadrado $3\times3$:

  |---|---|---|
  | 8 | 1 | 6 |
  |---|---|---|
  | 3 | 5 | 7 |
  |---|---|---|
  | 4 | 9 | 2 |
  |---|---|---|

e a soma é sempre igual a 15.

Existe um algoritmo para criar quadrados mágicos de ordem ímpar $n$ (a ordem é o número de linhas = número de colunas), preenchidos por todos os inteiros de 1 a $n^2$:


Algoritmo:

(i) Comece com o número 1 na célula central superior do quadrado (como no exemplo acima);
(ii) preencha sequencialmente na diagonal, seguindo para a direita e subindo;
(iii) quando atingir as bordas do quadrado, o próximo número é preenchido como se o quadrado estivesse “enrolado” feito uma rosquinha — ou seja, a borda esquerda “colada” à direita e a superior à inferior. Isso é o que se chama de condições de contorno periódicas;
(iv) uma exceção é o canto superior direito: quando atingi-lo, o próximo valor vai na célula de baixo;
(v) se a próxima célula já está ocupada, o próximo valor vai abaixo do último número preenchido;
(vi) continue até chegar em $n^2$ na célula central inferior.

Para ilustrar o uso do algoritmo, vejamos sua aplicação para gerar um quadrado mágico de ordem $n=5$:

  • Comece com o passo i, colocando o número 1 na célula central superior do quadrado:
|---|---|---|---|---|
|   |   | 1 |   |   |
|---|---|---|---|---|
|   |   |   |   |   |
|---|---|---|---|---|
|   |   |   |   |   |
|---|---|---|---|---|
|   |   |   |   |   |
|---|---|---|---|---|
|   |   |   |   |   |
|---|---|---|---|---|
  • Ao tentar usar o passo ii para inserir o próximo número (2), não temos célula acima e à direita da célula anterior (1). Temos então que usar o passo iii:
  |---|---|---|---|---|
  |   |   | 1 |   |   |
  |---|---|---|---|---|
  |   |   |   |   |   |
  |---|---|---|---|---|
  |   |   |   |   |   |
  |---|---|---|---|---|
  |   |   |   |   |   |
  |---|---|---|---|---|
  |   |   |   | 2 |   |
  |---|---|---|---|---|
  • Alguns passos depois, usando os passos ii e iii, o quadrado estará assim:
|---|---|---|---|---|
|   |   | 1 |   |   |
|---|---|---|---|---|
|   | 5 |   |   |   |
|---|---|---|---|---|
| 4 |   |   |   |   |
|---|---|---|---|---|
|   |   |   |   | 3 |
|---|---|---|---|---|
|   |   |   | 2 |   |
|---|---|---|---|---|
  • Como a próxima célula (1) já está ocupada, usamos o passo v para o próximo valor (6):
|---|---|---|---|---|
|   |   | 1 |   |   |
|---|---|---|---|---|
|   | 5 |   |   |   |
|---|---|---|---|---|
| 4 | 6 |   |   |   |
|---|---|---|---|---|
|   |   |   |   | 3 |
|---|---|---|---|---|
|   |   |   | 2 |   |
|---|---|---|---|---|
  • Continuando por mais alguns valores, usando os passos ii, iii e v:
|----|----|----|----|----|
|    |    | 1  | 8  | 15 |
|----|----|----|----|----|
|    | 5  | 7  | 14 |    |
|----|----|----|----|----|
| 4  | 6  | 13 |    |    |
|----|----|----|----|----|
| 10 | 12 |    |    | 3  |
|----|----|----|----|----|
| 11 |    |    | 2  | 9  |
|--- |----|----|----|----|
  • Atingido o canto superior direito, o próximo valor (16) vai abaixo dele, de acordo com o passo iv:
|----|----|----|----|----|
|    |    | 1  | 8  | 15 |
|----|----|----|----|----|
|    | 5  | 7  | 14 | 16 |
|----|----|----|----|----|
| 4  | 6  | 13 |    |    |
|----|----|----|----|----|
| 10 | 12 |    |    | 3  |
|----|----|----|----|----|
| 11 |    |    | 2  | 9  |
|--- |----|----|----|----|
  • E agora continue com os passos ii, iii e v até terminar de preencher o quadrado:
|----|----|----|----|----|
| 17 | 24 | 1  | 8  | 15 |
|----|----|----|----|----|
| 23 | 5  | 7  | 14 | 16 |
|----|----|----|----|----|
| 4  | 6  | 13 | 20 | 22 |
|----|----|----|----|----|
| 10 | 12 | 19 | 21 | 3  |
|----|----|----|----|----|
| 11 | 18 | 25 | 2  | 9  |
|--- |----|----|----|----|

Lembre que o algoritmo só vale para valores ímpares de $n$. Existem muitos outros quadrados mágicos de mesma ordem, o algoritmo só fornece uma possibilidade.

  1. Qual é a soma em cada linha, coluna e nas duas diagonais, em função de $n$? Responda a essa pergunta usando a cabeça, não o computador!
  2. Implemente o algoritmo em python para montar e exibir um quadrado mágico de ordem $n$ ($n$ ímpar) com os números inteiros de 1 a $n^2$. A ordem do quadrado ($n$) deve ser fornecida pelo usuário.

Exercício 31: Saindo do labirinto

  • dificuldade: 80%
  • utiliza:       

Ajude um rato a encontrar um pedaço de queijo num labirinto como o do desenho abaixo:

Exemplo de um labirinto
Exemplo de um labirinto

Um labirinto desses pode ser representado por uma matriz retangular $L$, cujo elemento $\ell_{ij}$ vale $0$ ou $-1$, conforme a casa correspondente do labirinto seja uma passagem livre ou uma parede, respectivamente.

Um método geral para resolver esse problema consiste em marcar com o número $k$ ($k = 1, 2,\ldots$) todas as casas livres que estejam exatamente a $k-1$ passos de distância do queijo, pelo caminho mais curto possível. Suponha que, a cada passo, o rato possa se deslocar de apenas uma casa na vertical ou na horizontal. Então, rotula-se inicialmente a posição do queijo com $1$ e para cada $k\ge2$ examinam-se todas as casas livre do labirinto, marcando-se com $k$ aquelas ainda não marcadas e que sejam adjacentes a alguma casa marcada com $k-1$.

A marcação continua até ser atingido um valor $k$ (28 no exemplo abaixo) tal que nenhuma casa esteja em condições de ser marcada. Ao final da marcação teremos a seguinte matriz, supondo o queijo em (5,10), ou seja, no canto inferior direito:

Marcação do labirinto
Marcação do labirinto

O caminho mais curto até o queijo pode então ser determinado, partindo-se da posição do rato e passando a cada etapa para uma casa adjacente cuja numeração seja menor do que a atual.

Por exemplo, partindo de (0, 0), i.e., o canto superior esquerdo, o rato precisará percorrer pelo menos 26 casas para chegar ao queijo: (0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4,2), …, (4, 10), (4, 15).

Dados o labirinto (matriz $L$) com elementos $0$ e $-1$ e as posições do rato e do queijo, determine o caminho mais curto que o rato deve percorrer até encontrar o queijo, se tal caminho existir.

Sugestão: escreva uma função que efetua a marcação (recebendo como argumentos a matriz $L$ e a posição do queijo) e uma outra que imprime o caminho (recebendo como argumentos a matriz $L$ já preenchida e a posição inicial do rato).

Com o código em mãos, teste a sua solução no seguinte labirinto:

Um labirinto mais complicado
Um labirinto mais complicado

Baixe o arquivo com a matriz $L$ clicando no botão abaixo com o botão direito e escolhendo “Salvar link como…”

Baixe o arquivo labirinto-grande.txt

O arquivo labirinto-grande.txt é composto por 0’s e -1’s, formando um labirinto de 41 linhas e 101 colunas, com o rato inicialmente na posição (1,0) e o queijo em (39, 100).


Página atualizada em 10/23/2020, 9:12:44 AM