10_exercicios.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "## Exercícios sobre recursão\n",
    "\n",
    "1. Implemente a função `potência`, $f(x,y) = x^y$, utilizando recursão.\n",
    "\n",
    "Começemos implementando o cálculo da potência iterativa."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2023-06-08T04:01:06.401972323Z",
     "start_time": "2023-06-08T04:01:06.286281287Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "16\n"
     ]
    }
   ],
   "source": [
    "def potencia_y_inteiro_positivo_iterativo(x,y):\n",
    "    resultado = 1\n",
    "    for i in range(y):\n",
    "        resultado *= x\n",
    "    return resultado\n",
    "\n",
    "print(potencia_y_inteiro_positivo_iterativo(2,3))\n",
    "print(potencia_y_inteiro_positivo_iterativo(2,4))"
   ]
  },
  {
   "cell_type": "markdown",
   "source": [
    "Para implementarmos a mesma função de maneira recursiva, devemos substituir o laço por recursividade."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "16\n"
     ]
    }
   ],
   "source": [
    "def potencia_y_inteiro_positivo(x,y):\n",
    "    if y == 0:\n",
    "        # Condição de parada\n",
    "        return 1\n",
    "    else:\n",
    "        # Função chamada recursivamente\n",
    "        # desmembra a potência para uma\n",
    "        # multiplicação do exponenciando\n",
    "        return x*potencia_y_inteiro_positivo(x, y-1)\n",
    "\n",
    "print(potencia_y_inteiro_positivo(2,3))\n",
    "print(potencia_y_inteiro_positivo(2,4))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-06-08T04:01:06.506346548Z",
     "start_time": "2023-06-08T04:01:06.299746268Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Também podemos extender para potências negativas inteiras, como citado em sala de aula.\n",
    "\n",
    "Uma potência negativa nada mais é que o inverso da potência positiva."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.5\n",
      "0.25\n"
     ]
    }
   ],
   "source": [
    "def potencia_y_inteiro_negativo(x,y):\n",
    "    return 1/potencia_y_inteiro_positivo(x,-y)\n",
    "\n",
    "print(potencia_y_inteiro_negativo(2,-1))\n",
    "print(potencia_y_inteiro_negativo(2,-2))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-06-08T04:01:06.510253390Z",
     "start_time": "2023-06-08T04:01:06.321424511Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Podemos envelopar ambas em uma mesma função acessível aos usuários."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.5\n",
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "def potencia_y_inteiro(x,y):\n",
    "    if y < 0:\n",
    "        return potencia_y_inteiro_negativo(x,y)\n",
    "    else:\n",
    "        return potencia_y_inteiro_positivo(x,y)\n",
    "\n",
    "print(potencia_y_inteiro(2,-1))\n",
    "print(potencia_y_inteiro(2,0))\n",
    "print(potencia_y_inteiro(2,1))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-06-08T04:01:06.511507957Z",
     "start_time": "2023-06-08T04:01:06.338729288Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Também poderíamos tratar casos extras, como potências com valor absoluto menor que 1 (raízes) e outros exponentes reais.\n",
    "\n",
    "Porém, é muito complexo e foge do propósito do exercício.\n",
    "\n",
    "A título de curiosidade, [aqui está a implementação padrão do cálculo do exponente do Python](https://github.com/python/cpython/blob/main/Modules/mathmodule.c#L2967), que chama a função `pow` da biblioteca C.\n",
    "\n",
    "A biblioteca C por sua vez [implementa o cálculo](https://github.com/JuliaMath/openlibm/blob/master/src/e_pow.c) conforme as especificações do IEEE 754."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "2. Implemente uma função que encontra recursivamente os valores máximo e mínimo de uma sequência.\n",
    "\n",
    "Podemos abordar uma estratégia buscando na ida (antes de chamar a recursão), ou na volta (quando voltamos da recursão)."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 9)\n",
      "(1, 9)\n"
     ]
    }
   ],
   "source": [
    "def busca_min_max_volta(sequencia):\n",
    "    if len(sequencia) == 1:\n",
    "        # Caso só tenha um elemento, ele é mínimo e máximo\n",
    "        return sequencia[0], sequencia[0]\n",
    "    elif len(sequencia) == 2:\n",
    "        # Retorna máximo e mínimo na volta\n",
    "        if sequencia[0] > sequencia[1]:\n",
    "            return sequencia[1], sequencia[0]\n",
    "        return sequencia\n",
    "    # Caso não seja nenhuma das condições de parada,\n",
    "    # busca o mínimo e máximo no resto da sequência\n",
    "    min, max = busca_min_max_volta(sequencia[1:])\n",
    "\n",
    "    # E depois compara com o primeiro valor da sequência\n",
    "    if min > sequencia[0]:\n",
    "        min = sequencia[0]\n",
    "    if max < sequencia[0]:\n",
    "        max = sequencia[0]\n",
    "    return min,max\n",
    "\n",
    "print(busca_min_max_volta([9, 3, 1, 7]))\n",
    "print(busca_min_max_volta([9, 3, 1, 2, 7]))\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-06-08T04:01:06.512595668Z",
     "start_time": "2023-06-08T04:01:06.349704532Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Também podemos fazer esta busca na ida, descartando sempre o menor entre os dois primeiros valores."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 9)\n",
      "(1, 9)\n"
     ]
    }
   ],
   "source": [
    "def busca_min_max_ida(sequencia, last_max=-999999999999, last_min=999999999999999):\n",
    "    # Casos de parada, sequência já totalmente pesquisada\n",
    "    if len(sequencia) == 0:\n",
    "        return last_min, last_max\n",
    "    # Ou sequência com apenas um valor restante\n",
    "    elif len(sequencia) == 1:\n",
    "        if sequencia[0] < last_min:\n",
    "            last_min = sequencia[0]\n",
    "        if sequencia[0] > last_max:\n",
    "            last_max = sequencia[0]\n",
    "        return last_min, last_max\n",
    "\n",
    "    # Busca o menor elemento entre os dois\n",
    "    if sequencia[0] < sequencia[1]:\n",
    "        min, max = sequencia[0], sequencia[1]\n",
    "    else:\n",
    "        min, max = sequencia[1], sequencia[0]\n",
    "    # Se máximos/mínimos já conhecidos forem maiores/menores,\n",
    "    # use eles\n",
    "    if last_max > max:\n",
    "        max = last_max\n",
    "    if last_min < min:\n",
    "        min = last_min\n",
    "    # Busca recursivamente\n",
    "    return busca_min_max_ida(sequencia[2:], last_max=max, last_min=min)\n",
    "\n",
    "print(busca_min_max_ida([9, 3, 1, 7]))\n",
    "print(busca_min_max_ida([9, 3, 1, 2, 7]))\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-06-08T04:01:06.513742771Z",
     "start_time": "2023-06-08T04:01:06.371282947Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Exercícios sobre ordenação"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Exercícios sobre busca"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Exercícios sobre tabelas de hash\n",
    "\n",
    "1. Dada uma tabela de hash com 5 posições, adicione os elementos listados a partir do cálculo do hash de suas respectivas chaves. A função de hash é dada pelo módulo por 5 do resultado da operação XOR entre os caracteres de uma chave de tipo string."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Chave 'um' resulta no hash '4'\n",
      "Chave 'dois' resulta no hash '2'\n",
      "Chave 'tres' resulta no hash '1'\n",
      "Chave 'quatro' resulta no hash '2'\n",
      "Chave 'cinco' resulta no hash '4'\n"
     ]
    }
   ],
   "source": [
    "def hash(chave):\n",
    "    temp = 0\n",
    "    for caractere in chave:\n",
    "        temp ^= ord(caractere)\n",
    "    return temp % 5\n",
    "\n",
    "for chave in [\"um\", \"dois\", \"tres\", \"quatro\", \"cinco\"]:\n",
    "    print(f\"Chave \\'{chave}\\' resulta no hash \\'{hash(chave)}\\'\")"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-06-08T04:01:06.537415163Z",
     "start_time": "2023-06-08T04:01:06.377898351Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Com o cálculo do hash, podemos criar nosso dicionário."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hash '0' contém os seguintes pares chave-valor:[]\n",
      "Hash '1' contém os seguintes pares chave-valor:[('tres', 3)]\n",
      "Hash '2' contém os seguintes pares chave-valor:[('dois', 2), ('quatro', 4)]\n",
      "Hash '3' contém os seguintes pares chave-valor:[]\n",
      "Hash '4' contém os seguintes pares chave-valor:[('um', 1), ('cinco', 5)]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "class dicionario:\n",
    "    # Cria uma lista para cada entrada de hash\n",
    "    def __init__(self):\n",
    "        self.hash_table = [[], [], [], [], []]\n",
    "\n",
    "    # Calcula hash da chave e insere o par na lista do hash correspondente\n",
    "    def insere_chave_valor(self, chave, valor):\n",
    "        hash_da_chave = hash(chave)\n",
    "        self.hash_table[hash_da_chave].append((chave, valor))\n",
    "\n",
    "    # Transforma a tabela de hash em um texto para impressão\n",
    "    def __str__(self):\n",
    "        saida = \"\"\n",
    "        for hash in range(5):\n",
    "            saida += f\"Hash \\'{hash}\\' contém os seguintes pares chave-valor:{self.hash_table[hash]}\\n\"\n",
    "        return saida\n",
    "\n",
    "teste = dicionario()\n",
    "# Insere elementos no dicionário\n",
    "teste.insere_chave_valor(\"um\", 1)\n",
    "teste.insere_chave_valor(\"dois\", 2)\n",
    "teste.insere_chave_valor(\"tres\", 3)\n",
    "teste.insere_chave_valor(\"quatro\", 4)\n",
    "teste.insere_chave_valor(\"cinco\", 5)\n",
    "# Imprime dicionário\n",
    "print(teste)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-06-08T04:01:06.538015861Z",
     "start_time": "2023-06-08T04:01:06.419552462Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-06-08T04:01:06.538176014Z",
     "start_time": "2023-06-08T04:01:06.419863150Z"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}