Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Quantas combinações para n pontos num jogo de basquete?

+1 voto
21 visitas
perguntada Mar 16 em Ciência da Computação por Julia Regina Scotti (31 pontos)  

Suponha que num jogo de basquete existem 3 movimentos que somam pontos, o movimento "A" vale 1 ponto, o movimento "B" vale dois pontos e o movimento "C" vale 3 pontos.

Como poderiamos escrever um código que contasse de quantas maneiras diferentes poderiamos atingir n pontos? Por exemplo, para 3 pontos as possibilidades são: AAA, AB, BA, C, ou seja, existem 4 possibilidades (note que a ordem importa)

Esse exercício está descrito no livro "Introduction to recursive programming" de Manuel Rubio Sanchez, de 2017 (exercício 8.3)

Compartilhe

1 Resposta

+1 voto
respondida Mar 16 por Julia Regina Scotti (31 pontos)  
editado Mar 16 por Julia Regina Scotti

Uma maneira bem força bruta de resolver está abaixo. Note que em vez de calcular o número de possibilidades estamos devolvendo uma lista com cada uma das possibilidades, para contar as possibilidades é só contar os elementos da lista

 import itertools

def adiciona_permutacoes (lista):
    listao = []

    for i in range(len(lista)):

        for e in itertools.permutations(lista[i], len(lista[i])):
            aux = ''
            for j in range(len(e)):
                aux = aux + str(e[j])
            listao.append(aux)
    return listao


def number_of_ways(n,lista=[]):
    lista1 =['A']
    lista2 = ['AA', 'B']
    lista3 = ['AAA', 'BA', 'C', 'AB']
    if n==1: return lista1
    if n==2: return lista2
    if n==3: return lista3
    if n>3:
        for i in range(1,n-1):
            if i<=n-1:
                for a in range(i):
                    for b in range(n-i):
                        aux = number_of_ways(i)[a]+number_of_ways(n-i)[b]
                        lista.append(aux)
                        lista = list(set(lista)-set(number_of_ways(n-1)))
        return lista

if __name__=='__main__':

    # para n=6
    lista_com_permutações = list(set(adiciona_permutacoes(number_of_ways(6))))

    #para a contagem com n=6
    contagem = len(list(set(adiciona_permutacoes(number_of_ways(6)))))

    print(lista_com_permutações)
    print(contagem)

O resultado para alguns n selecionados segue abaixo

n=4
['AC', 'AAAA', 'ABA', 'AAB', 'BAA', 'CA', 'BB']

n=5
['CB', 'ABB', 'BBA', 'BC', 'BAB', 'AAAAA', 'BAAA', 'AABA', 'AAAB', 'ABAA']

...