pc1-cap3

Prévia do material em texto

3. Algoritmos Estruturados 
•  Na programação estruturada, os programas são 
construídos usando apenas 3 estruturas: 
•  sequência (instruções executadas uma a uma, na 
sequência em que aparecem no programa) 
•  seleção (instrução if-else, que seleciona 1 dentre 2 
caminhos possíveis) 
•  repetição (instruções executadas várias vezes) 
•  Lembrando: algoritmo é uma sequência finita de 
instruções que, ao ser executada, chega à solução de um 
problema. 
•  Para ser um algoritmo, a sequência de instruções deve ter 
sua execução finalizada em algum momento. 
•  Com repetição, a execução de uma sequência finita de 
instruções pode não ter fim (algoritmo entrou em "loop"). 
 
 
 
 
© ELFS 89 
Exemplo: Suponha que somar (+) e subtrair (-) são as 
únicas operações disponíveis. Dados dois números inteiros 
positivos A e B, determine o quociente e o resto da divisão 
de A por B. 
•  Algoritmo: 
1.  Sejam A e B os valores dados; 
2.  Atribuir o valor 0 ao quociente (Q); 
3.  Enquanto B couber em A: 
 4. Somar 1 ao valor de Q; 
 5. Subtrair B do valor de A; 
6.  Atribuir o valor final de A ao resto (R). 
 
 
 
 
© ELFS 90 
A 
B 
A = 7, B = 2 
O que sobra em A 
é o resto da divisão. 
Quociente: no de vezes 
que B cabe em A. 
•  Algoritmo, expresso por meio de um fluxograma: 
 
 
 
 
© ELFS 91 
Início 
Fim 
A, B 
Q = 0 
B <= A R = A 
Q, R Q = Q + 1 
A = A - B 
Sim 
Não 
Iteração A B Q R 
0 19 3 0 
1 16 1 
2 13 2 
3 10 3 
4 7 4 
5 4 5 
6 1 6 
7 1 
Está garantido que a 
repetição irá terminar? 
Repetições 
•  Duas construções existentes nas linguagens de 
programação permitem escrever programas para resolver 
qualquer problema: 
•  a possibilidade de atribuir um valor para uma variável 
com base no valor atual desta mesma variável; 
•  a possibilidade de repetir a execução de um bloco de 
instruções quantas vezes forem necessárias. 
•  Sem essas duas construções seríamos capazes de 
escrever programas para resolver apenas problemas 
muito simples! 
•  Um programa que que executa um bloco de instruções 
repetidas vezes realiza um processamento iterativo. Cada 
execução do bloco de instruções denomina-se iteração. 
 
 
 
© ELFS 92 
Exemplo: 
•  Considere o seguinte problema: Dado o valor de N, 
determinar a soma dos números inteiros de 1 a N. 
•  Se o valor de N for conhecido no momento em que se 
está escrevendo o programa, o problema é trivial (embora 
possa ser trabalhoso): 
S = 1 + 2 + 3 + 4 + 5; 
•  Mas como fazer o programa sem conhecer o valor de N? 
•  O desafio é fazer um programa que funcione, qualquer 
que seja o valor de N. 
•  Isso é possível utilizando um comando de repetição. 
•  A ideia é somar uma parcela de cada vez, atualizar o valor 
da parcela e repetir esse processo N vezes. 
 
 
© ELFS 93 
•  Algoritmo: 
 
 
 
 
© ELFS 94 
Início 
Fim 
N 
p <= N 
S 
Sim 
Não 
S = S + p 
p = p + 1 
Iteração N S p 
0 10 0 1 
1 1 2 
2 3 3 
3 6 4 
4 10 5 
5 15 6 
6 21 7 
7 28 8 
8 36 9 
9 45 10 
10 55 11 
S = 0 
p = 1 
Está garantido que essa 
repetição irá terminar? 
•  Para codificar uma repetição pode-se usar o comando 
while: 
 
 
 
© ELFS 95 
#include <stdio.h> 
#include <stdlib.h> 
 
