Algoritmos e Estruturas de Dados

Algoritmos e Estruturas de Dados

Prof. Me. Claudio [email protected]

Estruturas de ControleEstruturas de Controle

SumárioSumário

Estrutura CondicionalEstrutura Condicional

Estrutura de RepetiçãoEstrutura de Repetição

SumárioSumário




início

separar ingredientes

fim

misturar ingredientes

colocar massa no forno

tirar bolo do forno

Execução Execução seqüencialseqüencial::

Cada comando é Cada comando é executado executado seqüencialmenteseqüencialmente, , na ordem em que na ordem em que são escritos.são escritos.

início

olhar o céu

fim

levar guarda-chuva

usar roupa leve

chuva?

V

F


Execução seletiva Execução seletiva ou condicional:ou condicional:

Permite a escolha Permite a escolha de um grupo de de um grupo de ações (bloco), ações (bloco), quando certas quando certas condiçõescondições são (ou são (ou não são) não são) satisfeitas.satisfeitas.


SimplesSimples

CompostaComposta

Múltipla escolhaMúltipla escolha

Estrutura Condicional SimplesEstrutura Condicional Simples

início

olhar o céu

fim

acenderluz

escuro?

V

F

se <condição> então<ação>

fim se

se <condição> então<ação>

fim se


Utilizada quando precisamos testar uma Utilizada quando precisamos testar uma certa condição antes de executar uma certa condição antes de executar uma ação.ação.

Exemplo:Exemplo:

// declaração de variáveis:real N1, N2, NF, media

// início do programa:ler(N1,N2,NF)media ← (N1 + N2 + NF) / 3.0

se (media ≥ 5.0) entãoescrever(“Aluno aprovado”)

fim se

fim programa



se (media ≥ 5.0) entãoescrever(“Aluno aprovado”)

fim se

fim programa


Estrutura Condicional CompostaEstrutura Condicional Composta

início

olhar a vovó

fim

Chamar caçador

narizgrande?

V

Entregar cesta de comida

F

se <condição> então<ação1>

senão<ação2>

fim se

se <condição> então<ação1>

senão<ação2>

fim se


Utilizada em situações em que Utilizada em situações em que duas duas alternativas alternativas dependemdependem da da mesmamesma condição, uma da condição condição, uma da condição verdadeira verdadeira (então)(então) e a outra da condição e a outra da condição falsa falsa (senão)(senão)..



se (media ≥ 5.0) entãoescrever("Aluno aprovado")

senãoescrever("Aluno reprovado")

fim se

fim programa



se (media ≥ 5.0) entãoescrever("Aluno aprovado")

senãoescrever("Aluno reprovado")

fim se

fim programa


Exemplo:Exemplo:

Estrutura Condicional de Múltipla EscolhaEstrutura Condicional de Múltipla Escolha

início

ler signo

fim

áries? VGanhará na loteria

F

touro?

gêmeos?

Não saia de casa hoje!

Sorte no amor

F

F

V

V

se <cond_01> então<ação1>

senão se <cond_02> então<ação2>


....senão

<ação default>fim se

se <cond_01> então<ação1>



....senão

<ação default>fim se

switch <variável> caso x1:

<ação1>caso x2:

<ação2>caso x3:

<ação3>...default

<ação default>fim switch

switch <variável> caso x1:

<ação1>caso x2:

<ação2>caso x3:

<ação3>...default

<ação default>fim switch


Utilizada quando um conjunto de valores Utilizada quando um conjunto de valores discretos e ações diferentes são discretos e ações diferentes são associadas a cada um desses valores.associadas a cada um desses valores.

O comando O comando switch-caseswitch-case testa apenas testa apenas igualdadeigualdade

A corrente A corrente if-esle-if if-esle-if pode avaliar uma pode avaliar uma expressão de relação ou lógicaexpressão de relação ou lógica


switch (mês)caso 1:

dias = 31caso 2:

dias = 28caso 3:

dias = 31caso 4:

dias = 30caso 5:

dias = 31caso 6:

dias = 30....

default:dias = 0

fim switch

switch (mês)caso 1:

dias = 31caso 2:

dias = 28caso 3:

dias = 31caso 4:

