3 - Perguntas básicas para implementar um algoritmo
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.
Um programa 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.
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.
- 1ª Pergunta: Quais variáveis são necessárias?
- 2ª Pergunta: Quais comandos devem apareceer dentro de um bloco de repetição?
- 3ª Pergunta: Qual a condição para que continue a repetição?
- 4ª Pergunta: Quais os comandos necessários antes e depois do bloco de repetição?
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.
Veremos, a seguir, o desenvolvimento de programas para alguns problemas.
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
3.1 - Como somar um número arbitrário de valores
Problema: Faça um programa que leia uma sequência de números inteiros, diferentes de zero, e calcule a sua soma.
Se a sequência de entrada tivesse um tamanho fixo conhecido, digamos 4, a descrição do processo não seria complicada, bastando escrever:
C |
Python |
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
|
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
|
Código no iVProg
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.
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.
Duas possíveis soluções são:
- Ao início da execução do algoritmo o usuário digitar qual o tamanho da sequência
- Utilizarmos um caracter de escape que indicará o final da sequência
Abaixo iremos apresentar a segunda solução, utilizar um caracter de escape.
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
- Leia o primeiro número 8;
- Como o número lido !=(diferente) 0, leia o próximo número 3, guardando a soma destes dois 19+3 = 22;
- Como o último número lido != 0, leia o próximo número 3, guardando com a soma anterior 19+3=22;
- Como o último número lido != 0, leia o próximo número -7, guardando com a soma anterior 22+(-7)=15;
.
.
.
- Lê o 0, e como o número lido foi 0 imprime a soma final
Quais variáveis são necessárias?
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:
C |
Python |
int num, soma;
|
num = 0
soma = 0
|
Quais os comandos necessários antes e depois do bloco de repetição?
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 while (num !=0). Quanto deve valer a variável num neste momento inicial?
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.
Exercício 1: Tente elaborar outra solução, que não faça uma primeira leitura de num dentro do laço
Após a repetição devemos imprimir o conteúdo da variável soma, que deverá conter a soma dos elementos da sequência de entrada.
Escrevendo o código temos:
C |
Python |
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);
|
1 num = input();
2 soma = num;
3 while num != 0
4 num = input()
5 soma = soma + num
6 print(soma)
|
Código no iVProg
Conceito de simulação de um Algoritmo
Um conceito muito importante à programação é o processo de simulação 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
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:
num |
soma |
comando em execução |
observações |
? |
? |
|
no início do programa valores das variáveis são desconhecidos, elas apenas foram declaradas |
10 |
? |
scanf("%d", &num) |
pega o 1º número de entrada e guarda em num |
10 |
10 |
soma = num |
Atribui o valor de num a soma |
10 |
10 |
while (num != 0) |
Como num é diferente de 0, executa os comandos dentro do bloco de repetição (linhas 5 e 6) |
3 |
10 |
scanf("%d", num) |
Recebe o 2º número de entrada e guarda em num |
3 |
13 |
soma = soma + num |
atribui a soma o valor da expressão soma + num |
3 |
13 |
while(num!=0) |
Como num é diferente de 0, o programa continuará a repetição |
4 |
13 |
scanf("%d", num) |
|
4 |
17 |
soma = soma+ num |
|
4 |
17 |
while(num!=0) |
|
0 |
17 |
soma = soma + num |
|
0 |
17 |
while(num!=0) |
Como soma é igual a 0, o programa pula para a linha 8 |
0 |
17 |
printf("%d", soma) |
Imprime o valor de soma: 17 |
Saída do programa: 17
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 while. 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?
Antes de seguir com a leitura pense na questão
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.
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.
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.
C |
Python |
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);
|
1 num = input();
2 soma = 0;
3 while num >= 0:
4 soma = soma + num
5 num = input()
6 print(soma)
|
Código no iVProg
Note também a diferença da inicialização da variável soma. Começando com zero ela ficará com o valor desejado após a primeira execução do comando soma = soma + num,
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.
Exercício 2: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 soma = soma + num, pois o teste do while fica falso e o programa para
o comando de escrita (printf no C; print no Python)
Exercício 3: Ainda considerando o enunciado do problema 2, verifique o que há de errado com o programa a seguir:
C |
Python |
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);
|
1 num = input();
2 soma = 0
3 while num != 0:
4 num = input()
5 soma = soma+num
6 print(soma)
|
3.2 - Como computar uma potência de inteiros usando laço de repetição
Problema 3:Dado X real e N natural, faça um programa que calcule XN
Novamente, se N fosse fixo, por exemplo n=3, bastaria fazer
C |
Python |
1 int x;
2 scanf("%d", &x);
3 printf("%d", x*x*x);
|
1 x = input()
2 print(x*x*x)
|
Código no iVProg
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.
Novamente, vamos iniciar o processo de resolução examinando um exemplo, x=2 e n=7.
1. Multiplique X por X, guardando o resultado desta conta(4);
2. Multiplique por x o resultado guardado, guardando o novo resultado (8);
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.
Quais são as variáveis necessárias?
Claramente precisamos de variáveis para armazenar X e N. Além destas, será necessária outra variável (result) 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!).
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
cont: a cada multiplicação somaremos 1 nessa variável. Assim, deveremos declarar as seguintes variáveis:
int x, n, result, cont;
Quais os comandos devem aparecer dentor do bloco de repetição?
Podemos observar no esquema inicial, elaborado acima, que o passo (2) é a parte repetitiva do processo: multiplicar o resultado atual de result por X, guardando este produto
novamente em result. Feito isto, devemos então somar 1 ao contador cont, para indicar que mais uma multiplicação foi efetuada.
C |
Python |
while (condição){
result = result*x;
cont = cont+1;
}
|
while condição:
result = result*x
cont = cont+1
|
Qual a condição para que continue a repetição?
Já foi observado que a variável cont serve para contar quantas vezes o fator X já entrou no produto, assim devemos interromper o laço quando cont==n, ou de outro modo,
devemos continuar enquanto cont< n.
C |
Python |
while (cont < n){
result = result*x;
cont = cont+1;
}
|
while cont < n:
result = result*x
cont = cont+1
|
O que deve vir antes da repetição?
Em primeiro lugar, devemos ler os valores x e n. Precisamos também atribuir valores iniciais adequados às variáveis cont e result. Como cont totaliza
quantos fatores x já entraram no produto, o valor inicial de cont é zero. Assim, após a primeira execução do comando result = result*x, gostariamos de obter o valor
de x em result e por isto devemos impor que result comece com o valor 1.
Interrompido o laço, a resposta estará armazenada em result:
C |
Python |
1 int x, n, result, cont;
2 scanf("%d %d", &x, &n);
3 cont = 0;
4 result = 1;
5 while (cont < n){
6 result = result*x;
7 cont = cont+1;
8 }
9 printf("%d", result);
|
1 x = input()
2 n = input()
3 cont = 0
4 result = 1
5 while cont < n:
6 result = result*x
7 cont = cont+1
8 print(result)
|
Código no iVProg
Exercício 4 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 00
é indeterminado.
Exercício 5 Sugerimos como exercício a simulação deste programa, para alguns dados de entrada à escolha do leitor.
Exercicio 6 O programa abaixo foi proposto para calcular xn. Analise o algoritmo, ele está correto? Se não estiver o que há de errado?
C |
Python |
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);
|
1 x = input()
2 n = input()
3 cont = 0
4 while cont < n:
5 x = x*x
6 cont = cont+1
7 print(x)
|
Código no iVProg
Exercício 7 É possível alterar o programa-solução do problema 3, dispensando a variável contadora cont? Isto é, tente deduzir uma outra versão para o
referido problema, utilizando apenas três variáveis x, n e result.