Récursivité

[Remyy]

Bonjour, j’ai besoin de votre aide concernant l’exercice en photo. J’ai plus ou moins compris l’algorithme et répondu aux deux premières question. Mais je n’arrive pas à expliquer les suivantes, quelqu’un pourrait m’aider svp?

[julesx]

Bonjour,

A priori, j'ai des problèmes avec la gestion de la récursivité (cf. des fils précédents). Tout ce que j'ai compris, c'est qu'il s'agit de fonctions qui s'appellent elle-même jusqu'à ce qu'un paramètre atteint une limite fixée.
C'est bien le cas dans la fonction nb_rendus qui s'appelle en fait deux fois à chaque tour en diminuant à chaque coup le montant ou le nombre de pièces. Le critère d'arrêt est défini avant le return 0.
A toi de voir comment tu peux utiliser cela pour répondre à la question 3.

4) Je suppose qu'il faut faire tourner le script et simplement donner la réponse retournée. J'ai obtenu 159.

5) Python interrompt le déroulement avec le message d'erreur RecursionError: maximum recursion depth exceeded in comparison.
En gros, le script empile des données dans une partie de la mémoire vive de l'ordinateur sans les effacer tant qu'il y a récursivité. Pour éviter de saturer la mémoire vive, Python limite le maximum de récursions à 1000, valeur qui serait largement dépassée avec un montant de 10000. 
Mais le mieux est d'aller voir sur la toile en mettant ce message dans ton moteur de recherche, tu trouveras des éléments de réponse plus détaillés avec, en particulier, comment outrepasser cette limite (ce qui n'est pas demandé ici).

6) Tu essaies de voir ce que tu peux faire ? Personnellement, je ne vois pas a priori comment utiliser la fonction fibo dans ce contexte. C'est déjà ce que j'ai répondu à un autre demandeur, voir
https://www.e-bahut.com/topic/58471-aide-python/

 

[Remyy]

Merci beaucoup pour ton aide et l’explication, je vais voir ce que je peut fair. Et il est vrai pour la question 6 que je ne vois pas vraiment le rapport avec fibo, je vais encore fair des recherches mais bon. 

[julesx]

Bonjour,

Si tu obtiens le corrigé pour la question 6, et si ce n'est pas confidentiel, j'aimerais bien le voir.

Bonne continuation.

[julesx]

Bonsoir,

Par curiosité, j'ai continué à explorer la toile et je suis tombé sur ce script non récursif

def crossprod (list1, list2):
    output = 0
    for i in range(0,len(list1)):
        output += list1[i]*list2[i]      
    return output

def breakit(target, coins):
    coinslimit = [(target // coins[i]) for i in range(0,len(coins))]
    count = 0
    temp = []
    for i in range(0,len(coins)):
        temp.append([j for j in range(0,coinslimit[i]+1)])
    # print(temp)
	r=[[]]
    for x in temp:
        t = []
        for y in x:
            for i in r:
                t.append(i+[y])
        r = t
    for targets in r:
        if crossprod(targets, coins) == target:
            print(targets)
            count +=1
    return count

coins = [1,5,10,25,50]
target = 20
print(breakit(target, coins))

Il affiche en plus toutes les possibilités mais tu peux supprimer cet affichage en enlevant la ligne print(targets).
C'est a priori avec des noms de variables en anglais, mais on les comprend aisément.

Par contre le gros problème est que :
* Il est beaucoup plus lent
* S'il n'y a pas de limite due à la profondeur de récursivité, il y en a une à la quantité de mémoire disponible. Je pense que c'est lié à la variable temp qui contient toutes les valeurs possibles de chaque monnaie entre 1 et le montant (en particulier, le premier terme de la liste contient montant fois la valeur 1). Tu peux le voir en activant le print(temp) que j'ai inhibé par #.

Bon, c'est juste pour le fun, comme dit, si on te donne la "bonne" solution, je suis toujours preneur.