LInE
/
material_intro_prog


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539
							<!DOCTYPE HTML>
<html>
<head>
  <meta charset="UTF-8"/>
  <link href="css/style.css" rel="stylesheet">
  <title>Exemplos</title>
</head>
<body>
    <h1>3 - Perguntas básicas para implementar um algoritmo</h1>
    <p>
      No restante desta apostila procuraremos mostrar como desenvolver programas utilizando as linguagens C e Python. Os problemas que abordaremos são, em sua
       maioria, bastante simples, no sentido de ser possível resolvê-los manualmente (sem o auxílio de programas de computador). A dificuldade consiste em obter
       soluções computacinais para tais problemas, ou seja, em escrever um processo que resolva tais problemas servindo-se de uma linguagem extremamente rígida e
       um pouco limitada.<br />

       Um <b>programa</b> pode ser entendido como uma sequência finita de comandos que manipulam um numero limitado de  variaveis  e  que  deve  devolver
       algum  conjunto-resposta. Em geral, os problemas que admitem solucoes via computador apresentam caracterısticas de repeticao, isto  ́e, permitem que
       uma mesma sequência de passos seja repetida (um numero finito de vezes) ate que se obtenha o resultado desejado.<br />

       Sugerimos ao leitor, principalmente aos iniciantes em programação, que se concentre em quatro questões chaves à resolução de problemas via algoritmos,
       independentemente da linguagem a ser utilizada, seja ela qual for.<br />

       <ul>
         <li><b>1ª Pergunta:</b> Quais variáveis são necessárias?</li>
         <li><b>2ª Pergunta:</b> Quais comandos devem apareceer dentro de um bloco de repetição?</li>
         <li><b>3ª Pergunta:</b> Qual a condição para que continue a repetição?</li>
         <li><b>4ª Pergunta:</b> Quais os comandos necessários antes e depois do bloco de repetição?</li>
       </ul>
       <br />

       Nem sempre é possível responder completamente estas perguntas nesta sequência. Muitas vezes, ao longo da descrição do programa surge a necessidades de novas
       variáveis, que devem ser acrescentadas à lista inicialmente pensada como resposta à 1ª pergunta.  Por outro lado, com o passar do tempo (e aquisiçao de
       experiência na programação), será natural que ao tentar responder a 2ª pergunta ja se note a necessidade de alguns comandos que  devem  aparecer  antes  do
       bloco  de  repetição (4ª pergunta). Alem  disto, somente “problemas pequenos” possuem um  ́unico bloco de repetição, sendo que as perguntas 2 a 4 devem ser
       levadas em conta para cada novo bloco de repetição. No entanto, a experiência tem-nos mostrado que, pelo menos enquanto se esta comecando a  aprender  a
      descrever  processos  em  liguagens  estruturadas,  estas  perguntas  servem  como  um  bom  roteiro  ao programador iniciante.<br />

      Veremos, a seguir, o desenvolvimento de programas para alguns problemas.<br />
      Obs: Nos códigos em C só serão mostradas as partes centrais do código, para ter um código funcional você deverá importar as respectivas bibliotecas e adicionar o código
      dentro da função main
    </p>
    <h2>3.1 - Como somar um número arbitrário de valores</h2>
    <p>
      <b>Problema: </b> Faça um programa que leia uma sequência de números inteiros, diferentes de zero, e calcule a sua soma.<br />
      Se a sequência de entrada tivesse um tamanho fixo conhecido, digamos 4, a descrição do processo não seria complicada, bastando escrever:
      <center>
      <table>
       <tr>
         <th> C </th>
         <th>Python</th></tr>
       <tr>
         <td>
           <pre>
int n1, n2, n3, n4, soma; //cria as 5 variáveis que serão utilizadas
scanf("%d %d %d %d", &n1, &n2, &n3, &n4); //lê 4 inteiros
soma = n1+n2+n3+n4; //soma os 4 inteiros lidos
printf("%d", soma); //imprime o resultado da soma
           </pre>
         </td>
         <td>
           <pre>
