Algo e estrutura de dados estruturas de repeticao

Prévia do material em texto

MC 102 – Algoritmos e programac¸a˜o de computadores
Estruturas de repetic¸a˜o
• Considere o algoritmo de Euclides para o ca´lculo do MDC:
Entrada: dois inteiros positivos m e n;
Sa´ıda: o ma´ximo divisor comum de m e n;
1. x← m;
2. y ← n;
3. repita
4. r ← resto(x, y);
5. x← y;
6. y ← r;
7. ate´ que r = 0;
8. retorne x.
1
MC 102 – Algoritmos e programac¸a˜o de computadores
Estruturas de repetic¸a˜o
• Permitem que uma sequeˆncia de comandos seja executada
repetidas vezes.
• A execuc¸a˜o termina quando um crite´rio de parada e´ atingido.
• Veremos:
– while;
– do. . .while;
– for.
2
MC 102 – Algoritmos e programac¸a˜o de computadores
Comando while
• No while, o crite´rio de parada e´ testado antes que a sequeˆncia
de comandos da ac¸a˜o seja executada.
Condic¸a˜o
True
False
Ac¸a˜o
Sintaxe: while (expressa˜o)
ac¸a˜o
3
MC 102 – Algoritmos e programac¸a˜o de computadores
Um exemplo simples – validac¸a˜o de dados de entrada
• Ler nu´meros ate´ que seja digitado um nu´mero positivo;
4
MC 102 – Algoritmos e programac¸a˜o de computadores
Um exemplo simples – validac¸a˜o de dados de entrada
• Ler nu´meros ate´ que seja digitado um nu´mero positivo;
#include < stdio.h >
int main(){
int num;
printf(‘‘Digite um nu´mero positivo: \n”);
scanf(‘‘%d’’, &num);
while (num <= 0) {
printf(‘‘ERRO: nu´mero na˜o positivo! \n”);
printf(‘‘Digite um nu´mero positivo: \n”);
scanf(‘‘%d’’,&num);
}
. . .
return 0;
}
4
MC 102 – Algoritmos e programac¸a˜o de computadores
• Programa que leia n nu´meros e calcule a me´dia aritme´tica
destes nu´meros.
5
MC 102 – Algoritmos e programac¸a˜o de computadores
• Programa que leia n nu´meros e calcule a me´dia aritme´tica
destes nu´meros.
#include < stdio.h >
int main()
{
int n, cont = 1;
float num, acum = 0;
printf(‘‘Digite quantos nu´meros:\n”);
scanf(‘‘%d”, &n)
while (cont <= n) {
scanf(‘‘%f”,&num);
acum = acum + num;
cont++;
}
printf(‘‘A me´dia e´ %.3f\n”, acum / n);
return 0;
}
5
MC 102 – Algoritmos e programac¸a˜o de computadores
• Quais sa˜o os valores de m e n apo´s a execuc¸a˜o do trecho de
co´digo abaixo.
6
MC 102 – Algoritmos e programac¸a˜o de computadores
• Quais sa˜o os valores de m e n apo´s a execuc¸a˜o do trecho de
co´digo abaixo.
int n = 123456789;
int m = 0
while (n != 0) {
m = (10 * m) + (n % 10);
n = n / 10;
}
6
MC 102 – Algoritmos e programac¸a˜o de computadores
• Programa que leia 10 nu´meros pares na˜o negativos e calcule a
me´dia aritme´tica destes nu´meros.
7
MC 102 – Algoritmos e programac¸a˜o de computadores
• Programa que leia 10 nu´meros pares na˜o negativos e calcule a
me´dia aritme´tica destes nu´meros.
#include < stdio.h >
int main()
{
int n, cont=0, acum=0;
printf(‘‘Digite 10 nu´meros pares:\n”);
while (cont<10) {
scanf(‘‘%d”,&n);
if (n>=0 && !(n%2)) {
acum = acum + n;
cont++;
}
}
printf(‘‘A me´dia e´ %.3f\n”, acum / 10.0);
return 0;
}
7
MC 102 – Algoritmos e programac¸a˜o de computadores
Imprimir os 20 primeiros nu´meros de Fibonacci
8
MC 102 – Algoritmos e programac¸a˜o de computadores
Imprimir os 20 primeiros nu´meros de Fibonacci
#include < stdio.h >
int main(){
int f1=0, f2=1, cont=2, aux;
printf(‘‘0, 1”);
while (cont < 20) {
aux = f2;
f2 = f1 + f2;
f1 = aux;
printf(‘‘, %d”, f2);
cont++;
}
printf(‘‘.\n”);
return 0;
}
8
MC 102 – Algoritmos e programac¸a˜o de computadores
• Programa que leia um nu´mero inteiro e imprima quantos d´ıgitos este
nu´mero possui.
9
MC 102 – Algoritmos e programac¸a˜o de computadores
• Programa que leia um nu´mero inteiro e imprima quantos d´ıgitos este
nu´mero possui.
#include < stdio.h >
#include < math.h >
int main()
{
int n, cont;
scanf(‘‘%d”, &n);
n = abs(n);
cont = 1;
n = n / 10;
while (n != 0) {
cont++;
n = n / 10;
}
printf(‘‘%d d´ıgitos.\n”, cont);
return 0;
}
9
MC 102 – Algoritmos e programac¸a˜o de computadores
Comando do – while
• O crite´rio de parada e´ testado apo´s a sequeˆncia de comandos da ac¸a˜o
ser executada.
– A ac¸a˜o e´ sempre executada pelo menos uma vez.
Condic¸a˜o
True
False
Ac¸a˜o
Sintaxe: do
ac¸a˜o
while (expressa˜o)
10
MC 102 – Algoritmos e programac¸a˜o de computadores
Validac¸a˜o de dados de entrada
11
MC 102 – Algoritmos e programac¸a˜o de computadores
Validac¸a˜o de dados de entrada
#include < stdio.h >
int main()
{
int num;
do {
printf(‘‘Digite um nu´mero positivo: \n”);
scanf(‘‘%d’’,&num);
} while (num <= 0)
. . .
return 0;
}
11
MC 102 – Algoritmos e programac¸a˜o de computadores
Estruturas de repetic¸a˜o
• Considere o algoritmo de Euclides para o ca´lculo do MDC:
Entrada: dois inteiros positivos m e n;
Sa´ıda: o ma´ximo divisor comum de m e n;
1. x← m;
2. y ← n;
3. repita
4. r ← resto(x, y);
5. x← y;
6. y ← r;
7. ate´ que r = 0;
8. retorne x.
12
MC 102 – Algoritmos e programac¸a˜o de computadores
Algoritmo de Euclides
#include < stdio.h >
int main(){
int m, n, x, y, r;
scanf(‘‘%d%d”,&m,&n);
x = m;
y = n;
do {
r = x % y;
x = y;
y = r;
} while (r>0);
printf(‘‘MDC de %d e %d e´ %d\n”, m, n, x);
return 0;
}
13
MC 102 – Algoritmos e programac¸a˜o de computadores
• Ca´lculo de xk, x, k inteiros. Retorne: xk se k > 0; 1 caso contra´rio.
14
MC 102 – Algoritmos e programac¸a˜o de computadores
• Ca´lculo de xk, x, k inteiros. Retorne: xk se k > 0; 1 caso contra´rio.
#include < stdio.h >
int main()
{
int x, k;
long int pot = 1;
scanf(‘‘%d%d”,&x, &k);
if (k>0)
do {
pot = pot * x;
k−−;
} while (k>0);
printf(‘‘%d\n”, pot);
return 0;
}
14
MC 102 – Algoritmos e programac¸a˜o de computadores
• Ideia espertinha −→ k = 2i
int main() {
int x, k;
long int pot=1;
scanf(‘‘%d%d”,&x, &k);
if (k>0) {
pot = x;
k = k / 2;
while (k > 0) {
pot = pot * pot;
k = k / 2;
}
}
printf(‘‘%d\n”, pot);
return 0;
}
15
MC 102 – Algoritmos e programac¸a˜o de computadores
Exerc´ıcios
1. Refac¸a os programas feitos em sala trocando do – while por
while e vice-versa.
2. Modifique o programa dos nu´meros de Fibonacci para que o
nu´mero de nu´meros impressos seja um dado fornecido pelo
usua´rio. Imprima cinco nu´meros por linha (a menos da u´ltima
linha que podera´ ter menos de cinco nu´meros).
3. Generalize a ide´ia espertinha de fazer o ca´lculo de xk,
considerando qualquer k ≥ 0.
xk =