dias = 30caso 5:

dias = 31caso 6:

dias = 30....

default:dias = 0

fim switch

Exemplo:Exemplo:

Dado a variável Dado a variável inteira inteira mêsmês, , determinar o determinar o número de dias ao número de dias ao mês mês correspondente.correspondente.


SumárioSumário



Estruturas de RepetiçãoEstruturas de Repetição

Permitem que uma seqüência de Permitem que uma seqüência de comandos seja executada comandos seja executada repetidamenterepetidamente, , até que determinada até que determinada condição de condição de interrupção seja satisfeitainterrupção seja satisfeita..

São também conhecidas como São também conhecidas como laçoslaços ou ou malhasmalhas..

Cada repetição do conjunto de comandos Cada repetição do conjunto de comandos é chamada é chamada iteraçãoiteração..

Estruturas de RepetiçãoEstruturas de Repetição

A repetição de comandos em um laço A repetição de comandos em um laço pode seguir um dos seguintes critérios:pode seguir um dos seguintes critérios:

Por Por CondiçãoCondição (Verificação no (Verificação no inícioinício))

Por Por CondiçãoCondição (Verificação no (Verificação no fimfim))

Por Por ContagemContagem

enquanto (<condição>) fazer<ações>

fim fazer

enquanto (<condição>) fazer<ações>

fim fazer

Estrutura de Repetição por Condição:: Verificação no inícioEstrutura de Repetição por Condição:: Verificação no início

Permite que comandos sejam repetidos Permite que comandos sejam repetidos enquantoenquanto uma condição não é atendida.uma condição não é atendida.

...soma = 0i = 1enquanto (i ≤ N) fazer

soma = soma + ii = i + 1

fim fazer...

...soma = 0i = 1enquanto (i ≤ N) fazer

soma = soma + ii = i + 1

fim fazer...

Estrutura de Repetição por Condição:: Verificação no inícioEstrutura de Repetição por Condição:: Verificação no início

Exemplo:Exemplo: Dado o valor de Dado o valor de NN, calcular a soma dos , calcular a soma dos

números inteiros de números inteiros de 11 a a NN..

fazer<ações>

enquanto <condição> fim fazer

fazer<ações>

enquanto <condição> fim fazer

Estrutura de Repetição por Condição:: Verificação no fimEstrutura de Repetição por Condição:: Verificação no fim

Permite que comandos sejam repetidos Permite que comandos sejam repetidos até queaté que uma condição seja atendida.uma condição seja atendida.

...s = 0i = 1fazer

s = s + ii = i + 1

enquanto (i ≤ N) fim fazer...

...s = 0i = 1fazer

s = s + ii = i + 1

enquanto (i ≤ N) fim fazer...

Estrutura de Repetição por Condição:: Verificação no fimEstrutura de Repetição por Condição:: Verificação no fim



Verificação no fimVerificação no fim

O conjunto de O conjunto de instruções será instruções será executado executado pelo pelo menos uma vezmenos uma vezCondição é Condição é verificada verificada depoisdepois do conjunto de do conjunto de instruçõesinstruções

Verificação no fimVerificação no fim

O conjunto de O conjunto de instruções será instruções será executado executado pelo pelo menos uma vezmenos uma vezCondição é Condição é verificada verificada depoisdepois do conjunto de do conjunto de instruçõesinstruções

Verificação no Verificação no inícioinício

Condição é Condição é verificada verificada antesantes do conjunto de do conjunto de instruçõesinstruções

Verificação no Verificação no inícioinício

Condição é Condição é verificada verificada antesantes do conjunto de do conjunto de instruçõesinstruções

Estrutura de Repetição por Condição:: Verificação no fim × Verificação no início

Estrutura de Repetição por Condição:: Verificação no fim × Verificação no início

para (início; fim; incremento)

<ações>

fim para

para (início; fim; incremento)

<ações>

fim para

Estrutura de Repetição por ContagemEstrutura de Repetição por Contagem

Permite que comandos sejam repetidos Permite que comandos sejam repetidos um determinado número de vezes.um determinado número de vezes.


inícioinício: define qual a variável de controle : define qual a variável de controle da malha (contador) e seu valor inicial.da malha (contador) e seu valor inicial.

