déclaration tableau de rationnels

Version imprimable

07/12/2012, 23h28
humanite

déclaration tableau de rationnels

Bonjour,

je souhaite déclarer un tableau de rationnels en C++, mais je ne connais pas sa taille à priori.

1) déjà, comment déclarer le type rationnel ? Y'a-t-un une librairie ?

2)Si j'appelle "type" ce type Dois-je écrire new type t[] ? comment le faire avec une référence ou pointeur ? En vérité, je ne comprends pas la différence de façon claire.

Merci de votre aide.

Cordialement
08/12/2012, 01h38
koala01
Citation:

Envoyé par matlab_

Bonjour,

je souhaite déclarer un tableau de rationnels en C++, mais je ne connais pas sa taille à priori.

1) déjà, comment déclarer le type rationnel ? Y'a-t-un une librairie ?

As tu été faire un tour du coté de std::complex :question: A moins que je ne me goure vraiment sur la signification de "nombre rationnel", c'est ce qu'il te faut ;)

En plus, c'est fourni en standard avec la STL dans l'espace de noms std. il suffit d'inclure le fichier d'en-tete <complex> pour en profiter ;)

Citation:

2)Si j'appelle "type" ce type Dois-je écrire new type t[] ?

Tu dois surtout utiliser la collection offerte par le standard qui correspond le mieux à tes besoins.

Tu peux te baser sur cette entrée de la FAQ pour choisir la bonne collection ;)

Citation:

comment le faire avec une référence ou pointeur ? En vérité, je ne comprends pas la différence de façon claire.

Alors, un pointeur n'est rien qu'une variable entière non signée dont la valeur correspond à l'adresse mémoire à laquelle on devrait trouver un objet du type indiqué, alors qu'une référence est un alias (comprends : un autre nom ) que l'on peut utiliser pour désigner un objet (une variable) existant(e).