x
k
2 . x
k
2 , se k ≡ 0 (mod 2);
x
k−1
2 . x
k−1
2 . x, caso contra´rio.
16
MC 102 – Algoritmos e programac¸a˜o de computadores
Comando for
Sintaxe: for ( expresssa˜o 1; expressa˜o 2; expressa˜o 3)
ac¸a˜o
• Expressa˜o 1: e´ usada para iniciar as varia´veis necessa´rias na
estrutura de repetic¸a˜o – e´ avaliada uma u´nica vez, antes da
primeira iterac¸a˜o;
• Expressa˜o 2: condic¸a˜o de parada – e´ avaliada no in´ıcio de cada
iterac¸a˜o; verdadeira quando seu valor e´ diferente de zero;
• Expressa˜o 3: atualizac¸a˜o das varia´veis envolvidas na condic¸a˜o
de parada – avaliada ao final de cada iterac¸a˜o.
17
MC 102 – Algoritmos e programac¸a˜o de computadores
• Ca´lculo de n!, n inteiro, na˜o muito grande. Retorne: n! se
n ≥ 0; −1 caso contra´rio.
#include < stdio.h >
int main() {
int n, i;
long int fat = 1;
scanf(‘‘%d”,&n);
if (n>=0)
for (i = 1; i<= n; ++i)
fat = fat * i;
else
fat = -1;
printf(‘‘%d\n”, fat);
return 0;
}
18
MC 102 – Algoritmos e programac¸a˜o de computadores
Exerc´ıcios
1. Refac¸a todos os exemplos anteriores nos quais foram usadas
estruturaswhile ou do – while usando for. Quando poss´ıvel
melhore os algoritmos.
2. Fac¸a um programa para ler um nu´mero positivo n ≥ 2 e decidir
se este nu´mero e´ primo.
• Um nu´mero positivo n ≥ 2 e´ primo se e´ divis´ıvel apenas por
1 e por n.
– Note que o nu´mero 1 na˜o e´ primo.
19
MC 102 – Algoritmos e programac¸a˜o de computadores
Ler um nu´mero positivo n ≥ 2 e decidir se este
nu´mero e´ primo
Soluc¸a˜o 1
• Armazenar a informac¸a˜o a priori sobre todos os inteiros
representa´veis.
– Pre´-processamento pode ser muito caro; e
– quantidade de memo´ria necessa´ria pode ser proibitiva.
20
MC 102 – Algoritmos e programac¸a˜o de computadores
Soluc¸a˜o 2
• Passo 1: Lemos o nu´mero, n, que queremos saber se e´ primo.
• Passo 2: Verificamos se n e´ divis´ıvel por i, ∀i ∈ [2, n− 1].
– Se sim para algum i: conclu´ımos que o nu´mero na˜o e´ primo.
• Passo 3: Se n na˜o e´ divis´ıvel por nenhum i ∈ [2, n− 1]
conclu´ımos que e´ primo.
21
MC 102 – Algoritmos e programac¸a˜o de computadores
#include < stdio.h >
int main()
{
int n, i, primo = 1;
printf(‘‘Digite um nu´mero maior ou igual a 2.\n”);
scanf(‘‘%d”, &n);
if (n>=2) {
for (i = 2; i < n; i++)
if (!(n % i)) primo = 0;
if (primo)
printf(‘‘O nu´mero e´ primo!\n”);
else
printf(‘‘O nu´mero na˜o e´ primo!\n”);
}
return 0;
}
22
MC 102 – Algoritmos e programac¸a˜o de computadores
Soluc¸a˜o 3
• Passo 1: Lemos o nu´mero, n, que queremos saber se e´ primo.
• Passo 2: Procuramos por divisores de n observando que
– Se n for par e n 6= 2, enta˜o n na˜o e´ primo.
– Se n na˜o e´ primo, enta˜o n = p.q.
∗ Logo, podemos supor p ≤ √n, com p, q ≥ 2.
• Passo 3: Se algum divisor de n for encontrado, enta˜o n na˜o e´
primo. Caso contra´rio, n e´ primo.
23
MC 102 – Algoritmos e programac¸a˜o de computadores
#include <stdio.h>
#include <math.h>
int main()
{
int n, i, sup, primo = 1;
printf(‘‘Digite um nu´mero maior ou igual a 2.\n”);
scanf(‘‘%d”, &n);
if (n>=2) {
sup = sqrt(n);
for (i=2; primo && (i <= sup) ; i++)
if (!(n%i)) primo = 0;
if (primo) printf(‘‘O nu´mero e´ primo!\n”);
else printf(‘‘O nu´mero na˜o e´ primo!\n”);
}
return 0;
}
24
MC 102 – Algoritmos e programac¸a˜o de computadores
Comando break
• Usado para alterar o fluxo normal do programa;
• E´ usado dentro de estruturas de repetic¸a˜o (em conjunto com
uma estrutura condicional), ou dentro do comando switch;
• Ocasiona a sa´ıda imediata destas estruturas;
– Ocasiona a sa´ıda apenas da estrutura mais interna (apenas
um n´ıvel).
25
MC 102 – Algoritmos e programac¸a˜o de computadores
Comando break
• E´ conveniente? Boa pra´tica de programac¸a˜o?
– Necessa´rio no caso do switch;
– Quando bem usado, pode gerar um co´digo mais conciso e
simples de entender.
while (1) {
scanf(‘‘%lf”, &x);
if (x < 0.0) break;
printf(‘‘%f\n”, sqrt(x));
}
26
MC 102 – Algoritmos e programac¸a˜o de computadores
Comando continue
• Usado para alterar o fluxo normal do programa;
• E´ usado dentro de estruturas de repetic¸a˜o (em conjunto com
uma estrutura condicional).
• Transfere o controle para o final da iterac¸a˜o corrente.
– No caso de while e do – while a condic¸a˜o de parada e´
avaliada imediatamente;
– No caso de for, o controle e´ passado para o passo de
incremento.
27
MC 102 – Algoritmos e programac¸a˜o de computadores
Comando continue
• E´ conveniente? Boa pra´tica de programac¸a˜o?
– Quando bem usado, pode gerar um co´digo mais conciso e
simples de entender.
while (i<10) {
scanf(‘‘%d”,&num);
if (num % 2) continue;
acum = acum + num;
i++;
}
28
MC 102 – Algoritmos e programac¸a˜o de computadores
Comando goto
Na˜o pode ser usado!!!!
Nunca!
De jeito nenhum!
Jamais!
• Estrutura que altera o fluxo do programa. Pode interferir
completamente no conceito de programac¸a˜o estruturada.
• Deve ser evitado.
• Na˜o vou ensinar!!! >:(
29