{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# EP1 - MAC0110 - Introdução à Computação"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NOME: insira seu nome\n",
    "\n",
    "NUSP: insira seu número USP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problema do Muro\n",
    "\n",
    "Nós temos dois tipos de tijolos, como mostrado na parte esquerda da figura abaixo. A ideia é construir uma mureta de altura 2 e comprimento `N`. A parte direita da figura ilustra uma forma de usar os dois tipos de tijolos para construir uma mureta de comprimento `N = 12`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Exemplo de muro para N = 12](1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Precisamos saber quantas formas distintas existem de construir a mureta com esses dois tipos de tijolos. Para isso, já temos duas observações: qualquer mureta de comprimento `N` vai terminar de uma das sete maneiras ilustradas abaixo e; o número de formas distintas de construir uma mureta de comprimento 2, 1 e 0 é, respectivamente, 5, 1 e 1 (Sim! Existe uma forma de construir a mureta de comprimento 0: usar nenhum tijolo)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Exemplo de muro para N = 12](2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Escreva uma função recursiva `muro(N)` que recebe o parâmetro `N` e devolve um inteiro que representa o número de formas distintas de construir uma mureta de comprimento `N`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Segue, abaixo, uma tabela com exemplos de N e seus resultados esperados:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| N | Resultado esperado |\n",
    "|--:|-------------------:|\n",
    "| 0 |                  1 |\n",
    "| 1 |                  1 |\n",
    "| 2 |                  5 |\n",
    "| 6 |                241 |\n",
    "|11 |              36543 |\n",
    "|30 |      7179637555201 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Instruções Gerais do EP1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Entregue apenas este notebook como resposta ao EP1. O nome do arquivo deve ser `<SEU NUSP>_EP1.ipynb` assim como nos outros exercícios;\n",
    "2. Você _DEVE_ usar recursão;\n",
    "3. Você está encarregado de testar sua resposta. Não há testes automatizados desta vez;\n",
    "4. Não é necessário testar para N grande! Na função puramente recursiva, para N = 40, leva quase 1 minuto para obter a resposta! Não testaremos para valores altos :)\n",
    "5. **BÔNUS:** Para melhorar a eficiência de sua resposta, você pode utilizar um vetor auxiliar que guarda os valores para os N já calculados (isto _NÃO É OBRIGATÓRIO_ )."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "muro (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# insira sua solução aqui\n",
    "\n",
    "function muro(n)\n",
    "    if n == 0\n",
    "        return 1\n",
    "    elseif n == 1\n",
    "        return 1\n",
    "    elseif n == 2\n",
    "        return 5\n",
    "    else\n",
    "        return muro(n - 1) + 4 * muro(n - 2) + 2 * muro(n - 3)\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "muro_com_vetor (generic function with 1 method)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# insira sua solução aqui\n",
    "\n",
    "visitados = [0 for i in 0:100]\n",
    "\n",
    "function muro_com_vetor(n)\n",
    "    if visitados[n + 1] != 0\n",
    "        return visitados[n + 1]\n",
    "    end\n",
    "\n",
    "    if n == 0\n",
    "        return 1\n",
    "    elseif n == 1\n",
    "        return 1\n",
    "    elseif n == 2\n",
    "        return 5\n",
    "    else\n",
    "        resultado = muro_com_vetor(n - 1) + 4 * muro_com_vetor(n - 2) + 2 * muro_com_vetor(n - 3)\n",
    "        visitados[n + 1] = resultado\n",
    "        return resultado\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0.004758 seconds (4.11 k allocations: 203.337 KiB)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "15196671"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@time muro(17)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0.030036 seconds (5.48 k allocations: 263.643 KiB)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "166337525546221569"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@time muro_com_vetor(40)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.3.1",
   "language": "julia",
   "name": "julia-1.3"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.3.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}