Il est, en gros, possible d'utiliser un pointeur partout où l'on aurait utiliser une référence, mais il faut savoir qu'une référence sera beaucoup plus simple et sécurisante à l'emploi car:
1. Une référence offre une garantie de non nullité :si tu obtiens une référence sur quelque chose, c'est que ce quelque chose existe, alors qu'un pointeur peut ne pas exister (si tu fais bien ton boulot, il devrait pointer sur NULL (nullptr en C++11) pour représenter quelque chose d'inexistant
2. Une référence te permet d'utiliser la même syntaxe que si tu utilisait l'objet référencé (alors qu'il faut utiliser une syntaxe particulière pour les pointeurs)
3. Une référence rend plus facile le respect de la const-correctness Si tu déclare une référence comme étant constante ( const UnType & ref), tu ne pourras appeler que les fonctions membres qui se sont engagée à ne pas modifier l'objet (les fonctions constantes)
4. Tu es sur de n'avoir jamais à appeler delete sur une référence, alors que le pointeur peut pointer sur une adresse mémoire qui a été allouée dynamiquement (... ou non :aie:)
Le conseil de base que je donne volontiers se résume donc en gros à

Citation:

Utilises une référence chaque fois que c'est possible et un pointeur quand tu n'as vraiment pas le choix

Evidemment, cela signifie qu'il faut savoir "quand on n'a vraiment pas le choix" :aie:

En fait, tu n'as vraiment pas le choix lorsque tu ne peux pas faire autrement que de recourir à l'allocation dynamique de mémoire.

Mais, si tu utilises à fond les possibilités offertes par le standard, 99.9999 % des cas (je te laisse quand meme un peu de pondération :D) où tu ne pourras pas faire autrement que de recourir à l'allocation dynamique de la mémoire sont liés à la sémantique d'entité et au polymorphisme.

On peut citer les cas suivants:
1. Lorsque tu dois pouvoir placer des objets polymorphes dans une collection quelconque (on ne peut pas placer une référence dans une collection, car la référence n'a pas d'existence "réelle")
2. Lorsqu'une fonction doit créer un objet polymorphe pour le renvoyer à la fonction appelante, ou pour pouvoir l'utiliser "comme s'il s'agissait" du type de base
3. Dans le cas d'une relation "parent <->enfant", quand l'enfant doit pouvoir disposer d'une référence sur son parent (cela n'a pas forcément à voir avec le polymorphisme (quoi que), mais cela a avoir avec la sémantique d'entité ;))
Quoi qu'il en soit, depuis la sortie de la nouvelle norme (connue sous le petit non de C++11), tu ne devrais presque plus jamais recourir à des pointeurs "nus" (comprends : des pointeurs comme on en utilise à la pelle en C, par exemple), mais tu aurais grandement intérêt à travailler avec les "pointeurs intelligents" que sont unique_ptr, shared_ptr et weak_ptr, tous trois fournis par le standard dans l'espace de noms std par simple inclusion du fichier d'en-tête <memory>.

Et ne penses meme pas faire une allocation dynamique de la mémoire pour gérer les chaines de caractères, ni meme utiliser un char[XXX] : pour cela, rien ne vaut la classe string ;)
08/12/2012, 09h53
humanite

suite()

merci d'avoir répondu. C'est très sympathique de votre part.

J'ai tellement vu de polycopiés qui expliquent ce qu'est un pointeur. J'avais aussi acheté un livre de c++ il y a longtemps. Mais la notion de pointeur n'est pas encore clair, dois-je reconnaître. Je vais tenir compte de votre explication

Je ne sais pas si il y a un document synthétique pour le c++, et complet en même temps , j'ai téléchargé un document de Henry Garetta qui est un document classique de c++, mais je pense qu'il me faudrait de exemples très subtiles différents pour bien comprendre la différence.

Cordialement
08/12/2012, 11h18
JolyLoic

Les nombre rationnels :
Il n'existe rien en C++ pour les représenter de base. Ce qui en est le plus proche sont les nombres flottants (float et double), mais ils ne peuvent pas représenter de manière exacte un nombre rationnel (par exemple, 10*(1/10) ne vaudra pas exactement 1).

Par contre, rien ne t'empêche de les définir toi même. Tu définis une classe fraction, puis lui donnes les opérations nécessaires pour pouvoir manipuler aisément les instances de cette classe. C'est un très bon exercice (je le donne à faire quand je donne des cours), car il est assez simple, mais laisse plusieurs possibilités de design différents qu'il est intéressant de parcourir.

Si tu veux, une fois que tu auras fait ça, poste ton résultat ici pour commentaires.

Les tableaux :
En C++, un tableau de taille variable s'écrit le plus souvent vector. Si ta classe de rationnels se nomme Fraction, tu peux déclarer ton tableau std::vector<Fraction> monTableau. Tu pourras alors changer sa taille (monTableau.resize(10)) ou, plus souvent, ajouter un élément au bout (monTableau.push_back(Fraction(1,3))), et pour accéder à un élément monTableau[12] = 3.

Il existe des alternatives à vector, avec des compromis différents, mais quand on débute (et même plus tard, dans la majorité des cas), vector est suffisant.

Les écritures à base de [] et de pointeurs n'ont pas vraiment leur place ici. Elles sont très bas niveau, et servent à implémenter des structures plus haut niveau, plus puissantes et plus simples, telles que vector.
09/12/2012, 00h27
humanite

suite

Bonsoir,

new int tableau[] ne fonctionnerait-il pas ? puisque le [] indique que l'on ne connaît pas la taille du tableau à priori.

Il me semble , si j'ai compris que alloue de la mémoire ? Est-ce bien sa fonction ?

S'il vous plaît, y'aurait-il un livre et un fichier pdf très complet et surtout très agréable à lire et qui soit synthétique pour C++ ?

il y a de nombreux livres, mais pour ma part, j'ai réellement besoin d'une bonne référence, car j'ai tellement lu à droite et à gauche sur les pointeurs et références en C++ que maintenant, je suis un peu égaré. Je n'ai vraiment pas les idées claires, car je n'ai pas un support de base. Certains fichiers pdf que je ne citerais pas pour leurs auteurs sont truffés de petites fautes, ce qui embrouille des gens comme moi, qui ont besoin de documents agréables et sans faute.

Merci d'avance pour vos propositions.

Cordialement

Salut,

en complément des réponses précédentes, tu peux regarder/utiliser cette classe, issue de boost, une bibliothèque bien connue en C++ :
http://www.boost.org/doc/libs/1_52_0.../rational.html
Bien sûr, tu en trouveras d'autres sur la toile.

En ce qui concerne l'allocation dynamique, on déclare un tableau dont on ne connaît pas la taille à l'aide d'un pointeur. Par exemple,

Code:

int* tab; // tableau 1d d'entiers

Ensuite, plus loin dans le code, on alloue ce tableau à la taille souhaitée comme ceci :

Code:

tab = new int[N]; // allocation de tab avec une taille N connue

L'allocation dynamique a un coût de maintenance. Il faut libérer la mémoire allouée avant de sortir de la fonction où a eu lieu l'allocation:

Code:

delete [] tab; // libération de la mémoire occupée par tab

L'allocation dynamique d'une donnée membre d'une classe fonctionne un peu sur le même principe mais les différentes étapes apparaissent à des endroits différents :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 class Tableau { // donnee membre (déclaration) int* donnees; // constructeur (allocation) Tableau(int taille) {donnees = new int[taille];}; // destructeur (libération) ~Tableau() {delete [] donnees;}; };
Ces petits exemples sont simples mais très imparfaits. Je pense qu'une bonne manière de se familiariser avec le C++ est tout simplement de lire la faq de cette rubrique. Elle n'est a priori pas spécialement faite pour cela mais, pour avoir appris une bonne partie du langage en la lisant, elle est assez efficace de ce point de vue.

Puisque tu sembles être familiarisé avec matlab, je pense comme dit précédemment que l'utilisation de la classe vector de la bibliothèque standard te sera bénéfique car elle te permettra de ne pas allouer tout de suite tes tableaux mais également de faire varier dynamiquement leur taille... presque comme en matlab.

Je ne sais vraiment pas quoi te conseiller comme livre pour apprendre le langage C++. En français, je n'en vois que deux :
- la référence en la matière qu'est le livre du créateur du C++ (Stroustrup);
- la dernière version du livre de Delannoy.
A noter que beaucoup sur le forum détestent ce dernier livre à cause de la présence de coquilles dans les versions précédentes. La dernière version est bien meilleure de ce point de vue et assez complète. Elle aborde certains aspects récents du langage. Bien évidemment, je ne peux que te conseiller le livre de Stroustrup mais je pense que son prix n'est absolument pas justifié. Il vaut trois fois plus cher que le Delannoy. :aie:

09/12/2012, 11h45
JolyLoic

Citation:

Envoyé par matlab_

new int tableau[] ne fonctionnerait-il pas ? puisque le [] indique que l'on ne connaît pas la taille du tableau à priori.

Il n'indique pas du tout ça. Lis les exemples donnés pas Aleph69. Mais honnêtement, la dernières fois que j'ai utilisé professionnellement cette écriture doit remonter à 5 ans au moins, et encore ,je pense que c'était une erreur à l'époque. vector et plus simple, plus sûr, et aussi rapide.

Citation:

Envoyé par Aleph69

Je ne sais vraiment pas quoi te conseiller comme livre pour apprendre le langage C++. En français, je n'en vois que deux :
- la référence en la matière qu'est le livre du créateur du C++ (Stroustrup);

Traduit en français, et plus orienté apprentissage que référence, il y a aussi l'autre Stroustrup : http://www.amazon.fr/Programmation-P...5049861&sr=8-6

Citation:

Envoyé par koala01

As tu été faire un tour du coté de std::complex :question: A moins que je ne me goure vraiment sur la signification de "nombre rationnel", c'est ce qu'il te faut ;)

