Inscription / Connexion Nouveau Sujet
Dérangements et algo
Bonsoir
On sait que le nombre de dérangements de n éléments peut être extrait de la factorielle de n , en effet n ! = 
C(n,k).Dn-k ,k compris entre 0 et n
Pouvez vous écrire un algo dans le langage de votre choix permettant de calculer le nombre de dérangements de n objets . ( on choisit un entier quelconque n>2 et le prog retourne le nombre de derangements) on pourra partir du fait que Do=1 et 1=0
Salut,
je propose, en python
Cliquez pour afficherps : j'ai optimisé le temps d'écriture de la fonction plus que le temps d'exécution d'icelle.
Une solution utilisant une autre formule que celle de verdurin
Une autre utilisant une simple factorielle et une division, mais avec une précision de "seulement" 10^9999, ce qui est largement assez en pratique
Cliquez pour afficher@Ulmiere
Oui, on peut.
Mais reversed(range(n+1)) retourne bien un itérateur. Essaye de faire next(reversed(range(10**200)) il n'y aura pas de soucis.
Essaye list(range(10**200)), aucune chance que ça passe.
Et ça parce que range implémente la méthode __reversed__(self).
D'un autre côté le coût le plus élevé du programme est le fact *= k (qui devient x*-y dans ta version).
Je trouve mon programme plus clair et plus proche de l'équation de départ le tout sans perte significative d'efficacité.
J'aurais pu même faire ceci :
def derangement(n):
""" Returns the number of derangement of n elements """
factorial = 1
partial_sum = 0
for k in reversed(range(n+1)):
partial_sum += (-1)**k * factorial
factorial *= k
return partial_sumJ'ai mesuré la durée d'exécution pour le calcul de des deux programmes de LittleFox et celle d'un programme utilisant
sans récursivité.
def derangeD(n):
" calcule directement le nombre de dérangements pour un ensemble de taille n"
if n==0 : return 1
elif n==1 : return 0
elif n==2 : return 1
a,b = 0,1
for k in range(2,n):
c=k*(a+b)
a=b
b=c
return cComme on pouvait s'y attendre le calcul direct de
Sur ma machine :
la première version met environ 0,89ms, la seconde environ 1,11ms et la version sans récursivité de la formule de récurrence met environ 0,49ms.
Je n'ai pas fait de mesure sur la première proposition de Ulmiere parce qu'elle ne peut pas raisonnablement être répétée : c'est contraire à sa logique qui est de conserver des résultats.
salut
en vba sous excel
Sub dérangements()
Dim D() As Variant
Dim k As Double
Dim n As Double
x = 0
D = Array(1, 0)
n = 2
valeur = CInt(InputBox("choix d'une valeur >=2 dont on veut calculer le nombre de dérangements"))
Do
x = 0
k = 1
Do
x = x + combi(n, k) * D(n - k)
k = k + 1
Loop Until n - k < 0
ReDim Preserve D(0 To n)
D(n) = (facto(n) - x)
n = n + 1
Loop Until n = valeur + 1
msgbox D(valeur)
End Sub
Salut flight,
je ne connais pas vba et ( donc ) je comprends mal l'algorithme que tu utilises.
Peux tu le donner en pseudo-code ?
D'avance merci.
PS : tous les programmes précédemment donnés ( je les ai testés ) donnent
D20=895 014 631 192 902 121.
Es-tu d'accord avec cette valeur ?
Je ne peux pas tester to programme, je n'ai pas excel.
pour faire tourner mon code j'ai du bien sur créer deux autres fonction , une qui calcul les combinaisons et une autre les factorielles ( en pseudo code .. je ne vois pas trop ce que tu veux dire )
Function facto(p As Double) As Double
Dim x As Double
x = 1
i = 1
If p = 0 Then
facto = 1
Else
Do
x = x * i
i = i + 1
Loop Until i = p + 1
facto = x
End If
End Function
Function combi(n As Double, p As Double) As Double
combi = facto(n) / (facto(p) * facto(n - p))
End Function
@verdurin
Évidemment ta formule est efficace. J'ai du mal à voir d'où elle vient par contre 
Mais elle marche nickel 
Si c'est un concours de rapidité d'exécution je propose :
def D(n):
d, a = 1, -1
for k in range(1, n+1):
d *= k
d += a
a = -a
return dAh ben si c'est la vitesse qu'on cherche, je pense que cette formule est beaucoup plus rapide
def derangement(n):
u,v = 1,0
for i in range(1,n):
u,v = v, i*(u+v)
return v
print derangement(2000)
Je ne pensais pas vraiment à un concours de vitesse.
En fait je m'intéresse plus à l'efficacité « grossière » des formules qu'a leur optimisation.
Mais je vais regarder ça.
@LittleFox,
« ma » formule vient de ce que j'ai une mémoire de poisson rouge.
Et donc je recherche à chaque fois.
Or il est facile de voir comment obtenir un dérangement de n+1 éléments à partir d'une permutation de n éléments :
-- soit on part d'un dérangement des n premiers éléments et on échange l'élément supplémentaire avec un des éléments de départ ;
-- soit on part d'une permutation n'ayant qu'un point fixe et on échange le point fixe avec l'élément supplémentaire.
Ensuite je me souviens d'avoir démontré que la proba d'avoir une permutation sans point fixe tend vers 1/e, ce qui permet de retrouver la formule que tu utilisas.
Bon j'ai fait la course avec timeit pour le calcul de
Premier Ulmiere avec 485,9
s
Second moi avec 489,8s
Troisième LittleFox avec 510,4s.
Soit des différences assez négligeables.
Et je suis curieux de savoir combien tu trouves pour mon approximation par en remplaçant fact(n) par functools.reduce(lambda x,y:x*y,range(2,n+1),1) ?
Mais je pense que ton script était bon car fact(n) n'était calculé qu'une fois, grâce au dictionnaire.
Si on le calcule deux fois ça va pas être bon au niveau temps.
Annuler
connectez vous