Supposons que vous ayez du code pour produire toutes les solutions.
(Pour le paramètre z ici, passer 9. Il est le numéro sur le côté droit des inégalités. Notez que ce code ne fonctionne que lorsque r est positif.)
from math import floor, ceil
def iter_solutions(r, n, z):
c = [None] * n
def iter_solutions_bounded(k, pick):
# pick is the last pick, if any, and 0 otherwise
assert (1 <= k < n and pick == c[k]) or (k == n and pick == 0)
min_ck = int(ceil(-pick/r))
max_ck = int(floor((z - pick)/r))
if k == 1:
for ck in range(max(min_ck, 0), min(max_ck, z) + 1):
c[0] = ck
yield c
else:
for ck in range(min_ck, max_ck + 1):
c[k - 1] = ck
for soln in iter_solutions_bounded(k - 1, ck):
yield soln
return iter_solutions_bounded(n, 0)
Vous pouvez convertir cela en code qui compte les solutions simplement en supprimant tout le code qui se réfère à c et en additionnant le nombre de solutions qui auraient été cédées. Enfin, vous pouvez améliorer les performances par mémo.
from math import floor, ceil
def memoize(f):
cache = {}
def g(*args):
if args in cache:
return cache[args]
tmp = cache[args] = f(*args)
return tmp
return g
def len_range(a, b):
if a <= b:
return b - a
return 0
def count_solutions(r, n, z):
@memoize
def count_solutions_bounded(k, pick):
min_ck = int(ceil(-pick/r))
max_ck = int(floor((z - pick)/r))
if k == 1:
return len_range(max(min_ck, 0), min(max_ck, z) + 1)
else:
return sum(count_solutions_bounded(k - 1, ck) for ck in range(min_ck, max_ck + 1))
return count_solutions_bounded(n, 0)
Quelques améliorations possibles:
S'il est vrai que c ... c n sont toujours ≤ z, puis en détectant immédiatement et que le retour 0 aiderait beaucoup pour grand n. En fait, cela réduirait le temps de fonctionnement à un O rapide comme l'éclair (nz).
S'il est prévu que c ... c n tous être non-négatif, qui est encore mieux. Apporter les modifications appropriées à min_ck et max_ck rendrait cette O (nz) avec une constante plus petite, et le cache pourrait être un tableau 2D plat au lieu de la table de hachage plus lente que j'ai.
Vous pourriez être en mesure de faire mieux en construisant le cache systématiquement, plutôt que de le remplir "à la demande" comme le fait ce code de mémo. Commencez par créer le cache entier pour n = 1, puis pour n = 2, et ainsi de suite. De cette façon, vous pouvez éviter la récursivité et, à chaque étape, vous pouvez jeter les données en cache dont vous n'avez plus besoin (après avoir calculé les résultats pour n = 2, vous n'avez plus besoin des entrées pour n = 1).
Vous montrez une matrice 4x3 en cours de multiplication par une matrice 3x1. Par conséquent, le résultat est une matrice 4x1. Qu'est-ce que cela signifie de dire qu'une matrice 4x1 est au moins zéro et au plus neuf? – jason
Veuillez corriger le Q ... cela me rappelle un peu la programmation mixte, sauf ... | Maintenant, qu'en est-il de ceci: Traitez les inégalités comme des demi-plans, calculez l'intersection de toutes les régions - devriez vous donner un polygone. Si certaines de ses coordonnées sont +/- infini, alors vous avez soit un nombre infini, soit zéro solution (je pense). Sinon, trouvez un rectangle de délimitation. pour le polygone, faites deux boucles d'imbrication dedans et vérifiez si chaque point est à l'intérieur du polygone (vous devrez le trianguler). Le pire des cas est O (n^2) mais vous obtenez des solutions O (n). La géométrie computationnelle est votre ami. –
Hm ... dans cet exemple particulier, il suffit d'énumérer (0,0,0) ... (9,9,9) (tant que la matrice a des entiers non négatifs) –