BIJECTION EXPLICITE ENTRE N ET Q+

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 - 23 juin 2004 à 20:49
cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 - 22 juin 2005 à 10:50

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/23945-bijection-explicite-entre-n-et-q

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
22 juin 2005 à 10:50

et oui a la base il s'agissait d'une illustration de l'algorithme, qui illustre de facon explicite et constructiviste l'equipotence de Z et de Q. car en tant que tel, trouver le rationnel associé a l'entier 2^83, ca ne sert pas a gd chose :)
tes docs m'interessent cela dit !!

raphaducasse Messages postés 1 Date d'inscription vendredi 27 mai 2005 Statut Membre Dernière intervention 27 mai 2005
27 mai 2005 à 17:21

j ai aussi bossé sur ces histoires de suites de Brocot et ton prgm tourne vrmt bien. Il y a par un inconveniant majeur : le fait que tu sois limité a des entiers < 2^63 (parce que ca fait pas des fractions si précises que ca etant donné que tu passe par le dvp en frac cont). Je suis en train de creer une class BigInt pour parlier a ça. En plus, vu que cet algorithme est rapide, ca permet d 'implementer efficacement des series de rationnels. Si tu veux mes docs sur ce que j ai fait, fait moi savoir.

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
26 juin 2004 à 16:03

non. tourner autour doit vouloir dire: classer les rationnels suivant la somme numerateur+denominateur. la ils sont classés suivant la somme des coefficients du développement en fraction continue.

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
26 juin 2004 à 14:35

