Analise o pseudocódigo abaixo e responda as seguintes questões. Faça uso da tabela para ir registrando os possíveis valores de cada variável presente no programa ( \mathbf{Q 1}=\mathbf{2 , 0} pontos).
programa
{
    funcao inicio()
    {
        inteiro k = 19
        inteiro a = 1
        inteiro b, x
        enquanto (k >= a)
        {
            b = a / 2
            se (b * 2 != k)
            {
                a = a + 2
            }
            senao
            {
                a = a + 3
            }
            k = k - 2
            x = a % 6
            escreva((x * 2) - 1, "\n") //Saída
        }
    }
}
# iteração k a b x saída
1
2
3
1.a - Determine os valores que serão impressos na saída do programa até a terceira ( 3^{\mathrm{a}} ) iteração. ( \mathbf{0 , 7 5} ponto)
1.b - Qual é o número máximo de repetições que o programa consegue rodar assumindo esses valores \mathbf{k}=\mathbf{1 9} e \mathbf{a}=\mathbf{1} ? (0,75 ponto)
1.c - Entendendo as diferenças entre as estruturas de repetição, qual seria a complexidade de substituir o uso do enquanto pelo para no caso anterior. ( \mathbf{0 , 5} ponto)

Passo 1

O enunciado apresenta um programa que inicia com \,k=19 e \,a=1, e dentro de um laço enquanto (k >= a) atualiza as variáveis assim:
  1. calcula b = \lfloor a/2\rfloor,
  2. testa se b\cdot2 \neq k para incrementar a em 2 ou em 3,
  3. decrementa k em 2,
  4. calcula x = a \bmod 6 e imprime (x\cdot2)-1.
    Precisamos simular iterações para (a) os três primeiros valores de saída, (b) descobrir quantas repetições até parar e (c) comentar a complexidade caso trocássemos enquanto por para.

Passo 2

Iteração 1 (início com k=19, a=1):
b = \lfloor1/2\rfloor = 0,\quad b\cdot2=0\neq19\;\Rightarrow\;a\gets1+2=3,
k\gets19-2=17,\quad x=3\bmod6=3,\quad\text{saída}=(3\cdot2)-1=5.í

Passo 3

Iteração 2 (início com k=17, a=3):
b = \lfloor3/2\rfloor = 1,\quad b\cdot2=2\neq17\;\Rightarrow\;a\gets3+2=5,
k\gets17-2=15,\quad x=5\bmod6=5,\quad\text{saída}=(5\cdot2)-1=9.í

Passo 4

Iteração 3 (início com k=15, a=5):
b = \lfloor5/2\rfloor = 2,\quad b\cdot2=4\neq15\;\Rightarrow\;a\gets5+2=7,
k\gets15-2=13,\quad x=7\bmod6=1,\quad\text{saída}=(1\cdot2)-1=1.í

Passo 5

Para saber quantas vezes o laço roda até k<a, note que em cada iteração k diminui de 2 e a aumenta de 2 (sempre cai no ramo “se”). Assim as sequências são
(k,a)\!: (19,1)\to(17,3)\to(15,5)\to(13,7)\to(11,9)\to(9,11)\,,
e o laço pára quando 9<11. Isso dá 5 iterações.

Passo 6

Substituir enquanto por para não altera a lógica nem o número de passos — continuamos fazendo um passo por iteração. Logo a complexidade de tempo é linear no número de iterações, isto é \mathcal{O}(n).

Resposta

1.a \,5,\;9,\;1
1.b \,5 iterações
1.c \mathcal{O}(n)

Exercícios relacionados