intr_prog/introducao_recursividade_binarios.html

<!--
 Introdução à Programação - 2017 - Prof. Leoônidas de Oliveira Brandão
 Introdução à recorrência/recursividade em algoritmos: gerar todos os binários
 LInE (Laboratory of Informatics in Education) - http://www.usp.br/line
 IME - USP
 Material didático
 Pode usar livrevemente este material para fins não comerciais, devendo sempre fazer referência à autoria.
 Sugestões/apontamento são bem vindos: leo@ime.usp.br (favor indicar no assunto "material de introducao 'a programacao")
 Prof. Leônidas de Oliveira Brandão
 http://www.ime.usp.br/~leo
 http://line.ime.usp.br
 http://www.matemtica.br
-->

  <meta http-equiv='Content-Type' content='text/html; charset=UTF-8'>
  <meta name='keywords' content='mac0122, material, professores, leonidas de oliveira brandao'>
  <link rel='stylesheet' type='text/css' href='css_img_js_conf/all.css'>
  <link rel='stylesheet' type='text/css' href='css_img_js_conf/line_introducao_programacao.css'>
  <script src="css_img_js_conf/defineLInE.js"></script> <!-- para referencias 'a documentos internos -->
<div class="pagina">


<p class="secao">Introdução à recorrência/recursividade em algoritmos: gerar todos os binários</p>

<center><p>[
  <a href="introducao_recursividade.html#binarios" title="Apresentando recursividade e o problema">Inicio</a> &nbsp; | &nbsp;
  <a href="#forma" title="Ideia de recursividade">Estrutura</a> &nbsp; | &nbsp;
  <a href="#aplicando" title="nao fazer Fibonacci recursivo">Resolvendo</a> &nbsp;
 ]</p>
</center>

<p>
Nesta seção apresentamos as ideias de como resolver um problema de forma recursiva, em particular ilustrando isso
para resolver o seguinte problema:
<i>como gerar todos os números binários com exatamente <i>k</i> <i>bits</i> (considerandos os "zeros à esquerda")?</i>.
</p>


<a name="forma"><span style="color: #0050A0">Estrutura de um problema a ser resolvido recursivamente</span></a>

<p>
Para que o problema seja natualmente resolvido por um algoritmo recursivo é preciso que ele seja facilmente
quebrável em sub-problemas menores (denominamos esta técnica de resolução por <b>divisão e conquista</b>)
e que depois as soluções dos problemas menores possam ser utilizadas para resolver o problema original.
</p>

<p>
O problema da geração dos binãrios com até <i>k</i> dígitos apresenta esta característica.
<ol>
 <li>(<b>divisão</b>) Podemos quebrá-lo da seguinte forma:
     resolver para <i>k</i> dígitos pode ser feito resolvendo primeiro para <i>k-1</i> dígitos (nesse caso a quebra é "linear").
 </li>
 <li>(<b>conquista</b>) Uma vez encontrada a solução <tt>(l1, ..., lk)</tt> para <i>k-1</i> dígitos, a solução para <i>k</i> dígitos é simplesmente
     <tt>("0"+l1, ..., "0"+lk, "1"+l1, ..., "1"+lk)</tt> (indicando por "+' o operador de concatenação).
 </li>
</ol>
</p>

<p>
A construção da solução recursiva para resolver o problema seria então aplicar a recorrência para cada um dos sub-problemas e
depois usar os resoltados devolvidos para compor a <b>solução global</b>.
</p>


<a name="aplicando"><span style="color: #0050A0">Resolvendo a geração ordenada de todos os números binário com até <i>k</i> dígitos</span></a>

<p>
Desse modo, para tentar resolver um problema recursivamente, deve-se primeiro imaginar como quebrar o problema, então fazer um raciocínio
de como reagrupar as soluções parciais para formar a solução global.
</p>

<p>
Para o problema considerado claramente a quebra poderia ser feita no número de dígitos.
Se desejamos gerar os binários com <i>k</i> dígitos, supnhamos então que alguém resolveu o problema com <i>k-1</i> dígitos.
Bem, se a solução para <i>k-1</i> dígitos é a lista <tt>(0...0, 0...1, ..., 1...0, 1...1)</tt>, então a solução global seria
duplicar a lista dada, sendo que para cada uma das cópias adicionamos o dígito "0" à frente e na outra o dígito "1", ou seja, a solução seria
a lista seguinte
<center><pre>00...0, 00...1, ..., 01...0, 01...1
10...0, 10...1, ..., 11...0, 11...1</pre></center>
</p>

<p>
Claro que um caso trivial, seria quando <i>k=1</i>, pois nesse caso <i>k-1=0</i> resultando em uma lista vazia.
Portanto a solução global seria apenas os números "0" e "1" (eles concatenados com sequência vazia resultari neles próprios).
E essa poderia ser a condição de terminação a recorrência: <tt>se k=0, devolver &lt;vazio&gt;</tt>.
</p>

<p>
Assim, vamos esquematizar o algoritmo refletindo precisamente essa ideia

<center><table><tr><td><pre>gerar_binario (vet, n, k) {
  se (k==n) { <cyan>// ja' gerou o ultimo bit =&lt; imprima e volte</cyan>
    imprima(vet, n);
    devolver; <cyan>// funcao e' vazia</cyan>
    }
  vet[k] = 0; <cyan>// define o k com '0'</cyan>
  gera_binario(vet,n,k+1); <cyan>// indutivamente, gera os proximos bits (de k+1 ate' n-1)</cyan>
  vet[k] = 1; <cyan>// altera o k</cyan>
  gera_binario(vet,n,k+1); <cyan>// idem</cyan>
  }</pre></td></tr></table></center>
</p>

<p>
Simule o algoritmo acima e veja que para <i>k=4</i> ele consegue construir a os 15 valores abaixo, na ordem correta.
</p>

<p>
<center><pre>Decimal Binário | Decimal Binário
      0    0000 |       8    1000
      1    0001 |       9    1001
      2    0010 |      10    1010
      3    0011 |      11    1011
      4    0100 |      12    1100
      5    0101 |      13    1101
      6    0110 |      14    1110
      7    0111 |      15    1111</pre><i>Exemplo: todos os binários com até 4 dígitos (com seu correspondente decimal à esquerda)</i>
</center>
</p>



<p>
  <a href="https://www.ime.usp.br/~leo" target="_blank" title="seguir para a pagina do prof. Leônidas">Leônidas de Oliveira Brandão</a><br/>
  <a href="http://www.ime.usp.br/~leo" target="_blank" title="seguir para a página do LInE">http://line.ime.usp.br</a>
</p>


<p class="rodape">
 <b>Alterações</b>:<br/>
  2020/08/20: acetos no formato, mais detalhes no gera_binario;<br/>
  2020/08/15: novo formato, pequenas revisões;<br/>
  2018/06/18: primeira versão
</p>

</p>

</div>
  </p>