petit problème algorithme euclide (python)

[souchi6]

Bonjour, je me permets de demander un peu d'aide concernant un petit programme en python que je suis sensé effectuer mais je débute donc j'ai un peu de mal.
On me demande de programmer la fonction nommée Euclide renvoyant le pgcd entre deux nombres a et b (seulement la fonction et non pas le programme entier demandant a,b, les conditions sur a et b etc...).
Pour ceci on me décrit la méthode:
Soit a et b, deux entiers positifs. On construit euclide (n) telle que:
-euclide(0)=a et euclide (1)=b
-euclide(n+1)=euclide(n-1) mod euclide(n)
Le dernier terme non nul de la suite est le pgcd entre a et b.

Voici mon programme :

def euclide(n):
     
     if n==0:
        return a
     elif n==1:
        return b
     else:
        return euclide(n-2)%euclide(n-1)  #même chose que l'énoncé je pense mais avec une égalité pour euclide(n) au lieu de euclide(n+1)

n=0
n=n+1

if euclide(n)==0:
    print 'le pgcd est : ',euclide(n-1)

Le problème est que le calcul de la fonction ne se met pas en route et je ne sais pas quoi rajouter de plus que n=n+1....
-----

[kwariz]

Bonjour,

à moins que l'exercice ne soit prpoposé dans le cadre de la programmation fonctionnelle, une fonction qui calcule le pgcd de deux entiers a au minimum deux paramètres entiers. Peux-tu nous donner l'énoncé en entier ?

[souchi6]

En fait dans un premier temps on m'a demande d'effectuer le programme complet demandant les deux entiers a et b à l'utilisateur mais .en supposant que la fonction qui renvoie le pgcd entre a et b était connu et s'appelait euclide.
Dans une deuxième question on m'a demande de coder cette fonction euclide sous forme récursive.
Tout l'énoncé est déjà dans mon dernier post...
J'ai voulu tester ma fonction en prédéfinissant un a et un b dans le terminal et quand je lance mon programme rien ne se passe.
Je pense que mes conditions sont bonnes mais j'aimerais faire en sorte que la fonction calcule elle même à partir de n=2 les parties entières des divisions jusqu'à tomber à 0 et le donner le pgcd.

[kwariz]

La forme récursive du pgcd est relativement simple



Pourquoi cherches-tu une fonction avec juste un paramètre ?

[A voir en vidéo sur Futura]

[souchi6]

Oui c'est vrai qu'il serait plus simple d'utiliser ceci mais l'énoncé demande d'utiliser la fonction ou suite
euclide(n+1)=euclide (n-1)mod euclide(n).
J'aimerais que mon programme calcule tous les termes de la suite(à partir de 2) jusqu'à tomber sur le terme égal à 0. Le terme avant sera alors le pgcd entre a et de b.
a et b seront demandé avant à l'utilisateur.

[souchi6]

ce a sera euclide(0) et b sera euclide (1) les deux premiers termes de la suite, indispensable au calcul de la suite (euclide)

[kwariz]

ta définition pour euclide est bonne :

> pythonPython 3.3.0 (default, Sep 29 2012, 15:50:43) 
[GCC 4.7.1 20120721 (prerelease)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def euclide(n):                                                                                  
...     if n==0:                                                                                     
...         return a                                                                                 
...     elif n==1:                                                                                   
...         return b                                                                                 
...     else:                                                                                        
...         return euclide(n-2) % euclide(n-1)                                                       
... 
>>> a=19
>>> b=3
>>> euclide(0)
19
>>> euclide(1)
3
>>> euclide(2)
1
>>> euclide(3)
0
>>>

[souchi6]

Et ne peut on pas trouver un moyen pour que le programme calcule lui même euclide(0), euclide(1), euclide(2) etc....jusqu'à tomber sur 0
plutot que d'avoir à tester chaque terme nous même ?

[kwariz]

Si, en utilisant une boucle par exemple. C'est dans le cadre de la programmation fonctionnelle ou impérative ?

[souchi6]

euh...je ne suis pas sur de connaître la différence entre ces deux termes.
Mais je pensais que c'est ce que faisait la fin de mon programme en initialisant n à 0, en le faisant augmenter par pas de 1 puis en introduisant la condition if.
C'est le seul moyen que je vois car pour une boucle for il faut que je connaisse le maximum de n (pour le range) or, il n'est pas défini.

[kwariz]

par exemple en pseudo code :

a=...
b=...
n=2
tant que euclide(n)<>0
  n=n+1
fin tant que
// ici tu es certaine que euclide(n)=0, donc euclide(n-1) contient le pgcd
afficher "pgcd = " euclide(n-1)

[souchi6]

ah oui en effet merci beaucoup je comprends mieux le n=n+1 doit être dans la boucle while du calcul c'est plus logique.
Avez vous une idée de ce que pourrait donner ce programme sous une version itérative?
Si je comprends bien (pas sur) la version iterative doit être sous forme de tableau peut être en utilisant la fonction zeros(x) qui donne un tableau de x cases de valeurs 0. Mais comment savoir combien de cases doit-il y avoir au début dans le tableau?
j'ai essaye ça je ne sais pas si le np.zeros(i) a un sens mais en tout cas le programme me donne index out of bounds :

import numpy as np
pgcd=np.zeros(i)
pgcd[0]==a
pgcd[1]==b
pgcd[i+1]=pgcd[i-1]%pgcd[i-2]
i=2
while pgcd[i]!=0:
    i=i+1
    
if pgcd[i]==O:
    print pgcd[i-1]

[kwariz]

Un algorithme itératif est simplement un algorithme qui n'utilise pas la récursivité. Si on reprend la définition :

on aboutit à :
tant que b n'est pas nul, on fait nouvelle valeur de a = ancienne de b et nouvelle de b= ancienne de a modulo ancienne de b.
En python ça doit donner quelque chose comme :

def euclide_it(a,b):
     while (b>0):
             a,b=b,a%b
     return a

C'est une des façons de dérécursiver une fonction récursive terminale.

Maintenant tu peux aussi essayer de partir d'un tableau contenant a et b puis l'étendre :

def euclide_it2(A):
     n=1
     while (A[n]!=0):
             n=n+1
             A.append(A[n-2]%A[n-1])
     return A

Effectivement tu ne sais pas combien d'éléments tu vas devoir ajouter, mais peu importe tu utilises append qui étend le tableau. L'élément que tu ajoutes est simplement le modulo des derniers comme dans la définition.