{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "591f918a",
   "metadata": {},
   "source": [
    "# Solução dos exercícios da aula 03"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62377442",
   "metadata": {},
   "source": [
    "### Exercício 1\n",
    "Modifique os programas acima para ler 7 notas no lugar de 5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f2134341",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Média:  6.7\n"
     ]
    }
   ],
   "source": [
    "# Programa para cálculo da média de 7 notas\n",
    "notas = [6, 7, 5, 8, 9, 4, 8]\n",
    "soma = 0\n",
    "i = 0\n",
    "while i < 7:\n",
    "    soma += notas[i]\n",
    "    i += 1\n",
    "print(f\"Média: {soma/i:4.1f}\")\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c671eb8",
   "metadata": {},
   "source": [
    "<!-- TEASER_END -->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "9dbc9362",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nota 0: 6\n",
      "Nota 1: 7\n",
      "Nota 2: 5\n",
      "Nota 3: 8\n",
      "Nota 4: 9\n",
      "Nota 5: 4\n",
      "Nota 6: 8\n",
      "Média:  6.7\n"
     ]
    }
   ],
   "source": [
    "# Versão do programa onde o professor pode entrar com 7 notas\n",
    "notas = [0,0,0,0,0,0,0]\n",
    "soma = 0\n",
    "i = 0\n",
    "while i < 7:\n",
    "    notas[i] = float(input(f\"Nota {i}: \"))\n",
    "    soma += notas[i]\n",
    "    i += 1\n",
    "print(f\"Média: {soma/i:4.1f}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1a1ba6d",
   "metadata": {},
   "source": [
    "### Exercício 2\n",
    "Reescreva o programa para calcular médias de modo que o professor primeiro entra com o número de notas e em seguida o programa lê este número de notas e calcula a média.\n",
    "\n",
    "[6, 7, 5, 8, 9, 4, 8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d8e22688",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Entre com o número de notas: 7\n",
      "Nota 0: 6\n",
      "Nota 1: 7\n",
      "Nota 2: 5\n",
      "Nota 3: 8\n",
      "Nota 4: 9\n",
      "Nota 5: 4\n",
      "Nota 6: 8\n",
      "Média:  6.7\n"
     ]
    }
   ],
   "source": [
    "notas = []\n",
    "soma = 0\n",
    "i = 0\n",
    "num_notas = int(input(f\"Entre com o número de notas: \"))\n",
    "while i < num_notas:\n",
    "    notas.append(float(input(f\"Nota {i}: \")))\n",
    "    i += 1\n",
    "i = 0    \n",
    "while i < num_notas:\n",
    "    soma += notas[i]\n",
    "    i += 1\n",
    "print(f\"Média: {soma/i:4.1f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7ab4ca9",
   "metadata": {},
   "source": [
    "### Exercício 3\n",
    "Faça um programa que percorra duas listas inteiras e gere uma terceira sem elementos repetidos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "260fd367",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 5, 6, 7, 0, 4, 8]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L1 = [1,2,3,5,6,7] # Primeira lista\n",
    "L2 = [1,0,3,4,0,7,8] # Segunda lista\n",
    "n1 = len(L1) # Comprimento da primeira lista\n",
    "n2 = len(L2) # Comprimento da segunda lista\n",
    "L = [] # Lista que será gerada\n",
    "i = 0 # Contador\n",
    "\n",
    "while i < n1: # Vamos percorrer a primeira lista\n",
    "    x = L1[i]\n",
    "    k = 0\n",
    "    n = len(L)\n",
    "    achou = False\n",
    "    while k < n:  # Vamos percorrer a terceira que estamos \n",
    "                  # construindo\n",
    "        y = L[k]\n",
    "        if y == x: # Achou um igual. Não pode ser inserido\n",
    "            achou = True\n",
    "            break\n",
    "        k += 1\n",
    "    if not achou:\n",
    "        L.append(x)\n",
    "    i += 1\n",
    "    \n",
    "# Repetir com a lista 2:\n",
    "i = 0\n",
    "while i < n2: # Vamos percorrer a primeira lista\n",
    "    x = L2[i]\n",
    "    k = 0\n",
    "    n = len(L)\n",
    "    achou = False\n",
    "    while k < n:  # Vamos percorrer a terceira que estamos \n",
    "                  # construindo\n",
    "        y = L[k]\n",
    "        if y == x: # Achou um igual. Não pode ser inserido\n",
    "            achou = True\n",
    "            break\n",
    "        k += 1\n",
    "    if not achou:\n",
    "        L.append(x)\n",
    "    i += 1\n",
    "\n",
    "        \n",
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3849eacd",
   "metadata": {},
   "source": [
    "### Exercício 4\n",
    "O que acontece quando não verificamos se a lista está vazia antes de chamar o método `pop`?\n",
    "\n",
    "\n",
    "Que tal testar? O bom do computador é que nada de ruim pode acontecer. (ou pode...)\n",
    "\n",
    "Para testar vamos diminuir o comprimento da file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "10e41bcb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Existem 4 clientes na fila\n",
      "Fila atual: [1, 2, 3, 4]\n",
      "Digite F para adicionar um cliente ao fim da fila, \n",
      "ou A para realizar o atendimento. S para sair.\n",
      "Operação (F, A ou S): A\n",
      "Cliente 1 atendido\n",
      "\n",
      "Existem 3 clientes na fila\n",
      "Fila atual: [2, 3, 4]\n",
      "Digite F para adicionar um cliente ao fim da fila, \n",
      "ou A para realizar o atendimento. S para sair.\n",
      "Operação (F, A ou S): A\n",
      "Cliente 2 atendido\n",
      "\n",
      "Existem 2 clientes na fila\n",
      "Fila atual: [3, 4]\n",
      "Digite F para adicionar um cliente ao fim da fila, \n",
      "ou A para realizar o atendimento. S para sair.\n",
      "Operação (F, A ou S): A\n",
      "Cliente 3 atendido\n",
      "\n",
      "Existem 1 clientes na fila\n",
      "Fila atual: [4]\n",
      "Digite F para adicionar um cliente ao fim da fila, \n",
      "ou A para realizar o atendimento. S para sair.\n",
      "Operação (F, A ou S): A\n",
      "Cliente 4 atendido\n",
      "\n",
      "Existem 0 clientes na fila\n",
      "Fila atual: []\n",
      "Digite F para adicionar um cliente ao fim da fila, \n",
      "ou A para realizar o atendimento. S para sair.\n",
      "Operação (F, A ou S): A\n"
     ]
    },
    {
     "ename": "IndexError",
     "evalue": "pop from empty list",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m/tmp/ipykernel_3519/3875226094.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      9\u001b[0m     \u001b[0moperação\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0minput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Operação (F, A ou S): \"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     10\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0moperação\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"A\"\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m         \u001b[0matendido\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfila\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     12\u001b[0m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34mf\"Cliente {atendido} atendido\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m     \u001b[0;32melif\u001b[0m \u001b[0moperação\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"F\"\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: pop from empty list"
     ]
    }
   ],
   "source": [
    "# Simulação de fila de banco:\n",
    "último = 4  # Tamanho menor\n",
    "fila = list(range(1, último + 1))\n",
    "while True:\n",
    "    print(f\"\\nExistem {len(fila)} clientes na fila\")\n",
    "    print(f\"Fila atual: {fila}\")\n",
    "    print(\"Digite F para adicionar um cliente ao fim da fila, \")\n",
    "    print(\"ou A para realizar o atendimento. S para sair.\")\n",
    "    operação = input(\"Operação (F, A ou S): \")\n",
    "    if operação == \"A\":\n",
    "        atendido = fila.pop(0)\n",
    "        print(f\"Cliente {atendido} atendido\")\n",
    "    elif operação == \"F\":\n",
    "        último += 1 # Incrementa o ticket\n",
    "        fila.append(último)\n",
    "    elif operação == 'S':\n",
    "        break\n",
    "    else:\n",
    "        print(\"Operação inválida. Digite apenas A, F ou S!\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69ec0fdd",
   "metadata": {},
   "source": [
    "**É dá erro! Não é possível tirar um elemento de uma lista vazia**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4300105b",
   "metadata": {},
   "source": [
    "### Exercício 5\n",
    "Altere o programa da fila de modo que se possa trabalhar com vários comandos digitados de uma só vez. No programa acima, apenas uma operação pode ser digitada por vez. Faça com que o programa aceite strings com vários comandos\n",
    "\n",
    "Exemplo: FFFAAAS significa três chegadas de novos clientes, três atendimentos e saída do programa."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "b49419a4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Existem 10 clientes na fila\n",
      "Fila atual: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n",
      "A operação é F.\n",
      "\n",
      "Existem 11 clientes na fila\n",
      "Fila atual: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]\n",
      "A operação é F.\n",
      "\n",
      "Existem 12 clientes na fila\n",
      "Fila atual: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]\n",
      "A operação é F.\n",
      "\n",
      "Existem 13 clientes na fila\n",
      "Fila atual: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]\n",
      "A operação é A.\n",
      "Cliente 1 atendido\n",
      "\n",
      "Existem 12 clientes na fila\n",
      "Fila atual: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]\n",
      "A operação é A.\n",
      "Cliente 2 atendido\n",
      "\n",
      "Existem 11 clientes na fila\n",
      "Fila atual: [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]\n",
      "A operação é A.\n",
      "Cliente 3 atendido\n",
      "\n",
      "Existem 10 clientes na fila\n",
      "Fila atual: [4, 5, 6, 7, 8, 9, 10, 11, 12, 13]\n",
      "A operação é S.\n"
     ]
    }
   ],
   "source": [
    "último = 10\n",
    "fila = list(range(1, último + 1))\n",
    "operações = \"FFFAAAS\"\n",
    "Nop = len(operações)\n",
    "i = 0\n",
    "while i < Nop:\n",
    "    print(f\"\\nExistem {len(fila)} clientes na fila\")\n",
    "    print(f\"Fila atual: {fila}\")\n",
    "    operação = operações[i]\n",
    "    print(f\"A operação é {operação}.\")\n",
    "    i += 1  # Não podemos esquecer...\n",
    "    if operação == \"A\":\n",
    "        if len(fila) > 0:\n",
    "            atendido = fila.pop(0)\n",
    "            print(f\"Cliente {atendido} atendido\")\n",
    "        else:\n",
    "            print(\"Fila vazia! Nenhum cliente para atender.\")\n",
    "    elif operação == \"F\":\n",
    "        último += 1 # Incrementa o ticket\n",
    "        fila.append(último)\n",
    "    elif operação == 'S':\n",
    "        break\n",
    "    else:\n",
    "        print(\"Operação inválida. Ela deve ser apenas A, F ou S!\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97f2aa77",
   "metadata": {},
   "source": [
    "### Exercício 6\n",
    "Faça um programa que leia uma expressão com parênteses. Usando pilhas, verifique se os parênteses foram abertos e fechados na ordem correta. Exemplo:\n",
    "\n",
    " * (()) OK\n",
    " * ()()(()()) OK\n",
    " * ()) Erro\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "d8e91de4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Erro\n"
     ]
    }
   ],
   "source": [
    "expressão = \"((())()(())))\"\n",
    "n = len(expressão)\n",
    "pilha = []\n",
    "i = 0\n",
    "ocorreu_erro = False\n",
    "while i < n:\n",
    "    c = expressão[i]\n",
    "    i += 1\n",
    "    if c == ')':\n",
    "        if len(pilha) > 0:\n",
    "            pilha.pop(-1)\n",
    "        else:\n",
    "            ocorreu_erro = True\n",
    "            break\n",
    "    elif c == '(':\n",
    "        pilha.append(1)\n",
    "    else: # Qualquer outro caracter, ignorar!\n",
    "        continue  \n",
    "if len(pilha) > 0:  # Se sobrou algo na pila, tá desbalanceado\n",
    "    ocorreu_erro = True\n",
    "\n",
    "if ocorreu_erro:\n",
    "    print(\"Erro\")\n",
    "else:\n",
    "    print(\"Ok\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d626b2e",
   "metadata": {},
   "source": [
    "### Exercício 7\n",
    "Modifique o programa de modo que  realize a mesma tarefa sem usar a variável `achou`. Dica: observe a condição de saída do `while`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "ad04251c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Digite o valor a procurar: 6\n",
      "6 não foi encontrado na lista.\n"
     ]
    }
   ],
   "source": [
    "L = [15, 7, 27, 39]\n",
    "p = int(input(\"Digite o valor a procurar: \"))\n",
    "i = 0\n",
    "while i < len(L):\n",
    "    if L[i] == p:\n",
    "        print(f\"{p} foi encontrado na posição {i}.\")\n",
    "        break\n",
    "    i += 1\n",
    "else:\n",
    "    print(f\"{p} não foi encontrado na lista.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4260b766",
   "metadata": {},
   "source": [
    "### Exercício 8\n",
    "Modifique o exemplo para pesquisar dois valores. Em vez de apenas `p`, leia outro valor `v` que também será procurado. Na impressão, indique qual dos dois valores foi encontrado primeiro."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "9ea41d9f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Digite o valor a procurar: 5\n",
      "Digite o valor a procurar: 6\n",
      "5 não foi encontrado na lista.\n",
      "6 não foi encontrado na lista.\n"
     ]
    }
   ],
   "source": [
    "L = [15, 7, 27, 39]\n",
    "p = int(input(\"Digite o valor a procurar: \"))\n",
    "v = int(input(\"Digite o valor a procurar: \"))\n",
    "achou_p = False\n",
    "achou_v = False\n",
    "i = 0\n",
    "while i < len(L):\n",
    "    if L[i] == p:\n",
    "        achou_p = True\n",
    "        break\n",
    "    i += 1\n",
    "ip = i\n",
    "i = 0\n",
    "while i < len(L):\n",
    "    if L[i] == v:\n",
    "        achou_v = True\n",
    "        break\n",
    "    i += 1\n",
    "iv = i\n",
    "\n",
    "if achou_p:\n",
    "    print(f\"{p} foi encontrado na posição {ip}.\")\n",
    "else:\n",
    "    print(f\"{p} não foi encontrado na lista.\")\n",
    "\n",
    "if achou_v:\n",
    "    print(f\"{v} foi encontrado na posição {iv}.\")\n",
    "else:\n",
    "    print(f\"{v} não foi encontrado na lista.\")\n",
    "if achou_p and achou_v:\n",
    "    if ip < iv:\n",
    "        print(f\"{p} foi achado antes que {v}\")\n",
    "    elif iv < ip:\n",
    "        print(f\"{v} foi achado antes que {p}\")\n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6683c29b",
   "metadata": {},
   "source": [
    "### Exercício 9\n",
    "Tente converter este programa (exemplo acima)\n",
    "\n",
    "```python\n",
    "# Programa para adicionar números a uma lista\n",
    "L = []\n",
    "while True:\n",
    "    n = int(input(\"Digite um número (0 sai): \"))\n",
    "    if n == 0:\n",
    "        break\n",
    "    L.append(n)\n",
    "```\n",
    "usando `for`.\n",
    "\n",
    "Explique se `for` pode ser sempre usado no lugar de `while` e porquê."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54c9b0bd",
   "metadata": {},
   "source": [
    "Estritamente falando, este programa não poderia ser escrito usando `for` pois não sabemos o número de repetições necessárias. O usuário pode parar a qualquer momento!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2dbf23fe",
   "metadata": {},
   "source": [
    "Tendo dito isso, este programa tem um problema: pode não sair nunca. É muito comum que se tenha um limite. Com esse limite (arbitrário vai depender do contexto), podemos usar o `for`. Sempre que possível, é recomendado fazer isso.\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "5dd7e5e5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Digite um número (0 sai): 1\n",
      "Digite um número (0 sai): 2\n",
      "Digite um número (0 sai): 3\n",
      "Digite um número (0 sai): 4\n",
      "Digite um número (0 sai): 5\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nmax = 5\n",
    "L = []\n",
    "for i in range(nmax):\n",
    "    n = int(input(\"Digite um número (0 sai): \"))\n",
    "    if n == 0:\n",
    "        break\n",
    "    L.append(n)\n",
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56244a03",
   "metadata": {},
   "source": [
    "### Exercício 10\n",
    "Escreva um programa que acha o menor elemento de uma lista"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "d742b3f8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O menor elemento da lista é 1.\n"
     ]
    }
   ],
   "source": [
    "L = [123,15, 12, 4352, 1, 4567]\n",
    "emin = L[0]\n",
    "for e in L:\n",
    "    if e < emin:\n",
    "        emin = e\n",
    "print(f\"O menor elemento da lista é {emin}.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "191de400",
   "metadata": {},
   "source": [
    "### Exercício 11\n",
    "Modifique o programa para achar o máximo de modo que encontre o máximo mas também encontre o índice onde este máximo ocorre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "b72d7f7b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O maior elemento da lista é 4567 e ocorre no índice 5.\n"
     ]
    }
   ],
   "source": [
    "L = [123,15, 12, 4352, 1, 4567]\n",
    "emax = L[0]\n",
    "imax = 0\n",
    "for i,e in enumerate(L):\n",
    "    if e > emax:\n",
    "        emax = e\n",
    "        imax = i\n",
    "print(f\"O maior elemento da lista é {emax} e ocorre no índice {imax}.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a89b8252",
   "metadata": {},
   "source": [
    "### Exercício 12\n",
    "Escreva um programa que encontra o máximo e o mínimo de uma lista"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "c4fa784d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O menor elemento da lista é 1.\n",
      "O maior elemento da lista é 4567.\n"
     ]
    }
   ],
   "source": [
    "L = [123,15, 12, 4352, 1, 4567]\n",
    "emin = L[0]\n",
    "emax = emin\n",
    "for e in L:\n",
    "    if e < emin:\n",
    "        emin = e\n",
    "    elif e > emax:\n",
    "        emax = e\n",
    "        \n",
    "print(f\"O menor elemento da lista é {emin}.\")\n",
    "print(f\"O maior elemento da lista é {emax}.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cdb25c72",
   "metadata": {},
   "source": [
    "### Exercício 13\n",
    "Modifique o programa anterior para que ordene a lista em modo decrescente"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "770120db",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9, 8, 6, 4, 3, 2]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L = [9, 2, 4, 3, 8, 6]\n",
    "N = len(L)\n",
    "for i in range(N):\n",
    "    trocou = False\n",
    "    for k in range(N-i-1):\n",
    "        if L[k] < L[k+1]: # Inverter a posição\n",
    "            trocou = True\n",
    "            tmp = L[k]\n",
    "            L[k] = L[k+1]\n",
    "            L[k+1] = tmp\n",
    "    if not trocou:\n",
    "        break\n",
    "\n",
    "L\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "625c48a3",
   "metadata": {},
   "source": [
    "### Exercício 14\n",
    "O que acontece se você tentar usar o programa acima com uma lista de strings? Tente e brinque um pouquinho.\n",
    "\n",
    "Por outro lado, o que acontece se misturarmos números e strings?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "557ab219",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ZEBRA', 'TELEFONE', 'PULGA', 'LIXO', 'FACA', 'BOLA']"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L = [\"LIXO\", \"BOLA\", \"ZEBRA\", \"TELEFONE\", \"FACA\", \"PULGA\"]\n",
    "N = len(L)\n",
    "for i in range(N):\n",
    "    trocou = False\n",
    "    for k in range(N-i-1):\n",
    "        if L[k] < L[k+1]: # Inverter a posição\n",
    "            trocou = True\n",
    "            tmp = L[k]\n",
    "            L[k] = L[k+1]\n",
    "            L[k+1] = tmp\n",
    "    if not trocou:\n",
    "        break\n",
    "\n",
    "L\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "4335dc87",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'<' not supported between instances of 'str' and 'int'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m/tmp/ipykernel_3519/3902378855.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mtrocou\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mk\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m         \u001b[0;32mif\u001b[0m \u001b[0mL\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mL\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# Inverter a posição\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      7\u001b[0m             \u001b[0mtrocou\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m             \u001b[0mtmp\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mL\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: '<' not supported between instances of 'str' and 'int'"
     ]
    }
   ],
   "source": [
    "L = [\"LIXO\", 3, \"ZEBRA\", \"TELEFONE\", \"FACA\", \"PULGA\"]\n",
    "N = len(L)\n",
    "for i in range(N):\n",
    "    trocou = False\n",
    "    for k in range(N-i-1):\n",
    "        if L[k] < L[k+1]: # Inverter a posição\n",
    "            trocou = True\n",
    "            tmp = L[k]\n",
    "            L[k] = L[k+1]\n",
    "            L[k+1] = tmp\n",
    "    if not trocou:\n",
    "        break\n",
    "\n",
    "L\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fa2438d",
   "metadata": {},
   "source": [
    "### Exercício 15\n",
    "Um aspecto importante é saber p quão eficiente é este algorítimo. Para tanto, precisamos saber quanto tempo leva para ordenar a lista. \n",
    "\n",
    "Mas isso vai depender do tamanho da lista, do tipo de dados dentro da lista e do computador que está executando o programa. No entanto, para efeito comparativo, podemos estimar o número de operações. Neste caso, podemos falar em quantas comparações foram realizadas (A linha `L[k] > L[k+1]`). Também é interessante saber quantas inversões foram realizadas. Estime esse custo para os dois seguintes casos:\n",
    "\n",
    " 1. Uma lista ordenada de maneira crescente de comprimento N\n",
    " 2. Uma lista ordenada de maneira decrescente de comprimento N\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "ab62fb5e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(18, 153, 153)"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#L = [9, 2, 4, 3, 8, 6]\n",
    "#L = list(range(18))\n",
    "L = list(range(18))[::-1]\n",
    "N = len(L)\n",
    "ntroca = 0\n",
    "ncomp = 0\n",
    "for i in range(N):\n",
    "    trocou = False\n",
    "    for k in range(N-i-1):\n",
    "        ncomp += 1\n",
    "        if L[k] > L[k+1]: # Inverter a posição\n",
    "            ntroca += 1\n",
    "            trocou = True\n",
    "            tmp = L[k]\n",
    "            L[k] = L[k+1]\n",
    "            L[k+1] = tmp\n",
    "    if not trocou:\n",
    "        break\n",
    "\n",
    "N, ncomp, ntroca\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c7db0e2",
   "metadata": {},
   "source": [
    "| Lista       | Compr. | Núm comparações | Núm trocas |\n",
    "| ----------- | ------ | --------------- | ---------- |\n",
    "| Original    |  6     |    12           |   7        |\n",
    "| Crescente   |  6     |     5           |    0       |\n",
    "| Crescente   |  12    |     11          |    0       |\n",
    "| Crescente   |  18    |     17          |    0       |\n",
    "| Decrescente |   6    |     15          |   15       |\n",
    "| Decrescente |   12   |     66          |   66       |\n",
    "| Decrescente |   18   |     153         |   153      |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a326a47",
   "metadata": {},
   "source": [
    "Assim, para uma lista ordenada de N elementos, o algorítimo fará N-1 comparações e nenhuma troca. O custo é linear: $\\mathcal{O}(N)$\n",
    "\n",
    "Por outro lado se a lista estiver ordenada em ordem contrária, o custo aumenta rapidamente segundo esta equação:\n",
    "\n",
    "$$\n",
    "N = \\frac{N\\times(N-1)}{2}\n",
    "$$\n",
    "\n",
    "Isso é um custo de ordem $\\mathcal{O}(N^2)$. Dobrou o tamanho da lista, quadruplicou o custo! Este não é um algorítimo muito bom..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8455930f",
   "metadata": {},
   "source": [
    "### Exercício 16\n",
    "Explore os métodos das listas\n",
    "\n",
    "Não tem solução...\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c91d94d9",
   "metadata": {},
   "source": [
    "### Exercício 17\n",
    "Não são apenas as listas que têm métodos. Números e strings também têm métodos. Explore-os da mesma maneira que você fez com os métodos das listas.\n",
    "\n",
    "Não tem solução"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}