Inscription / Connexion Nouveau Sujet
Niveau Autre prépa
Partager :

python

Posté par
nullptr19
13-01-21 à 20:56

Bonjour à toutes et a tous ,

alors j'ai un programme sur les fractions continues à rentrer en machine à l'aide du langage python .

je dois écrire un nombre rationnel sous forme de fraction continue . éventuellement je pourrais également traiter pour les nombres irrationnels ( développement multi periodique) , mais si je peux dans un premier temps réaliser le développement fini pour les rationnel , je pense que ce serait déjà intéressant .

alors mon idée est de créer une liste dont l'instance sera soit une liste soit une fraction .

ensuite définir deux méthodes qui va me traiter les deux cas . C'est encore un peu abstrait mais j'aimerai savoir déjà si c'est nécessaire vraiment de créer une liste , est ce que ca ne  fait pas trop de code pour rien ? puis je contourner cela ?

Merci .

Posté par
nullptr19
re : python 13-01-21 à 20:57

*vont

Posté par
GBZM
re : python 13-01-21 à 21:26

Bonsoir,

Le développement d'un rationnel en fraction continue est, par définition, une liste. Tu n'y couperas pas.

Posté par
nullptr19
re : python 13-01-21 à 21:52

bah du coup est ce vraiment nécessaire de créer une classe ?

Posté par
nullptr19
re : python 13-01-21 à 21:52

GBZM @ 13-01-2021 à 21:26

Bonsoir,

Le développement d'un rationnel en fraction continue est, par définition, une liste. Tu n'y couperas pas.


totalement d'accord !

Posté par
GBZM
re : python 13-01-21 à 22:27

nullptr19 @ 13-01-2021 à 21:52

bah du coup est ce vraiment nécessaire de créer une classe ?

Que veux-tu dire ?

Posté par
nullptr19
re : python 13-01-21 à 22:35

pour rentrer ce programme en machine j'ai envie de me servir d'une classe

class FracContinue :

et considérer deux instances (liste et fraction ) vu que j'ai envie de retrouver une liste à partir d'une fraction et vis versa , je demande donc si cest vraiment nécessaire de travailler avec une class , ou est ce que je peux m'en passer , juste pour pas que le programme il soit très long

Posté par
verdurin
re : python 13-01-21 à 22:59

Bonsoir nullptr19.
Je ne maîtrise pas du tout la programmation objet, mon conseil est donc limité.

Je te conseille d'écrire une fonction qui associe à un rationnel son développement en fraction continue et une fonction qui associe à une fraction continue finie le rationnel  qu'elle représente.

En voyant ce que tu as déjà écris comme « fonction » sur ce forum, ce serait pas mal.

On peut sans doute passer d'un niveau d'abstraction à un autre.
Mais commencer en disant : « j'ai envie de me servir d'une classe » ne me semble pas un bon début.

Posté par
nullptr19
re : python 13-01-21 à 23:14

verdurin ok merci je me lance , l'algorithme d'Euclide je lai déjà histoire de récupérer les quotients issues des divisions euclidiennes .

je reviens vers vous .

Posté par
nullptr19
re : python 15-01-21 à 15:49

Bonjour , du coup j'ai juste fait un petit programme qui récupère chaque quotient issue de division euclidienne de a par b bien sur a le numérateur et b le dénominateur . voici ce que ça donne

from math import *
def reduite(a,b):
   liste=[]    # on commence par créer une liste qui contiendra ces quotients.
   if a < b:  # on s'assure entre autre que le dividende soit plus grand que le diviseur.
       a, b = b, a
   while b != 0:   # dans cette boucle on déroule l'algorithme d'Euclide
       a, b , q = b, a % b , a // b # on descend l'algorithme d'Euclide 
       liste += [ q ] # ici on part du fait que [i]+[j]=[i,j] ,
   else:              #et a chaque fois on ajoute les q issus des divisions.
       return liste 


développement en fraction continue .

pour les rationnelle ça marche super bien mais pour les irrationnel ça me renvoi des flot dans ma liste , bon bref vous me donnerez vos appréciations.

Posté par
GBZM
re : python 15-01-21 à 16:31

