Ciencias da computação

Algoritmos gerais para resolver os Problemas 1 e 2 desta aula

============================ Problema 1

contA=0 contE=0 contI=0 contO=0 contU=0 para i=1 até n se texto[i]='a' então contA++ senão se texto[i]='e' então contE++ senão se texto[i]='i' então contI++ senão se texto[i]='o' então contO++ senão se texto[i]='u' então contU++ fim_para visualizar contA, contE, contI, contO, contU

Se tivéssemos “ifs” em lugar de “senão ses”, seria necessário fazer todas as comparações dos “ifs” (no caso, 5). Usando “senão ses”, não necessariamente precisaremos comparar todos: se o caracter for “a”, compara 1x, se for “i”, compara 3x, e assim por diante (com “senão ses”, compara-se até a condição ser verdadeira, e não compara então nos “senão ses” abaixo dele).

No caso pior (imagine letras ‘u’ dentro do texto) o algoritmo faz as 5 comparações, para cada um dos n caracteres do texto, então temos: 5*n comparações. O(5n) considerando o caso pior.
No caso mais otimista (o texto somente com letras ‘a’) o algoritmo efetuará apenas n comparações (por causa dos senão, que evitam comparações adicionais).

============================

Problema 2

vogal[1]='a' vogal[2]='e' vogal[3]='i' vogal[4]='o' vogal[5]='u' para j=1 até 5 cont=0 para i=1 até n se texto[i]=vogal[j] então cont++ fim_para visualizar cont fim_para Não existe caso melhor ou pior neste algoritmo.
Independentemente de quais sejam os caracteres do texto, serão efetuadas 5*n comparações, O(5n), porque o laço externo é executado para cada vogal (são 5 vogais), com n comparações somente no ciclo (loop) interno, logo temos 5*n