int main() 
{ 
 int N,S,p; 
 printf("Digite N: "); 
 scanf("%d",&N); 
 S = 0; 
 p = 1; 
 while (p <= N) 
 { 
 S = S + p; 
 p++; 
 } 
 printf("S = %d\n",S); 
 return 0; 
} 
O comando while permite que 
um bloco de instruções seja 
executado tantas vezes quantas 
forem necessárias, enquanto 
uma condição for verdadeira. 
•  Um processamento iterativo pode não terminar (por 
exemplo, devido a um erro de implementação). 
•  Exemplo: Soma dos N primeiros inteiros negativos. 
•  O loop infinito pode ser desejável. Exemplo: um programa 
que monitora um reator nuclear deve estar sempre em 
execução. 
 
 
© ELFS 96 
S = 0; 
p = -1; 
while (p <= N) 
{ 
 S = S + p; 
 p--; 
} 
Neste caso, se N >= 0, o valor de 
p sempre será menor do que N, 
ou seja, a condição será sempre 
verdadeira e, portanto, a 
repetição será infinita. 
Como corrigir essa repetição? 
while (1) 
{ 
 ... 
} 
•  Outra forma de codificar a repetição de um bloco de 
instruções é com o comando do-while. 
•  Note que no comando while, a condição é testada antes 
da execução do bloco de instruções, ao contrário do 
comando do-while. O que acontece para N = 0? 
•  Comando while: repete 0 ou mais vezes. 
•  Comando do-while: repete 1 ou mais vezes. 
 
 
© ELFS 97 
S = 0; 
p = 1; 
while (p <= N) 
{ 
 S = S + p; 
 p++; 
} 
Comando while 
S = 0; 
p = 1; 
do 
{ 
 S = S + p; 
 p++; 
} 
while (p <= N); 
Comando do-while 
•  Outra forma de codificar a repetição de um bloco de 
instruções é com o comando for. 
•  Os comandos for e while são absolutamente equivalentes. 
•  Notar que no comando for: 
•  A variável de controle recebe um valor inicial; 
•  Enquanto a condição de repetição for verdadeira, o 
bloco de instruções é executado e o valor da variável 
de controle é atualizado. 
 
 
© ELFS 98 
S = 0; 
p = 1; 
while (p <= N) 
{ 
 S = S + p; 
 p++; 
} 
Comando while 
S = 0; 
for (p = 1; p <= N; p++) 
{ 
 S = S + p; 
} 
Comando for 
Exercícios 
1.  A partir de um quadrado de lado L (float) podemos construir 
uma sequência de N (int) quadrados, tais que os vértices de 
cada novo quadrado são os pontos médios dos lados do 
quadrado anterior. Escrever um programa para mostrar a 
soma das áreas dos N quadrados da sequência. 
2.  Escrever um programa para calcular e mostrar o valor de PI 
usando a série: PI = 4 – (4/3) + (4/5) – (4/7) + ... até que 
um termo da série seja, em valor absoluto, menor do que 
0.0001. Usar a função fabs() para obter o valor absoluto de 
um float. 
3.  Escrever um programa para calcular o máximo divisor comum 
(MDC) entre dois inteiros A e B, com A > B, usando o seguinte 
algoritmo: Enquanto B for diferente de zero, calcular o resto 
da divisão de A por B e fazer: A = B e B = resto. Quando B for 
igual a zero, o MDC será o valor de A. 
 
 
 
© ELFS 99 
4.  Escrever um programa que, dado o valor de T, calcula: 
até que um termo da série seja menor do que T. Mostrar 
o valor de S e o número de termos usados na somatória. 
5.  Escrever um programa que, dado o valor de N (int), 
calcula e mostra o valor de N! = 1 × 2 × ... × N. 
6.  Escrever um programa que calcula: 
7.  Escrever um programa que, dado o valor inteiro N, calcula 
e mostra o valor de ponto flutuante L, dado por: 
8.  Um inteiro n é um número primo se seus únicos divisores 
são 1 e n. Escrever um programa que, dado m (int), 
mostra o menor número primo maior do que m. 
 
 
 