En plus, c'est fourni en standard avec la STL dans l'espace de noms std. il suffit d'inclure le fichier d'en-tete <complex> pour en profiter ;)

Mmmmm. Je crois que ce n'est pas une bonne idée. Un nombre complexe et un nombre rationnel ont des caractéristiques assez différentes :)

Pour rappel, un nombre rationnel est un nombre de l'ensemble des réels pouvant s'écrire sous la forme P/Q, ou P et Q sont des entiers. Un nombre complexe est défini dans R^2. Les opérateurs n'ont pas le même effet sur des nombres rationnels : q + q est différent de c + c ; q * q est différent de c * c ; etc.

Je pense qu'il est préférable de redéfinir une classe rational plutôt que d'utiliser la classe complex.

Cette classe est relativement simple à définir :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class rational { int m_p, m_q; public: rational(int p, int q) : m_p(p), m_q(q) { } // + copy ctor, + default ctor rational() { } rational& operator=(const rational& other) { rational(other).swap(*this); return *this; } void swap(rational& other) { std::swap(m_p, other.m_p); std::swap(m_q, other.m_q); } int p() const { return m_p; } int q() const { return m_q; } rational& operator+=(const rational& other) { m_p = m_p * other.q() + other.p() * m_q; m_q *= other.q(); return *this; } // similaire pour operator-= rational& operator*=(const rational& other) { m_p *= other.p(); m_q *= other.q(); return *this; } // similaire pour operator/= }; rational operator+(const rational& a, const rationala b) { return rational(a.p()*b.(q) + b.p() * a.q(), a.q() * b.q()); } // similaire pour operator- rational operator*(const rational& a, const rational& b) { return rational(a.p() * b.p(), a.q() * b.q()); } // similaire pour operator/
Bien sûr, il faut affiner la classe - utiliser l'algorithme de pgcd pour simplifier les fractions, ajouter les opérateurs ==, !=, <, >, <=, >= et peut être un algorithme permettant de créer un rationnel à partir d'un flottant quelconque (pour rappel, les flottants du C++ sont nécessairement des rationnels, puisqu'ils sont bornés). On peut aussi passer m_p et m_q en entiers de 64 bits, et proposer une implémentation explicite de la sémantique de mouvement. Bref, c'est une ébauche de classe.

09/12/2012, 22h47
Aleph69

Citation:

Envoyé par Emmanuel Deloget

peut être un algorithme permettant de créer un rationnel à partir d'un flottant quelconque (pour rappel, les flottants du C++ sont nécessairement des rationnels, puisqu'ils sont bornés)

Il doit être assez difficile à implémenter proprement parce que je ne vois pas trop comment déterminer les types du numérateur et du dénominateur. Ces deux nombres peuvent être a priori arbitrairement grands (non représentables en machine) alors que le flottant est lui plus petit (représentable en machine). Tu as un retour d'expérience là-dessus?
10/12/2012, 10h10
ternel

Bonjour,
En général, les implémentations sont "auto-simplifiantes", c'est à dire que 2/4 est conservé sous la forme 1/2.

Il y a ensuite deux variantes classiques: "int based" et "big rationnal".
La première utilise deux entiers (template?), et subit donc les limites entières.
La seconde est modelée sur le "big int", une chaine de caractère ou une série d'entiers. C'est lent, mais toujours exact.

le flottant est génant, parce que 1/3, 1/5, 1/7… et leurs multiples ne sont pas exacte. du coup, 1/6, 1/10, 1/12 non plus
10/12/2012, 10h42
Aleph69

Citation:

Envoyé par leternel

Bonjour,
En général, les implémentations sont "auto-simplifiantes", c'est à dire que 2/4 est conservé sous la forme 1/2.

Certes, mais sous sa forme irréductible la fraction peut avoir un numérateur et dénominateur arbitrairement grands (nombres premiers).

Citation:

Envoyé par leternel

Il y a ensuite deux variantes classiques: "int based" et "big rationnal".
La première utilise deux entiers (template?), et subit donc les limites entières.
La seconde est modelée sur le "big int", une chaine de caractère ou une série d'entiers. C'est lent, mais toujours exact.

Je suis curieux de voir la version int based. As-tu une source à m'indiquer?

Citation:

Envoyé par leternel

le flottant est génant, parce que 1/3, 1/5, 1/7… et leurs multiples ne sont pas exacte. du coup, 1/6, 1/10, 1/12 non plus

Le flottant est à mon avis beaucoup moins gênant que le rationnel car les calculs sont plus rapides et les erreurs d'approximation contrôlables.
10/12/2012, 11h53
ternel

en gros, la version "int based", c'est celle de Emmanuel Deloget (quelques posts plus haut), dans laquelle, la classe possède deux membres (int ou long, ou templatés avec ces types)

Enfin, je souligne l'existence de boost.rational (et boost.ratio?)
10/12/2012, 12h16
Aleph69

Citation:

Envoyé par leternel

en gros, la version "int based", c'est celle de Emmanuel Deloget (quelques posts plus haut), dans laquelle, la classe possède deux membres (int ou long, ou templatés avec ces types)

Oui, mais quelle est la version int based de l'algorithme de conversion d'un flottant en rationnel?
10/12/2012, 13h16
ternel

Un simple découpage et l'utilisation de la définition des chiffres après le séparateur décimal.

12,47 = 1247/100
de même, un float est défini comme signe * (1+m*2^-sizeof(m)) * 2^exposant (pour le float: exposant sur 8 bits, mantisse sur 23 bits de mantisse)
Un peu d'astuce devrait permettre de se baser directement sur l'écriture binaire.
10/12/2012, 13h28
Aleph69

Concrètement, comment tu convertis 9,9999999999999999 (je ne sais pas si c'est un flottant, c'est juste pour le principe avec 16 chiffres après la virgule)?
10/12/2012, 13h34
ternel

en 99999999999999999 / 10000000000000000?

EDIT:
plus pragmatiquement, supposons qu'on veuille écrire 7,5
Le float est écrit 0,10000010,11100000000000000000000 (+, 130 , 1/2+1/4+1/8) c'est à dire (1+ 1/2+1/4+1/8) * 2^(130-128)
Il se transpose en (4*8/8) +(4*4/8) +(4*2/8)+(4*1/8), ce qui donne donc ((8+4+2+1) / 2) = 15/2
10/12/2012, 13h36
Aleph69

Et avec quel type d'entier stockes-tu le numérateur et le dénominateur?

un long, par exemple?

De toutes les façons, hors du "BigInt", tu as toujours un ensemble fini de valeurs possibles. C'est une question de compromis. J'estime personnellement qu'un rationnel doit pouvoir gérer sans erreur 10 * (1/10).

Trouve moi un seul type T (en virgule flottante) tel que le programme suivant retourne 0 quand on lui donne 10 et 0.1 comme arguments
Code:

1 2 3 4 5 6 7 8 9 10 11 #include <sstream> using namespace std; int main (int argc, char** argv) { if(argc <3) return -1; T i, j; istringstream iss(argv[1]); iss>>i; iss.str(argv[2]); iss>>j; return ((i*j)==1) ? 0 : 1; }

10/12/2012, 18h57
Emmanuel Deloget

Citation:

Envoyé par Aleph69

Et avec quel type d'entier stockes-tu le numérateur et le dénominateur?

Un flottant de 32 bits a moins de digits utiles qu'un entier de 32 bits, donc un int ou un long devrait en théorie suffire pour stocker les numérateurs et dénominateurs. Avec un long long, on doit pouvoir traiter les double (64 bits). Les long double (80 bits) devront probablement utiliser quelques astuces (une classe bigint ?).

Ensuite, il y a le problème de l'exposant - celui devra probablement être stocké à part.

Pour ce qui est de l'algorithme float -> rationnel, le plus simple reste de traiter le problème simplement, en puissance de 10. 2.39e5 == 239/100*10^5 (on stocke p = 239, q=100, exp=5).
10/12/2012, 20h50
Aleph69

Citation:

Envoyé par Emmanuel Deloget

Ensuite, il y a le problème de l'exposant - celui devra probablement être stocké à part.

Pour ce qui est de l'algorithme float -> rationnel, le plus simple reste de traiter le problème simplement, en puissance de 10. 2.39e5 == 239/100*10^5 (on stocke p = 239, q=100, exp=5).

Cela n'a pas de sens de faire ça, tu vas toujours te retrouver avec une fraction rationnelle dont le dénominateur est une puissance de 10 dont l'exposant est parfaitement déterminé par la précision du type flottant. Autant faire directement 2.39e5=239e3, c'est-à-dire un rationnel avec un dénominateur à 1, c'est-à-dire un entier. La question se pose plutôt pour 2.39e-5=239e-2, mais là tu vas nécessairement devoir traiter l'exposant pour te ramener à une fraction rationnelle.

La solution du bigint n'est pas viable. Si tu ne réduis pas ton rationnel avec des types d'entiers moins coûteux quand c'est possible, tu risques d'avoir de sérieux problèmes d'overflow quand tu vas effectuer des opérations sur tes rationnels. Il y a sûrement beaucoup de situations où tu vas pouvoir réduire ta fraction a posteriori pour te ramener à un rationnel de précision moindre (encore que je me demande si cette étape est si triviale que cela), mais cela ne résout toujours la question de savoir s'il existe des flottants dont la représentation rationnel fait apparaître des nombres premiers de la taille d'un bigint justement.

@leternel :

tu sembles attacher beaucoup d'importance à la précision exacte des calculs entre rationnels mais c'est à mon avis un leurre pour plusieurs raisons :
1. le coût des opérations élémentaires entre rationnels est supérieur à celui des opérations élémentaires entre flottants (vitesse c'est certain, mémoire c'est probable cf commentaires précédents);
2. ce que tu gagnes en opérant sur des rationnels (exactitude des opérations), tu risques de le perdre à la toute fin lorsque tu devras convertir le résultat de tes opérations en flottant (avoir conservé 80 chiffres après la virgule, en admettant que cela ait du sens, ça ne sert pas à grand chose si au final tu en perds la majorité);
3. la stabilité des opérations flottantes est un phénomène complexe, en particulier les erreurs d'arrondis ne se cumulent pas contrairement à une idée reçue, et on sait très bien la contrôler (théorie des erreurs prograde et rétrograde);
4. enfin, comme dit précédemment, la stabilité des calculs avec des rationnels reste à démontrer.

La seule différence d'intérêt qui existe entre rationnels et flottants c'est que l'on peut approcher tout réel quelconque à une précision arbitraire pour les premiers, et à une précision fixée pour les seconds... mais à quel prix et surtout dans quel but?
11/12/2012, 00h49
bretus

Citation:

Envoyé par Aleph69

4. enfin, comme dit précédemment, la stabilité des calculs avec des rationnels reste à démontrer.

Les opérations + et * sont stables dans l'ensemble des rationnels. Au pire, on risque des dépassement d'entiers. Soit on contrôle ces débordements (a + b => MAX - b < a?), soit on prend des grands entiers et les grands rationnels qui vont avec (voir GMP).

Dès lors, tu peux faire du calcul exact tant que tu n'as pas de racine carrée, de cosinus ou autre joyeuseté à calculer. Dans bien des cas, tu peux t'y ramener (tu travailles sur le carré des distances; tu ne compares pas tes distances à epsilon = 1.0e-5, tu multiplies tes données par 1.0e5 et tu compares le carré de la norme à 1, etc.)

Citation:

Envoyé par Aleph69

3. la stabilité des opérations flottantes est un phénomène complexe, en particulier les erreurs d'arrondis ne se cumulent pas contrairement à une idée reçue, et on sait très bien la contrôler (théorie des erreurs prograde et rétrograde);

A ma connaissance, on arrive tout au mieux à estimer la précision à coup d'arrondi supérieur et d'arrondi inférieur dans les calculs pour savoir si la précision de calcul est suffisante.

A moindre coût, on a les méthodes de compensation type somme de Kahan et autres dérivées, mais rien de très palpable qui fasse état d'une grande maîtrise des phénomènes...

Pour ce qui est des performances, localement, les rationnels sont plus coûteux. Globalement, je serais curieux de voir ce que ça donne face à des arbres de construction en arithmétique flottante.

Sans dire que ça soit le Graal, quand on a besoin de faire des calculs robustes sans faire de l'analyse numérique à la moindre formule et qu'on a une notion de précision sur les données qu'on manipuler, se reposer sur des rationnels ne me semble pas si farfelus.
11/12/2012, 10h22
ternel

Bonjour à tous,

Les rationnels sont un sous-ensemble mathématiques qui n'ont, en général, aucun intérêt à être utilisés. Sauf, bien sûr, quand on fait du calcul exact.

Pour les calculs rapides, on a les floats et les doubles.
C'est la raison pour laquelle je pense que l'implémentation des rationnels devrait être pensée pour l'exactitude.

suite

Bonjour,

voilà un morceau de code et mes questions figurent après :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
class Q{
public:
        int num; // stocke le numérateur
        int den; // stocke le dénominateur
        Q(int a=0,int b=1); // le constructeur de la classe Q (le nombre 1 par défaut)
        Q operator+(Q a); // Définit l'opérateur +                                    // Le premier Q désigne le type de sortie
        void show(); // Affiche le nombre rationnel                                    // void est un type vide, il n'a pas de type
};
 
Q::Q(int a,int b){ // Le constructeur                                                // le constructeur est une méthode
        num=a;
        den=b;
}
 
Q Q::operator+(Q a){
        Q t; // crée un nouveau nombre rationnel                                      // Le Q le plus à gauche, désigne le type de sortie de la méthode, alors que le deuxième dans Q::operator permet d'accéder à la méthode de la classe Q
        t.num=num*a.den+den*a.num; // stock le numérateur des nombres additionnés
        t.den=den*a.den;  // stock le dénominateur des nombres additionnés.
        return t; // retourne le résultat de l'addition
}
 
void Q::show(){
     std::cout << num << " / " << den << " = " << (float)(num)/(float)(den) << "\n";
}
 
int main(void){                                                                            // le type d'élément de sortie de la fonction principale main est le type entier. preuve : return 0
Q a(3,4),b(1,2); // définit deux nouveaux nombres rationnels a et b
a=a+b; // additionne a et b est stocke le résultat sous a.
a.show(); // affiche a
return 0; 
}

1) Un ami m'a aidé à modifier ce code. Et m'expliquait qu'en linux(avec quoi je travaille) il faut impérativement mettre "int main" et pas seulement "main"car avec le seul main, nous avions un message d'erreur (avec les autres modifications qui s'imposent). Il m'expliquait qu'il y a différentes versions de c++. Alors que dans certains livres d'une bibliothèque , j'ai qu'il y a des programmes de C++, dans lesquels, il n'y a pas forcément le int....

Pourquoi ?

2) Dans la partie du code :

