Discussion :

[humanite]

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

[koala01]

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 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

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

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 )

Le conseil de base que je donne volontiers se résume donc en gros à

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"

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 ) 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

[humanite]

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

[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.

[humanite]

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

[Aleph69]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[JolyLoic]

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.

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

[Emmanuel Deloget]

As tu été faire un tour du coté de std::complex 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Aleph69]

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?

[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

[Aleph69]

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).

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?

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.

[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?)

[Aleph69]

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?

[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.

[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)?

[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

[Aleph69]

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

[ternel]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

[Emmanuel Deloget]

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).

[Aleph69]

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?