j'ai entendu un truc qui consiste à partir de zéro et à conter les rationnels en tournant autour, c'est comme ca que tu a fait? (j'ai pas trop e temps de ragerder la source)

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
25 juin 2004 à 11:13

bon, avec iostream et pas iostream.h, le if (cin >> i) marche.
par contre, pour remettre a l'etat normal, cin.clear() marche pas du tout... comment se fait-ce? :p

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
25 juin 2004 à 10:36

pour vérifier la saisie, if (cin >> i) ne marche pas chez moi (ca rentre toujours dans correct, car ca doit renvoyer un pointeur ou qqc vers le flux, qui n'est en tout k jamais nul)
ya til un moyen officiel? (c'est une biblioteque standard ... normalement oui !!)
sinon le fflush(stdin) est avant le getc qui est du C..., c'est 'mauvais' de mélanger, encore une fois je vois pas du tout pourkoi, de maniere interne c'est géré différement, donc pas de conflit. ya des conflits au cas ou plsrs threads font des entrées/sorties en meme temps, meme si tout est en C ou tout en C++... et la ya rien de simultané.

BlackGoddess Messages postés 338 Date d'inscription jeudi 22 août 2002 Statut Membre Dernière intervention 14 juin 2005
25 juin 2004 à 08:31

fflush(stdin) ;
choix = getchar() - 48 ;
-Saisie de 'valeur' pour la case 1:
char val[50] ;
cin >> val;

>> fflush est du C, cin du C++, au niveau des flux c'est tres mauvais de mélanger

vérifier une saisie :

int i;

if(cin >> i)
cout << "correct\n";
else
cout << "incorrect\n";

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
24 juin 2004 à 17:02

j'ai reglé le probleme de saisie, et j'ai remplacé tous les int par des __int64, ce qui permet de moins limiter le domaine de définition des deux fonctions.

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
24 juin 2004 à 15:43

ben si on peut compter les rationnels, vu qu'il s'agit d'un ensemble dénombrable. une bijection explicite avec N est donnée dans la source donc... dans ce que tu dis, tu confonds l'infini avec la non dénombrabilité. et la le comptage n'est pas en diagonale comme avec N². Tiens au fait, une bijection explicite de N² -> N est par exemple la fonction qui au couple (p,q) associe (p+q)(p+q+1)/2 + q (comptage en diagonale).
regarde, d'apres la source, le 1000e rationnel est 41/9, et le millionieme est 1153/325.
par contre il ne s'agit pas d'un isomorphisme, pour la simple et bonne raison qu'il ne s'agit pas du tout d'un morphisme (aucun isomorphisme de Z dans Q n'est possible, car l'image de Z par un isomorphisme fi est de la forme fi(1).Z, ce qui n'est pas le cas de Q)

MetalDwarf Messages postés 241 Date d'inscription mardi 29 octobre 2002 Statut Membre Dernière intervention 23 janvier 2006
24 juin 2004 à 15:15

Oui je connaissais ce petit truc de l isomorphisme entre N et Q+, c est vrai que c est assez surprenant... Cependant quand on y regarde de plus pres on ne peux pas "vraiment" compter les rationnels car quand on s eloigne la diagonale devient de plus en plus longue, ce qui montre un passage progressif a un ensemble "qu on ne peut pas compter".
Enfin pour ce qui est de la theorie des ensemble il est vrai qu elle possede ses limites, mais il est inutile de vouloir une theorie parfaite car c est impossible!! (theoreme d incompletude de Gödel)

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
24 juin 2004 à 10:37

si ya que le 1 qui est alors considéré comme fraction, mais apres la division a été redéfinie pour les fractions, donc pas de problemes...
si tu fais (fraction) (1/resultat) il faudrait que yait un operateur de division entre un entier (1) et une fraction (resultat) ce qui n'est pas le cas.

sinon pour le pdf faut un assez bon niveau scientifique pour comprendre qd meme.

Saros Messages postés 921 Date d'inscription vendredi 20 décembre 2002 Statut Membre Dernière intervention 23 septembre 2010
24 juin 2004 à 10:14

(fraction)1 / resultat;
Là, il n'y a pas que le 1 qui est considéré comme fraction ? Je veux dire, pour tout mettre en fraction, c'est pas ça :
(fraction)(1 / resultat);

Je suis un peu perdu à vrai dire ^^... Je vais commencer à lire le PDF...

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
24 juin 2004 à 00:20

ué bon jsavais qu'on pouvait se débrouiller avec getc mais bon... sinon pour in >> val, ben ca fait un buffer overflow si on ecrit trop de caracteres, ce qui a cependant moins de chances d'arriver que de taper autre chose qu'un entier.

enfin voila ca jle savais qu'on pouvait s'en sortir de cette maniere, mais yatil moyen de s'apercevoir que ce qui a été rentré par cin>> n'est pas correct? (pkoi cela ne leve til pas une exception par ex: ?)

bon de toute facons le but de la source c'est pas les trucs comme ca sur les entrées sorties...

cs_Chouchou182 Messages postés 252 Date d'inscription vendredi 13 juin 2003 Statut Membre Dernière intervention 25 avril 2011 1
23 juin 2004 à 23:30

Salut

Je pense avoir résolu le problème lié à cin provoquant un affichage ininterrompu en cas de saisie maladroite de la part de l'utilisateur. Voila les modifications :
-Saisie de 'choix' pour le menu :
fflush(stdin) ;
choix = getchar() - 48 ;
-Saisie de 'valeur' pour la case 1:
char val[50] ;
cin >> val;
valeur = atoi(val) ;
-Méthode de saisie d'une fraction:
istream & operator >> (istream & in, fraction &b)
{
char val[50] ;
in >> val ;
b.numerateur = atoi(val) ;
in >> val ;
b.denominateur = atoi(val) ;
b.simplifier();
return in;
}

Le principe est simple : on récupère la saisie de l'utilisateur comme une chaîne de caractères et transforme à l'aide de atoi. En cas d'erreur, atoi renvoie 0 donc le programme continue sans problème.

Bonne Prog !

Chouchou.

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
23 juin 2004 à 21:36

c'est qd tu rentres pas un entier (genre un caractere, un flotant ou un entier trop grand (>2^32)), il y a un probleme avec cin que j'ai pas su résoudre... si quelqu'un sait comment detecter l'erreur lors d'une entrée (autrement qu'en faisant des getc successif et formater soi meme), pour sortir proprement, dites le que j'update la source.

ce qui est aussi 'rigolo', c'est que bien qu'il y ait bcp plus de réels que de rationnels, l'existence d'un ensemble intermédiaire (contenant Q et inclus dans R, mais en bijection avec ni l'un ni l'autre) est un problème indécidable, ce qui pointe les limites de notre axiomatique sur les ensembles. (quelqu'un sait il rajouter un axiome 'simple' pour que ce probleme soit décidable? pour l'instant non, on veut rajouter le probleme ou sa négation tout entier)

et puis compter les rationnels, c'est qd meme qqc d'assez contraire au sens commun, alors que pourtant c'est possible

cs_JCDjcd Messages postés 1138 Date d'inscription mardi 10 juin 2003 Statut Membre Dernière intervention 25 janvier 2009 4
23 juin 2004 à 21:25

Ce qui est interressant dans ce resultat c'est que Q (ou Q+) est petit comme ensemble par rapport a R, et que Q est denombrable.
Mais on en conclu donc que dans R il y a bcp plus d'irrationnel que de rationnel (l'un denombrable, l'autre non).

sinon pourquoi des que l'on rentre une chaine "non reglementaire" ca defile grave a l'ecran ?

cosmobob Messages postés 700 Date d'inscription mardi 30 décembre 2003 Statut Membre Dernière intervention 27 janvier 2009 4
23 juin 2004 à 20:49

Ha, j'oubliais. Le code est livré avec une classe fraction faite vite fait pour manipuler les rationnels, qui est peut etre pas complete...

Si vous avez des remarques sur l'idée de la bijection, hésitez pas.

Discussions similaires

Qu'est ce que les fichiers .oca et .lib créés avec un ocx

vider les zones de text dynamique

option explicit

VBA =>desactiver Option Explicit

option explicit?

Votre réponse

Discussions similaires