Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... AnalyseTopics traitant de analyse [tout]Lister tous les topics de mathématiques
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
nullptr19re : python 13-01-21 à 20:57

*vont

Posté par
GBZMre : 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
nullptr19re : python 13-01-21 à 21:52

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

Posté par
nullptr19re : 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
GBZMre : 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
nullptr19re : 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
verdurinre : 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
nullptr19re : 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
nullptr19re : 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
GBZMre : 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
GBZMre : 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
verdurinre : 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
nullptr19re : 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
nullptr19re : 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
verdurinre : 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
nullptr19re : 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
nullptr19re : 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
nullptr19re : 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
verdurinre : 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
nullptr19re : 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
verdurinre : 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
GBZMre : 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
nullptr19re : 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
nullptr19re : 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
GBZMre : 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
nullptr19re : python 17-01-21 à 18:32

ok  je m'y met

Posté par
nullptr19re : 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
GBZMre : 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
nullptr19re : 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
nullptr19re : 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
nullptr19re : 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
GBZMre : 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
nullptr19re : 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
GBZMre : python 18-01-21 à 14:56

C'est mieux.

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

merci .

Posté par
verdurinre : 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
nullptr19re : 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.

Rechercher
Menu
Espace membre
Changer d'île

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 !