Para cada um dos algoritmos abaixo:
| Algoritmo 1 | Algoritmo 2 |
|---|---|
- Calcule o número de operações de:
a. Declaração de Variáveis
b. Atribuições - Calcule o número de operações em função de
para cada um dos algoritmos:
a. Comparação menor que
b. Comparação igual a
c. Incremento no melhor caso
d. Incremento no pior caso
Passo 1
Beleza, o enunciado pede pra gente analisar dois trechos de código e “contar” quantas vezes cada tipo de operação acontece. O conteúdo aqui é análise de algoritmo (contagem de operações básicas: declarações, atribuições, comparações e incrementos). Vamos precisar lembrar como funciona um laço
for (quantas vezes testa a condição, executa o corpo e faz o incremento) e como cada operador (=, ++, <, ==, *=) conta como uma operação.Passo 2
Algoritmo 1:
int count = 0;
int i;
for(i = 0; i < n; i++)
if (i % 2 == 1)
count++;
• Declarações de variáveis: contamos cada
int nome; como 1 operação de declaração. Aqui temosint countint i
→ total = 2 declarações.
• Atribuições: todo uso de=(fora de comparações) é atribuição. Aqui sãocount = 0;i = 0;(inicialização do for)
→ total = 2 atribuições.
Passo 3
Algoritmo 2:
for (int i = 1; i <= n; i *= 2)
if (i % 2 == 0)
printf("Olá");
• Declarações de variáveis: dentro do
• Atribuições: usamos
for declaramos int i → 1 declaração.• Atribuições: usamos
= só em i = 1; na inicialização → 1 atribuição.Passo 4
Agora vamos contar, em função de
, quantas vezes ocorrem comparações e incrementos no Algoritmo 1.
a) Comparação menor que (
O , são
i < n):O
for testa i < n a cada iteração e uma vez extra pra sair. Se i vai de 0 até
testes
<.b) Comparação igual (
O
i % 2 == 1):O
if roda uma vez a cada iteração, ou seja, exatamentetestes
==.c) Incremento no melhor caso:
Aqui o incremento do laço é
Aqui o incremento do laço é
i++, que acontece a cada iteração (sem variação). Sãoexecuções de
i++ (melhor e pior caso são iguais).d) Incremento no pior caso:
Como não muda, continua
Como não muda, continua
Passo 5
Para o Algoritmo 2:
a) Comparação menor ou igual (
Começamos em e dobramos até ultrapassar
. O número de iterações é
i <= n):Começamos em
logo
. O teste
i <= n acontece uma vez a mais pra sair do laço:b) Comparação igual (
Roda dentro do
i % 2 == 0):Roda dentro do
for em cada iteração, ou seja, tambémtestes
==.c) Incremento no melhor caso:
O “incremento” aqui é
O “incremento” aqui é
i *= 2, que roda uma vez por iteração (sem variação), entãod) Incremento no pior caso:
Igual ao acima, continua
Igual ao acima, continua
Resposta
Algoritmo 1:
1.a) Declarações = 2
1.b) Atribuições = 2
2.a)
2.b)
2.c) incremento (
2.d) incremento (
1.a) Declarações = 2
1.b) Atribuições = 2
2.a)
< =
2.b)
== =
2.c) incremento (
i++) melhor caso =
2.d) incremento (
i++) pior caso =
Algoritmo 2:
1.a) Declarações = 1
1.b) Atribuições = 1
2.a)
2.b)
2.c) atualização (
2.d) atualização (
1.a) Declarações = 1
1.b) Atribuições = 1
2.a)
<= =
2.b)
== =
2.c) atualização (
i *= 2) melhor caso =
2.d) atualização (
i *= 2) pior caso =