© ELFS 100 
S = 1+ 1
2
+
1
4
+
1
6
+ ...
S = 1
1
−
2
4
+
3
9
−
4
16
+ ... − 10
100
L = N+ (N−1)
2
+
(N− 2)
3
+
(N− 3)
4
+!+ 1
N
9.  Codifique o fluxograma abaixo como um programa C. 
Considere as variáveis E, S, T e X como float e as 
variáveis L, J e R como int. 
 
© ELFS 101 
Para E = 0.1, o 
que será 
mostrado? 
Quantas 
iterações serão 
feitas? 
Para X = 8, o 
que será 
mostrado? 
Quantas 
iterações serão 
feitas? 
10. Suponha que o número de um cartão de crédito seja 
composto por 12 dígitos decimais, sendo que o último 
dígito é calculado como o resto da divisão de S por 10, 
onde S é a soma dos 11 primeiros dígitos. Escrever um 
programa que, dado um inteiro, verifica se este inteiro é 
ou não um número válido de cartão de crédito. 
11. Uma sequência de inteiros positivos é K-alternante se for 
composta alternadamente por segmentos de números 
pares de tamanho K e segmentos de números ímpares de 
tamanho K. Por exemplo: 
•  A sequência: 1 3 6 8 9 11 2 4 1 7 6 8 é 2-alternante. 
•  A sequência: 2 1 4 7 8 9 12 é 1-alternante. 
•  A sequência: 4 2 3 1 6 4 2 9 3 5 não é alternante. 
Escrever um programa que, dados N, K e uma sequência 
com N inteiros, verifica se a sequência é K-alternante. 
 
 
© ELFS 102 
© ELFS 103 
Comandos break e continue em repetições 
•  Para encerrar um processamento iterativo, 
independentementedo valor da condição que controla a 
repetição, deve-se usar o comando break. 
•  Exemplo: dados os valores N (int) e A (float), determine a 
partir de qual termo, o valor de: S = 1 + 1/2 + 1/3 + ... + 
1/N é maior do que A. 
•  Suponha N = 10 e A = 2. 
 
 
 
 
 
Iteração Valor de S 
1 1.000000 
2 1.500000 
3 1.833333 
4 2.083333 
A partir do 4o termo S > A. 
S = 0; 
T = 1; 
while (T <= N) 
{ 
 S = S + 1.0/T; 
 T++; 
} 
•  Exemplo. Escrever um programa que, dados os valores N 
(int) e A (float), calcule S = 1 + 1/2 + 1/3 + ... + 1/N mas 
somente enquanto os termos da série forem maiores do 
do que A. 
•  A condição do while controla apenas o número de termos 
do somatório. A repetição será encerrada pelo comando 
break quando (T <= A). 
 
 
 
 
© ELFS 104 
S = 0; 
i = 1; 
while (i <= N) 
{ 
 T = 1.0/i; 
 if (T <= A) break; 
 S = S + T; 
 i++; 
} 
printf("S = %.2f\n",S); 
•  Exemplo: Ler a idade (int) e o peso (float) de N pessoas e 
determinar a soma dos pesos das pessoas com mais de 30 
anos. 
•  A execução da instrução continue obriga que a condição 
do while seja avaliada novamente. 
 
 
 
© ELFS 105 
printf("Valor de N: "); 
scanf("%d",&N); 
s = 0; 
i = 0; 
while (i < N) 
{ 
 i++; 
 printf("Idade e peso da pessoa %d: ",i); 
 scanf("%d %f",&idade,&peso); 
 if (idade <= 30) 
 continue; 
 s = s + peso; 
} 
printf("Soma dos pesos = %.1f\n",s); 
A execução do comando continue faz 
com que a instrução s = s + peso não 
seja executada quando idade <= 30. 
O comando switch 
 
 
 
 
 