fimfim: define o valor final da variável de : define o valor final da variável de controle.controle.

incrementoincremento: define como a variável de : define como a variável de controle se altera a cada repetição.controle se altera a cada repetição.

...soma = 0para (i=1; N; incremento=1)

soma = soma + ifim para...

...soma = 0para (i=1; N; incremento=1)

soma = soma + ifim para...




Estruturas de Repetição:: Considerações finaisEstruturas de Repetição:: Considerações finais

Número de repetições pode ser Número de repetições pode ser indeterminadoindeterminado, mas não deve ser infinito , mas não deve ser infinito ((looploop).).

As formas de laços de repetição são As formas de laços de repetição são equivalentesequivalentes entre si. entre si.

A escolha entre uma e outra é arbitrária.A escolha entre uma e outra é arbitrária.

s = 0i = 1enquanto (i ≤ N) fazer

s = s + ii = i + 1

fim fazer

s = 0i = 1enquanto (i ≤ N) fazer

s = s + ii = i + 1

fim fazer

s = 0para (i=1; N; incremento=1)

s = s + ifim para

s = 0para (i=1; N; incremento=1)

s = s + ifim para

atribuição-1enquanto (condição) fazer

instruçõesatribuição-2

fim fazer

atribuição-1enquanto (condição) fazer

instruçõesatribuição-2

fim fazer

para (atribuição-1; condição; atribuição-2)

instruçõesfim para

para (atribuição-1; condição; atribuição-2)

instruçõesfim para

Repetição por condiçãoRepetição por condição Repetição por contagemRepetição por contagem

Estruturas de Repetição:: Considerações finaisEstruturas de Repetição:: Considerações finais

Exemplo 1Exemplo 1

O IMC (Índice de Massa Corporal) é um critério da O IMC (Índice de Massa Corporal) é um critério da Organização Mundial da saúde para dar uma indicação Organização Mundial da saúde para dar uma indicação sobre a condição de peso de uma pessoa adulta. sobre a condição de peso de uma pessoa adulta.

A fórmula éA fórmula é

Elabore um algoritmo que leia o Elabore um algoritmo que leia o pesopeso e a e a alturaaltura de um de um adulto e adulto e mostre sua condiçãomostre sua condição..

