Preparatório Caixa TI: Algoritmos, pseudocódigo e resolução de problemas

O que é um algoritmo (na visão de prova)

Algoritmo é uma sequência finita e ordenada de passos para transformar entradas (dados fornecidos) em saídas (resultado esperado), respeitando regras claras (sem ambiguidades). Em questões de concurso, o foco costuma ser: interpretar o que o algoritmo faz, identificar entradas/saídas, prever o valor final de variáveis e reconhecer padrões como contadores, acumuladores, laços e decisões.

Entradas, saídas e estado (variáveis)

Entrada: valores lidos (ex.: N, vetor V, salário). Saída: valores exibidos/retornados (ex.: soma, maior elemento, “APROVADO”). Estado: conjunto de variáveis e seus valores durante a execução. Muitas questões pedem o estado final ou o estado em um ponto específico do código.

Erros comuns em prova

• Confundir “atribuição” com “igualdade” (ex.: X ← X + 1 não é comparação).
• Não observar o intervalo do laço (inclusive/exclusivo) e o valor inicial do contador.
• Ignorar o que acontece quando a condição do se falha (ramo senão).
• Trocar ordem de atualização: atualizar antes/depois altera o resultado.

Representações: pseudocódigo e fluxogramas

Pseudocódigo (padrão de leitura)

Em provas, o pseudocódigo costuma usar comandos como leia, escreva, se, senão, enquanto, para, além de operadores relacionais (>, <=, =) e lógicos (e, ou, não). A banca pode variar a notação, mas a intenção é a mesma: descrever um procedimento.

Algoritmo ExemploEntradaSaida    leia A, B    C ← A + B    escreva C

Fluxograma (como interpretar rapidamente)

Fluxogramas representam o mesmo algoritmo com símbolos: início/fim (oval), processamento (retângulo), decisão (losango), entrada/saída (paralelogramo) e setas de fluxo. Em questões, o mais importante é seguir as setas e entender onde há repetição (retorno para um bloco anterior) e onde há bifurcação (decisão com “sim/não”).

Leitura de algoritmos: técnica de rastreamento (dry run)

Como fazer um dry run eficiente

Dry run é simular a execução passo a passo, anotando valores das variáveis. Um método prático:

Continue em nosso aplicativo

Você poderá ouvir o audiobook com a tela desligada, ganhar gratuitamente o certificado deste curso e ainda ter acesso a outros 5.000 cursos online gratuitos.

ou continue lendo abaixo...

Baixar o aplicativo

• Liste as variáveis relevantes e seus valores iniciais.
• Para cada linha executada, atualize apenas o que mudou.
• Em laços, registre cada iteração (i = 1, 2, 3...) e o valor das variáveis após a atualização.
• Em decisões, marque qual ramo foi escolhido e por quê.

Modelo de tabela para prova

Iteração | i | x | soma | condição? | ação executada

Invariantes simples (o “sempre verdadeiro” durante o laço)

Invariante é uma propriedade que permanece verdadeira a cada repetição do laço. Em nível introdutório, isso ajuda a entender o que o algoritmo está acumulando ou contando. Exemplos típicos:

• Em um laço que soma valores, a invariante pode ser: “soma é a soma dos elementos já processados”.
• Em um laço que busca o maior, a invariante pode ser: “maior é o maior valor visto até agora”.

Em prova, invariantes aparecem indiretamente: a questão pede para identificar o propósito do algoritmo ou justificar por que ele funciona.

Decomposição de problemas (como a banca espera)

Decompor é quebrar um problema em partes menores e testáveis. Um roteiro que funciona bem para algoritmos de prova:

• Defina claramente a entrada e a saída.
• Escolha uma estratégia: varrer uma lista? comparar pares? contar ocorrências?
• Defina variáveis auxiliares (contador, acumulador, marcador).
• Escreva o laço principal e as condições.
• Teste com um exemplo pequeno (dry run).

Contadores e acumuladores

Contador incrementa por unidade (ou passo fixo): conta quantas vezes algo ocorreu. Acumulador agrega valores: soma, produto, concatenação, etc.

