intr_prog/indicador_passagem.html

<!--
 Introdução à Programação - 2017 - Prof. Leoônidas de Oliveira Brandão
 Introdução ao conceito de indicador de passagem
 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">


<!--
<center><p>[
  <a href="#" title=""></a> &nbsp; | &nbsp;
  <a href="#memoria" title=""></a> &nbsp; &nbsp;
 ]</p>
</center>
-->


<p class="secao">Introdução ao conceito de indicador de passagem</p>

<p>
  Nesta seção será apresentado o conceito de <i>indicador de passagem</i>, bastante útil em algoritmos que precisem detectar
  a ocorrência de um evento, não importanto quantos vezes ele ocorre,
  como saber se todos os elementos de uma sequência são <i>pares</i>, bastaria um valor <i>ímpar</i> para caracterizar
  a resposta como <i>negativa</i>.
</p>


<p class="secao">Ideia que se <i>repetem</i></p>

<p>
Em matemática é comum a existência de ideias que são usadas para resolver variados
problemas, como a <i>soma telescópica</i> (<i>soma<sub>i=1</sub><sup>n</sup> 1/(i (i+1)) =
soma<sub>i=1</sub><sup>n</sup> (1/i - 1/(n+1)) = soma<sub>i=1</sub><sup>n</sup> = (1-1/2) + (1/2 - 1/3) + ... + (1/n - 1/(n+1)) =
1 - 1/(n+1)</i>).
<!-- <i>1+2+3+...+n = (1/2)(1+2+...+n+1+2+...+n) = (1/2)((n+1)+(n+1)+...+(n+1)) = (1/2) (n x (n+1))</i> -->
</p>

<p>
Em desenvolvimento de <i>software</i> (programas computacionais) esse princípio do "reaproveitamento" de ideias é ainda mais usado.
O primeiro exemplo que você deve ter notado desse "reaproveitamento" é a ideia de <i>contador</i>
(sempre que executar determinada instrução, <i>acrescentar 1 ao contador</i>).
</p>


<p class="secao">Ideia de <i>indicador de passagem</i></p>

<p>
A ideia de <b style="color: #0000AA;">indicador de passagem</b> é utilizar uma variável que será usada
para registrar se <i>determinado evento ocorreu</i>.
Por exemplo, deseja-se saber se entre os valores digitados algum deles é negativo, então pode-se implementar
um semelhante ao indicado abaixo (em uma linguagem <i>Portugol</i>):
<pre>
 <tt class="com">// O indicador de passagem recebera o nome sugestivo 'existeNegativo'</tt>
 existeNegativo = 0; <tt class="com">// 0 =&gt; "ate' aqui" nenhum negativo - ou, "em principio, nao existem negativos"</tt>
 <tt class="cmd">repita</tt> N <tt class="cmd">vezes</tt>
   <tt class="fnc">leia</tt>(x);
   <tt class="cmd">se</tt> (x &lt; 0)
   <tt class="cmd">entao</tt> existeNegativo = 1; <tt class="com">// existe negativo! ("nunca mais" elimine o 1 dessa variavel indicadora)</tt>
 <tt class="com">// terminado o laco a resposta e' dada olhando se ocorreu o evento (ao menos uma vez)</tt>
 <tt class="cmd">se</tt> (existeNegativo == 1)
 <tt class="cmd">entao</tt> <tt class="fnc">imprima</tt>("Existe(m) negativo(s)");
 <tt class="cmd">senao</tt> <tt class="fnc">imprima</tt>("NAO existe sequer um valor negativo na sequencia digitada!");
</pre>
</p>

<p>
Portanto, esse <i>modelo solução</i> (ou <i>padrão</i>) é útil sempre que estiver interessado em
detectar se um evento ocorre ao menos uma vez.
</p>


<p class="secao">Cuidado com um erro comum ao tentar usar indicadores</p>

<p>
Um erro bastante comum para os iniciantes na <i>arte de programar</i> é, a cada passo, alterar o valor da variável indicadora.
Por exemplo, poder-se-ia "estragar" o código acima se for acrescentado um comando
<tt class="cmd">senao</tt> dentro do laço, do sguinte modo
<center><table><tr><td><pre>
 <tt class="com">// <b>Contra-exemplo</b> NAO implemente desse modo!</tt>
 existeNegativo = 0; <tt class="com">// 0 =&gt; "ate' aqui" nenhum negativo - ou, "em principio, nao existem negativos"</tt>
 <tt class="cmd">repita</tt> N <tt class="cmd">vezes</tt>
   <tt class="fnc">leia</tt>(x);
   <tt class="cmd">se</tt> (x &lt; 0)
   <tt class="cmd">entao</tt> existeNegativo = 1; <tt class="com">// existe negativo! ("nunca mais" elimine o 1 dessa variavel indicadora)</tt>
   <tt class="cmd">senao</tt> existeNegativo = 0; <tt class="com">// <b>NAO</b> use uma linha dessa (ela "desfaz" o indicador)!!!!</tt>
 <tt class="com">// terminado o laco a resposta SERIA dada olhando se ocorreu o evento</tt>
 <tt class="cmd">se</tt> (existeNegativo == 1)
 <tt class="cmd">entao</tt> <tt class="fnc">imprima</tt>("Existe(m) negativo(s)");
 <tt class="cmd">senao</tt> <tt class="fnc">imprima</tt>("NAO existe sequer um valor negativo na sequencia digitada!");