Pourquoi intervertis-tu a et b si a<b ? Ça va donner un mauvais résultat pour une fraction du genre 2/3.
Tu peux forcer a//b à être du type entier.

Par exemple :

def reduite(a,b=1):
    liste=[]    
    while b != 0: 
        q=int(a//b)
        liste += [q]
        a, b  = b, a-q*b
    return liste 


Pour les rationnels, pas de problème :
reduite(1789,2783)
[0, 1, 1, 1, 3, 1, 198]
Mais si on passe en flottant, ça diverge bien sûr :
reduite(1789/2783)
[0, 1, 1, 1, 3, 1, 197, 1, 7526760692, 1, 6, 1, 2, 9]
Et si on essaie pour la racine carrée de 2, ça déconne au bout d'un certain temps :
print(reduite(sqrt(2)))
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 7, 1, 2, 33, 2, 7, 5, 2, 1, 1, 16, 2]

Et puis ça s'arrête, alors que le développement en fraction continue pour un irrationnel est bien sûr infini.

Posté par
GBZM
re : python 15-01-21 à 16:51

Ah, une remarque sur la terminologie : réduite, c'est plutôt l'opération dans l'autre sens : partant d'un développement en fraction continue (tronqué), récupérer un rationnel.

Posté par
verdurin
re : python 15-01-21 à 18:34

Une remarque sur les flottants.
On peut avoir l'approximation d'un nombre x utilisé par python sous forme rationnelle en utilisant la méthode x.as_integer_ratio().

Par exemple

>>>sqrt(2).as_integer_ratio()
(6369051672525773, 4503599627370496)
.

En reprenant la fonction donnée par GBZM
def reduite(a,b=1):
    liste=[] 
    if b==1 and isinstance(a, float):
        a,b=a.as_integer_ratio() 
    while b != 0: 
        q=a//b
        liste += [q]
        a, b  = b, a-q*b
    return liste 


Un exemple d'exécution
>>>reduite((1+sqrt(5))/2)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
2, 7, 1, 5, 5, 1, 1, 2, 4, 1, 1, 10, 1, 2, 1, 8]

En principe la liste de la fraction continue est formée d'une suite infinie de 1.
Mais il ne faut pas croire que python est un logiciel de calcul formel.

PS : je suis d'accord avec GBZM : le nom de la fonction est mal choisi.

Posté par
nullptr19
re : python 15-01-21 à 19:28

GBZM @ 15-01-2021 à 16:31

Pourquoi intervertis-tu a et b si a<b ? Ça va donner un mauvais résultat pour une fraction du genre 2/3.
Tu peux forcer a//b à être du type entier.

Par exemple :
def reduite(a,b=1):
    liste=[]    
    while b != 0: 
        q=int(a//b)
        liste += [q]
        a, b  = b, a-q*b
    return liste 


Pour les rationnels, pas de problème :
reduite(1789,2783)
[0, 1, 1, 1, 3, 1, 198]
Mais si on passe en flottant, ça diverge bien sûr :
reduite(1789/2783)
[0, 1, 1, 1, 3, 1, 197, 1, 7526760692, 1, 6, 1, 2, 9]
Et si on essaie pour la racine carrée de 2, ça déconne au bout d'un certain temps :
print(reduite(sqrt(2)))
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 7, 1, 2, 33, 2, 7, 5, 2, 1, 1, 16, 2]

Et puis ça s'arrête, alors que le développement en fraction continue pour un irrationnel est bien sûr infini.


Bonsoir , bein je veux juste me rassurer que a le dividende est toujours plus grand que le diviseur , après si vous me dite que ce n'est pas nécessaire je peux comprendre

Posté par
nullptr19
re : python 15-01-21 à 19:30

a propos des nombres irrationnelle , je suis bien d'accord que la liste devrait être infinie , ce pendant , affiché ainsi mon programme reste toujours vraie ?

puisque à partir de la liste je peux bien voir les nombre qui se répète un bon nombre de fois  

Posté par
verdurin
re : python 15-01-21 à 19:36

On peut regarder 2/3.

\dfrac23=0+\dfrac1{1+\frac12}

La liste correspondante à son développement en fraction continue est [0, 1, 2].

