Considere uma partida de futebol entre duas equipes A times B, cujo placar final é m times n, em que m e n são números de gols marcados por A e B, respectivamente. Escreva um algoritmo recursivo que imprima todas as possíveis sucessões de gols marcados. Por exemplo, para um placar final de 3 x 1 , as possíveis sucessões de gols são AAAB, AABA, ABAA e BAAA.

Passo 1

Beleza, o que a questão está pedindo? Temos um jogo entre dois times A e B que terminou com m gols de A e n gols de B, ou seja, placar final m×n. Queremos listar todas as possíveis “histórias” de quem fez cada gol — cada sequência de tamanho m+n composta por “A” e “B”, com exatamente m letras A e n letras B.
Conteúdo: é um problema de recursão/backtracking, que gera todas as strings de comprimento m+n com m A’s e n B’s. Vamos usar:
  • conceito de caso base em recursão
  • chamadas recursivas para colocar um “A” ou um “B” até esgotar m e n

Passo 2

Entendendo a recursão:
  1. Se m=0 e n=0, já colocamos todos os gols, então imprimimos a sequência atual.
  2. Se m>0, podemos “colocar” um A agora e chamar recursão com m–1, mesmo n.
  3. Se n>0, podemos “colocar” um B agora e chamar recursão com mesmo m, n–1.
Isso garante que, a cada passo, a gente diminui o total de gols faltantes e chega no caso base.

Passo 3

Pseudocódigo (em estilo Python), explicando cada linha:
def geraSequencias(m, n, seq_atual):
    # Caso base: não faltam gols nem de A nem de B
    if m == 0 and n == 0:
        print(seq_atual)     # mostramos uma sequência completa
        return

    # Se ainda sobra gol para A, adiciona "A" e chama recursão
    if m > 0:
        geraSequencias(m-1, n, seq_atual + "A")

    # Se ainda sobra gol para B, adiciona "B" e chama recursão
    if n > 0:
        geraSequencias(m, n-1, seq_atual + "B")
Explicando:
  • geraSequencias(m, n, seq_atual) mantém quantos A e B ainda precisamos colocar.
  • A cada chamada, ou reduzimos m (colocando “A”) ou reduzimos n (colocando “B”).
  • Quando m=n=0, acabaram os gols e temos uma sequência completa.

Passo 4

Vamos testar no exemplo 3×1 (m=3, n=1):
Chamada inicial: geraSequencias(3,1,"")
  • Coloca A → geraSequencias(2,1,"A")
    • Coloca A → geraSequencias(1,1,"AA")
      • Coloca A → geraSequencias(0,1,"AAA")
        • Como m=0, só sobra B: vai ao caso n>0 e gera "AAAB".
      • Volta e coloca B → geraSequencias(1,0,"AAB") → só A sobra → imprime "AABA".
    • Volta em ("A",2,1) e coloca B primeiro: geraSequencias(2,0,"AB") → só A sobra → imprime "ABAA".
  • Volta na raiz e coloca B primeiro: geraSequencias(3,0,"B") → só A sobra → imprime "BAAA".
No total aparecem 4 sequências: AAAB, AABA, ABAA e BAAA.

Resposta

def geraSequencias(m, n, seq_atual=""):
    if m == 0 and n == 0:
        print(seq_atual)
        return
    if m > 0:
        geraSequencias(m-1, n, seq_atual + "A")
    if n > 0:
        geraSequencias(m, n-1, seq_atual + "B")

# Para usar:
geraSequencias(m, n)

Exercícios relacionados