MPO 95 : Balayage des rationnels

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 95 : Balayage des rationnels

Message par C.Ret »

Héhé, comme toi j'étais arrivé à des codes bien compliqués pour orienter systématiquement les branches descendantes (vers les 1/n mais aussi a/b avec b>a) et ascendantes (vers les n/1 mais aussi a/b avec a>b). C'est pour simplifier les code et les rendre plus lisible que j'ai introduit une variable d'état (nommée U dans le dernier code publié) qui me permet de monter ou descendre à volonté dans l'arbre; Les enroulement , agrandissement, déplacement horizontaux ou verticaux dans le graphe sont alors fait indépendamment, ce qui éclairci les mécanisme.

J'ai préparé deux graphiques que je publie ci-dessous, les lecteurs pourront ainsi essayer ton dernier code et vérifier les résultats donnés par cette mystérieuse fonction bijective.
MPO95 Arbre Stern-Brocot.gif
MPO95 Arbre Stern-Brocot.gif (21.49 Kio) Vu 4786 fois
MPO95 Arbre Calkin_Wilf.gif
MPO95 Arbre Calkin_Wilf.gif (21.42 Kio) Vu 4786 fois
Je redonne ci-dessous le programme de jxano converti

Code : Tout sélectionner

1 clr : input "n=";n: do while n>1 : q=int(n/2) : r=2*r+n-2*q : n=q : i=i+1 : loop : print r+2^i : end
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
jxano
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2362
Enregistré le : 16 févr. 2008 23:34
Localisation : Paris 20ème

Re: MPO 95 : Balayage des rationnels

Message par jxano »

Le temps passant, je peux bien le dire : la fonction-mystère permet le passage du numéro d'ordre d'une fraction dans le système Calkin-Wilf au numéro de la même fraction, mais dans Stern-Brocot. J'avais trouvé qu'en inversant les bits de la représentation binaire du numéro (sauf le premier, toujours à 1), on arrivait à ce résultat. La fonction exécutée deux fois redonne le numéro de départ. Quand les bits concernés forment un palindrome, le nombre est inchangé. Je ne sais pas quel propriété particulière pourrait avoir ces fractions ayant le même rang dans Calkin-Wilf et dans Stern-Brocot.

L'introduction du MPO 98 m'a donné une petite idée d'éclairage supplémentaire des rationnels : pourquoi pas sous la forme c + a/b, avec a<b. Lors de chaque affichage de a/b dans un programme, je pourrais toujours faire la division euclidienne pour déterminer le nouveau a et c. J'ai préféré rechercher une méthode incrémentale de calcul de ces trois entiers à chaque étape du parcours en profondeur de l'arbre binaire.

Départ : a=0 ; b=1 ; c=1
Descente vers fils gauche : A=b*c+a : B=A+b : C=0
Descente vers fils droit : C=c+1
Remontée dans l'arbre :
si c=0 ; [fils gauche] B=b-a ; C=int(a/B) ; A=a-C*B
si c>0 ; [fils droit] C=c-1

Comme pour a/b et le numéro de rationnel, cette représentation a son propre test de détermination de l'origine (gauche ou droite) à la remontée. Les lettres majuscules indiquent qu'il s'agit de valeurs calculées à cette étape, ce qui permet d'ordonner les affectations dans le code.

Voici ce à quoi ressemblent les 127 premiers rationnels dans un arbre en H "droit" (valeurs extrêmes dans les coins) :

Code : Tout sélectionner

0+1/7        0+6/11       0+4/15       0+11/18      0+2/11        0+9/16       0+5/18       0+13/21
0+1/6  0+1/5 1+1/5        0+4/11 0+4/7 1+4/7        0+2/9   0+2/7 1+2/7        0+5/13 0+5/8 1+5/8
1+1/6   |    2+1/5        1+4/11  |    2+4/7        1+2/9    |    2+2/7        1+5/13  |    2+5/8
       0+1/4 ______ 0+1/3 ______ 1+1/3                      0+2/5 ______ 0+2/3 ______ 1+2/3