Code:

1
2
3
4
5
6
Q Q::operator+(Q a){
        Q t; // crée un nouveau nombre rationnel                                      // Le Q le plus à gauche, désigne le type de sortie de la méthode, alors que le deuxième dans Q::operator permet d'accéder à la méthode de la classe Q
        t.num=num*a.den+den*a.num; // stock le numérateur des nombres additionnés
        t.den=den*a.den;  // stock le dénominateur des nombres additionnés.
        return t; // retourne le résultat de l'addition
}

je ne comprends pas comment le programme fait pour savoir que le "t" qui est une variable déclarée à l'intérieur de la méthode, est le deuxième élément avec lequel on va additionner le "a" qui lui est une variable d'entrée si j'ai bien compris.

Comment le programme sait-il que le "t" est une variable d'entrée ?

3) Qu'est-ce-que c'est : cstdlib ?

En espérant avoir été clair.

merci, cordialement

Citation:

Envoyé par matlab_

1) Un ami m'a aidé à modifier ce code. Et m'expliquait qu'en linux(avec quoi je travaille) il faut impérativement mettre "int main" et pas seulement "main"car avec le seul main, nous avions un message d'erreur (avec les autres modifications qui s'imposent). Il m'expliquait qu'il y a différentes versions de c++. Alors que dans certains livres d'une bibliothèque , j'ai qu'il y a des programmes de C++, dans lesquels, il n'y a pas forcément le int....

Pourquoi ?

Dans l'ancien temps, le C indiquait que toute fonction déclarée sans type de retour utiliserait int par principe. En ce temps-là, pour des raisons stylistiques, on n'écrivait pas le int du main, pour aider à le distinguer.

Cependant, dans le code implicite, il est présent.
De nos jours, ce n'est plus accepté, et normativement parlant, c'est interdit.
Citation:
Envoyé par matlab_
2) Dans la partie du code :
Code:

1 2 3 4 5 6 Q Q::operator+(Q a){ Q t; // crée un nouveau nombre rationnel // Le Q le plus à gauche, désigne le type de sortie de la méthode, alors que le deuxième dans Q::operator permet d'accéder à la méthode de la classe Q t.num=num*a.den+den*a.num; // stock le numérateur des nombres additionnés t.den=den*a.den; // stock le dénominateur des nombres additionnés. return t; // retourne le résultat de l'addition }
je ne comprends pas comment le programme fait pour savoir que le "t" qui est une variable déclarée à l'intérieur de la méthode, est le deuxième élément avec lequel on va additionner le "a" qui lui est une variable d'entrée si j'ai bien compris.

Comment le programme sait-il que le "t" est une variable d'entrée ?
Comme tu l'as indiqué, ce code est la définition de Q Q::operator+(Q a). En réalité, cette fonction est déclarée dans la classe Q, et donc est une méthode de cette classe.
Chaque méthode d'une classe possède un "argument discret" nommé this, qui est une référence à l'objet sur laquelle il est appelé.

Ici, si alpha et beta sont deux Q, Q somme = alpha+beta; est une liberté syntaxique traduite à la compilation par Q somme = alpha.operator+(beta);. c'est à dire l'exécution de Q::operator+, ce qui donnerait un code équivalent au suivant (sauf que somme serait initialisé dans cet équivalent)
Code:

1 2 3 4 5 6 7 8 9 10 11 Q somme; { //ces deux lignes représentent les arguments Q& this=alpha;//argument implicte de toute méthode d'un objet Q a=beta;//argument de la fonction, tel que déclaré //code de la fonction Q t;//variable locale t t.num=num*a.den+den*a.num; t.den=den*a.den; somme = t;//code effectif de "return t;" }
Par ailleurs,
t.den=den*a.den; s'explicite en t.den=this.den*a.den;.

La fonction serait mieux codée avec
Code:

1 2 3 4 5 6 7 8 Q& Q::operator+=(const Q& a){ num=num*a.den+den*a.num; den*=a.den; return *this; } Q operator+(const Q& a, const Q& b){ return Q(a.num*b.den+a.den*b.num, a.den*b.den); }
ou encore
Code:

1 2 3 4 5 6 7 8 9 Q& Q::operator+=(const Q& a){ num=num*a.den+den*a.num; den*=a.den; return *this; } Q operator+(const Q& a, const Q& b){ Q res(a); return res+=b; }
Citation:

Envoyé par matlab_

3) Qu'est-ce-que c'est : cstdlib ?

Simplement la version C++isée de stdlib.h, un entête standard hérité du C. Il contient la définition de exit(), entre autre.
C'est un fichier que tu peux tout à fait lire (mais ne le modifie pas, surtout...), mais son contenu risque d'être rébarbatif.
Tu trouvera un résumé sur cppreference, qui est un très bon compagnon.

11/12/2012, 20h23
Aleph69

Citation:

Envoyé par bretus

Les opérations + et * sont stables dans l'ensemble des rationnels. Au pire, on risque des dépassement d'entiers.

Oui, c'est bien des dépassements d'entiers dont je parle.

Citation:

Envoyé par bretus

Soit on contrôle ces débordements (a + b => MAX - b < a?), soit on prend des grands entiers et les grands rationnels qui vont avec (voir GMP).

Je ne vais pas répéter à chaque fois ma question initiale, mais il faut a priori que tu raisonnes avec des nombres premiers. ;) A moins que tu saches me dire quels sont les rapports de deux nombres premiers représentables par un flottant. Moi je n'en sais absolument rien!

