Lista 6 - Algoritmos iterativos

Algoritmos iterativos

  1. Escreva um programa que imprima uma tabela de números ímpares com $m$ linhas e $n$ colunas ($m$ e $n$ são lidos do teclado) como no seguinte formato de exemplo (para $m = 3$ e $n = 4$).

    01 03 05 07
    15 13 11 09
    17 19 21 23
    
  2. Múltiplas sequências:

    a) Faça um algoritmo que calcule e escreva o valor de S:

    $$ S= \frac{1}{1} + \frac{3}{2} + \frac{5}{3} + \frac{7}{4} + \dots + \frac{99}{50} $$

    b) Faça um algoritmo que calcule e escreva o valor de S:

    $$ S= \frac{2^1}{50} + \frac{2^2}{49} + \frac{2^3}{48} + \frac{2^4}{47} + \dots + \frac{2^{50}}{1} $$

    c) Faça um algoritmo que calcule o valor de S:

    $$ S= \frac{1}{1} - \frac{2}{4} + \frac{3}{9} - \frac{4}{16} + \dots - \frac{10}{100} $$

  3. Escreva um programa que leia um número inteiro positivo n e em seguida imprima n linhas do chamado triângulo de Floyd. O exemplo abaixo mostra o triângulo de Floyd com 6 linhas.

    1
    2 3
    4 5 6
    7 8 9 10
    11 12 13 14 15
    16 17 18 19 20 21
    
  4. Escreva um programa que leia um número inteiro n e escreva uma figura similar à seguinte, mas com n linhas.

    ...*......*...
    ..***....***..
    .*****..*****.
    **************
    
  5. Qual a saída quando você fornece os dados de seu RA? Tente descobrir sem usar um computador.

    def misterio(a, b):
        m = 20
        for i in range(m + 1):
            n = ((m - i) * a + (i + 1) * b) // m
            for i in range(n):
                print(".", end="")
            print()
    
    def main():
        ra = int(input("Digite seu RA: "))
        a = (ra // 10) % 10
        b = ra % 10
        misterio(6 * a, 6 * b)
    
    main()
    
  6. Uma matriz em Python é apenas uma lista de listas! Ainda vamos aprender mais sobre esta estrutura de dados, mas você já sabe simular códigos usando matrizes. Por exemplo, a matriz

    $$ mat_1 = \begin{bmatrix} 1 & 2 & 3\\
    4 & 5 & 6\\
    7 & 8 & 9\\
    \end{bmatrix} $$

    pode ser representada pela variável mat1 no trecho abaixo. O que contém a variável mat2 ao fim da execução do programa abaixo? Tente fazer sem o computador.

    mat1 = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]
    
    mat2 = [
        [0, 0 , 0],
        [0, 0 , 0],
        [0, 0 , 0],
    ]
    
    for i in range(3):
        for j in range(3):
            mat2[i][j] = mat1[j][i]
    

Algoritmos de ordenação

  1. Às vezes, a melhor maneira de descrever um algoritmo não é escrevendo.

    https://www.youtube.com/watch?v=lyZQPjUT5B4

    a) Faça um teste de mesa para um vetor com elementos $(5, 4, 3, 2, 1)$ e para um vetor com elementos $(1, 4, 3, 2, 5)$. Conte o número de vezes que trocamos dois elementos

    b) Você consegue dizer por que o algoritmo tem esse nome?

  2. Inconformado com a ordenação por bolha, em que os maiores elementos flutuam até o topo, como uma bolha, Joãozinho disse que esses elementos deveriam afundar até o fundo, como uma âncora. Assim, decidiu criar seu próprio algoritmo de ordenação.

    def anchor_sort(lista):
        n = len(lista)
        for i in range(1, n):
            a = i
            while a > 0:
                if lista[a] > lista[a-1]:
                    trocar(lista, a, a-1)
                a = a - 1
    

    a) Você concorda que algoritmo de Joãzinho está correto? Justifique.

    b) Explique o que esse algoritmo faz.

  3. Reescreva a função insertion_sort para que ela não utilize funções auxiliares.

  4. Crie uma função para determinar o número total de inversões em uma lista $a$. Uma inversão existe quando um elemento em uma posição $i < j$ é tal que $a[i] > a[j]$. Por exemplo, na lista $(10,4,6,1,2)$ existem 4 inversões para o número 10, 2 inversões para o número 4, 2 inversões para o número 6, nenhuma inversão para 1, e nenhuma para o 2. Portanto o total de inversões é 8.

  5. O algoritmo de ordenação por bolha pode ser implementado da seguinte maneira:

    def bubble_sort(lista):
        n = len(lista)
        for _ in range(n - 1):
            for i in range(n - 1):
                if lista[i] > lista[i + 1]:
                    aux = lista[i]
                    lista[i] = lista[i + 1]
                    lista[i + 1] = aux
    

    Simule o algoritmo ao ordenar a lista $(31,41,59,26,41,58,15,19)$ e conte quantas trocas foram feitas. Dê um exemplo de lista de tamanho 8 em que o número de trocas é mínimo e em que o número de trocas é máximo.

  6. Escreva uma função para ordenar uma lista de pessoas em ordem decrescente de idade e, havendo empate, em ordem crescente de nome. Uma pessoa é representada por uma tupla como ("Ana", 18), que representa a Ana que tem 18 anos.

