Suite non récurrente

**nellou90** · 03/11/2018, 09h42

Bonjour à tous, je dois actuellement coder sur python un algorithme avec des suites qui ne sont pas définis par récurrence. Le problème est que je ne sais pas comment y parvenir...

Pourriez vous m'aider svp ?

**Sve@r** · 03/11/2018, 09h51

Bonjour

Tu ne voudrais pas nous en dire plus ? Parce qu'en l'état, la réponse à "pouvez-vous m'aider" sera clairement "non".

Elles sont définies comment tes suites si ce n'est pas par récurrence ? Elles doivent forcément avoir une règle mathématique quelconque qui les définit (enfin ce n'est pas du hasard quoi). Donc tu codes la règle en Python et voilà.

PS: une suite est toujours définie par récurrence sinon ce n'est pas une suite. Et justement un des problèmes les plus difficiles est d'arriver à trouver une fonction qui supprime la récurrence afin de pouvoir calculer U(n) sans calculer les U(n-1) termes qui le précèdent. Donc si t'as une suite qui n'est pas définie par récurrence alors elle est définie par une fonction et c'est tout bonus pour toi.
PS2: au cas où ce serait vraiment du hasard, tu as le module random que tu peux importer et qui là aussi te permettra de coder tes suites.

**nellou90** · 03/11/2018, 10h11

Oui alors enfaîte j'ai deux suites Un et Vn.
Un est une somme tel que pour k allant de 0 a n on a 1/k! donc 1/0! + 1/1! + 1/2! + ... + 1/n!
et Vn= Un + 1/n!

Enfaîte jusqu’à maintenant j'ai toujours codé mes suites sur python par récurrence donc en fonction de Un+1.

**Sve@r** · 03/11/2018, 10h20

Envoyé par nellou90

Enfaîte jusqu’à maintenant j'ai toujours codé mes suites sur python par récurrence donc en fonction de Un+1.

Non, en fonction de Un-1. Tu peux pas coder Un en fonction de son suivant qui n'existe pas encore !!!

Donc ici tu as U0=1 et U(n)=U(n-1) + 1/n!. C'est bien une suite définie par récurrence.

**tyrtamos** · 03/11/2018, 11h20

Bonjour,

Il s'agit du calcul de 'e', base des logarithmes népériens: https://fr.wikipedia.org/wiki/E_(nombre).

C'est une suite convergente. Le principe de calcul est simple:
- on part de U(0)=1,
- on fait une boucle qui calcule le suivant U(n) en fonction du précédent U(n-1),
- on calcule dans la boucle la nouvelle somme en ajoutant le dernier U(n) à la précédente somme.
- on sort de la boucle quand la nouvelle somme est égale à la précédente.

Il est évident que si on doit à chaque boucle tenir compte des résultats de la boucle précédente, il faut conserver ceux-ci dans des variables.

Une mauvaise solution serait d'utiliser la fonction factorielle pour calculer chaque U(n). Il vaut mieux le déduire du précédent.

En faisant ça, on trouve rapidement: e=2.718281828459045

**nellou90** · 03/11/2018, 13h07

Merci à tous je pense avoir compris

**Sve@r** · 03/11/2018, 17h02

Envoyé par tyrtamos

Une mauvaise solution serait d'utiliser la fonction factorielle pour calculer chaque U(n). Il vaut mieux le déduire du précédent.

Moi je proposerais mieux (dans le sens "TP" je veux dire): faire une fonction factorielle pour calculer chaque U(n) mais l'encapsuler dans un décorateur pour qu'il puisse optimiser les calculs en stockant et récupérant les résultats déjà calculés...

**tyrtamos** · 03/11/2018, 18h03

Merci, Sve@r, montre-moi comment tu ferais! Mais ce serait par pur plaisir de développeur, car la solution que j’ai proposée est super facile!

**Sve@r** · 06/11/2018, 13h22

Envoyé par tyrtamos

Merci, Sve@r, montre-moi comment tu ferais!

Volontiers