0+5/14  |    0+9/13  |    0+7/17  |    0+10/13      0+7/19   |    0+12/17 |    0+8/19  |    0+11/14
0+5/9  1+1/4 2+1/4   |    0+7/10 2+1/3 3+1/3        0+7/12  1+2/5 2+2/5   |    0+8/11 2+2/3 3+2/3
1+5/9        3+1/4   |    1/7/10       4+1/3        1+7/12        3+2/5   |    1+8/11       4+2/3
                    0+1/2 ___________________ 1+0/1 ____________________ 2+0/1
0+3/14       0+11/19 |    0+5/17       0+12/19      0+3/13        0+10/17 |    0+4/13       0+9/14
0+3/11 0+3/8 1+3/8   |    0+5/12 0+5/7 1+5/7        0+3/10  0+3/7 1+3/7   |    0+4/9  0+4/5 1+4/5
1+3/11  |    2+3/8   |    1+5/12  |    2+5/7        1+3/10   |    2+3/7   |    1+4/9   |    2+4/5
       0+3/5 ______ 1+1/2 ______ 2+1/2                      0+3/4 ______ 3+0/1 ______ 4+0/1
0+8/21  |    0+13/18      0+7/16  |    0+9/11       0+7/18   |    0+11/15      0+5/11  |    0+6/7
0+8/12 1+3/5 2+3/5        0+7/9  3+1/2 4+1/2        0+7/11  1+3/4 2+3/4        0+5/6  5+0/1 6+0/1
1+8/13       3+3/5        1+7/9        5+1/2        1+7/11        3+3/4        1+5/6        7+0/1
J'ai laissé toutes les valeurs de a, b et c. On peut faire d'autres choix d'affichage.
Modifié en dernier par jxano le 20 nov. 2020 20:34, modifié 1 fois.
Programmeur abscons.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 95 : Balayage des rationnels

Message par C.Ret »

Mon très cher jxano tu es un géni, tu as trouvé le lien secret que j'avais établi en cachette entre mes deux MPO !

Oui, les info que tu donnes ici peuvent être très utiles dans l'autre MPO :)
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 95 : Balayage des rationnels

Message par C.Ret »

Un petit up de ce MPO pour signaler qu'ARTE vient de diffuser une petite vidéo très sympathique sur les nombres irrationnels qui, en introduction, parle, sans cependant nommer Stern ou les arbres de Calkin-Wilf ou Stern-Brocot, des rationnels.

J'aime bien le ton, le rythme et l'animation de cette série de petits films qui nous font Voyager au Pays des Mathématiques.
Modifié en dernier par C.Ret le 09 déc. 2021 16:12, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 498
Enregistré le : 05 mars 2020 20:45
Contact :

Re: MPO 95 : Balayage des rationnels

Message par Schraf »

Arte a vraiment de supers infographistes !

On te jète à l'eau !
On te jète à l'eau !
rac2.jpg (40.13 Kio) Vu 3227 fois
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5217
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: MPO 95 : Balayage des rationnels

Message par bernouilli92 »

J’ai regardé l’émission. C’est plutôt bien fait. Et il y en a d’autres.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
forgeron
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 152
Enregistré le : 28 sept. 2007 19:34
Localisation : Paris XIème

Re: MPO 95 : Balayage des rationnels

Message par forgeron »

Moi j'ai adoré le calcul infinitésimal et Un rond est aussi un carré. Ça dure 9 mn, c'est juste parfait comme format.
Un jour, mon père m'a offert une TI 57...
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6167
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: MPO 95 : Balayage des rationnels

Message par Marge »

Pfff, va falloir que je me repaie un réseau privé virtuel. Même Captvty ne fonctionne plus.
3 hommes, 3 demis, un 3a... Magnéto, Serge !

Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67
__: A L I E N .

« Boris », c'était juste Maurice enrhumé.
Répondre

Retourner vers « Tous les Pockets »