Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 28-06-2009 21:08:46

Golgup
Membre actif
Inscription : 09-07-2008
Messages : 574

[Python] Identité de Bachet-Bezout.

iHola!

J'ajoute à la collection ce ptit programme qui trouve donc u et v tq au+bv=pgcd(a,b) plus les solutions generales!

def pgcd(a,b):
    try:
        while b!=0:
            a=a%b
            b=b%a
        return a
    except:
        return b

def t1_t2(a,b):
    try:
        while b!=0:
            a=a%b
            t1.append(a)
            t2.append(b/a)
            b=b%a
            t1.append(b)
            t2.append(a/b)
        return t2
    except:
        return t2
   
print"                                                               *Recherche (a,b) <=> au+bv=gcd(a,b)*"            
a=input('Entrez a:')
b=input('Entrez b:')
t1,t2=[a,b],[a/b]
t2=t1_t2(a,b)
l,xk,yk=1,[1,0,1],[0,1,t2[0]]

while l!=len(t1)-2:
    l=l+1
    xk.append(t2[l-1]*xk[len(xk)-1]+xk[len(xk)-2])
    yk.append(t2[l-1]*yk[len(yk)-1]+yk[len(yk)-2])
   
print"*Solution particuliere:*"
print ""
print a,'*',((-1)**(len(t1)-2))*xk[len(xk)-2],'+',b,'*',((-1)**(len(t1)-1))*yk[len(yk)-2],'=',pgcd(a,b)
print""
print"*Solution generale:*"
print ""
print 'u_k','=',((-1)**(len(t1)-2))*xk[len(xk)-2],'+',xk[len(xk)-1],'k'
print 'v_k','=',((-1)**(len(t1)-1))*yk[len(yk)-2],'-',yk[len(yk)-1],'k'

++

Dernière modification par Golgup (12-07-2009 18:15:52)


« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »

Hors ligne

#2 04-07-2009 02:17:43

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : [Python] Identité de Bachet-Bezout.

Yop,
"Oh mon dieu que c'est moche" serait la remarque (absolument non constructive) que je m'autoriserais à faire si j'étais ton prof d'info (dans le supérieur, parce que dans le secondaire ça semblerait décourageant). Malheureusement, tu n'es pas mon élève, tu n'as sûrement pas de cours d'info digne de ce nom, tu n'es pas dans le supérieur et je ne suis pas prof (enfin, ça dépend de la définition de prof). Je me contenterai donc de justifier ma remarque par un argument primitif : j'évacue pour passer à la suite de façon plus constructive.

Tout d'abord, j'admire l'entrain et le bon sens dont tu fais preuve pour écrire un code permettant de résoudre des problèmes que l'on aborde normalement bien plus tard (les problèmes aussi bien que leur code).

Par contre, et pour que tu puisses progresser, voici les reproches que je fais à ton code :
1/ Il utilise des effets de bords : typiquement, l'utilisation de variables globales modifiées par un appel à une fonction (qui en plus retourne une valeur) est une chose déconseillée dans le cas général. (En fait, c'est une façon de programmer tout à fait acceptable quand on a une bonne raison de le faire, ce qui n'est à mon humble avis pas le cas ici).

2/ Le langage python te fourni un modulo : l'opérateur est %, utilise le ! Il est bon de savoir comment le reprogrammer à partir de rien, mais par exemple tu n'as jamais envisagé de reprogrammer l'addition ? De plus, le modulo de python a beaucoup de chance d'être plus efficace que ton implémentation.
2bis/ La division entière ne nécessite pas de typecast vers les entiers : a/b est le quotient dans la division euclidienne de a par b.

3/ Pour programmer de façon propre, on distingue (au moins) deux types de fonctionnalités : le calcul d'une part, l'interaction homme-machine d'autre part. Il convient alors d'encapsuler :
   * d'un côté les fonctions de calcul, comme pgcd ou modulo (ça tu l'as fait), mais aussi ta boucle while et tes calculs compliqués que tu as mis au milieu des print ! Ça constitue en quelque sorte ce qu'on appelle généralement "librairie" (sauf que là c'est une librairie locale)
   * de l'autre coté, une fonction qui fait appel aux input et aux print. Cette fonction étant appelée lors de l'exécution du fichier.


NB :
J'avais donné une version compacte de la fonction qui résout ton problème, que j'ai nommée bezout, ici : http://www.bibmath.net/forums/viewtopic.php?id=2479 (Il s'agit là d'une version fonctionnelle, de surcroît récursive)
Il y également une version impérative donnée par yoshi, ici : http://www.bibmath.net/forums/viewtopic.php?id=2701 sous le nom xeuklid qui doit être légèrement modifié pour te sortir les coefs de bezout, mais si tu me demandes, je te la donne.

N'hésite pas à poser des questions si je ne suis pas clair dans mon commentaire, si tu veux que je donne des exemples plus précis, où si tu veux que je développe quelque chose.

++

Dernière modification par Barbichu (04-07-2009 02:18:30)


Barbichu

Hors ligne

#3 04-07-2009 09:46:41

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : [Python] Identité de Bachet-Bezout.

Hello,

Seigneur Barbichu, quel plaisir de vous revoir en ces lieux !
Vous-êtes-vous laissé pousser les crocs ou bien avez-vous fait l'acquisition d'une "lime diamant' (travail plus fin) ?
T'aurais quand même dû penser à "marcher, bien davantage, sur des oeufs" ! ;-)