Et il n'y a aucun problème.

Posté par
nullptr19
re : python 15-01-21 à 19:53

ca marche effectivement , auriez vous une idée pour le chemin inverse , partir d'une réduite pour retrouver un rationnel par exemple .

Posté par
nullptr19
re : python 15-01-21 à 20:44

verdurin @ 15-01-2021 à 19:36

On peut regarder 2/3.

\dfrac23=0+\dfrac1{1+\frac12}

La liste correspondante à son développement en fraction continue est [0, 1, 2].

Et il n'y a aucun problème.


oui j'ai bien compris , en inversant ça change la réduite , merci .

Posté par
nullptr19
re : python 15-01-21 à 20:51

GBZM @ 15-01-2021 à 16:51

Ah, une remarque sur la terminologie : réduite, c'est plutôt l'opération dans l'autre sens : partant d'un développement en fraction continue (tronqué), récupérer un rationnel.


ah d'accord j'avais pas vu la remarque , du coup pour la réduite comment puis je faire le chemin inverse , partir de l'écriture tronqué à la réduite pour les rationnels

Posté par
verdurin
re : python 15-01-21 à 21:32

Disons que tu as une liste [1, 2, 3, 4].
Elle représente le nombre :

1+\dfrac1{2+\frac1{3+\frac14}}=1+\dfrac1{2+\frac1{\frac{13}4}}=1+\dfrac1{2+\frac4{13}}=1+\dfrac1{\frac{30}{13}}=1+\frac{13}{30}=\frac{43}{30}

La méthode de calcul me semble assez évidente.

Posté par
nullptr19
re : python 16-01-21 à 15:00

je comprend bien le procéder mais le mettre en machine je vois pas l'astuce , j'ai essayer de travailler avec le module "fractions " , mais je vois pas comment récupérer à chaque fois les fractions enfin bref je ne m'y retrouve pas

Posté par
verdurin
re : python 16-01-21 à 16:04

On peut utiliser la représentation matricielle des fonctions  x\mapsto \dfrac{ax+b}{cx+d}
À la fonction ci-dessus on fait correspondre la matrice \begin{pmatrix}a&b\\c&d\end{pmatrix}

Si f et g sont représentées respectivement par les matrices A et B alors fog est représentée par la matrice produit AB.

En partant de la liste [a_0 ; a_1 ;\dots; a_n] représentant une fraction continue on a les matrices \begin{pmatrix}a_0&1\\1&0\end{pmatrix}\ ,\ \begin{pmatrix}a_1&1\\1&0\end{pmatrix}\ldots\begin{pmatrix}a_n&1\\1&0\end{pmatrix}.

Les réduites s'obtiennent en prenant la première colonne du produit.

On en déduit une relation de récurrence permettant de calculer les réduites successives :

si la réduite de la liste [a_0 ; a_1 ;\dots; a_n] est \dfrac{p_n}{q_n}
alors la réduite de la liste  [a_0 ; a_1 ;\dots; a_n;a_{n+1}] est \dfrac{p_{n+1}}{q_{n+1}}
avec \begin{cases}p_{n+1}=a_{n+1}p_{n}+p_{n-1}\\q_{n+1}=a_{n+1}q_{n}+q_{n-1}\end{cases}. Pour amorcer la récurrence on peut poser p_{-1}=1 et q_{-1}=0

Un exemple avec la liste [1 ; 2 ; 3 ; 4]
p_0=1 et q_0=1 car la partie entière est 1 ( on a toujours q_0=1)
p_1=2\times p_0+p_{-1}=3  et q_1=2\times q_0+q_{-1}=2
p_2=3\times 3+1=10  et q_2=3\times 2+1}=7
p_3=4\times 10+3=43  et q_3=4\times 7+2}=30

soit
1=\frac11
 \\ 
 \\ 1+\frac12=\frac32
 \\ 
 \\ 1+\dfrac1{2+\frac1{3}}=\frac{10}7
 \\ 
 \\ 1+\dfrac1{2+\frac1{3+\frac14}}=\frac{43}{30}

Posté par
GBZM
re : python 16-01-21 à 16:31

