Exponentiation modulaire tres rapide
Résolu
Utilisateur anonyme
-
Utilisateur anonyme -
Utilisateur anonyme -
Bonjour,
Savez vous comment cette algorithme fonctionne réellement?
Je cherche a savoir comment ça se fait que après que la fonction soit appelé jusqu'à k=1 alors elle arrive a revenir en arrière et retrouver son chemin pour donner la bonne solution (je cherche donc des caractéristiques propres a python sur les fonctions récursives)
Si quelqu'un peut m'expliquer le principe de cette pile d'éxécution (si c'est bien cela), j'en serait ravi.
Voici le code:
Merci d'avance
Savez vous comment cette algorithme fonctionne réellement?
Je cherche a savoir comment ça se fait que après que la fonction soit appelé jusqu'à k=1 alors elle arrive a revenir en arrière et retrouver son chemin pour donner la bonne solution (je cherche donc des caractéristiques propres a python sur les fonctions récursives)
Si quelqu'un peut m'expliquer le principe de cette pile d'éxécution (si c'est bien cela), j'en serait ravi.
Voici le code:
import time
a=int(input())
k=int(input())
n=int(input())
hey=time.time() #rajouter pour obtenir le temps
def puis(a,k,n):
if k==0:
return 1
b=puis(a,(k//2),n)
if k%2==0:
return ((b*b)%n)
return ((b*b*a)%n)
print(puis(a,k,n))
ho=time.time()
print(ho-hey)
Merci d'avance
A voir également:
- Exponentiation modulaire tres rapide
- Acces rapide - Guide
- Copie rapide - Télécharger - Gestion de fichiers
- Telechargement rapide - Télécharger - Téléchargement & Transfert
- Desactiver demarrage rapide - Guide
- Assistance rapide - Accueil - Piratage
1 réponse
Bonjour
Le programme ne revient pas en arrière, il exécute simplement une à une les lignes. La récursivité est le fait de pouvoir appeler une fonction dans elle même.
A la ligne
Exemple :
Prenons a=6, k=3, n=4
puis(6,3,1)-> 1er appel de la fonction
k n'est pas égal à 0 mais à 3
b=puis(6,1,1)-> 2nd appel de la fonction
k n'est pas égal à 0 mais à 1
b=puis(6,0,1)-> 3ème appel de la fonction
k est égal à 0 -> on retourne 1, la récursivité est à partir de là stoppée
on revient au 2ème appel donc
b=1
k=1 dans le 2ème appel
k est multiple de 2
on retourne 1 ((1*1)%4 = 1)
on revient au premier appel
b=1
k=3 dans le premier appel
k n'est pas multiple de 2
on retourne 2 ((1*1*6%4) = 2)
En revenant aux origines des appels récursifs, il te retourne la valeur finale.
Je te conseille de faire des print dans ta fonction récursive. Tu comprendras alors bien mieux comment cela se passe.
Qui ne tente rien n'a rien
Le programme ne revient pas en arrière, il exécute simplement une à une les lignes. La récursivité est le fait de pouvoir appeler une fonction dans elle même.
A la ligne
b=puis(a,(k//2),n)tu appelles de nouveau la fonction puis(). Ce qui fait que le pointeur d'exécution revient à la première ligne de ta fonction puis() mais garde en mémoire dans la pile d'excution l'origine de l'appel de la fonction. Ainsi selon ta variable k, une fois que l'exécution de la fonction sera arrivée au bout, c'est à dire lorsque k sera égal à 0, le programme remontera toute la pile d'exécution. Si on met pas de condition dans une fonction récursive, alors la fonction est appelée indéfiniment. Ce qui à terme provoque un débordement dans la pile d'éxécution.
Exemple :
Prenons a=6, k=3, n=4
puis(6,3,1)-> 1er appel de la fonction
k n'est pas égal à 0 mais à 3
b=puis(6,1,1)-> 2nd appel de la fonction
k n'est pas égal à 0 mais à 1
b=puis(6,0,1)-> 3ème appel de la fonction
k est égal à 0 -> on retourne 1, la récursivité est à partir de là stoppée
on revient au 2ème appel donc
b=1
k=1 dans le 2ème appel
k est multiple de 2
on retourne 1 ((1*1)%4 = 1)
on revient au premier appel
b=1
k=3 dans le premier appel
k n'est pas multiple de 2
on retourne 2 ((1*1*6%4) = 2)
En revenant aux origines des appels récursifs, il te retourne la valeur finale.
Je te conseille de faire des print dans ta fonction récursive. Tu comprendras alors bien mieux comment cela se passe.
Qui ne tente rien n'a rien
Cette partie, je l'ai comprise, je cherche réellement a savoir comment python arrive a retenir la pile d'éxécution
C'est géré au niveau de l'interpréteur Python tout ça. Je ne vais pas pouvoir te dire précisément comment le système de pile a été codé, je n'en sais strictement rien.
Sujet résolu.