Atteindre un score visé au foot

Date 26 mars 2016 Catégories Algorithmique par VulgaireDev

En ligue 1, gagner un match de foot remporte 3 points, faire un match nul rapporte 1 point, et perdre en rapporte 0.
Connaissant le nombre de matchs qu'il nous reste à faire, ainsi que le nombre de points qu'on souhaite avoir en fin de saison, quelles sont les différentes manières d'atteindre ce score, càd combien doit-on faire de victoires, de match nul ou de défaite ?

 

Voici un code résolvant le problème :


def findSolutionRec(goal_score, current_score, current_solution, solutions, len_solution, possibilities):
	if current_score == goal_score and len(current_solution) == len_solution:
		#we need to do a deep copy here
		solutions.append(current_solution[:])
		return
	
	#if our score is higher than our goal_score, it is useless to continue. Idem for the len of solution
	if current_score > goal_score or len(current_solution) >= len_solution:
		return
	
	for i in possibilities:
		current_score += i
		current_solution.append(i)
		findSolutionRec(goal_score, current_score, current_solution, solutions, len_solution, possibilities)
		current_solution.pop()
		current_score -= i
	
	
possibilities = {0, 1, 3}
solutions = []
goal_score = 14
len_solution = 7

findSolutionRec(goal_score, 0, [], solutions, len_solution, possibilities)


for i in solutions:
	print(" ".join((str(j) for j in i)))

C'est une approche "force brute", càd on teste toutes les possibilités. Si on appelle n le nombre de match et p le nombre de façons de gagner des points (3 ici), on voit que pour chaque match, on test toutes les possibilités p (même si on effectue un "cut" dans l'arbre de recherche en regardant si le score courant est supérieur au score visé), on a donc une complexité en O(p^n). Cela signifie que notre algo fonctionnera bien pour des petites valeurs, mais qu'à partir d'un moment on va avoir une explosion combinatoire qui va rendre le procédé très long.

On dit qu'un on a une complexité exponentielle car :

\(p^n = e^{ln(p^n)} = e^{nln(p)} = e^n*e^{ln(p)} = ke^n\)

avec k = e^ln(p).

J'ai essayé avec différentes valeurs de n, en mettant un score élevé afin d'ignorer le cut, et voici ce qu'on obtient comme graphique :

C'est plutôt parlant.

 

Commentaires

blog comments powered by Disqus