MPO 95 : Balayage des rationnels

[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 (21.49 Kio) Consulté 1213 fois

MPO95 Arbre Calkin_Wilf.gif (21.42 Kio) Consulté 1213 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

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

[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