n1 = input() //lê o primeiro inteiro
n2 = input() //lê o segundo inteiro
n3 = input() //lê o terceiro inteiro
n4 = input() //lê o quarto inteiro
soma = n1+n2+n3+n4 //soma os 4 inteiros
print(soma) //imprime o resultado da soma
           </pre>
         </td>
       </tr>
    </table>
    <div>
      <img src="./imgs/soma_4_numeros.png" /><br />
      <span>Código no iVProg</span>
    </div>
  </center>
  <br />
     No entanto a solução muda radicalmente se desejamos escrever um algoritmo que funcione para um número arbitrário de valores de entrada (este número é
     definido pelo usuário durante a execução do algoritmo). Neste caso, a dificuldade reside no fato de o programa ser capaz de somar uma sequência de qualquer
     tamanho.<br />
     Antes de continuar, reflita um pouco sobre esta questão e tente escrever um código que permita a soma de uma sequência de qualquer tamanho.<br />
     Duas possíveis soluções são:
     <ul>
       <li>Ao início da execução do algoritmo o usuário digitar qual o tamanho da sequência</li>
       <li>Utilizarmos um caracter de escape que indicará o final da sequência</li>
     </ul>
    <br />
    Abaixo iremos apresentar a segunda solução, utilizar um caracter de escape.<br />
    Uma boa técnica para iniciar o processo de rogramação é admitir algumas sequências de dados de entrada e pensar a partir destes dados. Então examinaremos,
    por exemplo, a soma da seguinte sequência de entrada: 8  11  3  -7  2 ... 0
    <ol>
      <li>Leia o primeiro número 8;</li>
      <li>Como o número lido !=(diferente) 0, leia o próximo número 3, guardando a soma destes dois 19+3 = 22;</li>
      <li>Como o último número lido != 0, leia o próximo número 3, guardando com a soma anterior 19+3=22;</li>
      <li>Como o último número lido != 0, leia o próximo número -7, guardando com a soma anterior 22+(-7)=15;</li>
    <center>
      <pre>
        .
        .
        .
      </pre>
    </center>
    <li>Lê o 0, e como o número lido foi 0 imprime a soma final</li>
    </ol>

    <h3>Quais variáveis são necessárias?</h3>
    Vemos a necessidades de 2 variáveis: uma para guardar o último número lido e outra para guardar a soma dos número já lidos. Então teremos:
    <center>
    <table>
     <tr>
       <th> C </th>
       <th>Python</th></tr>
     <tr>
       <td>
         <pre>int num, soma;</pre>
       </td>
       <td>
         <pre>
num = 0
soma = 0</pre>
       </td>
     </tr>
  </table>
</center>

<h3>Quais os comandos necessários antes e depois do bloco de repetição?</h3>
<p>
  Inicialmente, no código em C o valor das variáveis(quaisquer) está indefinido, já no código em Python está definido em 0 e portanto devemos cuidar das
  "inicializações" antes do primeiro teste <b>while (num !=0)</b>. Quanto deve valer a variável num neste momento inicial?<br />
  Uma solução possível é o tratamento do primeiro número da sequência como caso à parte, antes de entrarmos no comando de repetição. Deste modo, devemos ler
  o primeiro número fora da repetição e já contabilizar na soma.
  <br />
  <b>Exercício 1:</b> <i>Tente elaborar outra solução, que não faça uma primeira leitura de num dentro do laço</i>
  <br />
  Após a repetição devemos imprimir o conteúdo da variável <b>soma</b>, que deverá conter a soma dos elementos da sequência de entrada.<br />
  Escrevendo o código temos:<br />
  <center>
  <table>
   <tr>
     <th> C </th>
     <th>Python</th></tr>
   <tr>
     <td>
       <pre>
1  int num, soma;
2  scanf("%d", &num);
3  soma = num;
4  while (num != 0){
5    scanf(%d, &num);
6    soma = soma + num;
7  }
8  printf("%d",soma);
       </pre>
     </td>
     <td>
       <pre>
1  num = input();
2  soma = num;
3  while num != 0
4    num = input()
5    soma = soma + num
6  print(soma)
       </pre>
     </td>
   </tr>
  </table>
  <div>
    <img src="./imgs/soma_n_numeros.png" /><br />
    <span>Código no iVProg</span>
  </div>
  </center>
