Je suis au lycée et je fais des recherches sur les tiroirs anti-sommes, c'est-à-dire des tiroirs dont la somme de deux éléments ne donne pas la valeur d'un autre élément dans le même tiroir.
(a + b !=c, a b et c dans le même tiroir)
Dans ce programme, il y a trois tiroirs, il teste toutes les combinaisons possibles qui permettent d'aller jusqu'à un nombre donné (n) et vérifie en même temps si celles-ci sont anti-sommes. Ce programme permet de prouver quelle est la meilleure combinaison pour trois tiroirs.
En observant le temps que mettait le programme pour les petits nombres, j'ai déduit que le programme était d'une complexité exponentielle, et qu'il faudrait donc plusieurs jours pour qu'il puisse trouver la solution.
(6-7 jours pour n = 23 avec mon ordinateur (pas très puissant)selon mes calculs
) C'est pourquoi j'aurai besoin que quelqu'un teste avec un ordinateur plus puissant, qui serait donc plus rapide le programme avec la valeur 23 puis 24.
Le programme devrait renvoyer plusieurs solutions pour 23 et rien pour 24 ce qui prouverait que 23 est le maximum. Ça m'aiderait beaucoup !
Je mets ci-dessous le programme, la fonction à lancer est combi(n) :
- Code: Tout sélectionner
import time
def gen_combinations(numbers, n):
if n == 0:
yield []
else:
for i in range(3):
for sub_comb in gen_combinations(numbers, n-1):
yield [i] + sub_comb
def combi(n):
start_time = time.time() # démarrer le chronomètre
numbers = list(range(1, n+1))
combinaisons = []
for combinaison in gen_combinations(numbers, n):
tiroir1 = []
tiroir2 = []
tiroir3 = []
for i in range(n):
if combinaison[i] == 0:
tiroir1.append(numbers[i])
elif combinaison[i] == 1:
tiroir2.append(numbers[i])
else:
tiroir3.append(numbers[i])
if est_anti_somme(tiroir1) and est_anti_somme(tiroir2) and est_anti_somme(tiroir3):
combinaisons.append((tuple(tiroir1), tuple(tiroir2), tuple(tiroir3)))
if combinaisons == []:
print("Il n'y a pas de solutions allant jusqu'à", n)
else :
print("il y a", len(combinaisons), 'possibilités')
# Convertir les tuples en sous-listes
result = [[list(tiroir1), list(tiroir2), list(tiroir3)] for (tiroir1, tiroir2, tiroir3) in combinaisons]
end_time = time.time() # arrêter le chronomètre
print(f"Temps d'exécution : {end_time - start_time:.4f} secondes")
return result
def est_anti_somme(tab):
'''
Renvoie True si on NE peut PAS obtenir un élément du tableau en ajoutant deux élements
de ce tableau et False sinon
: param tab (list) tableau d'entiers
: return (bool)
>>> est_anti_somme([1, 2, 3])
False
>>> est_anti_somme([1, 2, 4, 5])
False
>>> est_anti_somme([2, 3, 7, 11])
True
>>> est_anti_somme([])
True
>>> est_anti_somme([0, 0, 0, 0])
False
>>> est_anti_somme([0])
True
'''
if len(tab) < 2:
return True
return all(tab[i]+tab[j] not in tab for i in range(len(tab)) for j in range(i+1, len(tab)))
return result