Citation:

Envoyé par bretus

Dès lors, tu peux faire du calcul exact tant que tu n'as pas de racine carrée, de cosinus ou autre joyeuseté à calculer. Dans bien des cas, tu peux t'y ramener (tu travailles sur le carré des distances; tu ne compares pas tes distances à epsilon = 1.0e-5, tu multiplies tes données par 1.0e5 et tu compares le carré de la norme à 1, etc.)

Oui, d'accord. La question est plutôt de savoir si et quand le jeu en vaut la chandelle dans le cadre d'un calcul numérique. Quel avantage a un rationnel, pour lequel tu as possiblement besoin d'étendre les entiers, sur un flottant, même étendu? Sans même parler des problèmes d'overflow, la précision est exacte, certes, mais à quoi sert-elle? Quelle méthode numérique a besoin d'une telle précision?

Citation:

Envoyé par bretus

A ma connaissance, on arrive tout au mieux à estimer la précision à coup d'arrondi supérieur et d'arrondi inférieur dans les calculs pour savoir si la précision de calcul est suffisante.

A moindre coût, on a les méthodes de compensation type somme de Kahan et autres dérivées, mais rien de très palpable qui fasse état d'une grande maîtrise des phénomènes...

Je ne comprends pas ton interprétation. L'analyse de la méthode de Kahan,
http://en.wikipedia.org/wiki/Kahan_summation_algorithm,
comme l'analyse des algorithmes standards (horner, gauss, ...), permet d'obtenir une majoration de l'erreur relative par le produit d'un terme ne dépendant que des données, le conditionnement, et d'un terme dépendant de l'algorithme, l'erreur rétrograde. Dès lors, il est très facile de contrôler l'erreur relative à l'aide de méthodes de préconditionnement, d'autant que les majorations obtenues sont toujours pessimistes. Bref, je ne vois pas bien ce que tu cherches à dire à ce sujet.