<h3>Conceito de simulação de um Algoritmo</h3>
Um conceito muito importante à programação é o processo de <b>simulação</b> de um algoritmo. Útil na verificação da corretude do mesmo e também para entender
o seu funcionamento. Na simulação de um algoritmo/programa devemos anotar todas as alterações, de todas suas variáveis, ao longo de seu fluxo de execução para algum
conjunto de entrada<br />
Melhor que muitas explicações complicadas é um bom exemplo. Vejamos a simulação do programa acima para o conjunto de entradas 10 3 4 0 no algoritmo em C:
<center>
  <table>
    <tr>
      <th>num</th>
      <th>soma</th>
      <th>comando em execução</th>
      <th>observações</th>
    </tr>
    <tr>
      <td>?</td>
      <td>?</td>
      <td>  </td>
      <td>no início do programa valores das variáveis são desconhecidos, elas apenas foram declaradas</td>
    </tr>
    <tr>
      <td>10</td>
      <td>?</td>
      <td>scanf("%d", &num)</td>
      <td>pega o 1º número de entrada e guarda em num</td>
    </tr>
    <tr>
      <td>10</td>
      <td>10</td>
      <td>soma = num</td>
      <td>Atribui o valor de num a soma</td>
    </tr>
    <tr>
      <td>10</td>
      <td>10</td>
      <td> while (num != 0) </td>
      <td>Como num é diferente de 0, executa os comandos dentro do bloco de repetição (linhas 5 e 6)</td>
    </tr>
    <tr>
      <td>3</td>
      <td>10</td>
      <td> scanf("%d", num) </td>
      <td>Recebe o 2º número de entrada e guarda em num</td>
    </tr>
    <tr>
      <td>3</td>
      <td>13</td>
      <td> soma = soma + num </td>
      <td>atribui a soma o valor da expressão soma + num</td>
    </tr>
    <tr>
      <td>3</td>
      <td>13</td>
      <td> while(num!=0) </td>
      <td>Como num é diferente de 0, o programa continuará a repetição</td>
    </tr>
    <tr>
      <td>4</td>
      <td>13</td>
      <td> scanf("%d", num) </td>
      <td></td>
    </tr>
    <tr>
      <td>4</td>
      <td>17</td>
      <td>soma = soma+ num</td>
      <td></td>
    </tr>
    <tr>
      <td>4</td>
      <td>17</td>
      <td>while(num!=0)</td>
      <td></td>
    </tr>
    <tr>
      <td>0</td>
      <td>17</td>
      <td> soma = soma + num </td>
      <td></td>
    </tr>
    <tr>
      <td>0</td>
      <td>17</td>
      <td> while(num!=0) </td>
      <td>Como soma é igual a 0, o programa pula para a linha 8</td>
    </tr>
    <tr>
      <td>0</td>
      <td>17</td>
      <td>printf("%d", soma)</td>
      <td>Imprime o valor de soma: 17</td>
    </tr>
  </table>
</center>
<b>Saída do programa: 17</b>
<br />
Deve-se notar que após o programa "ler" o número 0(C: linha 5; Python: linha 4), ainda é executado o comando soma = soma + num antes do fluxo de execução
voltar ao inicio do comando <b>while</b>. Mas isto não provoca qualquer erro, uma vez que o valor "lido"(0) não altera o valor da soma. No entanto, o que
fazer se o programa consistisse em somar uma sequência de inteiros não negativos (positivos ou nulos), finalizada por um número negativo?<br />

Antes de seguir com a leitura pense na questão<br />

Uma primeira tentativa em responder à questão anterior é tentar aproveitar a versão anterior, trocando apenas a condição de parada do while de num != 0
para num >= 0.<br />
Porém isto não funcionaria, pois ao digitar um finalizador (número negativo), este será adicionado ao conteúdo de soma(C: linha 6; Python: linha 5), "estragando"
o resultado final.<br />
Se a solução do novo problema não pode ser tão semelhante à versão anterior, também não será radicalmente diferente. Basta efetuarmos uma mera inversão entre as
linhas dentro do comando while(C: 5 com 6; Python: linha 4 com 5), além da troca da condição de parada acima citada.<br />
<center>
<table>
 <tr>
   <th> C </th>
   <th>Python</th></tr>
 <tr>
   <td>
     <pre>
1  int num, soma;
2  scanf("%d", &num);
3  soma = 0;
4  while (num >= 0){
5    soma = soma + num;
6    scanf(%d, &num);
7  }
8  printf("%d",soma);
     </pre>
   </td>
   <td>
     <pre>