contador ← 0    soma ← 0    para i de 1 até N faça        leia x        se x > 0 então            contador ← contador + 1        fimse        soma ← soma + x    fimpara    escreva contador, soma

Busca (introdução): linear e binária (conceitual)

Busca linear

Varre elemento por elemento até encontrar (ou terminar). Não exige ordenação.

encontrou ← falso    para i de 1 até N faça        se V[i] = chave então            encontrou ← verdadeiro        fimse    fimpara    escreva encontrou

Ponto de atenção em prova: se o algoritmo não “para” ao encontrar, ele pode continuar e alterar variáveis (por exemplo, guardar a última ocorrência).

Busca binária (conceito)

Exige vetor ordenado. A cada passo, compara com o meio e descarta metade do intervalo. Em questões, costuma aparecer como descrição ou pseudocódigo com inicio, fim e meio. O essencial é entender a atualização do intervalo:

• Se chave < V[meio], então fim ← meio - 1.
• Se chave > V[meio], então inicio ← meio + 1.
• Se igual, encontrou.

Ordenação (introdução para interpretação): bolha e seleção

Bolha (bubble sort) para leitura

Ideia: comparar vizinhos e trocar se estiverem fora de ordem; a cada passagem, o maior “borbulha” para o final (ordem crescente). Em prova, observe:

• Quantas passagens externas ocorrem.
• Até onde vai o laço interno (geralmente diminui a cada passagem).
• Quando ocorre a troca.

para i de 1 até N-1 faça        para j de 1 até N-i faça            se V[j] > V[j+1] então                aux ← V[j]                V[j] ← V[j+1]                V[j+1] ← aux            fimse        fimpara    fimpara

Seleção (selection sort) para leitura

Ideia: em cada posição i, encontrar o menor do restante e colocar em i. Em prova, o detalhe é identificar o índice do menor e a troca ao final da busca.

para i de 1 até N-1 faça        min ← i        para j de i+1 até N faça            se V[j] < V[min] então                min ← j            fimse        fimpara        aux ← V[i]        V[i] ← V[min]        V[min] ← aux    fimpara

Como a banca costuma descrever algoritmos

É comum a banca:

• Usar índices começando em 0 ou em 1 (verifique no enunciado).
• Trocar nomes: repita...até no lugar de faça...enquanto, ou para com limites inclusivos.
• Apresentar algoritmo “quase correto” e perguntar o efeito (ex.: laço vai até N quando deveria ir até N-1).
• Inserir variáveis auxiliares (aux, temp) e pedir o estado final do vetor.

Exercícios progressivos (com dry run e gabarito comentado)

Exercício 1: contador e acumulador

Enunciado: Considere o pseudocódigo:

leia N    soma ← 0    cont ← 0    para i de 1 até N faça        leia x        se x mod 2 = 0 então            soma ← soma + x        senão            cont ← cont + 1        fimse    fimpara    escreva soma, cont

Para N = 5 e entradas x na ordem: 2, 7, 4, 9, 6. Determine a saída.

Dry run (tabela):

i | x | x par? | soma | cont    1 | 2 | sim    | 2    | 0    2 | 7 | não    | 2    | 1    3 | 4 | sim    | 6    | 1    4 | 9 | não    | 6    | 2    5 | 6 | sim    | 12   | 2

Gabarito comentado: soma acumula apenas pares (2+4+6=12) e cont conta ímpares (7 e 9, total 2). Saída: 12 2.

Exercício 2: decisão com atualização (atenção à ordem)

Enunciado: Considere:

x ← 3    y ← 0    enquanto x > 0 faça        se x > 1 então            y ← y + x        senão            y ← y + 10        fimse        x ← x - 1    fimenquanto    escreva y

Qual o valor impresso?

Dry run:

Iter | x (antes) | ramo        | y (depois) | x (depois)    1    | 3        | x>1 (sim)  | 3          | 2    2    | 2        | x>1 (sim)  | 5          | 1    3    | 1        | x>1 (não)  | 15         | 0

Gabarito comentado: soma 3 e 2, e quando x=1 soma 10. Resultado: 15.

Exercício 3: busca linear (primeira ou última ocorrência)

Enunciado: Dado V = [4, 1, 4, 2, 4] (índices de 1 a 5) e chave = 4, considere:

pos ← 0    para i de 1 até 5 faça        se V[i] = chave então            pos ← i        fimse    fimpara    escreva pos

Qual saída e o que pos representa?

Dry run:

i | V[i] | V[i]=4? | pos    1 | 4    | sim     | 1    2 | 1    | não     | 1    3 | 4    | sim     | 3    4 | 2    | não     | 3    5 | 4    | sim     | 5

Gabarito comentado: saída 5. Como o algoritmo não interrompe ao encontrar, pos guarda a última ocorrência da chave. Se a banca perguntasse “primeira ocorrência”, seria necessário parar no primeiro encontro ou condicionar a atualização.

Exercício 4: busca binária (conceitual, rastreando intervalos)

Enunciado: Vetor ordenado V = [2, 5, 7, 10, 13, 18, 21] (índices 1..7). Chave = 13. Considere:

inicio ← 1    fim ← 7    encontrou ← falso    enquanto inicio <= fim e não encontrou faça        meio ← (inicio + fim) div 2        se V[meio] = chave então            encontrou ← verdadeiro        senão se chave < V[meio] então            fim ← meio - 1        senão            inicio ← meio + 1        fimse    fimenquanto    escreva encontrou

Dry run (intervalos):

Passo | inicio | fim | meio | V[meio] | ação    1     | 1      | 7   | 4    | 10      | chave>10 => inicio=5    2     | 5      | 7   | 6    | 18      | chave<18 => fim=5    3     | 5      | 5   | 5    | 13      | igual => encontrou=true

Gabarito comentado: imprime verdadeiro. O essencial é acompanhar como o intervalo [inicio, fim] encolhe.

Exercício 5: interpretação de ordenação por bolha (uma passagem)

Enunciado: Considere V = [5, 1, 4, 2] (índices 1..4). Execute apenas a primeira iteração do laço externo (i = 1) do bubble sort abaixo e informe o vetor ao final dessa passagem:

para i de 1 até N-1 faça        para j de 1 até N-i faça            se V[j] > V[j+1] então                aux ← V[j]                V[j] ← V[j+1]                V[j+1] ← aux            fimse        fimpara    fimpara

Dry run (i=1):

Estado inicial: [5, 1, 4, 2]    j=1: compara 5 e 1 => troca => [1, 5, 4, 2]    j=2: compara 5 e 4 => troca => [1, 4, 5, 2]    j=3: compara 5 e 2 => troca => [1, 4, 2, 5]

Gabarito comentado: ao final da primeira passagem, o maior elemento (5) vai para o final. Vetor: [1, 4, 2, 5].

Exercício 6: seleção (identificando o menor e a troca)

Enunciado: Para V = [3, 2, 5, 1] (1..4), execute a primeira iteração do selection sort (i=1) e informe o vetor após a troca.

para i de 1 até N-1 faça        min ← i        para j de i+1 até N faça            se V[j] < V[min] então                min ← j            fimse        fimpara        aux ← V[i]        V[i] ← V[min]        V[min] ← aux    fimpara

Dry run (i=1):

Inicial: [3, 2, 5, 1]    min=1 (V[min]=3)    j=2: V[2]=2 < 3 => min=2    j=3: V[3]=5 < 2? não    j=4: V[4]=1 < 2 => min=4    troca V[1] com V[4] => [1, 2, 5, 3]

Gabarito comentado: após i=1, o menor do vetor vai para a primeira posição. Vetor: [1, 2, 5, 3].

Exercício 7: identificando entradas/saídas e propósito (estilo banca)

Enunciado: Analise o algoritmo:

leia N    leia V[1..N]    maior ← V[1]    para i de 2 até N faça        se V[i] > maior então            maior ← V[i]        fimse    fimpara    escreva maior

Perguntas: (a) quais são as entradas? (b) qual é a saída? (c) qual a invariante simples do laço?

Gabarito comentado:

• (a) Entradas: N e os valores do vetor V[1..N].
• (b) Saída: o valor de maior, que é o maior elemento do vetor.
• (c) Invariante: ao iniciar cada iteração com índice i, a variável maior contém o maior valor entre V[1] e V[i-1] (os já processados).