intr_prog/evitar_entrada_saida_em_funcao.html

<!--
 Introducao 'a Programacao - desde 2017 - Prof. Leo^nidas de Oliveira Branda~o
 Por que evitar entrada/saida de dados em funcoes?
 LInE (Laboratory of Informatics in Education) - http://www.usp.br/line
 IME - USP
 Material didatico
 Pode usar livrevemente este material para fins nao comerciais, devendo sempre fazer referencia `a autoria.
 Sugestões/apontamento são bem vindos: leo@ime.usp.br (favor indicar no assunto "material de introducao 'a programacao")
 Autor: Prof. Leo^nidas de Oliveira Branda~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">Por que evitar entrada/saida de dados em funções</p>

<p>
  A razão principal para se <b>evitar comandos de entrada e de saída dentro da definição de uma função</b> é conseguir
  maior flexibilidade para uso dessas funções, como explico a seguir.
  Evidentemente isso não se aplica quando a função for desenhada especificamente para providenciar a entrada (leitura) ou
  para a saída (impressão de dados. Por exemplo, o segundo caso ocorre na função <tt>imprime_comb</tt>
  Entretanto,

Para explicar as razões pelas quais deve-se <b>evitar comandos de entrada e de saída dentro da definição de uma função</b>,
devemos primeiro enfatizar o que é a uma função em linguagens como <i>C</i> ou  <i>Python</i>:
<ul>
  <li>é um código que recebe seus <em>dados de entrada</em> a partir de uma <i>lista de parâmetros</i> (<i class="def">parâmetros formais</i>);</li>
  <li>é um código que processa os dados de entrada e geralmente devolve algum valor como resposta (em seu comando <tt class="cmd">return</tt>);</li>
  <li>é um código que pode ser invocado a partir de outros trechos do programa, que providenciam os valores para os parâmetros
      (<i class="def">parâmetros efetivos</i>).</li>
</ul>
</p>

<p>
Desse modo, usando como exemplo a <i>função fatorial</i> (<i>fat(0)=1</i> e <i>fat(n)=n*fat(n-1), n&gt;0</i>), a razão para
se evitar comandos de entrada e de saída dentro da definição da função pode ser resumida em:
<ul>
  <li><i>Facilita o reúso de código</i>, ou seja, sempre que precisar de um algoritmo que compute o fatorial,
      basta copiar o código que já implementou (e testou);</li>
  <li><i>Facilita o desenvolvimento de programas maiores</i>, pois pode-se agrupar os blocos lógicos que tenham um propósito bem definido como
      uma função.</li>
</ul>
</p>

<p>
  A fim de ficar mais clara a vantagem de <i>passar os valores via parâmetro</i>, vamos examinar um exemplo matemático,
  <b style="color:#0000aa">computar o número de combinações de <i>n</i>, tomados <i>k</i> a <i>k</i></b>
  <a href="#comb" title="ver referência sobre combinação">[1]</a>.
  Vamos lembrar a combinatória usualmente estudada no <i>Ensino Médio</i>.
  Este problema pode ser traduzido em um exemplo do tipo "loteria":
  de quantas maneiras distintas é possível combinar <i>n=99</i> números (dentre <i>01</i> e <i>99</i>) tomando-se
  <i>k=5</i> deles? A resposta geral é dada pela expressão <i>C<sub>n,k</sub>=n!/((n-k)!k!)</i>, que com os dados de interesse
  resultaria em <i>C<sub>100,5</sub>=100!/((100-5)!5!) = 75.287.520</i>.
  <br/>
  Portanto, se você comprar um único bilhete dessa loteria por semana, em média precisaria de mais de 75 milhões de semanas para conseguir
  ter um bilhete premiado.
  <br/>
  <sabermais title="para saber um pouco mais">
  Como seria dificílimo tentar enumerar as mais de 75 milhões de possibilidade para verificar a corretuda da fórmula
  acima estão corretos, vamos testar com uma combinção menor, como combinar
  <i>n=5</i> valores <i>3</i> a <i>3</i>, neste caso a fórmula diz que teríamos<br/>
  &nbsp; &nbsp; &nbsp; &nbsp; <i>C<sub>5,3</sub>=5!/((5-3)!3!) = 5*4/2 = 10</i>
  <br/>
  e, de fato, existem <i>10</i> combinações:
  <i>{1,2,3}, {1,2,4}, {1,2,5},
     {1,3,4}, {1,3,5},
     {1,4,5},
     {2,3,4}, {2,3,5},
     {2,4,5},
     {3,4,5}</i>.
  </sabermais>
</p>

<p>
  Nesse contexto, imaginemos o uso
  <i style="color:#aa5555" title="conceitualmente errônea, como tento explicar a seguir">errôneo</i> de uma leitura do valor <i>n</i>
  dentro da função <tt class="var">fat</tt>.
  Então, se precisar computar a combinação de <tt>n</tt>, tomados <tt>k</tt> a <tt>k</tt> (<i>C<sub>n,k</sub>=n!/((n-k)!k!)</i>),
  esse valor <b>não</b> poderá ser computado usando a expressão seguinte (com chamada à função <tt class="var">fat</tt>):
  <tt class="var">fat(n)/(fat(n-k)fat(k))</tt>.
  <br/>
  <b style="color:#0000aa">Por que mesmo?</b>
  <br/>
  <porque>
    Se não percebe o <i style="color:#aa5555" title="erro conceitual">erro de programação</i>, vale a pena fazer uma simulação.
    Suponha que você tenha implementado o fatorial como uma função com comando de leitura, em "Portugol" <br/>
    &nbsp; &nbsp;
    <tt><verm>inteiro</verm> fat (n) {
      <verm>inteiro</verm> i=2, f=1; <verd>leia</verd>(n); <azul2>repita_enquanto</azul2> (i&lt;=n) { f = f*i; i = i+1; } devolva f; }</tt>
    <br/>
    e deseje saber <i>C<sub>5,2</sub>=5!/((5-2)!2!)</i>.
    <br/>
    Então, ao entrar na função para computar <tt>fat(5)</tt> o usuário terá que digitar o valor <tt>5</tt>, para computar
    <tt>fat(3)</tt>, será obrigado a digitar o valor 3 e, para computar <tt>fat(2)</tt>, terá também que digitar o valor <tt>2</tt>.
    <br/>
    Mas vamos tornar o <i style="color:#aa5555">erro</i> (ou <i style="color:#aa5555">problema</i>) mais óbvio.
    Vamos supor que desejamos imprimir várias combinações (<i title="do Latin, exempli gratia">e.g.</i>, para computar o triângulo de Pascal).
    Por exemplo, examine como ficaria o calculo de <i>C<sub>10,1</sub>, C<sub>10,2</sub></i>, assim por diante até <i>C<sub>10,10</sub></i>
    (vide a função <tt>fat</tt> da tabela 1).
    Seria necessário que o "sofrido" usuário tenha que ficar digitando 10 triplas! (<i>10,9,1</i>; <i>10,8,2</i>; <i>10,7,3</i>;
    <i>10,6,4</i>; <i>10,5,5</i>; <i>10,4,6</i>; <i>10,3,7</i>; <i>10,2,8</i>; <i>10,1,9</i>; e <i>10,0,10</i>).
    Mas bastaria exigir que o usuário digitasse apenas um valor, <i>10</i>, se o programador (você) tivesse implementado o fatorial via
    parâmetro e sem leituras dentro dessa função. Bastaria usar um laço (vide a função <tt>main</tt> da tabela 3).
    <br/>
    Ou seja, não faz sentido obrigar o usuário a digitar dezenas, centenas, milhares, ou mais vezes, quando bastaria digitar um único valor.
    Se não estiver convencido da inviabilidade do uso de leitura dentro da função fatorial, copie os códigos da tabela 1 e o experimente.
  </porque>
</p>


<p>
  Assim, em exercícios que apresentam o conceito de função (portanto envolvendo um bloco lógico com propósito bem definido),
  procure, sempre que possível, <b>não</b> usar comandos de entrada ou de saída de dados <b>dentro da função</b>.
  Esse é um <i>bom hábito de programação</i>, no sentido de reduzir erros e facilitar que reaproveite sues códigos em outras
  situações.
  <br/>
  Mas vale lembrar que existem exceções: em uma função desenhada especificamente para "ler" dados, é necessá comandos para entrada e
  uma função específica para imprimir o <i>Triângulo de Pascal</i> precisa de comando de impressão.
</p>

<p>
<!-- F<sub>0</sub>=1, F<sub>1</sub>=1, F<sub>k</sub> = F<sub>k-1</sub> + F<sub>k-2</sub>, k&gt;2 -->
Entretanto, existem as exceções, exemplos nos quais é útil usar comando de entrada ou de saída dentro da função. Ilustraremos
o caso de utilidade de um comando de saída dentro da função, isso ocorre se desejamos computar (e imprimir) os <tt>n</tt> primeiros termos da
<i title="F_{0}=1, F_{1}=1, F_{k} = F_{k-1} + F_{k-2}, k&gt;1">sequência de Fibonacci</i>.
Então, naturalmente precisaremos do comando de impressão/saída e como isso pode ser feito para qualquer
<tt>n</tt> é adequado agrupar esse código na forma de um procedimento separado (no caso uma função <b>sem</b> valor de retorno).
<br/>
Porém se o objetivo fosse conhecer apenas o termo <tt>n</tt> da sequência, a função <b>não deveria ter o comando de saída</b>.
</p>

<p>
<center>
<i>Tab. 1. Códigos "errôneos" para imprimir o Triângulo de Pascal via fórmula de combinação</i>
<table class="tableCd">
 <tr><td></td><td bgcolor="8aaada"><i>C</i>              <td bgcolor="8aaada"><i>Python</i></td></tr>
  <tr><td><table class=""><tr class="trCd" valign="top"><td><pre style="font-size:0.8em"> 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
20
</pre></td></tr></table></td>
  <td><table class=""><tr class="trCd" valign="top"><td><pre style="font-size:0.8em"><verm>int</verm> fat (<verm>int</verm> n) { <cyan>// define funcao com 1 parametro</cyan>
  <verm>int</verm> ft = 1, i=2;
  <cyan>// Experimente com esta linha,</cyan>
  <verd>scanf</verd>("%d", &n); <cyan>// depois sem ela</cyan>
  <azul2>while</azul2> (i &lt;= n) {
    i = i + 1;
    ft = ft * i;
    }
  return ft;
  }
<verm>void</verm> imprime_comb (<verm>int</verm> n) {
  <verm>int</verm> i=0, aux;
  <cyan>// Com mais a leitura abaixo o codigo ficaria</cyan>
  <cyan>// scanf("%d", &n); // "absurdo" ao quadrado!</cyan>
  <azul2>while</azul2> (i &lt;= n) {
    aux = fat(n)/(fat(n-i)*fat(i));
    <verd>printf</verd>("%3d ", aux);
    i++;
    }
  <verd>printf</verd>("\n");
  }
<verm>void</verm> main (void) {
  <verm>int</verm> i=0, n;
  <cyan>// Experimente com n pequeno, digamos n=3, assim ja'</cyan>
  <verd>scanf</verd>("%d", &n); <cyan>// percebera' o absurdo da leitura</cyan>
  <azul2>while</azul2> (i&lt;=n) {
    imprime_comb(i);
    i++;
    }
  }</pre></td></tr></table></td>
  <td><table class=""><tr class="trCd" valign="top"><td><pre style="font-size:0.8em"><cyan># Python2 para 'print' sem pular linha : print("*" , end = "");</cyan>
from __future__ import print_function

<verm>def</verm> fat (n) :
  <cyan># Experimente com esta linha,</cyan>
  n = int(<verd>input</verd>()); <cyan># depois sem ela</cyan>
  f = 1;
  i = 2;
  <azul2>while</azul2> (i&lt;=n) :
    f *= i;
    i += 1;
  return f;

<verm>def</verm> imprime_comb (n) :
  <cyan># Com mais a leitura abaixo o codigo ficaria</cyan>
  <cyan># n = int(<verd>input</verd>()); # "absurdo" ao quadrado!</cyan>
  i=0;
  <azul2>while</azul2> (i&lt;=n) :
    <cyan># C(n,k) = n!/((n-k)!*k!)</cyan>
    val = fat(n)/(fat(n-i)*fat(i));
    <cyan># print("C(%d,%d)=%d" % (n,i,val));</cyan>
    <verd>print</verd>("%3d " % (val), end="");
    i += 1;

<verm>def</verm> main () :
  n = int(<verd>input</verd>());
  for i in range(n+1) :
    imprime_comb(i);
    <verd>print</verd>();

main();
</pre></td></tr></table></td></tr>
  </table>
</center>
</p>

<span style="color: #0055AA;font-size:1.1em">Exemplo 1. Dados naturais <tt>n</tt> e <tt>k</tt>, computar a combinação de <tt>n</tt> <tt>k-a-k</tt></span>

<p>
Suponha que precisemos fazer um programa para computar
quantas são as combinações de <tt>n</tt> termos combinados <tt>k</tt>-a-<tt>k</tt>, ou seja, tendo <tt>n</tt> elementos,
desejamos saber de quantos modos distintos podemos formar grupos com <tt>k</tt> dos elementos.
</p>

<p>
Esse conceito aparece em <i>probabilidade</i> e em <i>combinatória</i>, sabemos que esta combinação corresponde ao agrupamentos de
elementos nos quais a ordem não importa (tanto faz a ordem dos <tt>k</tt> elementos do tipo <tt>a</tt>) e que a fórmula que fornece
o total desses subconjuntos é a seguinte:
<center><a href="https://en.wikipedia.org/wiki/Binomial_theorem" title="explicacao mais detalhada na WikiPedia">C(n,k) = n! / ((n-k)! k!)</a>.</center>
</p>

<p>
Por exemplo, combinar <tt>6</tt> valores distintos, tomados <tt>2</tt> a <tt>2</tt> resulta <tt>15=6!/((6-2)!2!)=6!/(4!2!)</tt>, que
são os <tt>15</tt> subconjuntos: 
 <tt>(6,5)</tt>, <tt>(6,4)</tt>, <tt>(6,3)</tt>, <tt>(6,2)</tt>, <tt>(6,1)</tt>, 
 <tt>(5,4)</tt>, <tt>(5,3)</tt>, <tt>(5,2)</tt>, <tt>(5,1)</tt>,
 <tt>(4,3)</tt>, <tt>(4,2)</tt>, <tt>(4,1)</tt>,
 <tt>(3,2)</tt>, <tt>(3,1)</tt>,
 <tt>(2,1)</tt>.
</p>

<p>
Assim, existem duas possibilidades de implementar esse código, uma implementando a função fatorial (<tt>fat(n)</tt>) que seria
invocada três vezes pelo programa principal (com algo como  <tt><verd>imprima</verd>(fat(n) / (fat(k) * fat(n-k))</tt>.
Outra possibilidade é implementar também o cômputo de <tt>fat(n) / (fat(k) * fat(n-k))</tt> também como uma função.
Apesar dessa segunda possibilidade não ajudar tanto na organização do código (pois a segunda função (<tt>comb(n,k)</tt>) seria muito
simples, ilustraremos dessa forma por ela usar função chamando função que chama função (a principal chama <tt>comb(n,k)</tt> e essa
chama <tt>fat(n)</tt>).
Veja como ficaria o código em uma <i>pseudo-linguagem</i> de programação:

<pre style="font-size:0.8em"><verm>inteiro</verm> fat(n) { <cyan>//# estou supondo que o valor digitado pelo usuario seja um natural maior ou igual a 0 (n>=0)</cyan>
  <verm>inteiro</verm> valfat = 1;
  <verm>inteiro</verm> cont = 2;
  <azul2>repita_enquanto</azul2> (cont&lt;=n) { <cyan>//# continue computando enquanto nao chegar ao valor cont==n</cyan>
    valfat = valfat * cont;
    cont = cont + 1;
    }
  devolva valfat;
  }
<verm>inteiro</verm> comb(n, k) {
  devolva fat(n) / (fat(n-k)*fat(k));
  }
<verm>vazio</verm> principal() {
  <verm>inteiro</verm> N, k; <cyan>//# note que os nomes de variaveis daqui NAO tem qualquer relacao com aqueles em 'fat'</cyan>
  <verm>inteiro</verm> a, b, c; <cyan>//# para uma segunda versao</cyan>
  <verd>leia</verd>(N, k); <cyan>//# leia 2 valores naturais e armazene-os respectivamente em N e em k (espera-se que digite N>=k)</cyan>
  <cyan>//# pode-se invocar seguidamente 'fat' 3 vezes como abaixo:</cyan>
  <verd>imprima</verd>(comb(N,k);
  <cyan>//# pode-se invocar a funcao 'fat' quanta vezes forem necessarias, aqui fazermos 3 vezes, armazenando cada resultado</cyan>
  a = fat(N);
  b = fat(k);
  c = fat(N-k);
  <verd>imprima</verd>(a/( b * c))); <cyan>//# usamos os 3 resultados de chamada de 'fat' para compor a resposta final N!/(k!*(N-k)!)</cyan>
  }</pre>
</p>

<p>
  A figura 1 ilustra os desvios no <i>fluxo de execução</i> do código acima.
  Note o destaque da instrução 2, que é uma atribuição que define o valor para a variável <i>c</i>, a ordem de construção é a
  usual de expressão, primeiro computa-se o <i>lado direito</i> da expressão e o resultado dela é armazenado na variável
  (que é o <i>lado esquerdo</i> da atribuição).  Como o <i>lado direito</i> contém uma chamada de função, para computá-lo,
  desvia-se o <i>fluxo de execução</i> (seta que "sai" de <i>fat(k);</i>) para a execução da função <i>fat(.)</i>, inicia-se
  a variável local (na verdade declarada como parâmetro) <i>n</i> com o valor vindo de <i>k</i> (<i>parâmetro efetivo</i>),
  segue-se executando as instrução de <i>fat(.)</i> e, no exemplo, a última instrução indica que deve-se devolver para local
  que <i>invocou</i> <i>fat(.)</i> o valor atual na variável (local) <i>ft</i>.
</p>

<center>
  <img src="img/exemplo_exec_funcao.jpg" title="exemplo de execucao da funcao"/>
  <br/>
  <i>Fig. 1. Diagrama esquemática indicando desvio de execução função e local de retorno.</i>
</center>

<p>
Novamente para enfatizar as desvantagens de usar leitura ou impressão dentro de funções, 
procure implementar o código acima, em sua linguagem favorita, e colocar nele comandos para
leitura ou saída dentro da função <tt>fat(n)</tt>, como discutido abaixo.
</p>


<span style="color: #0055AA;font-size:1.1em">Observação 1. Vantagem de uso de função sem comandos de entrada/saída - combinação n, k-a-k</span>

<p>
  Note que, <b>se</b> dentro da função <tt>fat</tt> exitisse um comando do tipo <tt><verd>leia</verd>(n);</tt>,
  a função NÃO poderia ser usada para computar o fatorial de algum valor já registrado em alguma variável, pois ao ser invocada,
  digamos <tt>fat(n)</tt>, seria necessário que o usuário <i style="color: #AA0000;">digitasse novamente</i> o valor para calculo
  do fatorial e valor para o qual desejava-se o fatorial (na variável <tt>n</tt>) seria descartado.
  No exemplo do código associado à figura 1, na primeira chamada para <i>N</i>, o usuário teria que digitar algum valor
  para calcular fatorial (e provavelmente nem saberia qual o valor guardado em <i>N</i>),
  na segunda chamada, para o valor para <i>k</i> ocorreria o mesmo, e por fim, o mesmo para o valor <i>N-k</i>.
</p>

<p>
  De forma análoga, se a função <i>fat</i> tivesse algum comando de saída, ao usar a função 3 vezes, o usuário
  receberia informações confusas: ele deseja a combinação de <i>n</i>, tomado <i>k</i>-a-<i>k</i>, mas
  receberia 4 infomações: na primeira chamada <i>fat(.)</i> imprimiria <i>n!</i>,
  segunda imprimiria <i>k!</i>, na terceira imprimiria o resultado de <i>(n-k)!</i> e, ao voltar
  para o código que invocou <i>fat(.)</i>, imprimiria finalmente a única coisa que o usuário desejava saber,
  <i>n!/(k! (n-k)!)</i>.
</p>


<span style="color: #0055AA;font-size:1.1em">Observação 2. Propriedade interessante de C(n,k) - Triângulo de Pascal</span>

<p>
Vamos aproveitar o código que computa a combinação de <i>n</i>, <i>k-a-k</i>, <i>C(n,k) = n!/(k!*(n-k)!)</i>, para computar
a seguinte sequência de valores: <i>C(n,0)</i>, <i>C(n,1)</i>, <i>C(n,2)</i> e assim por diante, até <i>C(n,n)</i>.
Mais ainda, vamos fazer isso para <i>n=1</i>, <i>n=2</i>, <i>n=3</i> e <i>n=4</i>.
</p>

<center>
<i>Tab. 2. Triângulo de Pascal, como combinação e de modo direto</i>
<table class="tableCd"><tr><td>
<pre>Linha | Combinacoes C(n,0) ate C(n,n)                         | As saidas
    0 | C(0,0)                                                |   1
    1 | C(1,0) C(1,1)                                         |   1   1 
    2 | C(2,0) C(2,1) C(2,2)                                  |   1   2   1 
    3 | C(3,0) C(3,1) C(3,2) C(3,3)                           |   1   3   3   1 
    4 | C(4,0) C(4,1) C(4,2) C(4,3) C(4,4)                    |   1   4   6   4   1 
    5 | C(5,0) C(5,1) C(5,2) C(5,3) C(5,4) C(5,5)             |   1   5  10  10   5   1 
    6 | C(6,0) C(6,1) C(6,2) C(6,3) C(6,4) C(6,5) C(6,6)      |   1   6  15  20  15   6   1</pre>
</td></tr></table>
</center>

<p>
Ou seja, na tabela acima, a linha <i>0</i>, tem uma única saída, a saber <i>C(0,0)</i>.
A linha <i>1</i> tem duas saídas, <i>C(1,0)</i> e <i>C(1,1)</i>.
A linha <i>2</i> tem três saídas, <i>C(2,0)</i>, <i>C(2,1)</i> e <i>C(2,2)</i>.
Assim, por diante, até a linha <i>6</i> que tem sete saídas.
</p>

<p>
  O que é interessante, é que no <i>triângulo</i> (na coluna das saídas) aparece uma propriedade interessante:
  o elemento da linha <i>k</i>, na coluna <i>j</i> é igual à soma do elemento da
  linha <i>k-1</i>, na coluna <i>j-1</i>, com o elemento da
  linha <i>k-1</i>, na coluna <i>j</i>.
  Ou seja, vale a propriedade
  <i>C(k,j) = C(k-1,j-1) + C(k-1,j)</i> (sempre que <i>k&gt;0</i> e <i>j</i> estiver entre <i>1</i> e <i>k</i>,
  essa é a relação de <i title="Michael Stifel (ca. 1487 1567)">Stifel</i>
  [<a href="#boyer" title="examinar referencia 2 - Boyer">2</a>, <a href="#dantzig" title="examinar referencia 2 - Dantzig">3</a>],
  e aquele é o
  <b title="Atribuido a Blaise Pascal (1623 1662) mas já conhecido por Yang Hui (fl. ca. 1261 1275) e Michael Stifel (ca. 1487 1567)">
    Triângulo de Pascal</b>.
  Veja por exemplo o
  <a href="https://en.wikipedia.org/wiki/Pascal%27s_triangle" title="seguir para WikiPedia">Triângulo de Pascal</a>
  <a href="#boyer" title="examinar referência Boyer">[2]</a>
  na <i>WikiPedia</i>.
</p>

<!--
<pre>1 0
---
1 1
1 0
---
2 0
2 1
2 2
---
3 0
3 1
3 2
3 3
---
4 0
4 1
4 2
4 3
4 4</pre>

<p>
Examinando as saídas (última coluna) notamos uma propriedade interessante:
o elemento da linha <tt>n+1</tt>, coluna <tt>k+1</tt> = o elemento da linha <tt>n</tt>, coluna <tt>k</tt> + o elemento da linha <tt>n</tt>, coluna </tt>k+1</tt>.
Veja por exemplo, a última linha, linha <tt>4</tt>: o segundo elemento = <tt>4</tt> = <tt>1 + 3</tt> (da linha acima).
</p>
-->

<!-- https://pt.wikipedia.org/wiki/Produtos_not%C3%A1veis -->

<!--
<span style="color: #0055AA;font-size:1.1em">Exemplo 2. Coeficientes da expansão do produto notável <tt>(a+b)^n</tt></span>

<p>
Suponhamos que precisemos fazer um programa que computa os termos dos coeficientes da expansão de <tt>(a+b)^n</tt>.
Ou seja, desejamos um programa que dado <tt>n</tt> liste quantos termos do tipo <tt>a^i x b^j</tt> existe, para cada
<tt>i</tt> e cada <tt>j</tt> tais que <tt>i+j=n</tt>.

  o valor da combinação de <i>N</i> tomado <i>k</i> a <i>k</i>, ou seja,
C(N,k) = N! / ( k! (N-k)!).
Para isso percebe-se que é necessário implementar o cômputo de fatorial que será utilizado 3 vezes.
Para facilitar a compreensão, podemos escrever um código com 3 variáveis auxiliares para armazenar, respectivamente,
<i>N!</i>, <i>k!</i> e <i>(N-k)!</i>.
</p>

<pre>(a+b)^0                                                         = 1 a^0 b^0
(a+b)^1 = (a+b) (0 a^0 b^0 + 0 a^0 b^0)                         = 1 a^1 b^0 + 1 a^0 b^0 
(a+b)^2 = (a+b) (1 a^1 b^0 + 0 a^0 b^1)                         = 1 a^2 b^0 + 2 a^1 b^1 + 1 a^0 b^2
(a+b)^3 = (a+b) (1 a^2 b^0 + 2 a^1 b^1 + 1 a^0 b^2)             = 1 a^3 b^0 + 3 a^2 b^1 + 3 a^1 b^2 + 1 a^0 b^3
(a+b)^4 = (a+b) (1 a^3 b^0 + 3 a^2 b^1 + 3 a^1 b^2 + 1 a^0 b^3) = 1 a^4 b^0 + 4 a^3 b^1 + 6 a^2 b^2 + 4 a^1 b^3 + 1 a^0 b^3a
</pre>
<pre>1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
</pre>
-->


<span style="color: #0055AA;font-size:1.1em;">Implementações para gerar o "Triângulo de Pascal" em <i>C</i> e em <i>Python</i></span>

<p>
Abaixo apresento uma implementação para gerar o "Triângulo de Pascal" (como apresentado acima), nas linguagens
<i>C</i> e <i>Python</i>.
<center>
  <i>Tab. 3. Outra versão de códigos para imprimir o Triângulo de Pascal via fórmula de combinação.</i>
  <br/>
 <table>
  <tr><td>Gerando "Triângulo de Pascal" em <i>C</i></td> <td>&nbsp;</td> <td>Gerando "Triângulo de Pascal" em <i>Python</i></td></tr>
<tr>
<td><pre style="font-size:0.8em">#include &lt;stdio.h&gt;
<verm>int</verm> fat (<verm>int</verm> n) { <cyan>// supondo usuario digite natural n&gt;=0)</cyan>
  <verm>int</verm> valfat = 1;
  <verm>int</verm> cont = 2;
  <azul2>while</azul2> (cont&lt;=n) { <cyan>// continue enquanto nao chegar a cont==n</cyan>
    valfat = valfat * cont;
    cont++;
    }
  return valfat;
  }

<verm>int</verm> comb (<verm>int</verm> n, <verm>int</verm> k) { return fat(n) / (fat(n-k)*fat(k)); }

<verm>void</verm> main (void) {
  <verm>int</verm> N, k; <cyan>//  usa inteiros N, k</cyan>
  <verm>int</verm> a, b, c, n;
  <verd>printf</verd>("Digite N - para computar C(N,0), C(N,1), ..., C(N,N): ");
  <verd>scanf</verd>("%d",  &N);
  <cyan>// pode-se invocar seguidamente 'fat' 3 vezes como abaixo:</cyan>
  for (n=0; n&gt;N; n++) {
    for (k=0; k&lt;=n; k++) {
      a = fat(n);
      b = fat(k);
      c = fat(n-k);
      <cyan>// usamos resultados de 'fat' para resposta N!/(k!*(N-k)!)</cyan>
      <verd>printf</verd>("%3d ", a/(b * c));
      }
    <verd>printf</verd>("\n");
    }
  }
</pre></td> <td>&nbsp;</td> 
<td><pre style="font-size:0.8em"><cyan># Python2 para 'print' sem pular linha : print("*" , end = "");</cyan>
from __future__ import print_function

<verm>def</verm> fat (n) : <cyan># supondo usuario digite natural n&gt;=0)</cyan>
  valfat = 1;
  cont = 2;
  <azul2>while</azul2> (cont&lt;=n) : <cyan># continue enquanto nao chegar a cont==n</cyan>
    valfat = valfat * cont;
    cont = cont + 1;
  return valfat;

<verm>def</verm> comb(n, k) :
  return fat(n) / (fat(n-k)*fat(k));

<verm>def</verm> main () :
  <cyan># usa inteiros N, k</cyan>
  <verd>print</verd>("Digite N - para computar C(N,0), C(N,1), ..., C(N,N): ");
  N = int(<verd>input</verd>());
  <cyan># pode-se invocar seguidamente 'fat' 3 vezes como abaixo:</cyan>
  for n in range(N) :
    for k in range(n+1) :
      a = fat(n);
      b = fat(k);
      c = fat(n-k);
      <cyan># usamos resultados de 'fat' para resposta N!/(k!*(N-k)!)</cyan>
      <verd>print</verd>("%3d " % (a/(b * c)), end="");
    <verd>print</verd>();

main();
</pre></td>
</tr></table>
</center>
</p>

<span style="color: #0055AA;font-size:1.1em">Referências bibliográficas sobre "Triângulo de Pascal"</span>


<ol type="1">
 <li> <a name="comb">[1]</a>
   <a href="https://en.wikipedia.org/wiki/Binomial_coefficient" title="examinar combinação na WikiPedia"
      target="_blank">https://en.wikipedia.org/wiki/Binomial_coefficient</a>.</li>
 <li> <a name="boyer">[2] Uta C. Merzbach e Carl B. Boyer</a>,
      "A History of Mathematics", third edition, John Wiley & Sons, Inc., 2011 (primeira edicao de 1968)
 </li>
 <li> <a name="dantzig">[3] Tobias Dantzig</a>, "NUMBER: The Language of Science", Pi Press, New Yourk, 2005
 </li>
</ol>

 <!--
 Boyer, Carl B. (Carl Benjamin), 1906 1976.
 pg 184. "The Jade Mirror opens with a diagram of the arithmetic triangle,
  inappropriately known in the West as “Pascal’s triangle.” (See the fol-
  lowing illustration.) In Zhu’s arrangement, we have the coefficients of"
 -->
 <!--
 republicacao da 4a edicao de 1954
 (primeira edicao de 1930)
 pg. 71. "It is significant that we owe the first explicit formulation of
 the principle of recurrence to the genius of Blaise Pascal, a contem-
 porary and friend of Fermat. Pascal stated the principle in a tract
 called The Arithmetic Triangle which appeared in 1654. Yet it was"
 pg 279. "FIG 2. THE ARITHMETIC TRIANGLE OF PASCAL"
 -->

  <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/09: revisão do formato e ampla revisão do texto;<br/>
  2019/06/06: vários pequenos acertos ao longo do texto;<br/>
  2019/04/07: versao 2 (acrescentado novos paragrafos, melhorando explicacoes e frases);<br/>
  2017/04/06: primeira versao.
</p>

</div>