1  num = input();
2  soma = 0;
3  while num >= 0:
4    soma = soma + num
5    num = input()
6  print(soma)
     </pre>
   </td>
 </tr>
</table>
<div>
  <img src="./imgs/soma_n_positivos.png" /><br />
  <span>Código no iVProg</span>
</div>
</center>
Note também a diferença da inicialização da variável <b>soma</b>. Começando com zero ela ficará com o valor desejado após a primeira execução do comando <i>soma = soma + num</i>,
ou seja, ela assumirá o valor do primeiro elemento da sequência (se este não for negativo). Note também que para uma sequência vazia, ou seja, para a entrada que já começa com um
número negativo, o resultado escrito na saida será 0, que é o desejado.<br />
<b>Exercício 2:</b><i>Fala a simulação deste programa para as entradas 10   3   4   -5 e veja as diferenças em relação à versão anterior do código, prestando atenção às linhas
5 e 6 no C, 4 e 5 no Python. Note que após a leitura do número -5, não é executado o comando <b>soma = soma + num</b>, pois o teste do <b>while</b> fica falso e o programa para
o comando de escrita (printf no C; print no Python) </i><br /><br />

<b>Exercício 3: </b><i>Ainda considerando o enunciado do problema 2, verifique o que há de errado com o programa a seguir:</i><br />
<center>
<table>
 <tr>
   <th> C </th>
   <th>Python</th></tr>
 <tr>
   <td>
     <pre>
1  int num, soma;
2  scanf("%d", &num);
3  soma = 0;
4  while(num!=0){
5    scanf("%d", num);
6    soma = soma + num;
7  }
8  printf("%d", soma);
     </pre>
   </td>
   <td>
     <pre>
1  num = input();
2  soma = 0
3  while num != 0:
4    num = input()
5    soma = soma+num
6  print(soma)
     </pre>
   </td>
 </tr>
</table>
</center>
</p>

<h2>3.2 - Como computar uma potência de inteiros usando laço de repetição</h2>
<p>
  <b>Problema 3:</b><i>Dado X real e N natural, faça um programa que calcule X<sup>N</sup></i><br />
  Novamente, se N fosse fixo, por exemplo n=3, bastaria fazer<br />
  <center>
    <table>
     <tr>
       <th> C </th>
       <th>Python</th></tr>
     <tr>
       <td>
         <pre>
1  int x;
2  scanf("%d", &x);
3  printf("%d", x*x*x);
         </pre>
       </td>
       <td>
         <pre>
1  x = input()
2  print(x*x*x)
         </pre>
       </td>
     </tr>
    </table>
    <div>
      <img src="./imgs/potencia_x_3.png" /><br />
      <span>Código no iVProg</span>
    </div>
  </center>
Portanto a dificuldade deste problema se encontra na repetição arbitrária: repetir a operação de multiplicação um número variável de vezes, dependente da vontade do usuário.<br />
Novamente, vamos iniciar o processo de resolução examinando um exemplo, x=2 e n=7.<br />
1. Multiplique X por X, guardando o resultado desta conta(4); <br />
2. Multiplique por x o resultado guardado, guardando o novo resultado (8);<br />
3. Repita o passo(2) outras 4 vezes (pois n=7 e x já entrou 3 vezes como fator de multiplicação) obtendo o resultado final, 128.<br />
<h3>Quais são as variáveis necessárias?</h3>
Claramente precisamos de variáveis para armazenar X e N. Além destas, será necessária outra variável (<b>result</b>) para armazenar o resultado das operações de potenciação de X,
sem a qual não será possível guardar o resultado das multiplações executadas(reflita sobre isto!).<br />
Neste problema, notamos uma novidade em relação ao anterior, precisamos contar quantas vezes já usamos o fator X (original). assim, vamos denotar esta variável pelo sugestivo nome de
<b>cont</b>: a cada multiplicação somaremos 1 nessa variável. Assim, deveremos declarar as seguintes variáveis:<br />
<center>
  int x, n, result, cont;
</center>
<h3>Quais os comandos devem aparecer dentor do bloco de repetição?</h3>
Podemos observar no esquema inicial, elaborado acima, que o passo (2) é a parte repetitiva do processo: multiplicar o resultado atual de <b>result</b> por X, guardando este produto
novamente em <b>result</b>. Feito isto, devemos então somar 1 ao contador <b>cont</b>, para indicar que mais uma multiplicação foi efetuada.
<center>
<table>
 <tr>
   <th> C </th>
   <th>Python</th></tr>
 <tr>
   <td>
     <pre>
