par nodjim » 15 Juin 2013, 13:09
Un bon exemple valant mieux qu'un long discours...
Prenons le cas de 19. D'entrée, on a comme fraction disponible: 0.5 (1/38), 1 (1/19) et 19 (19/19=1/1)
0.5;1;19;
1 et 19 donne directement 10
0.5;1;10;19;
1 et 10--->5.5
0.5;1;5.5;10;19
0.5 et 5.5--->3
0.5;1;3;5.5;10;19
2 et 4 tombent alors, et je n'ai plus besoin des 0.5
1;2;3;4;10;19
(4,10)-->7 et (3,7)-->5
1;2;3;4;5;7;10;19
6 tombe
1;2;3;4;5;6;7;10;19
(7,19)-->13 et (13;19)-->11
1;2;3;4;5;6;7;10;11;13;19
(11,19) et (13,19) --->15 et 16
1;2;3;4;5;6;7;10;11;13;15;16;19
Pratiquement c'est fini: 9,12,14,17,18 tombent.
L'étape critique est le début, la descente des 0.5.
Ici, on a eu de la chance avec 0.5+5.5 qui donne un entier.
On aurait pu avoir 0.5+4.5 qui donne 2.5, et donc 0.5+2.5 qui donne 1.5.
Mais ce 1.5, dans le cas le pire, on tombe dessus de toute façon.
et 1.5 associé avec 4.5 donne cette fois un entier: 3, qui donnera à son tour 2.