(désolé si j'ai tardé, je suis chez mes parents et comme je ne voulais pas leur pourrir leur ordi avec Python... puis j'ai trouvé une version portable alors je m'y suis mis)

Envoyé par tyrtamos

Mais ce serait par pur plaisir de développeur

Tout à fait. Un forum de développeurs doit aussi servir au plaisir des développeurs

Envoyé par tyrtamos

car la solution que j’ai proposée est super facile!

Exact. Et justement les décorateurs s'adaptent super bien à ta proposition... mais en mieux

Si je ne me trompe pas, ton idée est de mémoriser les factorielles déjà calculées pour pouvoir calculer la suivante. Si par exemple j'ai déjà en mémoire fact(4), alors calculer fact(5) se fera en multipliant ce résultat par 5 ce qui est effectivement assez facile et assez direct. Et qui justement s'adapte directement à ce TP où on calcule les factorielles à suivre.

Le seul inconvénient de cette méthode c'est que tu dois modifier ta fonction factorielle. C'est ici faisable car la fonction est de toi mais qu'en est-il s'il s'agit maitenant d'une fonction extérieure (librairie ou autre) ?

Le décorateur est un outil qui est justement fait pour optimiser une fonction qui ne t'appartient pas. Tu encapsules en fait cette fonction dans un mécanisme qui, lui, t'appartient et qui te permet alors d'enrober l'appel à la fonction. Tu peux par exemple compter combien de fois on l'appelle, ou bien la chronométrer, ou plus simplement gérer les cas connus ou évidents pour ne pas avoir à les faire calculer par la fonction en question.

Exemple

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Création du décorateur qui va optimiser une fonction X
def optimizeFact(fct):
	# Le moteur du décorateur qui se charge de gérer si l'appel à la fonction est utile
	def wrapper(n):
		# Si le résultat n'est pas encore connu
		if n not in wrapper.res:
			# Si le résultat peut se calculer simplement
			if (n-1) in wrapper.res:	
				# On le calcule directement
				wrapper.res[n]=wrapper.res[n-1] * n
			else:
				# On utilise la fonction
				wrapper.res[n]=fct(n)
			# if
		# if
 
		# On retourne maintenant le résultat enregistré
		print(wrapper.res)
		return wrapper.res[n]
	# wrapper
 
	# Les résultats évidents (facultatif mais tant qu'à faire...)
	wrapper.res={
		0 : 1,
		1 : 1,
		2 : 2,
	}
 
	# Le décorateur doit renvoyer la fonction définie pour le moteur d'optimisation
	return wrapper
# optimizeFact()
 
@optimizeFact                           # Activation du décorateur
def fact(n):
	print("fact %d" % n)
	if n == 0: return 1
	return n * fact(n-1)
# fact

J'ai mis des print pour que tu voies ce qui se passe. Tu appelles par exemple fact(5) le truc t'affichera qu'il part dans le calcul de fact(5) puis de fact(4) et puis c'est tout car le calcul de fact(3) se fera via le calcul direct à partir de res[2] * 3.
Si tu redemandes ensuite fact(5) comme ce résultat est déjà connu la fonction n'est pas appelée.

Ainsi ta factorielle ne change pas. C'est le décorateur qui se charge lui des tâches de contrôle et d'optimisation. Le jour où tu ne veux plus encapsuler ta factorielle tu supprimes simplement l'appel au décorateur. La fonction sera alors appelée à chaque demande et l'exécution prendra plus de temps mais les résultats ne changeront pas.

**wiztricks** · 06/11/2018, 13h47

Et les fainéants comme moi préféreront utiliser un décorateur prêt à l'emploi : functools.lru_cache.

- W

**tyrtamos** · 08/11/2018, 07h24

Bonjour,

Merci, Sve@r, d'avoir excité ma curiosité!

J'avais bien pensé à un décorateur-cache (comme lru_cache proposé par wiztricks), mais ça ne répond pas au problème posé. En effet, si on a déjà calculé fact(25) avant et qu'on veut calculer fact(26), le calcul devra se faire complètement, et non à partir de fact(25). Et puis il faut reconnaître que lru_cache n'est pas facile à comprendre, et que sa doc est nulle sur le sujet...

Ton code est astucieux, mais j'ai l'impression qu'il suppose que la fonction fact se code de façon récursive. En tout cas, son comportement est très différent si ce n'est pas le cas.

Je te propose un autre décorateur, toujours dans le cadre du "plaisir du développeur"...

Je suis parti d'un décorateur-cache construit sur la base d'une classe, pour qu'on puisse conserver des données entre plusieurs appels successifs. Sur le principe, un décorateur-cache est facile à faire puisqu'il englobe la fonction: à chaque appel, il commence par regarder si les arguments d'appel de la fonction ont déjà été demandés, et si oui, retourne le résultat précédemment calculé au lieu d'appeler la fonction une nouvelle fois.

Ça, c'est le principe. Dans le cas général, la complexité vient surtout du repérage de l'ensemble des arguments fournis du genre "*args, **kwargs". Par exemple, les arguments par défaut ne sont pas forcément donnés explicitement, mais il faut tout de même en tenir compte. Je m'étais penché sur le sujet, il y a quelque temps, et j'avais proposé du code: http://python.jpvweb.com/python/mesr...orateurs_cache. Et, bien sûr, quand on utilise un dictionnaire pour conserver les arguments des calculs déjà faits, il faut que ces arguments soient "hachables" (donc: pas de liste ni de dictionnaire, etc...).

Mais avec la fonction factorielle, c'est plus simple puisqu'il n'y a qu'un seul argument, et que c'est un entier. De ce fait, on peut pousser les astuces, comme de garder triés les arguments entiers des calculs déjà faits, afin de rendre plus rapide la recherche par dichotomie (avec bisect). Voilà le code que je propose (Python 3):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from bisect import bisect
import functools
 
#############################################################################
class decofact(object):
    """ decorateur pour la fonction fact(n)
    """
 
    #========================================================================
    def __init__(self, fonc):
        self.fonc = fonc # fonction décorée
        self.args = [0] # liste des arguments
        self.results = [1] # liste des résultats
        functools.wraps(fonc)(self) # pour que fonc garde nom et docstring
 
    #========================================================================
    def __call__(self, arg):
        """ méthode appelée à chaque appel de la fonction décorée
        """
        ind = bisect(self.args, arg) # recherche dichotomique de l'index
        if self.args[ind-1]==arg:
            # l'argument "arg" se trouve déjà dans la liste des arguments
            print(arg, "déjà calculé antérieurement" )
            return self.results[ind-1] # retour du résultat enregistré
        else:
            # l'argument "arg" n'a pas encore été demandé
            # trouve la valeur inférieure la plus proche de arg
            a = self.args[ind-1]
            res = self.results[ind-1]
            if a==0:
                # aucun résultat proche disponible: on appelle la fonction
                res = self.fonc(arg)
            else:    
                # on calcule le résultat à partir de la valeur proche
                print("Trouvé un calcul proche:", a, "pour", arg)
                for n in range(a+1, arg+1):
                    res *= n
            # enregistrement de la nouvelle valeur arg, res
            self.args.insert(ind, arg)
            self.results.insert(ind, res)
            # retour du nouveau résultat
            return res

On voit qu'à chaque nouveau calcul, il cherche non seulement si le calcul a déjà été fait, mais aussi si un argument inférieur a déjà été utilisé. Dans ce dernier cas, il recalcule à partir de ce dernier résultat.

Exemple d'application:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#############################################################################
@decofact
def fact(n):
    """fact(n): calcule la factorielle de n (entier >= 0)
    """
    x = 1
    for i in range(2, n+1):
        x *= i
    return x
 
#############################################################################
from random import randint
 
for i in range(0,10000):
    n = randint(1, 100)
    r = fact(n)
    print(i, n, r)

J'ai laissé dans le code du décorateur deux "print": l'un dit quand le calcul demandé a déjà été fait, auquel cas le résultat précédemment calculé est retourné, et l'autre quand on utilise un argument inférieur déjà enregistré pour recalculer la nouvelle valeur. De ce fait, si fact(25) a déjà été calculé et qu'on demande fact(33), le décorateur calculera le résultat de fact(33) à partir de celui de fact(25), sans nouvel appel de la fonction. A foriori, bien sûr, si l'argument succède au précédent (demande de fact(26) avec fact(25) déjà calculé). Et sur les 10000 calculs demandés, on voit que ça marche de mieux en mieux au fur et à mesure de l'évolution de la boucle!

Voilà pour le "plaisir du développeur"...

**Sve@r** · 10/11/2018, 17h20

Ok, de retour. Encore un peu de retard parce que je voulais attendre d'être rentré chez-moi pour bien prendre le temps d'examiner cet intéressant exemple...

Envoyé par tyrtamos

Ton code est astucieux, mais j'ai l'impression qu'il suppose que la fonction fact se code de façon récursive.

Oui en effet j'avoue

J'avais d'abord monté un exemple de base s'appuyant sur le fait que fact() s'appelerait elle-même en récursif. Donc chaque appel récursif est d'abord filtré par le décorateur pour voir s'il est nécessaire. Puis j'ai triché encore plus en rajoutant l'étape du wrapper.res[n]=wrapper.res[n-1] * n qui, elle, était pile poil adaptée au problème initial de ce topic où on calcule d'abord fact(1) puis fact(2) puis fact(3) etc.

D'ailleurs mon commentaire c'est "# Création du décorateur qui va optimiser une fonction X" et le décorateur se nomme "optimiseFact". Si on ne voit pas là le super gros parti pris totalement partial...

Envoyé par tyrtamos

Je te propose un autre décorateur, toujours dans le cadre du "plaisir du développeur"...
On voit qu'à chaque nouveau calcul, il cherche non seulement si le calcul a déjà été fait, mais aussi si un argument inférieur a déjà été utilisé. Dans ce dernier cas, il recalcule à partir de ce dernier résultat.

J'ai laissé dans le code du décorateur deux "print": l'un dit quand le calcul demandé a déjà été fait, auquel cas le résultat précédemment calculé est retourné, et l'autre quand on utilise un argument inférieur déjà enregistré pour recalculer la nouvelle valeur. De ce fait, si fact(25) a déjà été calculé et qu'on demande fact(33), le décorateur calculera le résultat de fact(33) à partir de celui de fact(25), sans nouvel appel de la fonction. A foriori, bien sûr, si l'argument succède au précédent (demande de fact(26) avec fact(25) déjà calculé). Et sur les 10000 calculs demandés, on voit que ça marche de mieux en mieux au fur et à mesure de l'évolution de la boucle!

Voilà pour le "plaisir du développeur"...

Magnifique

J'avais aussi pensé à récupérer un résultat inférieur (style partir de fact(26) pour calculer par exemple fact(30) mais je n'envisageais pas le rapport développement/gain tellement utile.
En plus je cherchais la syntaxe pour faire le "décorateur objet"

J'ai juste changé ta façon de tester par celle-là...

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
import sys
for n in map(int, sys.argv[1:]):
	r = fact(n)
	print(n, r)

... plus sympa pour regarder ses propres exemples

**tyrtamos** · 11/11/2018, 10h21

Bonjour,

Et le plus amusant, c'est que, comme j'ai initialisé le cache avec la valeur la plus faible possible (fact(0)=1), TOUTES les autres valeurs peuvent en être déduites par calcul.

Cela veut dire que, si on retire la condition "if a==0:" de mon code, ce décorateur n'a jamais besoin d'appeler la fonction décorée!!!

Curieux, non?

**wiztricks** · 11/11/2018, 13h43

Salut,

Envoyé par tyrtamos

Cela veut dire que, si on retire la condition "if a==0:" de mon code, ce décorateur n'a jamais besoin d'appeler la fonction décorée!!!

Curieux, non?

Votre décorateur a une connaissance intime de ce qui doit être calculé.
ligne 33:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
           else:    
                # on calcule le résultat à partir de la valeur proche
                print("Trouvé un calcul proche:", a, "pour", arg)
                for n in range(a+1, arg+1):
                    res *= n