while (condição){
  result = result*x;
  cont = cont+1;
}
     </pre>
   </td>
   <td>
     <pre>
while condição:
  result = result*x
  cont = cont+1
     </pre>
   </td>
 </tr>
</table>
</center>
<h3>Qual a condição para que continue a repetição?</h3>
Já foi observado que a variável <b>cont</b> serve para contar quantas vezes o fator X já entrou no produto, assim devemos interromper o laço quando <b>cont==n</b>, ou de outro modo,
devemos continuar enquanto <b>cont< n</b>.
<center>
<table>
 <tr>
   <th> C </th>
   <th>Python</th></tr>
 <tr>
   <td>
     <pre>
while (<b>cont < n</b>){
  result = result*x;
  cont = cont+1;
}
     </pre>
   </td>
   <td>
     <pre>
while <b>cont < n</b>:
  result = result*x
  cont = cont+1
     </pre>
   </td>
 </tr>
</table>
</center>
<h3>O que deve vir antes da repetição?</h3>
Em primeiro lugar, devemos ler os valores <b>x</b> e <b>n</b>. Precisamos também atribuir valores iniciais adequados às variáveis <B>cont</B> e <b>result</b>. Como <b>cont</b> totaliza
quantos fatores <b>x</b> já entraram no produto, o valor inicial de <b>cont</b> é zero. Assim, após a primeira execução do comando <b>result = result*x</b>, gostariamos de obter o valor
de <b>x</b> em <b>result</b> e por isto devemos impor que <b>result</b> comece com o valor 1.<br />
Interrompido o laço, a resposta estará armazenada em <b>result</b>:
<center>
<table>
 <tr>
   <th> C </th>
   <th>Python</th></tr>
 <tr>
   <td>
     <pre>
1  int x, n, result, cont;
2  scanf("%d %d", &x, &n);
3  cont = 0;
4  result = 1;
5  while (<b>cont < n</b>){
6    result = result*x;
7    cont = cont+1;
8  }
9  printf("%d", result);
     </pre>
   </td>
   <td>
     <pre>
1  x = input()
2  n = input()
3  cont = 0
4  result = 1
5  while <b>cont < n</b>:
6    result = result*x
7    cont = cont+1
8  print(result)
     </pre>
   </td>
 </tr>
</table>
<div>
  <img src="./imgs/potencia_x_n.png" /><br />
  <span>Código no iVProg</span>
</div>
</center>
<b>Exercício 4</b> <i>Repare que o programa dá a resposta correta quando n==0, porém quando x==0 e n==0 teriamos um resultado, mesmo que na matemática 0<sup>0</sup>
  é indeterminado.</i><br />
<b>Exercício 5</b> <i>Sugerimos como exercício a simulação deste programa, para alguns dados de entrada à escolha do leitor.</i><br />
<b>Exercicio 6</b> <i>O programa abaixo foi proposto para calcular x<sup>n</sup>. Analise o algoritmo, ele está correto? Se não estiver o que há de errado?</i>
<center>
<table>
 <tr>
   <th> C </th>
   <th>Python</th></tr>
 <tr>
   <td>
     <pre>
1  int x, n, cont;
2  scanf("%d %d", &x, &n);
3  cont = 0;
4  while (cont < n){
5    x = x*x;
6    cont = cont+1;
7  }
8  printf("%d", x);
     </pre>
   </td>
   <td>
     <pre>
1  x = input()
2  n = input()
3  cont = 0
4  while cont < n:
5    x = x*x
6    cont = cont+1
7  print(x)
     </pre>
   </td>
 </tr>
</table>
<div>
  <img src="./imgs/potencia_x_n_errada.png" /><br />
  <span>Código no iVProg</span>
</div>
</center>
<b>Exercício 7</b> <i>É possível alterar o programa-solução do problema 3, dispensando a variável contadora <b>cont</b>? Isto é, tente deduzir uma outra versão para o
referido problema, utilizando apenas três variáveis <b>x</b>, <b>n</b> e <b>result</b></i>.
</p>
</body>
</html>