Si tu utilises le module "fractions" de Python, c'est simple.
Tu pars d'un développement en fraction continue qui est une liste finie d'entiers de longueur au moins 1 dont tous les termes après le premier sont >0..
Si la liste est de longueur 1, la réduite est l'entier unique terme de la liste, que l'on convertit en fraction.
Sinon, la réduite est le premier terme de la liste + l'inverse de la réduite de la liste composée des termes suivants (entier plus inverse d'une fraction non nulle donne une fraction).

Posté par
nullptr19
re : python 17-01-21 à 17:01

Bonjour verdurin merci pour ta proposition , je vais essayer avec ce que me propose GBZM car c'est dans l'esprit de l'exercice que le prof nous a demandé de faire .

je reviens vers vous j'essaie de le traduire en machine ,

Posté par
nullptr19
re : python 17-01-21 à 18:23

GBZM j'arrive pas à saisir l'idée voici ce que j'ai essayé:

ef reduite (list):
    k=0
    for i in list:
        if len(list)==1:
            return list[0] + Fraction(0,1)
        while list[0]!=0 and len(list)>1:
             
            list[0] + Fraction(1,list[k])
            k+=1
        return list[0] + Fraction(1,list[k])


c'est un peu du n'importe quoi mais j'arrive pas à saisir l'idée

Posté par
GBZM
re : python 17-01-21 à 18:27

Je t'ai donné l'idée d'une procédure récursive, qui me semble claire.
Là, tu as effectivement écrit un peu n'importe quoi.
Le mot "récursif" fera-t-il tilt ?

Posté par
nullptr19
re : python 17-01-21 à 18:32

ok  je m'y met

Posté par
nullptr19
re : python 17-01-21 à 21:49

def reduite (liste):

    if len(liste)==1: # le cas ou la liste est de taille 1
                    
        return Fraction(liste[0],1)

    while len(liste)>0 and liste[0]!=0:

        return Fraction(liste[0] + 1/reduite(liste[1:])) 


ça marche bien merci ,

cordialement

Posté par
GBZM
re : python 17-01-21 à 23:40

Ton instruction while est pour le moins surprenante, et pourquoi ce liste[0] !)= 0 ???

As-tu essayé reduite([0,1,2,3]), pour voir ?

Posté par
nullptr19
re : python 18-01-21 à 13:42

ah oui çà m'affiche "none" et oui maintenant que je m'en rend compte , liste [0] !=0  n' a pas d'importance ici ..

Posté par
nullptr19
re : python 18-01-21 à 13:49

et la ça marche parfaitement ! en fait je sais même pas comment liste [0] !=0 a pu se retrouver comme condition de ma boucle , c'est assez étrange , mais bon ...

Posté par
nullptr19
re : python 18-01-21 à 13:52

du coup :

def reduite (liste):

    if len(liste)==1: 
                
        return Fraction(liste[0],1)

    while len(liste)>1:

        return Fraction(liste[0] + 1/reduite(liste[1:]))

Posté par
GBZM
re : python 18-01-21 à 14:06

Ça marche, mais ton "while" est vraiment incongru ici (je te l'avais déjà dit). Heureusement que le "return" lui coupe l'herbe sous le pied.

Posté par
nullptr19
re : python 18-01-21 à 14:08

un else peut etre ?

ef reduite (liste):

    if len(liste)==1: # 
                    
        return Fraction(liste[0],1)

    else:

        return Fraction(liste[0] + 1/reduite(liste[1:])) 
              

Posté par
GBZM
re : python 18-01-21 à 14:56

C'est mieux.

Posté par
nullptr19
re : python 18-01-21 à 17:19

merci .

Posté par
verdurin
re : python 19-01-21 à 12:13

Juste pour donner une solution moins élégante que la récursivité, mais qui correspond exactement au calcul tel que je l'avais présenté.


def reduite(liste):
    r=Fraction(liste.pop(),1) # r=dernier élément de liste/1 et on le supprime de liste
    for a in reversed(liste) : # a parcourt la liste du dernier élément au premier
        r=a+1/r
    return r

Posté par
nullptr19
re : python 19-01-21 à 13:26

verdurin merci pour le complément je prend en compte

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1446 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !