Listas, recursão e algoritmos de ordenação

Ordenar cartas na mão, buscar em listas e resolver problemas que contêm versões menores de si mesmos.

Habilidades da BNCC

• EF08CO01Construir soluções de problemas usando a técnica de recursão e automatizá-las com uma linguagem de programação. 📥 Baixar slides (PDF)
• EF08CO02Criar soluções que usem listas para descrever informações e automatizá-las com uma linguagem de programação. 📥 Baixar slides (PDF)
• EF08CO03Utilizar algoritmos clássicos de manipulação sobre listas. 📥 Baixar slides (PDF)
• EF08MA10Identificar a regularidade de uma sequência não recursiva e construir um fluxograma que indique os próximos termos.

Objetivos de aprendizagem

• Manipular listas: inserir, remover, buscar e ordenar elementos.
• Executar algoritmos clássicos de ordenação e de busca e comparar sua eficiência.
• Reconhecer e construir soluções recursivas e relacioná-las a sequências numéricas.

Materiais

• Baralho ou cartões numerados (1 por grupo)
• Bonecas russas ou caixas uma dentro da outra (opcional)
• Scratch ou Python

Desenvolvimento

Tempo total previsto: 150 minutos.

1. 15 minOrganizando a mão

   Cada grupo embaralha 8 cartas e as ordena. Como cada um fez? Nomeie a estratégia mais comum: ordenação por inserção (pegar uma carta e encaixar na posição certa).

2. 25 minDuas ordenações

   Executem com as cartas a ordenação por seleção (achar a menor e colocar no início) e a por inserção, contando quantas comparações cada uma fez. Qual foi mais rápida para essas cartas?

3. 20 minAdivinhe o número

   Jogo: o professor pensa num número de 1 a 100 e responde “maior” ou “menor”. Comparem a busca um a um com a busca binária (sempre chutar o meio). Quantas tentativas, no máximo, em cada uma?

4. 20 minProblemas dentro de problemas

   Apresente a recursão com as bonecas russas e com o fatorial: 5! = 5 × 4!. Relacione com sequências: uma sequência recursiva usa o termo anterior; uma não recursiva usa uma fórmula direta (ex.: 3n + 1). Construam o fluxograma de cada uma.

5. 50 minProgramando

   As duplas escolhem: programar a ordenação por seleção de uma lista, a busca binária ou uma função recursiva (fatorial, contagem regressiva, sequência). Testem com listas e valores diferentes.

6. 20 minSocialização

   Compare: com 1 milhão de nomes, quantos passos a busca binária precisaria? (cerca de 20). Por que isso importa para buscadores e aplicativos?

Avaliação

Registro das comparações nas ordenações; fluxograma de uma sequência; programa funcionando para listas ou entradas diferentes.

Acessibilidade e inclusão

Materiais relacionados