Barbichu a écrit :

2bis/ La division entière ne nécessite pas de typecast vers les entiers : a/b est le quotient dans la division euclidienne de a par b.

C'est vrai 5/3 donne 1 comme quotient...
Mais, Golgup, si tu veux un quotient décimal : 5.0/3  ou 5/3.0 --> 1.3333
Je te concède que c'est un peu tordu...
Les développeurs de Python en ont eu bien conscience, et ils ont rectifié le tir dans la version 3.0 et au delà :
En effet :

Python - Pep Index -PEP 238 -- Changing the Division Operator a écrit :

We propose to fix this by introducing different operators for different operations: x/y to return a reasonable approximation of  the mathematical result of the division ("true division"), x//y to return the floor ("floor division").  We call the current, mixed meaning of x/y "classic division".

Donc, la question est : Golgup utilise-t-il une version 2.5 ou 2.6 ou une 3.x ?
La réponse est dans son script :

print "*Solution particulière:*"

En python 3.x, il aurait eu un joli message d'erreur : print y est devenu une fonction. On y écrit donc print(" * Solution particulière : *")

J'aurais pu par contre faire une remarque sur le Input : il est dit partout qu'il vaut mieux utiliser raw_input() qui retourne une chaîne de caractères. Mais il se trouve qu'avec Python 3.x on retrouve input :

Python - Pep Index -PEP 3111 -Simple Input built-in Python 3000 a écrit :

Specification
The Python 2 to 3 conversion tool will replace calls to input() with eval(input()) and raw_input() with input()
The existing raw_input() function will be renamed to input().

D'après ce que j'ai cru comprendre, input avec version < 3.0 pouvait permettre l'exécution de code, et donc de code malveillant, genre si j'accède à un programme sur ta machine, programme qui demande quelque chose via input, je peux donner l'ordre de formater ton disque dur...
Marrant, hein ?

Par contre, Golgup :

while l!=len(t1)-2:
    l=l+1
    xk.append(t2[l-1]*xk[len(xk)-1]+xk[len(xk)-2])
    yk.append(t2[l-1]*yk[len(yk)-1]+yk[len(yk)-2])
    if l==len(t1)-2:
        break

Ca, ce n'est pas logique :
tant que l est différent de len(t1)-2, alors fais.... : d'accord !
Mais ça veut dire aussi :
arrête-toi dès que l == len(t1)-2. Donc à quoi sert  le :

if l==len(t2)-1:
    break

J'ai cru lire aussi qu'il valait mieux écrire, par ex :

lg2=len(t1)-2
while l! = lg2:

que c'est plus rapide...

D'autre part, si Golgup a logé des fonctions au milieu du calculs, c'est que probablement, il ne sait pas pas que les fonctions ne sont exécutées que si on les appelle, donc que pour une meilleure lisibilité il vaut mieux faire !

#!/usr/bin/env python
# -*- coding: cp1252 -*

## ou tout autre encodage de caractère... Pour sortie dos --> cp437

def ............ :
     return

def .......:
    return


def .........:
    return

Prog principal
--------
..........
---------

Il est de plus recommandé de sauter une ligne pour séparer...

@Barbichu
Est-ce que tu peux préciser ta pensée ? Je ne comprends pas :

l'utilisation de variables globales modifiées par un appel à une fonction (qui en plus retourne une valeur)

Si tu ne passes pas en argument à une fonction, une valeur obtenue depuis le corps du prog, comment fais-tu alors ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#4 05-07-2009 23:42:33

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : [Python] Identité de Bachet-Bezout.

Yop,

yoshi a écrit :

@Barbichu
Est-ce que tu peux préciser ta pensée ? Je ne comprends pas :

l'utilisation de variables globales modifiées par un appel à une fonction (qui en plus retourne une valeur)

Si tu ne passes pas en argument à une fonction, une valeur obtenue depuis le corps du prog, comment fais-tu alors ?

je parle, dans le cas particulier de Golgup, de l'utilisation des variables 't1' et 't2' qui sont modifiées par effet de bord par chaque appel à la fonction 'modulo' (dans le corps de laquelle on n'a même pas moyen de comprendre d'où viennent ces deux variables). Ces deux variables sont les "resultats" plus ou moins utiles de la fonction pgcd, qui dépend donc d'une bonne initialisation exterieure des deux variables en question (qu'il n'est pas possible de garantir dans le cas d'un autre programme).
Ce genre de manipulation rend les deux fonctions modulo et pgcd extrêmement dangereuses à être appelées : en effet, leur correction dépend complètement du contexte d'exécution, ... une chose extrêmement regrettable.
++


Barbichu

Hors ligne

#5 12-07-2009 18:30:12

Golgup
Membre actif
Inscription : 09-07-2008
Messages : 574

Re : [Python] Identité de Bachet-Bezout.

sveiki!!(Excusez le retard)

OOlala c'est vrai que ce n'est pas tres joli! mais pourquoi ai-je donc créé cette fonction modulo?! m'enfin le problème est résolu et j'en est profité aussi pour ameliorer mes 3 autres prog.

Si jamais, la methode utilisée et celle que j'avais décrite ici http://www.bibmath.net/forums/viewtopic.php?id=2312

En tous cas merci à Barbichu et Yoshi!!

bye


« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante quatorze moins vingt
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums