06.Números Binários, Laços Encaixados.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\" style=\"margin-top: 1em;\"><ul class=\"toc-item\"><li><span><a href=\"#Representações-Binárias-e-Decimais\" data-toc-modified-id=\"Representações-Binárias-e-Decimais-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Representações Binárias e Decimais</a></span><ul class=\"toc-item\"><li><span><a href=\"#Conversão-Binário-Decimal\" data-toc-modified-id=\"Conversão-Binário-Decimal-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Conversão Binário-Decimal</a></span></li><li><span><a href=\"#Conversão-Decimal-Binária\" data-toc-modified-id=\"Conversão-Decimal-Binária-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Conversão Decimal-Binária</a></span></li><li><span><a href=\"#Exercício\" data-toc-modified-id=\"Exercício-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Exercício</a></span></li></ul></li><li><span><a href=\"#Laços-Encaixados\" data-toc-modified-id=\"Laços-Encaixados-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Laços Encaixados</a></span><ul class=\"toc-item\"><li><span><a href=\"#Equações-Lineares\" data-toc-modified-id=\"Equações-Lineares-2.1\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Equações Lineares</a></span></li><li><span><a href=\"#Mega-Sena\" data-toc-modified-id=\"Mega-Sena-2.2\"><span class=\"toc-item-num\">2.2&nbsp;&nbsp;</span>Mega-Sena</a></span></li><li><span><a href=\"#Exercícios\" data-toc-modified-id=\"Exercícios-2.3\"><span class=\"toc-item-num\">2.3&nbsp;&nbsp;</span>Exercícios</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Representações Binárias e Decimais"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conversão Binário-Decimal\n",
    "Sabemos que um computador armazena todas as informações na representação binária. Portanto, é útil saber como converter valores binários em decimal e vice versa. Dado um número na sua representação binária $b_{n}b_{n−1} . . . b_{2}b_{1}b_{0}$, este corresponde na forma decimal à:\n",
    "$$\\sum_{i=0}^{n} b_{i} * 2^{i}$$\n",
    "\n",
    "Exemplos:\n",
    "\n",
    "$$101 = 2^{2} + 2^{0} = 5$$\n",
    "\n",
    "$$1001110100 = 2^{9} + 2^{6} + 2^{5} + 2^{4} + 2^{2} = 512 + 64 + 32 + 16 + 4 = 628$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Vamos supor que lemos do teclado um inteiro na sua representação binária.\n",
    "Ou seja, ao lermos n = 111 assumimos que este é o número binário (e não cento e onze).\n",
    "Como transformar este número no correspondente valor em decimal (7 neste caso)?\n",
    "\n",
    "Basta usarmos a expressão:\n",
    "$$\\sum_{i=0}^{n} b_{i} * 2^{i}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Mas, para tal, precisamos recuperar os dígitos individuais do número.\n",
    "\n",
    "- Note que $n\\ \\%\\ 10$ recupera o último dígito de n.\n",
    "- Note que $n\\ //\\ 10$ remove o último dígito de $n$, pois ocorre a divisão inteira por 10.\n",
    "\n",
    "Exemplo:\n",
    "Com $n = 345$, ao fazermos $n\\ \\%\\ 10$ obtemos $5$. E ao fazermos $n\\ //\\ 10$ obtemos $34$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O programa abaixo imprime cada um dos dígitos de $n$ separadamente:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = int(input(\"Digite um número:\"))\n",
    "while n != 0:\n",
    "    digito = n % 10\n",
    "    print(digito, end=\" \")\n",
    "    n = n // 10\n",
    "print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Para transformar um número em binário para decimal, devemos gerar as potências $2^{0}, . . . , 2^{n}$, e multiplicar cada potência $2^{i}$ pelo i-ésimo dígito. E, finalmente, para armazenar a soma $\\sum_{i=0}^{n} b_{i} * 2^{i}$ usamos uma variável acumuladora:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = int(input(\"Digite um número na representação binária:\"))\n",
    "soma = 0\n",
    "potencia = 1\n",
    "while n != 0:\n",
    "    digito = n % 10\n",
    "    soma += potencia * digito\n",
    "    potencia *= 2\n",
    "    n //= 10\n",
    "print(\"Valor em decimal é: \", soma)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conversão Decimal-Binária\n",
    "Dado um número em decimal, vamos obter o correspondente em binário. Qualquer decimal pode ser escrito como uma soma de potências de 2:\n",
    "\n",
    "$$5 = 2^{2} + 2^{0}$$\n",
    "$$13 = 2^{3} + 2^{2} + 2^{0}$$\n",
    "\n",
    "Nesta soma, para cada potência $2^{i}$ , sabemos que na representação em binário haverá um $1$ no dígito $i$. Exemplo: $13 = 1101$.  O que acontece se fizermos sucessivas divisões por $2$ de um número decimal?\n",
    "- 13/2 = 6 com resto 1\n",
    "- 6/2 = 3 com resto 0\n",
    "- 3/2 = 1 com resto 1\n",
    "- 1/2 = 0 com resto 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Dado um número $n$ na representação decimal, fazemos repetidas divisões por $2$, obtendo os dígitos do valor em binário:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = int(input(\"Digite um número:\"))\n",
    "while n != 0:\n",
    "    digito = n % 2\n",
    "    n = n // 2\n",
    "    print(digito, end=\"\")\n",
    "print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercício\n",
    "\n",
    "Na conversão decimal-binário, modifique o programa para que este obtenha o valor binário em uma variável inteira, ao invés de imprimir os dígitos separados por espaço.\n",
    "Dica: Suponha $n = 7$ ($111$ em binário), e você já computou $x = 11$. Para ”inserir” o último dígito $1$ em $x$ você deve fazer $x = x + 100$. Ou seja, você precisa de uma variável acumuladora que armazena as potências de $10: 1, 10, 100, 1000$, etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ],
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Solução:\n",
    "n = int(input(\"Digite um número:\"))\n",
    "b = 0\n",
    "pot = 1\n",
    "while n != 0:\n",
    "    digito = n % 2\n",
    "    n = n // 2\n",
    "    b = b + digito * pot\n",
    "    pot = pot * 10\n",
    "print(\"sua representação binária é: \",b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Laços Encaixados\n",
    "Também é possível ter laços dentro dos laços. Estes são chamados de laços aninhados (ou laços encaixados). Um uso comum de laços encaixados ocorre quando para cada um dos valores de uma determinada variável, precisamos gerar/checar algo com valores de outras variáveis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Equações Lineares\n",
    "\n",
    "Problema: Determinar todas as soluções inteiras de um sistema linear como:\n",
    "\n",
    "$$x_{1} + x_{2} = C$$\n",
    "\n",
    "com $x_{1} >= 0$, $x_{2} >= 0$, $C >= 0$ e todos inteiros.\n",
    "\n",
    "Uma solução possível é: para cada um dos valores de $0 <= x_{1} <= C$, teste todos\n",
    "os valores de $x_{2}$ possíveis e verifique quais deles são soluções."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "C = int(input(\"Digite o valor da constante C:\"))\n",
    "for x1 in range(C + 1):\n",
    "    for x2 in range(C + 1):\n",
    "        if x1 + x2 == C:\n",
    "            print(x1, \" + \", x2, \" = \", C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Note que fixado $x_{1}$, não precisamos testar todos os valores de $x_{2}$, pois este é determinado como $x_{2} = C − x_{1}$.\n",
    "\n",
    "```\n",
    "  C = int(input(\"Digite o valor da constante C:\"))\n",
    "  for x1 in range(C + 1):\n",
    "      x2 = C - x1\n",
    "      print(x1, \" + \", x2, \" = \", C)\n",
    "```\n",
    "\n",
    "Mas em um caso geral com $n$ variáveis, $x_{1} + x_{2} + . . . + x_{n} = C$, \n",
    "será preciso fixar $n − 1$ variáveis para só então determinar o valor de $x_{n}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Exercicio:** Quais são as soluções de $x_{1} + x_{2} + x_{3} = C$ com $x_{1} >= 0, x_{2} >=0, x_{3} >=0, C >= 0$ e todas inteiras?\n",
    "\n",
    "Note que fixado $x_{1}$, o valor máximo de $x_{2}$ é $C − x_{1}$.\n",
    "Fixados $x_{1}$ e $x_{2}$, o valor de $x_{3}$ é determinado como $C − x_{1} − x_{2}$.\n",
    "Escreva a solução em Python, levando em conta as dicas acima."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "C = int(input(\"Digite o valor da constante C:\"))\n",
    "for x1 in range(C + 1):\n",
    "    for x2 in range(C + 1 - x1):\n",
    "        x3 = C - x1 - x2\n",
    "        print(x1, \" + \", x2, \" + \", x3, \" = \", C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Mega-Sena\n",
    "Na Mega-Sena, um jogo consiste de 6 números distintos com valores entre 1 e 60.\n",
    "Problema: Imprimir todos os jogos possíveis da Mega-Sena."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Solução: Partindo da mesma idéia vista anteriormente, podemos gerar todos os possíveis valores para cada um dos 6 números do jogo. Assumindo que um possível jogo é sempre apresentado com os números em ordem crescente, fixamos o valor de $d_{1}$, assim, $d_{2}$ necessariamente é maior que $d_{1}$. E com $d_{1}$ e $d_{2}$ fixados, $d_{3}$ é maior que $d_{2}$, etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "nSolucoes = 0\n",
    "for d1 in range(1, 61):\n",
    "    for d2 in range(d1 + 1, 61):\n",
    "        for d3 in range(d2 + 1, 61):\n",
    "            for d4 in range(d3 + 1, 61):\n",
    "                for d5 in range(d4 + 1, 61):\n",
    "                    for d6 in range(d5 + 1, 61):\n",
    "                        nSolucoes += 1\n",
    "                        if nSolucoes <= 15:\n",
    "                            print(d1, d2, d3, d4, d5, d6, sep=\" \")\n",
    "print(\"Total de soluções: \", nSolucoes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercícios"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Faça um programa que leia um número $n$ e imprima $n$ linhas na tela com o seguinte formato (exemplo se $n = 6$):"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "1\n",
    "1 2\n",
    "1 2 3\n",
    "1 2 3 4\n",
    "1 2 3 4 5\n",
    "1 2 3 4 5 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Solução:\n",
    "n = int(input(\"Digite um número:\"))\n",
    "for i in range(1, n + 1):\n",
    "    for j in range(1, i + 1):\n",
    "        print(j, end=\" \")\n",
    "    print()    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Faça um programa que leia um número $n$ e imprima $n$ linhas na tela com o seguinte formato (exemplo se $n = 6$):"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "+ * * * * *\n",
    "* + * * * *\n",
    "* * + * * *\n",
    "* * * + * *\n",
    "* * * * + *\n",
    "* * * * * +"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Solução:\n",
    "n = int(input(\"Digite um número:\"))\n",
    "for i in range(n):\n",
    "    for j in range(n):\n",
    "        chr = '+' if i == j else '*'\n",
    "        print(chr, end=\" \")\n",
    "    print()    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Escreva um programa Python para construir o seguinte padrão, usando um laço aninhado."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* \n",
    "* * \n",
    "* * * \n",
    "* * * * \n",
    "* * * * * \n",
    "* * * * \n",
    "* * * \n",
    "* * \n",
    "*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Solução:\n",
    "n=5;\n",
    "for i in range(n):\n",
    "    for j in range(i):\n",
    "        print ('* ', end=\"\")\n",
    "    print()\n",
    "\n",
    "for i in range(n,0,-1):\n",
    "    for j in range(i):\n",
    "        print('* ', end=\"\")\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Um jogador da Mega-Sena é supersticioso, e só faz jogos em que o primeiro número do jogo é par, o segundo é ímpar, o terceiro é par, o quarto é ímpar, o quinto é par e o sexto é ímpar. Faça um programa que imprima todas as possibilidades de jogos que este jogador supersticioso pode jogar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.4"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "livereveal": {
   "theme": "solarized",
   "transition": "slide"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}