Algoritmos iterativos

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
```
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} $$
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
```
Escreva um programa que leia um número inteiro n e escreva uma figura similar à seguinte, mas com n linhas.
```
...*......*...
..***....***..
.*****..*****.
**************
```

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()

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

À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?
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.
Reescreva a função insertion_sort para que ela não utilize funções auxiliares.
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.
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.
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

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
```
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.