</pre></td></tr></table></center>
</p>


<p>
Simule a pseudo-solução acima, usando os seguintes dados como entrada: <tt>N=4</tt> e a sequência de 4 dados como sendo
<tt>2, -1, -3, 4</tt>. Será usado <tt>i</tt> para indicar o número de dados digitados (auxiliar, faria parte do código
se for usado um comando <tt>for</tt> do <i>C</i> ou <i>Python</i>).
<center><table><tr><td><pre> i |  x | existeNegativo
 1 |  2 |              0
 2 | -1 |              1
 3 | -3 |              1
 4 |  2 |              0</pre></td></tr></table></center>
</p>

<p>
  Note que ao final da simulação, <tt>existeNegativo</tt> está com o valor 0, que indicaria a não existência de
  negativos na sequência, mas existem 2 negativos! Logo, solução errada!
</p>

<p>
  Na verdade, na implementação <i style="color:#aa0000">errônea</i> acima, a resposta será definida exclusivamente pela
  última iteração do laço. Por que?
  <br/>
  A razão é que, a cada passo a variável <tt>existeNegativo</tt> receberá um valor (esse é o <i style="color:#aa0000">erro</i>),
  pois se a condição for <i>verdadeira</i> executa-se
  a atribuição <tt>existeNegativo = 1</tt> e se for <i>falsa</i> executa-se
  a atribuição <tt>existeNegativo = 0</tt>.
  <br/>
  Portanto, não importa quais sejam os <tt>N-1</tt> primeiros valores digitados, o único usado para definir o
  valor final de <tt>existeNegativo</tt> seria o último! <i style="color:#aa0000">Erro</i>!
</p>


<p class="secao">Códigos em <i>C</i> e em <i>Python</i> para o exemplo acima de <i>indicador de passagem</i></p>

<p>
Abaixo está indicado em <i>C</i> e em <i>Python</i> o código para digitar <i>N</i> valores (inteiros)
e imprimir se algum negativo foi ou não registrado (digitado).
</p>


<center><table><tr>
<td bgcolor="8aaada"><i>C</i>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td bgcolor="8aaada"><i>Python</i></td></tr>
<tr><td colspan="2"><pre>
  <tt class="tipo">int</tt> n, i;                             <tt class=""></tt>
  <tt class="fnc">scanf</tt>("%d", &n);                      n = <tt class="fnc">int</tt>(<tt class="fnc">input</tt>());
  <tt class="">existeNegativo = 0;                   existeNegativo = 0;
  <tt class="cmd">for</tt> (i=0; i&lt; n; i++)                  <tt class="cmd">for</tt> i in range(n) :
    <tt class="cmd">if</tt> (x &lt; 0 )                           <tt class="cmd">if</tt> (x &lt; 0 ) :</tt>
      <tt class="">existeNegativo = 1;                   <tt class="">existeNegativo = 1;</tt>
  <tt class="cmd">if</tt> (existeNegativo == 1)              <tt class="cmd">if</tt> (existeNegativo == 1) :
    <tt class="fnc">printf</tt>("Existe(m) negativo(s)\n");    <tt class="fnc">print</tt>("Existe(m) negativo(s)");
  <tt class="cmd">else</tt> <tt class="fnc">printf</tt>("NAO existe!\n");         <tt class="cmd">else</tt> : <tt class="fnc">print</tt>("NAO existe!");
</pre></td></tr></table></center>


<p class="secao">Outros exemplos de uso do conceito de <i>indicador de passagem</i></p>

<p>
Existe uma quantidade arbitrária de exemplos em que o conceito de <i>indicador de passagem</i> é útil.
Abaixo listo apenas alguns exemplos simples:
<ul>
<li>Verificar se existe algum débito em um extrato bancário (identificar negativo em uma sequência);</li>
<li>Verificar se uma sequência é crescente;</li>
<li>Verificar se uma sequência é ou não uma <i>progressão aritmética (PA)</i> (o candidato à razão poderia ser a diferença do primeiro par);</li>
<li>Verificar se algum dos valores é raíz de determinada equação;</li>
<li>Verificar se um vetor é solução de um sistema linear (sequência seriam os produtos linha vetor candidato).</li>
<!--li></li-->
</ul>
</p>



  <p class="autoria">
    <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/15: novo formato, pequenas revisões<br/>
    2020/08/12: novo formato, pequenas revisões<br/>
    2019/05/08: primeira versão
  </p>


</div>