Considere uma partida de futebol entre duas equipes
, cujo placar final é
, em que
e
são números de gols marcados por
e
, 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:
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:
- Se m=0 e n=0, já colocamos todos os gols, então imprimimos a sequência atual.
- Se m>0, podemos “colocar” um A agora e chamar recursão com m–1, mesmo n.
- 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:
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"
.
- Como m=0, só sobra B: vai ao caso n>0 e gera
- Volta e coloca B →
geraSequencias(1,0,"AAB")
→ só A sobra → imprime"AABA"
.
- Coloca A →
- Volta em
("A",2,1)
e coloca B primeiro:geraSequencias(2,0,"AB")
→ só A sobra → imprime"ABAA"
.
- Coloca A →
- 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)