© ELFS 106 
int main() 
{ 
 int m,dias; 
 printf("Qual mes? "); 
 scanf("%d",&m); 
 if (m == 1) dias = 31; 
 else if (m == 2) dias = 28; 
 else if (m == 3) dias = 31; 
 else if (m == 4) dias = 30; 
 else if (m == 5) dias = 31; 
 else if (m == 6) dias = 30; 
 else if (m == 7) dias = 31; 
 else if (m == 8) dias = 31; 
 else if (m == 9) dias = 30; 
 else if (m == 10) dias = 31; 
 else if (m == 11) dias = 30; 
 else if (m == 12) dias = 31; 
 printf("No.dias = %d\n",dias); 
 return 0; 
} 
•  O uso do comando 
switch é interessante 
quando se tem muitos 
comandos if-else 
interrelacionados. 
•  Imagine que se deseja 
obter o número de dias 
de um dado mês m 
(considere que 
fevereiro tem sempre 
28 dias). 
 
 
 
 
 
•  Usando o 
comando switch: 
 
 
 
 
 
© ELFS 107 
int main() 
{ 
 int m,dias; 
 printf("Qual mes? "); 
 scanf("%d",&m); 
 switch (m) 
 { 
 case 1: dias = 31; break; 
 case 2: dias = 28; break; 
 case 3: dias = 31; break; 
 case 4: dias = 30; break; 
 case 5: dias = 31; break; 
 case 6: dias = 30; break; 
 case 7: dias = 31; break; 
 case 8: dias = 31; break; 
 case 9: dias = 30; break; 
 case 10: dias = 31; break; 
 case 11: dias = 30; break; 
 case 12: dias = 31; break; 
 } 
 printf("No.dias = %d\n",dias); 
 return 0; 
} 
No comando switch, uma 
vez selecionado um 
caso, todos os comandos 
associados a este caso e 
aos casos seguintes serão 
executados em sequência 
até o final do switch. Para 
evitar a execução dos 
comandos seguintes, o 
comando break é usado. 
•  Outra forma de escrever o comando switch: 
 
 
 
 
 
© ELFS 108 
 switch (m) 
 { 
 case 1: 
 case 3: 
 case 5: 
 case 7: 
 case 8: 
 case 10: 
 case 12: dias = 31; break; 
 case 2: dias = 28; break; 
 case 4: 
 case 6: 
 case 9: 
 case 11: dias = 30; break; 
 } 
Observar que, uma vez 
selecionado um caso, 
serão executados todos os 
comandos a partir desse 
caso até encontrar um 
break. 
•  Em geral, num comando switch, após cada caso existe um 
comando break. Mas o uso do break não é obrigatório. 
•  O uso do break é necessário quando os casos são 
independentes uns dos outros, ou seja, quando se quer 
executar apenas 1 dos casos. 
•  Imagine a seguinte situação: dados os valores de dia, 
mes, ano deseja-se calcular o número de dias 
transcorridos desde 01/01/ano até dia/mes/ano 
(considerando que fevereiro tem sempre 28 dias). 
•  Por exemplo: 13/05/2019 
•  Quantos dias já foram transcorridos? 
•  31 (jan) + 28 (fev) + 31 (mar) + 30 (abr) + 13 (mai) = 
133 dias. 
•  Como usar o switch para esse cálculo? 
 
 
 
 
 
© ELFS 109 
© ELFS 110 
int main() 
{ 
 int d,m,a,dias; 
 scanf("%d %d %d",&d,&m,&a); 
 dias = d; 
 switch (m-1) 
 { 
 case 11: dias = dias + 30; 
 case 10: dias = dias + 31; 
 case 9: dias = dias + 30; 
 case 8: dias = dias + 31; 
 case 7: dias = dias + 31; 
 case 6: dias = dias + 30; 
 case 5: dias = dias + 31; 
 case 4: dias = dias + 30; 
 case 3: dias = dias + 31; 
 case 2: dias = dias + 28; 
 case 1: dias = dias + 31; 
 } 
 printf("Transcorridos %d dias.", dias); 
 return 0; 
} 
Observar que, neste 
programa, o uso do 
break é inadequado, 
pois deseja-se que uma 
vez selecionado um 
caso, todos os casos 
seguintes também 
sejam executados.