Exercícios da aula 05¶

Exercício 1¶

O que o programa a seguir vai imprimir?

a = 1
b = 2
soma2(a,b)

e o programa

a = 1
b = 2
soma2(b, a)

In [1]:

def soma2(a,b):
    print(a+2*b)

In [2]:

a = 1
b = 2
soma2(a,b)

In [3]:

a = 1
b = 2
soma2(b, a)

Existe uma diferença entre variáveis que são passadas como argumentos e os argumentos. A função soma2 tem dois argumentos a e b. No primeiro exemplo, a assume o valor de a (definindo fora da função) e b assume o valor de b (definido fora da função). E portanto a função imprime o valor de a + 2*2 que vale 5.

Já no segundo exemplo o a dentro da função assume o valor de b de fora da função e o b de dentro da função assume o valor de a de fora da função.

O primeiro exempl equivale a soma2(1,2) e o segundo exemplo a soma2(2,1)

Exercício 2¶

Escreva a função máximo que retorna o maior de dois números

In [5]:

def máximo(a,b):
    if a > b:
        return a
    else:
        return b

In [6]:

máximo(1,2)

Out[6]:

In [7]:

máximo(2,1)

Out[7]:

In [8]:

máximo(1,1)

Out[8]:

Exercício 3¶

Escreva a função múltiplo que retorna True se o primeiro argumento for um múltiplo do segundo

In [15]:

def múltiplo(a, b):
    return a % b == 0 and a > 0

In [16]:

múltiplo(1,2)

Out[16]:

False

In [20]:

múltiplo(0,2)

Out[20]:

False

In [22]:

múltiplo(4,2)

Out[22]:

True

In [23]:

múltiplo(5,2)

Out[23]:

False

Exercício 4¶

Escreva a função área_quadrado que recebe o lado de um quadrado e calcula a área.

In [24]:

def área_quadrado(L):
    return L*L

In [26]:

área_quadrado(1)

Out[26]:

In [27]:

área_quadrado(2)

Out[27]:

In [28]:

área_quadrado(3.3)

Out[28]:

10.889999999999999

Exercício 5¶

Escreve a função área_triângulo que recebe a base e a altura de um triângulo e retorna a sua área

In [29]:

def área_triângulo(B,H):
    return B*H/2

In [30]:

área_triângulo(1,1)

Out[30]:

0.5

In [31]:

área_triângulo(1,2)

Out[31]:

1.0

Exercício 6¶

Reescreve a função para pesquisar uma lista (pesquise) acima de modo a que use os métodos de pesquisa em lista que vimos na última aula.

In [35]:

def pesquise(L, val):
    return L.index(val)

In [36]:

pesquise([1,2,3,4], 3)

Out[36]:

In [37]:

pesquise([1,2,3,4], 4)

Out[37]:

In [38]:

pesquise([1,2,3,4], 5)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
/tmp/ipykernel_39169/664349085.py in <module>
----> 1 pesquise([1,2,3,4], 5)

/tmp/ipykernel_39169/4221004609.py in pesquise(L, val)
      1 def pesquise(L, val):
----> 2     return L.index(val)

ValueError: 5 is not in list

Exercício 7¶

Defina uma função recursive que calcule o maior divisor comum (MDC) entre dois números a e b em que a > b.

mdc(a,b) = a se b==0 e se a > b, mdc(a,b) = mdc(b, a % b)

In [40]:

def mdc(a,b):
    if b==0:
        return a
    elif a > b:
        return mdc(b, a % b)
    else:
        return mdc(a, b % a)

In [45]:

mdc(8,2)

Out[45]:

In [46]:

mdc(2,8)

Out[46]:

In [47]:

mdc(8,8)

Out[47]:

In [48]:

mdc(1*2*3*4*5, 1*2*3*4)

Out[48]:

Exercício 8¶

Usando a função mdc do exercício anterior, defina uma função para calcular o mínimo múltiplo comum (MMC) entre dois números:

$$ mmc(a,b) = \frac{|a\times b|}{mdc(a,b)} $$

Lembre que $|a \times b|$ é escrito como abs(a * b) em Python.

In [49]:

def mmc(a,b):
    return abs(a*b) // (mdc(a,b))

In [53]:

mmc(4,5)

Out[53]:

In [54]:

mmc(5,4)

Out[54]:

In [55]:

mmc(5,5*4)

Out[55]:

Exercício 9¶

Reescreva o programa para calcular a sequência de Fibonacci sem utilizar recursão.

Compare o desempenho com a função recursiva. Se você estiver usando o notebook do jupyter ou o ipython você pode usar a instrução %time como mostrado a seguir

In [109]:

def fibonacci_recursivo(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursivo(n-1) + fibonacci_recursivo(n-2)

In [58]:

def fibonacci(n):
    if n <= 1:
        return n
    fib_n_menos_1 = 0
    fib_n = 1
    
    for i in range(2,n+1):
        tmp = fib_n
        fib_n = fib_n + fib_n_menos_1
        fib_n_menos_1 = tmp
    return fib_n

In [65]:

[fibonacci(i) for i in range(11)]

Out[65]:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

In [66]:

[fibonacci_recursivo(i) for i in range(11)]

Out[66]:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Vamos medir o tempo:¶

In [87]:

%timeit fibonacci(2)

279 ns ± 0.831 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [88]:

%timeit fibonacci(5)

399 ns ± 2.29 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [70]:

%timeit fibonacci(10)

607 ns ± 1.09 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [77]:

%timeit fibonacci(15)

817 ns ± 1.45 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [78]:

%timeit fibonacci(20)

1.06 µs ± 1.74 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [79]:

%timeit fibonacci(25)

1.3 µs ± 4.71 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [80]:

%timeit fibonacci(30)

1.53 µs ± 4.33 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [82]:

%timeit fibonacci(35)

1.78 µs ± 11.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [83]:

%timeit fibonacci(40)

1.99 µs ± 5.67 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [125]:

n1 = [2, 5,10,15,20,25,30,35] #,40]
t1 = [279e-9,399e-9, 607e-9, 817e-9, 1.06e-6, 1.3e-6, 1.53e-6, 1.78e-6] #, 1.99e-6]

In [93]:

from matplotlib import pyplot as plt

In [100]:

plt.plot(n1, t1, "o")

Out[100]:

[<matplotlib.lines.Line2D at 0x7f2781094190>]

In [110]:

%timeit fibonacci_recursivo(2)

300 ns ± 0.703 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [111]:

%timeit fibonacci_recursivo(5)

1.46 µs ± 2.44 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [112]:

%timeit fibonacci_recursivo(10)

17.1 µs ± 20.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [113]:

%timeit fibonacci_recursivo(15)

190 µs ± 681 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [114]:

%timeit fibonacci_recursivo(20)

2.13 ms ± 7.45 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [115]:

%timeit fibonacci_recursivo(25)

23.5 ms ± 89.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [116]:

%timeit fibonacci_recursivo(30)

260 ms ± 711 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [118]:

%timeit fibonacci_recursivo(35)

2.92 s ± 5.12 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [ ]:

In [119]:

n2 = [2,5,10,15,20, 25, 30, 35]
t2 = [300e-9, 1.46e-6, 17.1e-6, 190e-6, 2.13e-3, 23.5e-3, 260e-3, 2.92]

In [120]:

plt.plot(n2, t2, "o")

Out[120]:

[<matplotlib.lines.Line2D at 0x7f2781079730>]

In [124]:

plt.semilogy(n1, t1, "ro", label="Iteração")
plt.semilogy(n2, t2, "bs", label="Iteração")

Out[124]:

[<matplotlib.lines.Line2D at 0x7f27810cb700>]

In [127]:

fator_mult = [t2[i] / t1[i] for i in range(len(t1))]

In [130]:

plt.semilogy(n1, fator_mult, "ro")

Out[130]:

[<matplotlib.lines.Line2D at 0x7f2780cfd850>]

Análise do custo¶

O custo de cálculo do número de Fibonacci aumenta linearmente conforme n aumenta.

Já a usando a definição recursiva, o custo aumenta de maneira considerável. No último gráfico, com eixo log em y, pode-se ver que o custo da função recursiva aumenta exponencialmente em relação à implementação usando iteração. Assim, dado um número n, o custo computacional pode ser descrito assim:

Algoritmo iterativo: $\mathcal{O}(n)$
Algoritmo recursivo: $\mathcal{O}(n\cdot \exp n)$

Exercício 10¶

Na aula 03 implementamos o algoritmo de reordenação de listas bubble sort. Crie uma função bubble_sort que reordena os elementos de uma lista de números em ordem crescente

In [131]:

def bubble_sort(L):
    N = len(L)
    for i in range(N):
        trocou = False
        for k in range(N-i-1):
            if L[k] > L[k+1]: # Inverter a posição
                trocou = True
                tmp = L[k]
                L[k] = L[k+1]
                L[k+1] = tmp
        if not trocou:
            break

In [135]:

L = [23,4,5,2,3,6,2345,6,32,345,4]
bubble_sort(L)
L

Out[135]:

[2, 3, 4, 4, 5, 6, 6, 23, 32, 345, 2345]

Exercício 11¶

Mude o programa do exercício 10 de modo que tenha um segundo parâmetro comparador que é uma função que compara dois elementos

def maior(a, b):
    return a > b

def bubble_sort(L, comparador=maior)
    # Corpo da função

Esse segundo parâmetro é o que compara os elementos da lista. Se esse parâmetros for a função maior, a lista será reordenada em ordem crescente.

Qual seria a função passada para o parâmetro comparador para que a lista fosse reordenada em ordem decrescente?

In [136]:

def maior(a,b):
    return a > b
def menor(a,b):
    return a < b

In [137]:

def bubble_sort(L, comparador=maior):
    N = len(L)
    for i in range(N):
        trocou = False
        for k in range(N-i-1):
            if comparador(L[k],L[k+1]): # Inverter a posição
                trocou = True
                tmp = L[k]
                L[k] = L[k+1]
                L[k+1] = tmp
        if not trocou:
            break

In [138]:

L = [23,4,5,2,3,6,2345,6,32,345,4]
bubble_sort(L, maior)
L

Out[138]:

[2, 3, 4, 4, 5, 6, 6, 23, 32, 345, 2345]

In [139]:

L = [23,4,5,2,3,6,2345,6,32,345,4]
bubble_sort(L, menor)
L

Out[139]:

[2345, 345, 32, 23, 6, 6, 5, 4, 4, 3, 2]

Exercício 12¶

Escreva uma função mapa que recebe como primeiro parâmetro uma função e segundo parâmetro uma lista e cria uma nova lista aplicando esta função em cada elemento da lista.

Exemplo:

python-repl
In [10]: def dobro(n):
    ...:     return 2*n
    ...: 

In [11]: mapa(dobro, [1,2,3])
Out[11]: [2, 4, 6]

In [141]:

def mapa(fun, L):
    Lout = []
    for e in L:
        v = fun(e)
        Lout.append(v)
    return Lout

In [142]:

def dobro(n):
    return 2*n
mapa(dobro, range(10))

Out[142]:

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

In [144]:

mapa(lambda x: x**2, range(10))

Out[144]:

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

In [145]:

mapa(lambda x: x^3, range(10))

Out[145]:

[3, 2, 1, 0, 7, 6, 5, 4, 11, 10]

Funções lamda¶

São funções pequenas de uma linha que são usadas para serem passadas como argumentos