2)(altura

pesoIMC

IMC em adultosIMC em adultos CondiçãoCondição

abaixo de 18,5abaixo de 18,5 abaixo do pesoabaixo do peso

entre 18,5 e 25entre 18,5 e 25 peso normalpeso normal

entre 25 e 30entre 25 e 30 acima do pesoacima do peso

acima de 30acima de 30 obesoobeso

Exemplo 1 – EsboçoExemplo 1 – Esboço

Variáveis:Variáveis:

EntradaEntrada: peso, altura: peso, altura

TipoTipo: real (float): real (float)

IntervaloIntervalo: maior que zero: maior que zero

SaídaSaída: IMC: IMC

TipoTipo: real: real

Comandos:Comandos:

Ler variáveis de entradaLer variáveis de entrada

Checar validade das variáveis de entradaChecar validade das variáveis de entrada

Calcular IMCCalcular IMC

Determinar condição Determinar condição

Exemplo 1 – AlgoritmoExemplo 1 – Algoritmo

iníciofloat peso, altura, imcler(peso, altura)se ((peso ≤ 0) OU (altura ≤ 0)) então

escrever("Valores Inválidos")senão

imc = peso / (altura * altura)se (imc ≤ 18,5) então

escrever("Abaixo do peso")senão se (imc ≤ 25) então

escrever("Peso normal")senão se (imc ≤ 30) então

escrever("Acima do peso")senão

escrever("Obeso")fim se

fim sefim programa

iníciofloat peso, altura, imcler(peso, altura)se ((peso ≤ 0) OU (altura ≤ 0)) então

escrever("Valores Inválidos")senão

imc = peso / (altura * altura)se (imc ≤ 18,5) então

escrever("Abaixo do peso")senão se (imc ≤ 25) então

escrever("Peso normal")senão se (imc ≤ 30) então

escrever("Acima do peso")senão

escrever("Obeso")fim se

fim sefim programa

verifica verifica validade dos validade dos valores valores inseridosinseridoscalcula IMCcalcula IMC

verifica verifica posição na posição na tabelatabela

Exemplo 2Exemplo 2

Anacleto tem Anacleto tem 1,50m1,50m e cresce e cresce 2cm2cm por por ano, enquanto Felisberto tem ano, enquanto Felisberto tem 1,10m1,10m e e cresce cresce 3cm3cm por ano. por ano.

Construa um algoritmo que calcule e Construa um algoritmo que calcule e imprima imprima quantos anosquantos anos serão necessários serão necessários para que Felisberto seja maior que para que Felisberto seja maior que Anacleto.Anacleto.


Crescimento da Crescimento da AnacletoAnacleto:: Altura inicial:Altura inicial: alt_a = 1,5alt_a = 1,5

Altura após cada ano:Altura após cada ano: alt_a = alt_a + 0,02alt_a = alt_a + 0,02

Crescimento de Crescimento de FelisbertoFelisberto:: Altura inicial:Altura inicial: alt_f = 1,1alt_f = 1,1

Altura após cada ano:Altura após cada ano: alt_f = alt_f + 0,03alt_f = alt_f + 0,03

Condição de parada:Condição de parada: alt_f > alt_aalt_f > alt_a

Exemplo 2 – AlgoritmoExemplo 2 – Algoritmo

iníciointeiro ano = 0float alt_a = 1,5float alt_f = 1,1enquanto (alt_a > alt_f)

fazeralt_a = alt_a + 0,02alt_f = alt_f + 0,03ano = ano + 1

fim fazerescrever(ano)

fim programa

iníciointeiro ano = 0float alt_a = 1,5float alt_f = 1,1enquanto (alt_a > alt_f)

fazeralt_a = alt_a + 0,02alt_f = alt_f + 0,03ano = ano + 1

fim fazerescrever(ano)

fim programa

condiçõecondições iniciaiss iniciais

Exemplo 3Exemplo 3

Apresente dois algoritmos para calcular o Apresente dois algoritmos para calcular o valor da seguinte soma.valor da seguinte soma. Estrutura de Estrutura de repetiçãorepetição por por condiçãocondição..

Estrutura de Estrutura de repetiçãorepetição por por contagemcontagem..

100

10

36

6

25

5

16

4

9

3

4

21 S

Exemplo 3 – Termo geralExemplo 3 – Termo geral

100

10

36

6

25

5

16

4

9

3

4

21 S

2222 3322 4422 5522 6622 101022

Termo geral:Termo geral:

1122

11

21)1(i

ii

Exemplo 3 – AlgoritmosExemplo 3 – Algoritmos

início // Contagemfloat ifloat soma = 0para ((i = 1); (i ≤ 10); (incremento = 1))

soma = soma + (-1)^(i+1)*(i)/(i*i)fim paraescrever(soma)

fim programa

início // Contagemfloat ifloat soma = 0para ((i = 1); (i ≤ 10); (incremento = 1))

soma = soma + (-1)^(i+1)*(i)/(i*i)fim paraescrever(soma)

fim programa

termo termo geralgeral

início // Condiçãofloat soma, isoma = 0i = 1enquanto (i ≤ 10) fazer

soma = soma + (-1)^(i+1)*(i)/(i*i)i = i + 1

fim fazerescrever(soma)

fim programa

início // Condiçãofloat soma, isoma = 0i = 1enquanto (i ≤ 10) fazer

soma = soma + (-1)^(i+1)*(i)/(i*i)i = i + 1

fim fazerescrever(soma)

fim programa

termo termo geralgeral

Exemplo 4Exemplo 4

iníciointeiros: A, B, i, jler(A)fazer

para (i=1; i ≤ A; incremento=1)j = ienquanto (j ≤ A) fazer

escrever(j)j = j + 1

fim fazerfim paraB = Aler(A)

enquanto ((A ≠ B) AND (A > 0))fim fazer

fim

iníciointeiros: A, B, i, jler(A)fazer

para (i=1; i ≤ A; incremento=1)j = ienquanto (j ≤ A) fazer

escrever(j)j = j + 1

fim fazerfim paraB = Aler(A)

enquanto ((A ≠ B) AND (A > 0))fim fazer

fim

O que será mostrado se inserirmos 4 e 0?O que será mostrado se inserirmos 4 e 0? O que será mostrado se inserirmos 3, 2 e 2?O que será mostrado se inserirmos 3, 2 e 2? O que será mostrado se inserirmos 2, 1 e 0?O que será mostrado se inserirmos 2, 1 e 0? O que será mostrado se inserirmos 1 e 0?O que será mostrado se inserirmos 1 e 0?

Exemplo 5Exemplo 5

Construa um algoritmo que verifique se Construa um algoritmo que verifique se um número fornecido pelo usuário é primo um número fornecido pelo usuário é primo ou não.ou não.


O que é um número primo?O que é um número primo?

(divisível por ele mesmo) (divisível por ele mesmo) EE (divisível por 1) (divisível por 1)

ZeroZero e e UmUm não são primos não são primos

Se Se AA é divisível por é divisível por BB, então (, então (A % B = 0A % B = 0))

Checar divisibilidade entre número em teste e Checar divisibilidade entre número em teste e divisores.divisores.

Repetir teste, incrementando-se o divisor a partir de Repetir teste, incrementando-se o divisor a partir de 22..

Se um dos resto for Se um dos resto for zerozero, não há necessidade de , não há necessidade de testar novos divisores testar novos divisores número em teste é primo. número em teste é primo.

Não há necessidade de testar divisores Não há necessidade de testar divisores maiores que maiores que a metadea metade do número em teste. do número em teste.

Exemplo 5 – Algoritmo:: Refinamento 1Exemplo 5 – Algoritmo:: Refinamento 1

iníciointeiro num, div, restoler(num)div = 2enquanto ((div < num/2) AND (resto ≠ 0)) fazer

resto = num % divdiv = div + 1

fim fazerse (resto ≠ 0) então

escrever("É primo")senão

escrever("Não é primo")fim se

fim programa

iníciointeiro num, div, restoler(num)div = 2enquanto ((div < num/2) AND (resto ≠ 0)) fazer



escrever("É primo")senão

escrever("Não é primo")fim se

fim programa

testa testa divisibilidadedivisibilidade

determina determina primalidade primalidade de acordo de acordo com o restocom o resto


iníciointeiro num, div, restoler(num)se (num < 0) então

escrever("Valor Inválido")senão

div = 2enquanto ((div < num/2) AND (resto ≠

0)) fazerresto = num % divdiv = div + 1


escrever("É primo")senãoescrever("Não é primo")

fim sefim se

fim programa



div = 2enquanto ((div < num/2) AND (resto ≠

0)) fazerresto = num % divdiv = div + 1



fim sefim se

fim programa

verifica verifica validade dos validade dos valores valores inseridosinseridostesta testa divisibilidadedivisibilidade





se ((num == 1) OU (num == 0)) entãoescrever("Não é primo")

senãodiv = 2enquanto ((div < num/2) AND (resto ≠ 0))

fazerresto = num % divdiv = div + 1



fim sefim se

fim programa




senãodiv = 2enquanto ((div < num/2) AND (resto ≠ 0))

fazerresto = num % divdiv = div + 1



fim sefim se

fim programa

verifica verifica validade dos validade dos valores valores inseridosinseridos



0 e 1 não são 0 e 1 não são primosprimos





senão se ((num == 2) OU (num == 3) OU (num == 5)) entãoescrever("É primo")

senãodiv = 2enquanto ((div < num/2) AND (resto ≠ 0)) fazer




fim sefim se

fim programa




senão se ((num == 2) OU (num == 3) OU (num == 5)) entãoescrever("É primo")

senãodiv = 2enquanto ((div < num/2) AND (resto ≠ 0)) fazer




fim sefim se

fim programa

verifica verifica validade dos validade dos valores valores inseridosinseridos



0 e 1 não são 0 e 1 não são primosprimos2, 3 e 5 são 2, 3 e 5 são primos, mas não primos, mas não passariam no passariam no testeteste

QuestõesQuestões

Documents

Algoritmos e Estruturas de Dados