Citation:

Envoyé par bretus

Pour ce qui est des performances, localement, les rationnels sont plus coûteux. Globalement, je serais curieux de voir ce que ça donne face à des arbres de construction en arithmétique flottante.

Un contre-exemple m'intéresserait aussi si tu en as sous la main.

Citation:

Envoyé par bretus

Sans dire que ça soit le Graal, quand on a besoin de faire des calculs robustes sans faire de l'analyse numérique à la moindre formule et qu'on a une notion de précision sur les données qu'on manipuler, se reposer sur des rationnels ne me semble pas si farfelus.

L'idée d'utiliser en soi des rationnels n'est pas farfelue. Je m'interrogeais seulement sur l'algorithme de conversion d'un flottant en rationnel et par suite sur la manière de les manipuler sans faire de dépassement. Pour un entier ou flottant, le phénomène de dépassement dans un sens où dans l'autre est facile à comprendre car il varie de façon monotone : tu as un intervalle défini dans lequel il faut rester. Pour les rationnels, c'est beaucoup plus compliqué car cette monotonie est perdue : sur l'ensemble des rationnels, ceux qui ne sont pas représentables avec un type d'entier fixé ne forment pas un intervalle. Tu peux t'amuser à le vérifier avec des nombres premiers connus si tu veux :
http://fr.wikipedia.org/wiki/Liste_de_nombres_premiers
Cela me paraît plutôt légitime de s'interroger sur l'algorithmique liée à ces nombres.
12/12/2012, 13h08
ternel

Citation:

Envoyé par aleph69

Pour un entier ou flottant, le phénomène de dépassement dans un sens où dans l'autre est facile à comprendre car il varie de façon monotone : tu as un intervalle défini dans lequel il faut rester.

Non, les flottants ne sont pas continuement précis, il y a des débordements partout dans l'espace représentables (qui n'est pas un intervalle, du coup…).
32769 = 2^15+1 n'est pas représentable par un float alors que 2080768 = 127*2^14 l'est très bien.

il faut bien comprendre, qu'un float, c'est deux entiers: la mantisse et l'exposant. Il y a 2 * (nombre de valeurs de l'exposants) possibilitées de dépassements. C'est la raison même de l'erreur flottante.
12/12/2012, 15h21
humanite

suite

Bonjour,

y'a-t-il une libraire c++ ou un code c++, pour pouvoir obtenir la forme irréductible d'un rationnel ?

(l'algorithme qui va avec serait instructif pour moi)

Cordialemnt
12/12/2012, 16h22
ternel

Surement, cherche donc, ou écris la, c'est tout bête.

Suppose p et q deux entiers.
p/q est réductible s'il existe un entier d>1 tel que p=d*p' et q=d*q'. auquel cas, p/q = p'/q'.
Cet entier d est appelé diviseur commun de p et q.
Réduire p/q revient donc simplement à chercher le plus grand diviseur commun de p et q (leur PGCD)

Pour ce faire, il existe la méthode d'Euclide.
Tu trouveras de plus ample renseignement sur wikipedia
12/12/2012, 20h10
Aleph69

Citation:

Envoyé par leternel

Non, les flottants ne sont pas continuement précis, il y a des débordements partout dans l'espace représentables (qui n'est pas un intervalle, du coup…).
32769 = 2^15+1 n'est pas représentable par un float alors que 2080768 = 127*2^14 l'est très bien.

il faut bien comprendre, qu'un float, c'est deux entiers: la mantisse et l'exposant. Il y a 2 * (nombre de valeurs de l'exposants) possibilitées de dépassements. C'est la raison même de l'erreur flottante.

Merci, je suis au courant. ;)
Je crois qu'on ne parle pas de la même chose et à mon avis c'est parce les deux problèmes sont justement liés dans le cas des rationnels.

Je disais simplement qu'un type de flottant étant fixé, tu as bien un plus petit flottant et un plus grand flottant qui définissent un intervalle. Qu'il n'y ait pas que des flottants dans cet intervalle n'intervient pas dans ma remarque car on n'a jamais prétendu que les flottants sont les réels. On fait bien des calculs en précision finie.

Pour faire du calcul exact avec des rationnels, il faut justement que tu puisses représenter TOUS les rationnels supérieurs à un certain nombre et inférieurs à un autre nombre, ces deux nombres étant fixés par un typage. Or, je me demande dans quelle mesure il est possible de le faire en gardant à l'esprit l'existence de rapports de nombres premiers. C'est pour cela que je dis qu'il me semble y avoir des "trous" ou, si tu préfères, que le calcul exact avec des rationnels n'est finalement peut-être pas possible.
13/12/2012, 13h06
ternel

si, les langages de calculs formels en sont la preuve.

Par contre, ce que je disais, c'est que la précision des nombres flottants n'est pas absolument constante. En effet, elle est proportionnelle au nombre représenté.
Ce qui est le contraire des entiers ou des relatifs (précisions de 1 et 1/int_max, respectivement).
13/12/2012, 14h13
Aleph69

Citation:

Envoyé par leternel

si, les langages de calculs formels en sont la preuve.

Le calcul formel est un tout autre problème. Depuis le début, on parle bien de calcul numérique avec une classe de rationnels dont le typage est subordonné à ceux de deux entiers.

Citation:

Envoyé par leternel

Par contre, ce que je disais, c'est que la précision des nombres flottants n'est pas absolument constante. En effet, elle est proportionnelle au nombre représenté.

Encore fois, ça ne pose aucun problème car cette précision est majorée en valeur absolue (permettant l'analyse de stabilité à la Kahan) et signée en valeur relative (pas d'accumulation en moyenne, distribution brownienne des erreurs).