Exercícios criativos

  1. Suponha que um time de voleibol é representado por uma string contendo o nome. Além disso, existe uma lista de tuplas representando os confrontos dos times, e.g.,

    confrontos = [
        ("Estaleiro", "Mavista"),
        ("Estaleiro", "Manos"),
        ("Estaleiro", "São Saulo"),
        ("Mavista", "Manos"),
        ("Mavista", "São Saulo"),
        ("Mavista", "Tio de Janeiro"),
        ("Tio de Janeiro", "Estaleiro"),
        ("Tio de Janeiro", "Manos"),
        ("Manos", "São Saulo"),
        ("São Saulo", "Tio de Janeiro"),
    ]
    

    Essa lista representa que o Estaleiro venceu o Mavista, mas foi derrotado pelo Tio de Janeiro.

    a) Para ordenar uma lista de times, não basta olhar para os nomes dos times: devemos prestar atenção às regras do campeonato! Crie uma função ordenar_times que respeita as regras do campeonato. Para isso, o algoritmo receberá como entrada, além da lista de nomes, uma função funcao_comparar. Essa função é chamada como funcao_comparar(time_x, time_y, confrontos) e devolve True sempre que time_x puder aparecer antes de time_y em uma lista ordenada.

    def ordenar_time(lista_nomes, funcao_comparar, confrontos):
        pass
    

    b) Implemente agora uma função comparar para ser usada como parâmetro da função de ordenação. Nesse campeonato, vem primeiro o time com maior número de vitórias; se houver empate, a ordem é desempatada pelo confronto direto.

    def comparar(time_x, time_y, confrontos):
        pass
    
  2. Obter números aleatórios é um aspecto delicado de Computação. A noção de aleatoriedade em Computação é bem distinta da noção da linguagem natural. Normalmente, quando falamos de números aleatórios estamos falando de uma sequência que satisfaz determinadas propriedades, chamada sequência pseudoaleatória. Em muitos casos, essa distinção é irrelevante; por exemplo quando queremos apenas embaralhar um conjunto de cartas. Em Python, a maneira de obter números aleatórios é usando o módulo random. Por exemplo, para escolher um número aleatório entre 1 e 10, incluindo os extremos, fazemos:

    import random
    
    numero = random.randint(1, 10)
    chute = int(input("Adivinhe em qual número pensei: "))
    if chute == numero:
        print("Você é de mais!")
    else:
        print(f"O número era {numero}.")
    

    Uma pessoa com humor aleatório, mas que está bem em 80% dos dias, bem poderia registrar o seguinte diário

    import random
    
    for dia in range(1, 11):
        if random.random() < 0.8:
            print(f"No dia {dia} estive feliz =)")
        else:
            print(f"No dia {dia} estive triste :(")
    

    Execute várias vezes os códigos acima e procure a documentação do módulo random.

    O objetivo dessa questão é escrever uma função que embaralha uma lista de inteiros. Você não pode utilizar uma lista auxiliar.